Learning Centre

A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Andelmin, Juho
dc.contributor.author Bartolini, Enrico
dc.date.accessioned 2019-06-03T14:17:13Z
dc.date.available 2019-06-03T14:17:13Z
dc.date.issued 2019-09-01
dc.identifier.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 en
dc.identifier.issn 0305-0548
dc.identifier.other PURE UUID: b0ed0e18-6f7b-4d34-abdb-a22bd692b1e1
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/b0ed0e18-6f7b-4d34-abdb-a22bd692b1e1
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85064982988&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/33842218/SCI_Andelmin_Bartolini_A_Multi_Start_Local_Search.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/38347
dc.description.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. en
dc.format.extent 43-63
dc.format.mimetype application/pdf
dc.language.iso en en
dc.relation.ispartofseries Computers and Operations Research en
dc.relation.ispartofseries Volume 109, issue September 2019 en
dc.rights openAccess en
dc.title A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Mathematics and Systems Analysis
dc.contributor.department RWTH Aachen University
dc.subject.keyword vehicle routing
dc.subject.keyword alternative fuel vehicles
dc.subject.keyword local search
dc.subject.keyword multigraph
dc.identifier.urn URN:NBN:fi:aalto-201906033432
dc.identifier.doi 10.1016/j.cor.2019.04.018
dc.date.embargo info:eu-repo/date/embargoEnd/2022-05-05

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication