Benders decomposition for charging station location-routing problem with time-dependent travel times: a space-time-electricity network perspective

Chenhao Zhang, Rui Yong, Xia Jiang, Yibei Zhang, Maocan Song and Lin Cheng

Energy, 2025, vol. 333, issue C

Abstract: The urgency of carbon reduction has made electric vehicle (EV) adoption essential. Charging station planning is key to easing range anxiety and advancing green energy use. Although numerous studies examine location-routing problems on space networks, limited attention has been given to time-dependence, charging capacity constraints, or space-time models that accurately capture feasible paths. To address these gaps, we propose a mixed-integer linear programming (MILP) model for intercity electric freight transportation within a space-time-electricity network. The model integrates time-dependent travel times, station capacity limits, time windows, queuing delays, nonlinear energy consumption and heterogeneous deliveries. To improve efficiency, a branch-and-Benders-cut approach based on classical Benders decomposition is proposed, dividing the origin problem into an assignment problem (i.e., the master problem) and a minimum-cost flow problem with capacity constraints (i.e., the subproblem). The master problem is solved only once, while the subproblem dynamically provides cuts along the branching. Computational experiments on 178 instances from the Sioux Falls, inter-district road and inter-city expressway networks in real world demonstrate that the proposed method reduces computation time by 65.5 %-70.6 % compared to conventional Benders decomposition and by 11.1 %-39.5 % relative to branch-and-bound. Incorporating time-dependent dynamics reduces objective values by 9.3 %-33.1 %. Sensitivity analysis offers further insights for infrastructure development and policy-making.

Keywords: Charging station location; Vehicle routing problem; Space-time-electricity network; Benders decomposition; Charging station capacity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0360544225029524
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:energy:v:333:y:2025:i:c:s0360544225029524

DOI: 10.1016/j.energy.2025.137310

Access Statistics for this article

Energy is currently edited by Henrik Lund and Mark J. Kaiser

More articles in Energy from Elsevier
Bibliographic data for series maintained by Catherine Liu ().