International Journal of Nonlinear Analysis and Applications
Developing a green vehicle routing problem model with time windows and simultaneous pickup and delivery under demand uncertainty: Minimizing fuel consumption
Document Type : Research Paper
Authors
Department of Industrial Engineering, Yazd University, Yazd, Iran
Abstract
The vehicle routing problem has attracted much attention in the recent decade. Considering the real-world constraints, many extensions have been developed. This paper develops a new model for the green vehicle routing problem with simultaneous pickup and delivery under demand uncertainty. Due to the problem's complexity, the standard solvers are only able to solve small-scale instances. To solve the large-scale problems, a two-stage algorithm based on the modified AVNS is proposed. Extensive computational experiments are conducted using modified versions of Solomon’s benchmark instances to show the performance of the algorithm. The results affirm that the two-stage algorithm is capable of generating optimal solutions for small-size instances and the planned routes generated for large-size instances were significantly more robust against the increase of uncertainty parameters.
Keywords
[1] A. Agra, M. Christiansen, R. Figueiredo, L.M. Hvattum, M. Poss, and C. Requejo, The robust vehicle routing problem with time windows, Comput. Oper. Res. 40 (2013), no. 3, 856–866.
[2] T.J. Ai and V. Kachitvichyanukul, A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Comput. Oper. Res. 36 (2009), no. 5, 1693–1702.
[3] F. Arnold and K. S¨orensen, Knowledge-guided local search for the vehicle routing problem, Comput. Oper. Res. 105 (2019), 32–46.
[4] H. Ashtineh and M.S. Pishvaee, Alternative fuel vehicle-routing problem: A life cycle analysis of transportation fuels, J. Cleaner Prod. 219 (2019), 166–182.
[5] R. Baldacci, A. Mingozzi, and R. Roberti, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, Eur. J.f Oper. Res. 218 (2012), no. 1, 1–6.
[6] D. Bertsimas and D.B. Brown, Constructing uncertainty sets for robust linear optimization, Oper. Res. 57 (2009), no. 6, 1483–1495.
[7] D. Bertsimas and M. Sim, The price of robustness, Oper. Res.earch 52 (2004), no. 1, 35–53.
[8] Benjamin Biesinger, Bin Hu, and G¨unther Raidl, An integer l-shaped method for the generalized vehicle routing problem with stochastic demands, Electronic Notes in Discrete Mathematics 52 (2016), 245–252.
[9] M.aurizio Bruglieri, S. Mancini, F. Pezzella, and O. Pisacane, A new mathematical programming model for the green vehicle routing problem, Electronic Notes Discrete Math. 55 (2016), 89–92.
[10] H. Caceres, R. Batta, and Q. He, School bus routing with stochastic demand and duration constraints, Transport. Sci. 51 (2017), no. 4, 1349–1364.
[11] W.C. Chiang and C.Y. Cheng, Considering the performance bonus balance in the vehicle routing problem with soft time windows, Procedia Manufactur. 11 (2017), 2156–2163.
[12] G.B. Dantzig and J. Ramser, The truck dispatching problem, Manag. Sci. 6 (1959), no. 1, 80–91.
[13] S. Erdo˘gan and E. Miller-Hooks, A green vehicle routing problem, Transport. Res. Part E: Logistics Transport. Rev. 48 (2012), no. 1, 100–114.
[14] M. Gendreau, O. Jabali, and W. Rei, 50th anniversary invited article—future research directions in stochastic vehicle routing, Transport. Sci. 50 (2016), no. 4, 1163–1173.
[15] B.L. Golden and A.A. Assad, Vehicle routing with time-window constraints, Amer. J. Math. Manag. Sci. 6 (1986), no. 3-4, 251–260.
[16] P. Hansen, N. Mladenovi´c, R. Todosijevi´c, and S. Hanafi, Variable neighborhood search: basics and variants, Eur. J. Comput. Optim. 5 (2017), no. 3, 423–454.
[17] C. Hu, J. Lu, X. Liu, and G. Zhang, Robust vehicle routing problem with hard time windows under demand and travel time uncertainty, Comput. Oper. Res. 94 (2018), 139–153.
[18] J.W. Joubert and S.J. Claasen, A sequential insertion heuristic for the initial solution to a constrained vehicle routing problem, ORiON 22 (2006), no. 1, 105–116.
[19] B. Kallehauge, Formulations and exact algorithms for the vehicle routing problem with time windows, Comput. Oper. Res. 35 (2008), no. 7, 2307–2330.
[20] V. Leggieri and M. Haouari, A practical solution approach for the green vehicle routing problem, Transport. Res. Part E: Logistics Transport. Rev. 104 (2017), 97–112.
[21] S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem, Oper. Res. 21 (1973), no. 2, 498–516.
[22] R. Liu, X. Xie, V. Augusto, and C. Rodriguez, Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, Eur. J. Oper. Res. 230 (2013), no. 3, 475–486.
[23] H. Min, The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transport. Res. PartA: Gen. 23 (1989), no. 5, 377–386.
[24] D.M. Miranda and S.V. Concei¸c˜ao, The vehicle routing problem with hard time windows and stochastic travel and service time, Expert Syst. Appl. 64 (2016), 104–116.
[25] R. Moghdani, K. Salimifard, E. Demir, and A. Benyettou, The green vehicle routing problem: A systematic literature review, J. Cleaner Prod. 279 (2021), 123691.
[26] S.N. Parragh, K.F. Doerner, and R.F. Hartl, A survey on pickup and delivery models part ii: Transportation between pickup and delivery locations, J. Betriebswirtschaft 58 (2006), 81–117.
[27] M. Schneider, A. Stenger, and J. Hof, An adaptive vns algorithm for vehicle routing problems with intermediate stops, Or Spectrum 37 (2015), no. 2, 353–387.
[28] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res. 35 (1987), no. 2, 254–265.
[29] A. Stenger, D. Vigo, S. Enz, and M. Schwind, An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping, Transport. Sci. 47 (2013), no. 1, 64–80.
[30] E. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, ´ A tabu search heuristic for the vehicle routing problem with soft time windows, Transport. Sci. 31 (1997), no. 2, 170–186.
[31] D. Ta¸s, O. Jabali, and T. Van Woensel, A vehicle routing problem with flexible time windows, Comput. Oper. Res. 52 (2014), 39–54.
[32] Paolo Toth and Daniele Vigo, Vehicle routing: problems, methods, and applications, SIAM, 2014.
[33] H.-F. Wang and Y.-Y. Chen, A genetic algorithm for the simultaneous delivery and pickup problems with time window, Comput. Ind. Engin. 62 (2012), no. 1, 84–95.
[2] T.J. Ai and V. Kachitvichyanukul, A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Comput. Oper. Res. 36 (2009), no. 5, 1693–1702.
[3] F. Arnold and K. S¨orensen, Knowledge-guided local search for the vehicle routing problem, Comput. Oper. Res. 105 (2019), 32–46.
[4] H. Ashtineh and M.S. Pishvaee, Alternative fuel vehicle-routing problem: A life cycle analysis of transportation fuels, J. Cleaner Prod. 219 (2019), 166–182.
[5] R. Baldacci, A. Mingozzi, and R. Roberti, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, Eur. J.f Oper. Res. 218 (2012), no. 1, 1–6.
[6] D. Bertsimas and D.B. Brown, Constructing uncertainty sets for robust linear optimization, Oper. Res. 57 (2009), no. 6, 1483–1495.
[7] D. Bertsimas and M. Sim, The price of robustness, Oper. Res.earch 52 (2004), no. 1, 35–53.
[8] Benjamin Biesinger, Bin Hu, and G¨unther Raidl, An integer l-shaped method for the generalized vehicle routing problem with stochastic demands, Electronic Notes in Discrete Mathematics 52 (2016), 245–252.
[9] M.aurizio Bruglieri, S. Mancini, F. Pezzella, and O. Pisacane, A new mathematical programming model for the green vehicle routing problem, Electronic Notes Discrete Math. 55 (2016), 89–92.
[10] H. Caceres, R. Batta, and Q. He, School bus routing with stochastic demand and duration constraints, Transport. Sci. 51 (2017), no. 4, 1349–1364.
[11] W.C. Chiang and C.Y. Cheng, Considering the performance bonus balance in the vehicle routing problem with soft time windows, Procedia Manufactur. 11 (2017), 2156–2163.
[12] G.B. Dantzig and J. Ramser, The truck dispatching problem, Manag. Sci. 6 (1959), no. 1, 80–91.
[13] S. Erdo˘gan and E. Miller-Hooks, A green vehicle routing problem, Transport. Res. Part E: Logistics Transport. Rev. 48 (2012), no. 1, 100–114.
[14] M. Gendreau, O. Jabali, and W. Rei, 50th anniversary invited article—future research directions in stochastic vehicle routing, Transport. Sci. 50 (2016), no. 4, 1163–1173.
[15] B.L. Golden and A.A. Assad, Vehicle routing with time-window constraints, Amer. J. Math. Manag. Sci. 6 (1986), no. 3-4, 251–260.
[16] P. Hansen, N. Mladenovi´c, R. Todosijevi´c, and S. Hanafi, Variable neighborhood search: basics and variants, Eur. J. Comput. Optim. 5 (2017), no. 3, 423–454.
[17] C. Hu, J. Lu, X. Liu, and G. Zhang, Robust vehicle routing problem with hard time windows under demand and travel time uncertainty, Comput. Oper. Res. 94 (2018), 139–153.
[18] J.W. Joubert and S.J. Claasen, A sequential insertion heuristic for the initial solution to a constrained vehicle routing problem, ORiON 22 (2006), no. 1, 105–116.
[19] B. Kallehauge, Formulations and exact algorithms for the vehicle routing problem with time windows, Comput. Oper. Res. 35 (2008), no. 7, 2307–2330.
[20] V. Leggieri and M. Haouari, A practical solution approach for the green vehicle routing problem, Transport. Res. Part E: Logistics Transport. Rev. 104 (2017), 97–112.
[21] S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem, Oper. Res. 21 (1973), no. 2, 498–516.
[22] R. Liu, X. Xie, V. Augusto, and C. Rodriguez, Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, Eur. J. Oper. Res. 230 (2013), no. 3, 475–486.
[23] H. Min, The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transport. Res. PartA: Gen. 23 (1989), no. 5, 377–386.
[24] D.M. Miranda and S.V. Concei¸c˜ao, The vehicle routing problem with hard time windows and stochastic travel and service time, Expert Syst. Appl. 64 (2016), 104–116.
[25] R. Moghdani, K. Salimifard, E. Demir, and A. Benyettou, The green vehicle routing problem: A systematic literature review, J. Cleaner Prod. 279 (2021), 123691.
[26] S.N. Parragh, K.F. Doerner, and R.F. Hartl, A survey on pickup and delivery models part ii: Transportation between pickup and delivery locations, J. Betriebswirtschaft 58 (2006), 81–117.
[27] M. Schneider, A. Stenger, and J. Hof, An adaptive vns algorithm for vehicle routing problems with intermediate stops, Or Spectrum 37 (2015), no. 2, 353–387.
[28] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res. 35 (1987), no. 2, 254–265.
[29] A. Stenger, D. Vigo, S. Enz, and M. Schwind, An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping, Transport. Sci. 47 (2013), no. 1, 64–80.
[30] E. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, ´ A tabu search heuristic for the vehicle routing problem with soft time windows, Transport. Sci. 31 (1997), no. 2, 170–186.
[31] D. Ta¸s, O. Jabali, and T. Van Woensel, A vehicle routing problem with flexible time windows, Comput. Oper. Res. 52 (2014), 39–54.
[32] Paolo Toth and Daniele Vigo, Vehicle routing: problems, methods, and applications, SIAM, 2014.
[33] H.-F. Wang and Y.-Y. Chen, A genetic algorithm for the simultaneous delivery and pickup problems with time window, Comput. Ind. Engin. 62 (2012), no. 1, 84–95.
)
Volume 14, Issue 1
January 2023Pages 2655-2669
- Receive Date: 04 February 2021
- Revise Date: 20 April 2021
- Accept Date: 30 April 2021