Variable-Depth Search for the Single-Vehicle Pickup and Delivery Problem with Time Windows

L. J. J. van der Bruggen, J. K. Lenstra and P. C. Schuur
Additional contact information
L. J. J. van der Bruggen: Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands
J. K. Lenstra: Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands
P. C. Schuur: Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands

Transportation Science, 1993, vol. 27, issue 3, 298-311

Abstract: We consider a single depot and a set of customers with known demands, each of which must be picked up and delivered at specified locations and within given time windows. We seek a route and a schedule for a single vehicle with known capacity, which minimizes the route duration, i.e., the difference between the arrival time and the departure time at the depot. We develop a local search method for this problem based on a variable-depth search, similar to the Lin-Kernighan algorithm for the traveling salesman problem. The method consists of two phases. In the first phase, a feasible route is constructed; in the second phase, it is iteratively improved. In both phases, we use a variable-depth search built up out of seven basic types of arc-exchange procedures. When tested on real-life problems, the method is shown to produce near-optimal solutions in a reasonable amount of computation time. In spite of this, there is the theoretical possibility that the method may end up with a poor or even infeasible solution. As a safeguard against such an emergency, we have developed an alternative algorithm based on simulated annealing. As a rule, it finds high quality solutions in a relatively large computation time.

Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.27.3.298 (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:ortrsc:v:27:y:1993:i:3:p:298-311

Access Statistics for this article

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