Variable-depth search for the single-vehicle pickup and delivery problem with time windows

L.J.J. Bruggen, van der, J.K. Lenstra, P.C. Schuur

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

66 Citaten (Scopus)
2 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)298-311
TijdschriftTransportation Science
Volume27
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 1993

Vingerafdruk

Duik in de onderzoeksthema's van 'Variable-depth search for the single-vehicle pickup and delivery problem with time windows'. Samen vormen ze een unieke vingerafdruk.

Citeer dit