Title | ||
---|---|---|
Variable-Depth Search for the Single-Vehicle Pickup and Delivery Problem with Time Windows |
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. |
Year | DOI | Venue |
---|---|---|
1993 | 10.1287/trsc.27.3.298 | Transportation Science |
Field | DocType | Volume |
Simulated annealing,Mathematical optimization,Iterative method,Depth-first search,Travelling salesman problem,Schedule,Local search (optimization),Pickup,Operations management,Mathematics,Computation | Journal | 27 |
Issue | ISSN | Citations |
3 | 0041-1655 | 33 |
PageRank | References | Authors |
6.01 | 2 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
L. J. J. van der Bruggen | 1 | 33 | 6.01 |
J. K. Lenstra | 2 | 1689 | 329.39 |
P. C. Schuur | 3 | 87 | 14.40 |