Electric Vehicle Fleets: Scalable Route and Recharge Scheduling Through Column Generation

Axel Parmentier (), Rafael Martinelli () and Thibaut Vidal ()
Additional contact information
Axel Parmentier: CERMICS, Ecole des Ponts, 77455 Marne-la-Vallée, France
Rafael Martinelli: Department of Industrial Engineering, Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil
Thibaut Vidal: Data-Driven Supply Chains, Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montreal, Quebec, Canada; Department of Computer Science, Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil

Transportation Science, 2023, vol. 57, issue 3, 631-646

Abstract: The rise of battery-powered vehicles has led to many new technical and methodological hurdles. Among these, the efficient planning of an electric fleet to fulfill passenger transportation requests still represents a major challenge. This is because of the specific constraints of electric vehicles, bound by their battery autonomy and necessity of recharge planning, and the large scale of the operations, which challenges existing optimization algorithms. The purpose of this paper is to introduce a scalable column generation approach for routing and scheduling in this context. Our algorithm relies on four main ingredients: (i) a multigraph reformulation of the problem based on a characterization of nondominated charging arcs, (ii) an efficient bidirectional pricing algorithm using tight backward bounds, (iii) sparsification approaches permitting to decrease the size of the subjacent graphs dramatically, and (iv) a diving heuristic, which locates near-optimal solutions in a fraction of the time needed for a complete branch-and-price. Through extensive computational experiments, we demonstrate that our approach significantly outperforms previous algorithms for this setting, leading to accurate solutions for problems counting several hundreds of requests.

Keywords: routing and scheduling; electric vehicles; column generation; diving heuristics (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.1199 (application/pdf)

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:inm:ortrsc:v:57:y:2023:i:3:p:631-646

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().