The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement

•A new variant of the Multiple Depot Vehicle Routing Problem is described.•We develop a heuristic that generates high-quality solutions to benchmark and new instances.•Our heuristic could be used by managers in applications such as newspaper delivery and disaster relief routing.

The min–max Split Delivery Multi-Depot Vehicle Routing Problem with Minimum Service Time Requirement (min–max SDMDVRP-MSTR) is a variant of the Multi-Depot Vehicle Routing Problem. Each customer requires a specified amount of service time. The service time can be split among vehicles as long as each vehicle spends a minimum amount of service time at a customer. The objective is to minimize the duration of the longest route (where duration is the sum of travel and service times).We develop a heuristic (denoted by MDS) that solves the min–max SDMDVRP-MSTR in three stages: (1) initialize a feasible solution without splits; (2) improve the longest routes by splitting service times; (3) ensure all minimum service time requirements are satisfied. The first stage of MDS is compared to an existing heuristic to solve the min–max Multi-Depot Vehicle Routing Problem on 43 benchmark instances. MDS produces 37 best-known solutions. We also demonstrate the effectiveness of MDS on 21 new instances whose (near) optimal solutions can be estimated based on geometry. Finally, we investigate the savings from split service and the split patterns as we vary the required service times, the average number of customers per route, and the minimum service time requirement.