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

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.