Abstract
This study addresses the Waste Collection Vehicle Routing Problem with Time Windows (WCVRPTW) with multiple disposal sites and drivers’ lunch breaks. The problem consists of routing garbage trucks to collect customers waste within given time window in order to minimize the total travel cost. The waste is driven to disposal sites, multiple trips to disposal sites are allowed per day for the vehicles, and the vehicles must be empty when returning to the depot. To find near-optimal routes for the waste collecting vehicles, we propose a heuristic algorithm based on the meta-heuristics Iterated Local Search (ILS) and Variable Neighborhood Descent (VND). The performance of the proposed algorithm is evaluated by comparing its results to CPLEX commercial solver, and a variable neighbourhood tabu search (VNTS) algorithm addressed in the literature. The results obtained, on benchmark problems from the literature, are highly competitive and a number of new improved solutions are reported.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Benjamin, A.M., Beasley, J.E.: Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Comput. Oper. Res. 37(12), 2270–2280 (2010)
Benjamin, A.M., Beasley, J.E.: Metaheuristics with disposal facility positioning for the waste collection VRP with time windows. Optim. Lett. 7(7), 1433–1449 (2013)
Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., Semet, F.: A guide to vehicle routing heuristics. J. Oper. Res. Soc. 53(5), 512–522 (2002)
Buhrkal, K., Larsen, A., Ropke, S.: The waste collection vehicle routing problem with time windows in a city logistics context. Procedia-Soc. Behav. Sci. 39, 241–254 (2012)
Han, H., Ponce Cueto, E.: Waste collection vehicle routing problem: literature review. PROMET-Traffic Transp. 27(4), 345–358 (2015)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)
Kim, B.I., Kim, S., Sahoo, S.: Waste collection vehicle routing problem with time windows. Comput. Oper. Res. 33(12), 3624–3642 (2006)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, vol. 57, pp. 320–353. Springer, Heidelberg (2003)
Ombuki-Berman, B.M., Runka, A., Hanshar, F.T.: Waste collection vehicle routing problem with time windows using multiobjective genetic algorithms. Brock University 2007; Technical report CS-07-04, pp. 91–97 (2007)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper. Res. 35, 254–265 (1987)
Acknowledgments
The authors thanks the financial support of CNPq, CAPES and FAPEMIG, Brazilian research agencies.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Campos, A.A., Arroyo, J.E.C. (2017). An ILS Heuristic for the Waste Collection Vehicle Routing Problem with Time Windows. In: Madureira, A., Abraham, A., Gamboa, D., Novais, P. (eds) Intelligent Systems Design and Applications. ISDA 2016. Advances in Intelligent Systems and Computing, vol 557. Springer, Cham. https://doi.org/10.1007/978-3-319-53480-0_88
Download citation
DOI: https://doi.org/10.1007/978-3-319-53480-0_88
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53479-4
Online ISBN: 978-3-319-53480-0
eBook Packages: EngineeringEngineering (R0)