Partial linear recharging strategy for the electric fleet size and mix vehicle routing problem with time windows and recharging stations

Weiquan Wang and Jingyi Zhao

European Journal of Operational Research, 2023, vol. 308, issue 2, 929-948

Abstract: The electric fleet size and mix vehicle routing problem with time windows and recharging stations (E-FSMFTW) is an extension of the well-known electric vehicle routing problem with time windows (EVRPTW). The fleet consists of heterogeneous electric vehicles that differ in their fixed cost, transport capacity and battery size. In this paper, we introduce the electric fleet size and mix vehicle routing problem with a partial linear recharging strategy (E-FSMFTW-PR). To solve this problem, we formulate a path-based mixed-integer linear model without replicating any recharging stations. Then, we propose a tailored hybrid heuristic that combines a large neighborhood search algorithm with a set partitioning component. Our methods are tested on the public E-FSMFTW benchmark instances. The results show that our model can be used in a commercial solver to solve 88 out of 108 small-scale E-FSMFTW-PR instances. Allowing partial linear recharging can significantly reduce the logistical cost of large-scale E-FSMFTW instances compared to the best-known solutions with full recharging strategy. We also use the heuristic algorithm to solve a newly designed instance set from a real-world dataset, and investigate the benefit of the partial linear recharging strategy. Finally, our heuristic is benchmarked against state-of-the-art algorithms on benchmark instances of related problems. Our algorithm finds 38 new best solutions on large-scale E-FSMFTW-FR instances, finds 11 new best solutions on large-scale EVRPTW-PR instances, and obtains a high-quality local optimal solution on a real-world dataset.

Keywords: Routing; Heterogeneous fleet; Partial linear recharging; Path-based model; Large neighborhood search (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722009389
Full text for ScienceDirect subscribers only

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:eee:ejores:v:308:y:2023:i:2:p:929-948

DOI: 10.1016/j.ejor.2022.12.011

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().