A hybrid algorithm based on GRASP and variable neighborhood descent guided by machine learning for waste collection synchronization

This study addresses a variant of the Capacitated Vehicle Routing Problem with Time Windows and Synchronization, motivated by applications in the waste collection industry, where multiple vehicles must be coordinated at customer locations. The setting reflects environments in which the simultaneous presence of different vehicles is required to collect distinct waste types, introducing synchronization constraints at the customer level. The problem is NP-hard and is generalized in this study to incorporate heterogeneous waste generation, variable and non-negative quantities per customer, and the possibility of deploying a non-fixed number of vehicles per service point, increasing complexity. The transport company is modeled as an auctioneer selecting winning bids to maximize profit, computed as the difference between the cumulative value of accepted customer bids and total transportation costs. Notably, all assigned vehicles must arrive within the same valid time window specified in the customer bid but not necessarily concurrently. To address this problem, we introduce a hybrid metaheuristic wherein initial solutions are constructed via a Greedy Randomized Adaptive Search Procedure (GRASP) and refined using a Random Variable Neighborhood Descent (RVND) that is enhanced by online learning strategies from machine learning to guide the search process more effectively, showing a strong influence in improving GRASP-generated solutions by escaping local optima and promoting diversification. Computational experiments assess the metaheuristic against an exact approach using the Gurobi solver. For small-sized instances, Gurobi achieves competitive results, but its scalability is limited, with rising computation times and deteriorating solution quality. On larger instances, GRASP-RVND outperforms Gurobi in both solution quality and efficiency, producing better objective values in less computational time. Further analysis shows that customer distribution affects difficulty, with denser clusters improving routing. Moreover, the robustness of the solution is studied and compared to solutions where a time buffer was set to aid this problem.