The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results

In the split delivery vehicle routing problem (SDVRP), a customer's demand can be split among several vehicles. In this article, we review applications of the SDVRP including the routing of helicopters in the North Sea and solution methods such as integer programming and tabu search. We develop a new heuristic that combines a mixed integer program and a record-to-record travel algorithm. Our heuristic produces high-quality solutions to six benchmark problems that have 50-199 customers and generally performs much better than tabu search. On five other problems for which lower bounds exist, our heuristic obtains solutions within 5.85%, on average. Finally, we generate 21 new test problems that have 8-288 customers. A near-optimal solution can be visually estimated for each problem. We apply our heuristic to these new problems and report our computational results. (c) 2007 Wiley Periodicals, Inc.