9 October 2024 in Reliability Engineering & System Safety
31 January 2026 in Computers & Industrial Engineering
15 July 2025 in Reliability Engineering & System Safety
15 July 2026 in Applied Energy
3 October 2026 in SSRN Electronic Journal
The actual mileage cost between two places varies according to the weather, speed, traffic scenario, payload, pick-up and delivery drops, and driving behaviors, resulting in the stochastic traveling salesman problem under mileage uncertainty. We apply logic-based Benders decomposition (LBBD) to model a two-stage battery swap stochastic traveling salesman problem (BS-STSP), where the first-stage direct mileage and second-stage detour mileage costs vary across different traffic scenarios. The objective is to minimize the total mileage cost. We propose three accelerating strategies: (1) a branch-and-cut reformulation, (2) solving the subproblem with dynamic programming, and (3) generating analytical cuts for the master problem. Our computational study, modified from a widely used Montoya’s data set of 540 instances with up to 40 customer nodes, 8 swap stations, and 50 scenarios, demonstrates the effectiveness of the proposed acceleration strategies. Our acceleration strategies accelerate the optimization process by up to 49.5% while maintaining stable performance across general instances, making it applicable for real-world operators. A key additional finding is that the analytical feasibility cut generated by our novel dynamic programming based cut strengthening technique successfully proves 91 out of 180 instances to be infeasible when battery size is limited under stochastic scenarios, while the existing methods fail to prove any instance infeasible. The proposed approach successfully mitigates the mileage anxiety of electric vehicles under mileage uncertainty by providing a novel infeasibility (run out of energy halfway) proving method, and demonstrates the potential of combining dynamic programming and LBBD for infeasibility proving of resource-constrained optimization problems.
31 March 2026 in Internet of Things