Solving a Multi-Depot Battery Swapping Cabinet Location-Routing Problem with Time Windows via a Heuristic-Enhanced Branch-and-Price Algorithm

Yongtong Chen, Haojie Zheng and Shuzhu Zhang ()
Additional contact information
Yongtong Chen: Department of Information Management, School of Government, Beijing Normal University, Beijing 100875, China
Haojie Zheng: School of Management, Zhejiang University of Finance and Economics, Hangzhou 310018, China
Shuzhu Zhang: School of Management, Zhejiang University of Finance and Economics, Hangzhou 310018, China

Mathematics, 2025, vol. 13, issue 20, 1-24

Abstract: On-demand urban delivery increasingly relies on electric delivery bicycles (EDBs), yet their limited battery capacity creates coupled challenges of routing efficiency and energy replenishment. We study a novel battery swapping cabinet location-routing problem (BSC-LRP) with multiple depots, which jointly optimizes routing and modular energy infrastructure deployment under time-window and battery constraints. To address the problem’s complexity, we design an improved branch-and-price algorithm enhanced with adaptive heuristic-exact labeling (IBP-HL) and a robust arc-based branching scheme. This hybrid framework accelerates column generation while preserving exactness, representing a methodological advancement over standard B&P approaches. Computational experiments on modified Solomon instances show that IBP-HL consistently outperforms Gurobi in both runtime and solution quality on small cases, and achieves substantial speedups and improved bounds over baseline B&P on medium and large cases. These results demonstrate not only the scalability of IBP-HL but also its practical relevance: the framework provides decision support for operators and planners in designing cost-efficient, reliable, and sustainable last-mile delivery systems with battery-swapping infrastructure.

Keywords: on-demand delivery; battery swapping cabinet; electric delivery bicycle; location-routing problem; branch-and-price; heuristic labeling (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/20/3243/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/20/3243/ (text/html)

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:gam:jmathe:v:13:y:2025:i:20:p:3243-:d:1768001

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().