A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies

Alberto Ceselli (), Ángel Felipe (), M. Teresa Ortuño (), Giovanni Righini () and Gregorio Tirado ()
Additional contact information
Alberto Ceselli: Università degli Studi di Milano
Ángel Felipe: Universidad Complutense de Madrid
M. Teresa Ortuño: Universidad Complutense de Madrid
Giovanni Righini: Università degli Studi di Milano
Gregorio Tirado: Universidad Complutense de Madrid

SN Operations Research Forum, 2021, vol. 2, issue 1, 1-33

Abstract: Abstract We provide an exact optimization algorithm for the electric vehicle routing problem with multiple recharge technologies. Our branch-and-cut-and-price algorithm relies upon a path-based formulation, where each column in the master problem represents a sequence of customer visits between two recharge stations instead of a whole route. This allows for massive decomposition, and parallel implementation of the pricing phase, exploiting the large number of independent pricing sub-problems. The algorithm could solve instances with up to thirty customers, nine recharge stations, five vehicles and three technologies to proven optimality. Near-optimal heuristic solutions were obtained with a general-purpose MIP solver from the columns generated at the root node.

Keywords: Electric vehicle routing; Column generation; Cutting planes; Dynamic programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s43069-020-00052-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:2:y:2021:i:1:d:10.1007_s43069-020-00052-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-020-00052-x

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().