Comparison of compact formulations for the electric vehicle routing problem

Zhiguo Wu and Hande Yaman

Transportation Research Part B: Methodological, 2025, vol. 200, issue C

Abstract: The electric vehicle routing problem is an extension of the capacitated vehicle routing problem, where en-route recharging needs to be addressed due to the limited driving range of electric vehicles. In this study, we compare four compact formulations that differ in the way they model the battery consumption. The first two formulations use Miller–Tucker–Zemlin’s approach, while the last two use single-commodity flows for this purpose. Within each approach, the two formulations have distinct ways of dealing with the fact that recharging stations may be visited more than once. In particular, two formulations make use of arcs that correspond to two-leg paths with a recharging station in the middle, whereas the other two formulations use copies of recharging stations, as suggested in the literature. We compare the linear programming bounds of these four formulations as well as the existing formulations from a theoretical point of view. Then, we analyze the performance of the new and existing formulations using six sets of benchmark instances. The computational results show that our formulations tighten the linear programming bounds and require less computation time to prove optimality.

Keywords: Electric vehicle routing problem; Compact formulations; Linear programming bounds (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261525001638
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:transb:v:200:y:2025:i:c:s0191261525001638

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2025.103314

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().