A branch-and-price algorithm for two-echelon electric vehicle routing problem
Tóm tắt
Motivated by express and e-commerce companies’ distribution practices, we study a two-echelon electric vehicle routing problem. In this problem, fuel-powered vehicles are used to transport goods from a depot to intermediate facilities (satellites) in the first echelon, whereas electric vehicles, which have limited driving ranges and need to be recharged at recharging stations, are used to transfer goods from the satellites to customers in the second echelon. We model the problem as an arc flow model and decompose the model into a master problem and pricing subproblem. We propose a branch-and-price algorithm to solve it. We use column generation to solve the restricted master problem to provide lower bounds. By enumerating all the subsets of the satellites, we generate feasible columns by solving the elementary shortest path problem with resource constraints in the first echelon. Then, we design a bidirectional labeling algorithm to generate feasible routes in the second echelon. Comparing the performance of our proposed algorithm with that of CPLEX in solving a set of small-sized instances, we demonstrate the former’s effectiveness. We further assess our algorithm in solving two sets of larger scale instances. We also examine the impacts of some model parameters on the solution.
Từ khóa
Tài liệu tham khảo
Awaga AL, Xu W, Liu L, Zhang Y (2020) Evolutionary game of green manufacturing mode of enterprises under the influence of government reward and punishment. Adv Production Eng Manag 14(4):416–430. https://doi.org/10.14743/apem2020.4.375
Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math Program 120(2):347
Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper Res 59(5):1269–1283. https://doi.org/10.1287/opre.1110.0975 Cited By 84
Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. Informs J Comput 24(3):356–371
Baldacci R, Mingozzi A, Roberti R, Calvo RW (2013) An exact algorithm for the two-echelon capacitated vehicle routing problem. Oper Res 61(2):298–314
Barros L, Linfati R, Escobar JW (2020) An exact approach for the consistent vehicle routing problem (convrp). Adv Prod Eng Manag 15(3):255–266. https://doi.org/10.14743/apem2020.3.363
Breunig U, Baldacci R, Hartl RF, Vidal T (2019) The electric two-echelon vehicle routing problem. Comput Oper Res 103:198–210
Breunig U, Schmid V, Hartl RF, Vidal T (2016) A large neighbourhood based heuristic for two-echelon routing problems. Comput Oper Res 76:208–225
Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164
Cortés-Murcia DL, Prodhon C, Murat Afsar H (2019) The electric vehicle routing problem with time windows, partial recharges and satellite customers. Transportation Research Part E: Logistics and Transportation Review 130:184–206. https://doi.org/10.1016/j.tre.2019.08.015http://www.sciencedirect.com/science/article/pii/S1366554518310597
Crainic TG, Perboli G, Mancini S, Tadei R (2010) Two-echelon vehicle routing problem: a satellite location analysis. Proc-Soc Behav Sci 2(3):5944–5955
Crainic TG, Ricciardi N, Storchi G (2004) Advanced freight transportation systems for congested urban areas. Trans Res Part C 12(2):119–137
Crainic TG, Ricciardi N, Storchi G (2009) Models for evaluating and planning city logistics systems. Trans Sci 43(4):432–454
Cuda R, Guastaroba G, Speranza MG (2015) A survey on two-echelon routing problems. Comput Oper Res 55:185–199
Dellaert N, Dashty Saridarq F, Van Woensel T, Crainic TG (2019) Branch-and-price-based algorithms for the two-echelon vehicle routing problem with time windows. Trans Sci 53(2):463–479
Desaulniers G, Errico F, Irnich S, Schneider M (2016) Exact algorithms for electric vehicle-routing problems with time windows. Oper Res 64(6):1388–1405
Du J, Li Q, Qiao F, Yu L (2018) Estimation of vehicle emission on mainline freeway under isolated and integrated ramp metering strategies. Environ Eng Manag J 17(5):1237–1248
Du J, Li Q, Qiao F, Yu L (2019) Temporal characteristics and forecasting of pm2.5 concentration based on historical data in Houston, USA. Conserv Recycl 147:145–156
Du J, Qiao F, Yu L (2020) Improving bus transit services for disabled individuals: demand clustering, bus assignment, and route optimization. IEEE Access 8:121564–121571. https://doi.org/10.1109/ACCESS.2020.3007322
EC: Together towards competitive and resource-efficient urban mobility. https://ec.europa.eu/transparency/regdoc/rep/1/2013/EN/1-2013-913-EN-F1-1.Pdf (2013)
Felipe Á, Ortuño MT, Righini G, Tirado G (2014) A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Trans Res Part E 71:111–128
Froger A, Mendoza JE, Jabali O, Laporte G (2019) Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions. Comput Oper Res 104:256–294
H G, X Y (2019) Optimal deployment of charging stations and movable charging vehicles for electric vehicles. J Syst Manag Sci 9(1):105–116
GDZ: Zero emission stadslogistiek. http://greendealzes.connekt.nl (2016)
Gocken T, Yaktubay M (2019) Comparison of different clustering algorithms via genetic algorithm for vrptw. Int J Simul Modelling 18(4):574–585
Gonçalves F, Cardoso SR, Relvas S, Barbosa-Póvoa A (2011) Optimization of a distribution network using electric vehicles: A vrp problem. In: Proceedings of the IO2011-15 Congresso da associação Portuguesa de Investigação Operacional, Coimbra, Portugal, pp. 18–20
Gonzalez-Feliu J, Semet F, Routhier JL (2014) Sustainable urban logistics: concepts, methods and information systems. Springer, Berlin
Grangier P, Gendreau M, Lehuédé F, Rousseau LM (2016) An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. Euro J Oper Res 254(1):80–91
Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput Oper Res 39(12):3215–3228
Hiermann G, Puchinger J, Ropke S, Hartl RF (2016) The electric fleet size and mix vehicle routing problem with time windows and recharging stations. Euro J Oper Res 252(3):995–1018
IEA: Global ev outlook 2019. https://webstore.iea.org/download /direct/2807?fileName= Global_ EV_ Outlook _2019.pdf (2019)
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Column generation, pp. 33–65. Springer
Jepsen M, Spoorendonk S, Ropke S (2013) A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Trans Sci 47(1):23–37
Jie W, Yang J, Zhang M, Huang Y (2019) The two-echelon capacitated electric vehicle routing problem with battery swapping stations: formulation and efficient methodology. Euro J Oper Res 272(3):879–904
Keskin M, Çatay B (2018) A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Comput Oper Res 100:172–188
Keskin M, Laporte G, Çatay B (2019) Electric vehicle routing problem with time-dependent waiting times at recharging stations. Comput Oper Res 107:77–94
Li H, Zhang L, Lv T, Chang X (2016) The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems. Trans Res Part B 94:169–188
Li HY, Xu W, Cui Y, Wang Z, Xiao M, Sun ZX (2020) Preventive maintenance decision model of urban transportation system equipment based on multi-control units. IEEE Access 8:15851–15869. https://doi.org/10.1109/ACCESS.2019.2961433
Liao CS, Lu SH, Shen ZJM (2016) The electric vehicle touring problem. Transportation Research Part B: Methodological 86:163–180
Montoya A, Guéret C, Mendoza JE, Villegas JG (2017) The electric vehicle routing problem with nonlinear charging function. Trans Res Part B 103:87–110
NBSPRC: Cumulative value of sales of new energy vehicles. http://data.stats.gov.cn/easyquery.htm?cn=B01&zb=A03011M&sj=2019A (2019)
Pelletier S, Jabali O, Laporte G (2016) 50th anniversary invited article-goods distribution with electric vehicles: review and research perspectives. Trans Sci 50(1):3–22
Perboli G, Tadei R (2010) New families of valid inequalities for the two-echelon vehicle routing problem. Electron Notes Discrete Math 36:639–646
Perboli G, Tadei R, Fadda E (2018) New valid inequalities for the two-echelon capacitated vehicle routing problem. Electron Notes Discrete Math 64:75–84
Perboli G, Tadei R, Vigo D (2011) The two-echelon capacitated vehicle routing problem: models and math-based heuristics. Trans Sci 45(3):364–380
Righini G, Salani M (2009) Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Comput Oper Res 36(4):1191–1203
Santos FA, Mateus GR, da Cunha AS (2015) A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Trans Sci 49(2):355–368
Schneider M, Stenger A, Goeke D (2014) The electric vehicle-routing problem with time windows and recharging stations. Trans Sci 48(4):500–520
Tahami H, Rabadi G, Haouari M (2020) Exact approaches for routing capacitated electric vehicles. Transportation Research Part E: Logistics and Transportation Review 144:102126. https://doi.org/10.1016/j.tre.2020.102126http://www.sciencedirect.com/science/article/pii/S1366554520307742
Wang D, Zhou H, Feng R (2019) A two-echelon vehicle routing problem involving electric vehicles with time windows. In: Journal of Physics: Conference Series, vol. 1324, p. 012071. IOP Publishing
xianjichina.com: New energy logistics vehicle replacing fuel logistics vehicle has become a trend. https://www.xianjichina.com/news/details_83369.html (2018)
Zhang H, Cui Y (2019) A model combining a bayesian network with a modified genetic algorithm for green supplier selection. SIMULATION: Transactions of The Society for Modeling and Simulation International 95(12):1165–1183