A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation
No Thumbnail Available
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2019-09-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
21
Series
Computers and Operations Research, Volume 109, issue September 2019, pp. 43-63
Abstract
We consider the Green Vehicle Routing Problem (G-VRP) which is an extension of the classical vehicle routing problem for alternative fuel vehicles. In the G-VRP, vehicles' driving autonomy and possible refueling stops en-route are explicitly modeled. We propose a multi-start local search algorithm that consists of three phases. The first two phases iteratively construct new solutions, improve them by local search, and store all vehicle routes forming these solutions in a route pool. Phase three optimally combines vehicle routes in the route pool by solving a set partitioning problem and improves the final solution by local search. The algorithm is based on a multigraph reformulation of the G-VRP in which nodes correspond to customers and a depot, and arcs correspond to possible sequences of refueling stops for vehicles traveling between two nodes. All local search operators used by our algorithm are tailored to exploit this reformulation and do not explicitly deal with refueling stations. We report computational results on benchmark instances with up to ~ 470 customers, showing that the algorithm is competitive with state-of-the-art heuristics.Description
Keywords
vehicle routing, alternative fuel vehicles, local search, multigraph
Other note
Citation
Andelmin, J & Bartolini, E 2019, ' A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation ', Computers and Operations Research, vol. 109, no. September 2019, pp. 43-63 . https://doi.org/10.1016/j.cor.2019.04.018