Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 1288-1303 |
Journal | TRANSPORTATION SCIENCE |
Volume | 51 |
Issue number | 4 |
DOIs | |
Publication status | Published - 6 Jul 2017 |
MoE publication type | A1 Journal article-refereed |
Keywords
- Vehicle Routing
- column generation
- k-path cuts
- green logistics