Parallel Savings Based Heuristics for the Delivery Problem

Kemal Altinkemer and Bezalel Gavish
Additional contact information
Kemal Altinkemer: Purdue University, West Lafayette, Indiana
Bezalel Gavish: Vanderbilt University, Nashville, Tennessee

Operations Research, 1991, vol. 39, issue 3, 456-469

Abstract: 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.

Keywords: integer programming: Lagrangian relaxation for delivery problems; vehicle routing: heuristics for vehicle routing (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.3.456 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:3:p:456-469

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().