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 repre-sents 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 sta-tions, five vehicles and three technologies to proven optimality. Near-optimal heu-ristic solutions were obtained with a general-purpose MIP solver from the columns generated at the root node.

A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies / A. Ceselli, Á. Felipe, M. Teresa Ortuño, G. Righini, G. Tirado. - In: SN OPERATIONS RESEARCH FORUM. - ISSN 2662-2556. - 2:1(2021 Jan 26). [10.1007/s43069-020-00052-x]

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

A. Ceselli
Primo
;
G. Righini
Penultimo
;
2021-01-26

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 repre-sents 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 sta-tions, five vehicles and three technologies to proven optimality. Near-optimal heu-ristic solutions were obtained with a general-purpose MIP solver from the columns generated at the root node.
Electric vehicle routing · Column generation · Cutting planes · Dynamic programming;
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
EVRP_ORFO.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 397.98 kB
Formato Adobe PDF
397.98 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/827106
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact