Parallel savings based heuristics for the delivery problem

The delivery problem consists of finding a set of routes for a fleet of capacitated vehicles to satisfy the cargo delivery requirements of customers. The vehicles are located in a central depot, and have to fulfill the delivery requirements in a sequence that minimizes total delivery costs. Each vehicle tour starts and terminates at the central depot, and each node is supplied by exactly one vehicle. All vehicles have the same cargo carrying capacity. The paper presents parallel savings algorithms (PSAs) for generating feasible solutions to this problem. The new algorithms combine the savings approach, with matching based procedures. In computational tests the heuristic produces better solutions than the best known solutions for six problems out of a standard set of 14 difficult test problems. Augmented Lagrangian based lower bounding procedures are developed, and used to evaluate the quality of the solutions generated by PSAs. The lower bounds generated by the augmented Lagrangian are the tightest bounds known for delivery problems. The performance of the PSAs is also compared to tour partitioning based heuristics which have better worst case error bounds. The average quality of solutions generated by PSAs is shown to be significantly superior on large sets of test problems.