Heuristic Approach For Robust Counterpart Open Capacitated Vehicle Routing Problem With Time Windows

Evi Yuliza, Fitri Maya Puspita, Siti Suzlin Supadi

Abstract

Garbage is one of the environmental problems. The process of transporting garbage sometimes occurs delays such as congestion and engine failure. Robust optimization model called a robust counterpart open capacitated vehicle routing problem (RCOCVRP) with time windows was formulated to get over this delays. This model has formulated with the limitation of vehicle capacity and time windows with an uncertainty of waste volume and travel time. The RCOCVRP model with time windows is solved by a heuristic approach. The heuristic approach used to solve the RCOCVRP model with time windows uses the nearest neighbor and the cheapest insertion heuristic algorithm. The RCOCVRP with time windows model is implemented on the problem of transporting waste in Sako sub-district. The solutions of these two heuristic approaches are compared and analyzed. The RCOCVRP model with time windows to optimize the route problems of waste transport vehicles that is solved using the cheapest insertion heuristics algorithm is more effective than the nearest neighbor method.

References

Agra, A. et al. (2013) ‘The robust vehicle routing problem with time windows’, Computers and Operations Research. Elsevier, 40(3), pp. 856–866.
Alatartsev, S., Augustine, M. and Ortmeier, F. (2013) ‘Constricting insertion heuristic for traveling salesman problem with neighborhoods’, Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, (January), pp. 1–10. doi: 10.13140/2.1.4267.6165.
Braaten, S. et al. (2017) ‘Heuristics for the robust vehicle routing problem with time windows’, Expert Systems with Applications. Elsevier Ltd, 77, pp. 136–147.
Buhrkal, K., Larsen, A. and Ropke, S. (2012) ‘The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context’, Procedia - Social and Behavioral Sciences, 39(May 2014), pp. 241–254. doi: 10.1016/j.sbspro.2012.03.105.
Campos, A. A. and Arroyo, J. E. C. (2017) ‘An ILS heuristic for the waste collection vehicle routing problem with time windows’, Advances in Intelligent Systems and Computing, 557(June), pp. 889–899. doi: 10.1007/978-3-319-53480-0_88.
Gounaris, C. E., Wiesemann, W. and Floudas, C. A. (2013) ‘The robust capacitated vehicle routing problem under demand ncertainty’, Operations Research, 61(3), pp. 677–693.
Hannan, M. A. et al. (2018) ‘Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm’, Waste Management. Elsevier Ltd, 71, pp. 31–41.
Hartono, Y. et al. (2018) ‘LINGO-based on robust counterpart open capacitated vehicle routing problem (RC-OCVRP) model of waste transportation in Palembang’, International Conference on Information and Communications Technology, ICOIACT, 18(978-1-5386-954–5), pp. 429–435.
De la Vega, J., Munari, P. and Morabito, R. (2017) ‘Robust optimization for the vehicle routing problem with multiple deliverymen’, Central European Journal of Operations Research, pp. 1–32. doi: 10.1007/s10100-017-0511-x.
Nguyen, P. K., Crainic, T. G. and Toulouse, M. (2013) ‘A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows’, European Journal of Operational Research. Elsevier B.V., 231(1), pp. 43–56. doi: 10.1016/j.ejor.2013.05.026.
Perea, F., Ruiz, R. and Katragjini, K. (2016) ‘Integer programming, clustering, and local search approaches for grouping urban waste collection sites’, Boletin de Estadistica e Investigacion Operativa, 32(3), pp. 203–224.
Pop, P. C. et al. (2011) ‘Heuristic algorithms for solving the generalized vehicle routing problem definition of the GVRP’, International Journal of Computers, Communications and Control, VI(1), pp. 158–165.
Puspita, F. M., Cahyono, E. S., et al. (2018) ‘Model of demand robust counterpart open capacitated vehicle routing problem (DRC- OCVRP ) simplification by applying preprocessing techniques in rubbish controlling in Sematang Borang District , Palembang’, E3S Web of Conferences 68, 25, pp. 1–6.
Puspita, F. M., Hartono, Y., et al. (2018) ‘Robust counterpart open capacitated vehicle routing (RC-OCVRP) model in optimization of garbage transportation in District Sako and Sukarami, Palembang City’, International Journal of Electrical and Computer Engineering, 8(6), pp. 4382–4390.
Scutellà, M. G. (2015) Logistics.
Sun, L. and Wang, B. (2015) ‘Robust optimisation approach for vehicle routing problems with uncertainty’, Mathematical Problems in Engineering, 2015. doi: 10.1155/2015/901583.
Sungur, I., Ordóñez, F. and Dessouky, M. (2008) ‘A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty’, IIE Transactions, 40(5), pp. 509–523.
Yuliza, E. et al. (2020) ‘The robust counterpart open capacitated vehicle routing problem with time windows’, Journal of Physics: Conference Series, 1663, p. 12030. doi: 10.1088/1742-6596/1663/1/012030.
Yuliza, E., Puspita, F. M. and Supadi, S. S. (2020) ‘The robust counterpart open capacitated vehicle routing problem with time windows on waste transport problems’, Bulletin of Electrical Engineering and Informatics, 9(5), pp. 2074–2081.

Authors

Evi Yuliza
evibc3@yahoo.com (Primary Contact)
Fitri Maya Puspita
Siti Suzlin Supadi
Yuliza, E., Puspita, F. M., & Supadi, S. S. . (2021). Heuristic Approach For Robust Counterpart Open Capacitated Vehicle Routing Problem With Time Windows. Science and Technology Indonesia, 6(2), 53–57. https://doi.org/10.26554/sti.2021.6.2.53-57

Article Details