Comparison of mixed-integer linear programming models for delivery problem with transshipments and battery swapping

Abstract

Efficient last-mile delivery in dense urban areas is complicated due to high costs, traffic congestion, and environmental impact. In this study, we presented two Mixed-Integer Linear Programming (MILP) formulations for the multi-depot and multi-robot vehicle routing problem with transshipment and battery swapping. We further enhanced them by applying a partitioning orbitope (PO) symmetry-breaking method on each model. We then compared all four models (two formulations with and without PO) to Gurobi’s runtime. Computational experiments on small and medium-sized problems confirmed that Gurobi’s built-in methods suffice for smaller problems, whereas the partitioning orbitope approach significantly improved runtimes for large-scale instances.