A variable depth approach for the single-vehicle pickup and delivery problem with time windows

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

    Research output: Book/ReportReportAcademic

    18 Downloads (Pure)


    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 has two time windows in which the pickup and delivery must take place. 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. In this paper we present a local search method for this problem based on a variable depth approach, 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 this solution 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. Despite this practical evidence, 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.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherEindhoven University of Technology
    Number of pages21
    Publication statusPublished - Dec 1990

    Publication series

    NameCOSOR Memorandum
    PublisherCOSOR, Eindhoven University of Technology


    Dive into the research topics of 'A variable depth approach for the single-vehicle pickup and delivery problem with time windows'. Together they form a unique fingerprint.

    Cite this