A solution approach for multi‐trip vehicle routing problems with time windows, fleet sizing, and depot location

We present a solution approach for a multi-trip vehicle routing problem with time windows in which the locations of a prescribed number of depots and the fleet sizes must also be optimized. Given the complexity of the task, we divide the problem into subproblems that are solved sequentially. First, we address strategic decisions, which are solved once and remain constant thereafter. Depots are allocated by solving a p-median problem and fleet sizes are determined by identifying the vehicle requirements of several worst-case demand instances. Then, we address the operational planning aspect: optimizing the vehicle routes on a daily basis to satisfy the fluctuating customer demand. We assign customers to depots based on distance and “routing effort,” and for the routing problem we combine a tailor-made branch-and-cut algorithm with a heuristic consisting of a route construction phase and packing of routes into vehicle trips. Our strategic decision models are robust in the sense that when applied to unseen data, all customers could be visited with the allocated fleet sizes and depot locations. Our operational routing methods are both time and cost-effective. The exact method yields acceptable optimality gaps in 20 min and the heuristic runs in less than 2min, finding optimal or near-optimal solutions for small instances. Finally, we explore the trade-off between depot and fleet costs, and routing costs to make recommendations on the optimal number of depots. Our solution approach was entered into the 12th AIMMS-MOPTA Optimization Modeling Competition and was awarded the first prize.

Uncontrolled Keywords

• branch-and-cut
• fleet sizing
• heuristics
• multiple depots
• multiple trips
• subtour elimination constraints
• time windows
• vehicle routing