A decomposition approach for the multi-depot vehicle routing problem with heterogeneous fleets, pickup–delivery, time windows, and route balance

Abstract

In this paper, we address the problem of equitable workload distribution in the multi-depot vehicle routing problem (MDVRP) with simultaneous pickup and delivery, time windows, and heterogeneous fleets. To ensure fairness, route balance is incorporated into the problem. This is motivated by real-world logistics applications in e-commerce, courier services, and online retail, where efficient and reliable operations are essential for minimizing costs and enhancing customer satisfaction. The integration of simultaneous pickup and delivery, time windows, and route balance captures the operational challenges faced in practice. The objective is to determine optimal and balanced vehicle routes while controlling costs. Direct exact methods, such as branch-and-cut, often perform poorly on large-scale instances due to computational complexity. To address this, we develop a feasibility-based Benders decomposition algorithm, which exploits problem structure to improve scalability while remaining exact. We evaluate its performance against the branch-and-cut method embedded in Gurobi. Results show that for small-scale instances, both approaches perform similarly, while for large instances, the BD method achieves smaller optimality gaps within a time limit of 1800 s, demonstrating superior scalability and efficiency.