We propose an exact algorithm for solving the green vehicle routing problem (G-VRP). The G-VRP models the optimal routing of an alternative fuel vehicle fleet to serve a set of geographically scattered customers. Vehicles’ fuel autonomy and possible refueling stops en route are explicitly modeled and maximum duration constraints are imposed on each vehicle route. We model the G-VRP as a set partitioning problem in which columns represent feasible routes corresponding to simple circuits in a multigraph. Each node in the multigraph represents one customer and each arc between two customers represents a nondominated path through a set of refueling stations visited by a vehicle when traveling directly between the two customers. We strengthen the set partitioning formulation by adding valid inequalities including k -path cuts and describe a method for separating them. We provide computational results on benchmark instances showing that the algorithm can optimally solve instances with up to ∼110 customers. The online appendix is available at https://doi.org/10.1287/trsc.2016.0734 .
An Exact Algorithm for the Green Vehicle Routing Problem
Transportation science ; 51 , 4 ; 1288-1303
2017
Aufsatz (Zeitschrift)
Englisch
Lokalklassifikation TIB: | 770/1935/7000 | |
BKL: | 55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines |
An Exact Algorithm for the Green Vehicle Routing Problem
British Library Online Contents | 2017
|An Exact Algorithm for the Vehicle Routing Problem with Backhauls
British Library Online Contents | 1997
|An Exact Algorithm for the Vehicle Routing Problem with Backhauls
Online Contents | 1997
|A Green Vehicle Routing Problem
Online Contents | 2012
|Exact Solution of the Vehicle Routing Problem
Springer Verlag | 1998
|