A variable neighborhood search for a new multi-depot green vehicle routing problem with multiple starting points and distinct serving areas for recyclable waste collection
Utku Kantekinutkukantekin97@gmail.comDepartment of Industrial EngineeringFaculty of EngineeringIki Eylul CampusEskisehir Technical UniversityEskisehir, 26555, TürkiyeView full profile → , *Gulcin Dinc YalcinCorresponding authorgdinc@eskisehir.edu.trDepartment of Industrial EngineeringFaculty of EngineeringIki Eylul CampusEskisehir Technical UniversityEskisehir, 26555, TürkiyeView full profile → , Emine Akyol Ozeremineakyol@eskisehir.edu.trDepartment of Industrial EngineeringFaculty of EngineeringIki Eylul CampusEskisehir Technical UniversityEskisehir, 26555, TürkiyeView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 10 Aug 2022
- Accepted:
- 06 Dec 2022
- Published Online:
- 31 Mar 2025
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1337
- Pages:
- 57–85
Abstract
Keywords
Subject Classifications
References
[1] S. Z. Aliahmadi, F. Barzinpour, and M. S. Pishvaee, “A novel bi-objective credibility-based fuzzy model for municipal waste collection with hard time windows,” Journal of Cleaner Production, vol. 296, p. 126364, Mar. (2021), doi: 10.1016/j.jclepro.2021.126364.
[2] M. Amous, S. Toumi, B. Jarboui, and M. Eddaly, “A variable neighborhood search algorithm for the capacitated vehicle routing problem,” Electronic Notes in Discrete Mathematics, vol. 58, pp. 231–238, Apr. (2017), doi: 10.1016/j.endm.2017.03.030.
[3] T. Bektaş and G. Laporte, “The Pollution-Routing problem,” Transportation Research Part B Methodological, vol. 45, no. 8, pp. 1232–1250, Mar. (2011), doi: 10.1016/j.trb.2011.02.004.
[4] M. Behnke, T. Kirschstein, and C. Bierwirth, “A column generation approach for an emission-oriented vehicle routing problem on a multigraph,” European Journal of Operational Research, vol. 288, no. 3, pp. 794–809, Jul. (2020), doi: 10.1016/j.ejor.2020.06.035.
[5] A. M. Benjamin and J. E. Beasley, “Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities,” Computers & Operations Research, vol. 37, no. 12, pp. 2270–2280, Apr. (2010), doi: 10.1016/j.cor.2010.03.019.
[6] J.-F. Cordeau, M. Gendreau, and G. Laporte, “A tabu search heuristic for periodic and multi-depot vehicle routing problems,” Networks, vol. 30, no. 2, pp. 105–119, Sep. (1997), doi: 10.1002/(sici)1097-0037(199709)30:2.
[7] D. Cinar, K. Gakis, and P. M. Pardalos, “A 2-phase constructive algorithm for cumulative vehicle routing problems with limited duration,” Expert Systems With Applications, vol. 56, pp. 48–58, Mar. (2016), doi: 10.1016/j.eswa.2016.02.046.
[8] G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Management Science, vol. 6, no. 1, pp. 80–91, Oct. (1959), doi: 10.1287/mnsc.6.1.80.
[9] E. Demir, T. Bektaş, and G. Laporte, “An adaptive large neighborhood search heuristic for the Pollution-Routing Problem,” European Journal of Operational Research, vol. 223, no. 2, pp. 346–359, Jul. (2012), doi: 10.1016/j.ejor.2012.06.044.
[10] J. F. Ehmke, A. M. Campbell, and B. W. Thomas, “Vehicle routing to minimize time-dependent emissions in urban areas,” European Journal of Operational Research, vol. 251, no. 2, pp. 478–494, Dec. (2015), doi: 10.1016/j.ejor.2015.11.034.
[11] S. Elbasan, “Vehicle routing with simultaneously pickup-delivery considering carbon footprint,” M.S. thesis, Department of Industrial Engineering, Eskisehir Osmangazi University, Eskisehir, Turkiye (2015).
[12] EPA (United Staged Environmental Protection Agency) “Inventory of U.S. greenhouse gas emissions and sinks.” EPA.gov. Accessed: Feb. 11 (2021). [Online.] Available: https://www.epa.gov/ghgemissions/inventory-us-greenhouse-gas-emissions-and-sinks
[13] D. R. Gaur, A. Mudgal, and R. R. Singh, “Routing vehicles to minimize fuel consumption,” Operations Research Letters, vol. 41, no. 6, pp. 576–580, Aug. (2013), doi: 10.1016/j.orl.2013.07.007.
[14] D. R. Gaur, A. Mudgal, and R. R. Singh, “Approximation Algorithms for Cumulative VRP with Stochastic Demands,” in Lecture notes in computer science, pp. 176–189 (2016). doi: 10.1007/978-3-319-29221-2_15.
[15] A. Gruler, A. P. Navarro, L. Calvet, and A. A. J. Pérez, “A simheuristic algorithm for time-dependent waste collection management with stochastic travel times,” Sort-statistics and Operations Research Transactions, vol. 44, no. 2, pp. 285–310, Jul. (2020), doi: 10.2436/20.8080.02.103.
[16] P. Hansen and N. Mladenović, “Variable neighborhood search: Principles and applications,” European Journal of Operational Research, vol. 130, no. 3, pp. 449–467, May (2001), doi: 10.1016/s0377-2217(00)00100-4.
[17] P. Hansen and N. Mladenović, and D. Perez-Brito, “Variable neighborhood decomposition search,” Journal of Heuristics, vol. 7, pp. 335-350 (2021).
[18] A. Imran, S. Salhi, and N. A. Wassan, “A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem,” European Journal of Operational Research, vol. 197, no. 2, pp. 509–518, Jul. (2008), doi: 10.1016/j.ejor.2008.07.022.
[19] E. Jabir, V.V. Pancker, and R. Sridharan, “Design and development of a hybrid ant colony-variable neighborhood search algorithm for a multi-depot green vehicle routing problem,” Transportation Research Part D, vol. 57, pp. 422-457 (2017).
[20] V. Hemmelmayr, K. F. Doerner, R. F. Hartl, and S. Rath, “A heuristic solution method for node routing based solid waste collection problems,” Journal of Heuristics, vol. 19, no. 2, pp. 129–156, Sep. (2011), doi: 10.1007/s10732-011-9188-9.
[21] İ. Kara, B. Y. Kara, and M. K. Yetis, “Energy minimizing vehicle routing problem,” in Lecture notes in computer science, pp. 62–71 (2007). doi: 10.1007/978-3-540-73556-4_9.
[22] B.-I. Kim, S. Kim, and S. Sahoo, “Waste collection vehicle routing problem with time windows,” Computers & Operations Research, vol. 33, no. 12, pp. 3624–3642, Nov. (2005), doi: 10.1016/j.cor.2005.02.045.
[23] T. Kirschstein and F. Meisel, “GHG-emission models for assessing the eco-friendliness of road and rail freight transports,” Transportation Research Part B Methodological, vol. 73, pp. 13–33, Dec. (2014), doi: 10.1016/j.trb.2014.12.004.
[24] Ç. Koç, T. Bektaş, O. Jabali, and G. Laporte, “The fleet size and mix pollution-routing problem,” Transportation Research Part B Methodological, vol. 70, pp. 239–254, Oct. (2014), doi: 10.1016/j.trb.2014.09.008.
[25] Y. Kuo and C.-C. Wang, “A variable neighborhood search for the multi-depot vehicle routing problem with loading cost,” Expert Systems With Applications, vol. 39, no. 8, pp. 6949–6954, Jan. (2012), doi: 10.1016/j.eswa.2012.01.024.
[26] S. A. Lenis and J. C. Rivera, “A metaheuristic approach for the cumulative capacitated arc routing problem,” in Communications in computer and information science, pp. 96–107 (2018). doi: 10.1007/978-3-030-00353-1_9.
[27] H. Li, T. Lv, and Y. Li, “The tractor and semitrailer routing problem with many-to-many demand considering carbon dioxide emissions,” Transportation Research Part D Transport and Environment, vol. 34, pp. 68–82, Nov. (2014), doi: 10.1016/j.trd.2014.10.004.
[28] I. Markov, S. Varone, and M. Bierlaire, “Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities,” Transportation Research Part B Methodological, vol. 84, pp. 256–273, Dec. (2015), doi: 10.1016/j.trb.2015.12.004.
[29] N. Mladenović and P. Hansen, “Variable neighborhood search,” Computers & Operations Research, vol. 24, no. 11, pp. 1097–1100, Nov. (1997), doi: 10.1016/s0305-0548(97)00031-2.
[30] J. C. Molina, I. Eguia, and J. Racero, “Reducing pollutant emissions in a waste collection vehicle routing problem using a variable neighborhood tabu search algorithm: a case study,” Top, vol. 27, no. 2, pp. 253–287, Mar. (2019), doi: 10.1007/s11750-019-00505-5.
[31] R. Moghdani, K. Salimifard, E. Demir, and A. Benyettou, “The green vehicle routing problem: A systematic literature review,” Journal of Cleaner Production, vol. 279, p. 123691, Aug. (2020), doi: 10.1016/j.jclepro.2020.123691.
[32] B. Peng, L. Wu, Y. Yi, and X. Chen, “Solving the Multi-Depot green vehicle routing problem by a hybrid evolutionary algorithm,” Sustainability, vol. 12, no. 5, p. 2127, Mar. (2020), doi: 10.3390/su12052127.
[33] M. Polacek, R. F. Hartl, K. Doerner, and M. Reimann, “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows,” Journal of Heuristics, vol. 10, no. 6, pp. 613–627, Dec. (2004), doi: 10.1007/s10732-005-5432-5.
[34] G. Poonthalir and R. Nadarajan, “A Fuel Efficient Green Vehicle Routing Problem with varying speed constraint (F-GVRP),” Expert Systems With Applications, vol. 100, pp. 131–144, Feb. (2018), doi: 10.1016/j.eswa.2018.01.052.
[35] M. Rabbani, H. Farrokhi-Asl, and H. Rafiei, “A hybrid genetic algorithm for waste collection problem by heterogeneous fleet of vehicles with multiple separated compartments,” Journal of Intelligent & Fuzzy Systems, vol. 30, no. 3, pp. 1817–1830, Mar. (2016), doi: 10.3233/ifs-151893.
[36] T.R.P. Ramos, M.I. Gomes, and A. P. Barbosa-Póvoa, “Economical and environmental concerns in planning recyclable waste collection systems,” Transportation Research Part E, vol. 62, pp. 34-54 (2014).
[37] L. Reyes-Rubiano, L. Calvet, A. A. Juan, J. Faulin, and L. Bové, “A biased-randomized variable neighborhood search for sustainable multi-depot vehicle routing problems,” Journal of Heuristics, vol. 26, no. 3, pp. 401–422, Feb. (2018), doi: 10.1007/s10732-018-9366-0.
[38] S. Salhi, A. Imran, and N. A. Wassan, “The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation,” Computers & Operations Research, vol. 52, pp. 315–325, May (2013), doi: 10.1016/j.cor.2013.05.011.
[39] J. Sánchez-Oro, A. D. López-Sánchez, and J. M. Colmenar, “A general variable neighborhood search for solving the multi-objective open vehicle routing problem,” Journal of Heuristics, vol. 26, no. 3, pp. 423–452, Dec. (2017), doi: 10.1007/s10732-017-9363-8.
[40] Y. Suzuki, “A dual-objective metaheuristic approach to solve practical pollution routing problem,” International Journal of Production Economics, vol. 176, pp. 143–153, Mar. (2016), doi: 10.1016/j.ijpe.2016.03.008.
[41] E-G. Talbi, Metaheuristics: from Design to Implementation. John Wiley & Sons, Inc. ISBN 978-0-470-27858-1 (2009).
[42] M. Taslimi, R. Batta, and C. Kwon, “Medical waste collection considering transportation and storage risk,” Computers & Operations Research, vol. 120, p. 104966, Apr. (2020), doi: 10.1016/j.cor.2020.104966.
[43] J. Teixeira, A. P. Antunes, and J. P. De Sousa, “Recyclable waste collection planning––a case study,” European Journal of Operational Research, vol. 158, no. 3, pp. 543–554, Sep. (2003), doi: 10.1016/s0377-2217(03)00379-5.
[44] P. Toth, and D. Vigo, The Vehicle Routing Problem. Discrete Mathematics and Applications, SIAM, Philadelpha, PA (2002). https://doi.org/10.1137/1.9780898718515
[45] S. Wang, X. Wang, X. Liu, and J. Yu, “A Bi-Objective Vehicle-Routing Problem with Soft Time Windows and Multiple Depots to Minimize the Total Energy Consumption and Customer Dissatisfaction,” Sustainability, vol. 10, no. 11, p. 4257, Nov. (2018), doi: 10.3390/su10114257.
[46] Y. Wang, K. Assogba, J. Fan, M. Xu, Y. Liu, and H. Wang, “Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost,” Journal of Cleaner Production, vol. 232, pp. 12–29, May (2019), doi: 10.1016/j.jclepro.2019.05.344.
[47] WWF (World Wild Fund) “Causes of global warming.” WWF.org.au. Accessed: Feb. 2 (2021). [Online.] Available:https://www.wwf.org.au/what-we-do/climate/causes-of-global-warming#gs.t7xph0
[48] J. Wy, B.-I. Kim, and S. Kim, “The rollon–rolloff waste collection vehicle routing problem with time windows,” European Journal of Operational Research, vol. 224, no. 3, pp. 466–476, Sep. (2012), doi: 10.1016/j.ejor.2012.09.001.
[49] Y. Xiao, Q. Zhao, I. Kaku, and Y. Xu, “Development of a fuel consumption optimization model for the capacitated vehicle routing problem,” Computers & Operations Research, vol. 39, no. 7, pp. 1419–1431, Sep. (2011), doi: 10.1016/j.cor.2011.08.013.
[50] Y. Xiao and A. Konak, “The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion,” Transportation Research Part E Logistics and Transportation Review, vol. 88, pp. 146–166, Mar. (2016), doi: 10.1016/j.tre.2016.01.011.
[51] Y. Xu, L. Wang, and Y. Yang, “A New Variable Neighborhood Search Algorithm for the Multi Depot Heterogeneous Vehicle Routing Problem with Time Windows,” Electronic Notes in Discrete Mathematics, vol. 39, pp. 289–296, Nov. (2012), doi: 10.1016/j.endm.2012.10.038.
[52] Z. Zsigraiova, V. Semiao, and F. Beijoco, “Operation costs and pollutant emissions reduction by definition of new collection scheduling and optimization of MSW collection routes using GIS. The case study of Barreiro, Portugal,” Waste Management, vol. 33, no. 4, pp. 793–806, Dec. (2012), doi: 10.1016/j.wasman.2012.11.015.
