More efficient formulations and valid inequalities for the Green Vehicle Routing Problem

被引:23
作者
Bruglieri, M. [1 ]
Mancini, S. [2 ]
Pisacane, O. [3 ]
机构
[1] Politecn Milan, Dipartimento Design, Milan, Italy
[2] Univ Cagliari, Dipartimento Matemat & Informat, Cagliari, Italy
[3] Univ Politecn Marche, Dipartimento Ingn Informaz, Ancona, AN, Italy
关键词
Alternative Fuel Vehicle; Consecutive refueling; Efficient alternative fuel station; Valid inequalities; OPTIMIZATION; DELIVERY;
D O I
10.1016/j.trc.2019.05.040
中图分类号
U [交通运输];
学科分类号
08 ; 0823 ;
摘要
The Green Vehicle Routing Problem (G-VRP) aims to efficiently route a fleet of Alternative Fuel Vehicles, based at a common depot, in order to serve a set of customers, minimizing the total travel distance. Because of the limited driving range of these vehicles, intermediate stops at the Alternative Fuel Stations must also be considered. For the G-VRP, we propose two Mixed Integer Linear Programming formulations allowing multiple visits to the stations without introducing dummy copies of them. In the first model, only one visit to a station between two customers or between a customer and the depot is allowed. While, in the second model, two consecutive visits to stations are also permitted. In addition, the two formulations are strengthened through both dominance criteria to a priori identify the stations that are more efficient to use in each route and valid inequalities, specifically tailored for the G-VRP. Computational results, carried out on benchmark instances, show that our formulations strongly outperform the exact solution approaches presented in the literature. Finally, in order to better investigate the issue of the consecutive refueling stops, a new set of instances is properly generated and significant transport insights are also provided.
引用
收藏
页码:283 / 296
页数:14
相关论文
共 23 条
[11]   The green vehicle routing problem: A heuristic based exact solution approach [J].
Koc, Cagri ;
Karaoglan, Ismail .
APPLIED SOFT COMPUTING, 2016, 39 :154-164
[12]  
Kontovas C A., 2016, Green transportation logistics, P41, DOI DOI 10.1007/978-3-319-17175-32
[13]   Mathematical models for green vehicle routing problems with pickup and delivery: A case of semiconductor supply chain [J].
Madankumar, Sakthivel ;
Rajendran, Chandrasekharan .
COMPUTERS & OPERATIONS RESEARCH, 2018, 89 :183-192
[14]   The Hybrid Vehicle Routing Problem [J].
Mancini, Simona .
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2017, 78 :1-12
[15]   A multi-space sampling heuristic for the green vehicle routing problem [J].
Montoya, Alejandro ;
Gueret, Christelle ;
Mendoza, Jorge E. ;
Villegas, Juan G. .
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2016, 70 :113-128
[16]   Fuel emissions optimization in vehicle routing problems with time-varying speeds [J].
Qian, Jiani ;
Eglese, Richard .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 248 (03) :840-848
[17]  
Sbihi A, 2007, 4OR-Q J OPER RES, V5, P99, DOI [10.1007/s10288-007-0047-3, 10.1007/s10479-009-0651-z]
[18]  
Schneider M., 2013, APPENDIX ELECT VEHIC
[19]  
Sharafi A., 2016, J OPTIMIZAT IND ENG, V10, P93, DOI DOI 10.22094/JOIE.2016.264
[20]   A block recombination approach to solve green vehicle routing problem [J].
Tiwari, Anurag ;
Chang, Pei-Chann .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2015, 164 :379-387