The Vehicle Routing Problem with Time Windows and Temporal Dependencies

Matias Sevel Rasmussen, Anders Høeg Dohn, Jesper Larsen

    Research output: Contribution to conferenceConference abstract for conferenceResearch


    The vehicle routing problem with time windows and temporal dependencies (VRPTWTD) is an extension of the vehicle routing problem with time windows (VRPTW). Given is a fixed set of customers with individual demands and with time windows specifying when each customer accepts service. The objective is to find routes for a number of vehicles, all starting and ending at a central depot in such a way that the total distance is minimized. The extension that we present here is concerned with temporal dependencies between customers. A temporal dependency which is often encountered in practical instances and that has received the most attention in the literature, is the rather strict requirement of synchronization between two visits. Synchronization on visits is also used to model rendezvous between vehicles. Other, less restrictive, dependencies are constraints on minimum overlap between visits and limits on minimum or maximum gaps between visits. There is a vast amount of literature on VRPTW and its variants. VRPTW is known to be NP-hard, nevertheless exact solution of the problem has received a lot of attention. The most successful approach is based on a Dantzig-Wolfe decomposition of the mathematical model using column generation in a branch-and-cut-and-price framework. The motivation behind this work on the VRPTWTD is its many practical applications. With the inclusion of temporal dependencies in the model, we are able to describe numerous concrete problems. Practical applications include the fleet assignment and routing problem with synchronization constraints. The problem has been solved by column generation. The synchronized vehicle dispatching problem (SVDP), which is a dynamic vehicle routing problem with synchronization between vehicles. Constraint programming and local search are applied to arrive at high-quality feasible solutions. A problem from the Port of Singapore, where technicians are allocated to service jobs has previously been studied. For each job, a certain combination of technicians with individual skills is needed. The technicians must be present at the same time, and hence the schedule for each technician must respect a number of synchronization constraints with other schedules. The problem is solved using metaheuristics. Another application with synchronization between visits is in ground handling at airports. Teams drive around at the airport and are assigned tasks on the parked aircrafts. A recent paper describes this setup and present exact solutions to the instances considered. Another work considers ground handling with synchronization constraints as well, and present computational results for a tailored heuristic applied to data instances from an in-flight caterer in Malaysia. An application of vehicle routing with synchronization constraints is done with a branch-and-price algorithm applied to a realistic home care routing problem and yields promising results. The generalization of synchronization to other temporal dependencies has been described for a few applications. A paper presents a workforce scheduling software from a practical perspective. In the problem described, both synchronization and various other sequencing constraints occur. Another application describes a problem in school bus routing. Busses must wait for each other at various intermediate stops and hence precedence relations are introduced for such stops. The problem is referred to as the vehicle routing problem with coupled time windows. A work describes an application in blood collection from satellite locations for a central blood bank. Multiple visits at each location have to be scheduled with a certain slack between them. They refer to the vehicle problem as having interdependent time windows. Temporal dependencies have been modeled for a home care routing problem in a mixed integer programming model (MIP) which was solved with a standard MIP solver. An application with general temporal dependencies is also found in machine scheduling. Column generation is used to solve the problem. The pricing problem is primarily solved heuristically by local search and occasionally to optimality using a standard solver on an integer programming formulation of the pricing problem. Two compact formulations of the problem are introduced and the Dantzig-Wolfe decompositions of these formulations are presented to allow for a column-generation-based solution approach. Temporal dependencies are modeled by generalized precedence constraints. A total of four different master problem formulations are proposed and it is shown that the formulations can be ranked according to the tightness with which they describe the solution space. A tailored time window branching is used to enforce feasibility on the relaxed master problems. The contribution of this work is the generalization of synchronization to any temporal dependency that can be described by generalized precedence constraints, as well as the inclusion of this in a branch-and-price context. We prove that the generalization is as strong as the formerly introduced model with synchronization. The use of the time-indexed model in the column generation is novel as well. Finally, we introduce a new set of context-free benchmark instances which enables a thorough quantitative analysis and which we hope will facilitate future research in this area. The analysis shows that, even though the time-indexed model has some nice properties, it also retains its major drawback, namely the number of constraints. As a consequence, a hybrid method is implemented, where only a limited number of the violated cuts are added. This approach keeps most of the nice features of the time-indexed model, while at the same time lowering the solution time to the same level as the solution time of the relaxed model. In fact the hybrid method is only slower than the relaxed model in a small number of instances. The model presented in this paper is general and is therefore applicable to various practical problems. Future work could be adaption to real world problems. Another very interesting direction for future research could be to include additional cuts. Using the time-indexed formulation, we were able to solve many instances already in the root node of the branch-and-bound tree, and this number could be increased by introducing additional cuts. The performance of the time-indexed model was clearly better than the relaxed model for the instances where the optimal solution was obtained in the root node.
    Original languageEnglish
    Publication date2009
    Publication statusPublished - 2009
    EventROUTE 2009: International Workshop on Vehicle Routing, Intermodal Transport and Related Areas - Skodsborg, Denmark
    Duration: 21 Jun 200924 Jun 2009
    Conference number: 6


    ConferenceROUTE 2009: International Workshop on Vehicle Routing, Intermodal Transport and Related Areas

    Cite this

    Rasmussen, M. S., Dohn, A. H., & Larsen, J. (2009). The Vehicle Routing Problem with Time Windows and Temporal Dependencies. Abstract from ROUTE 2009: International Workshop on Vehicle Routing, Intermodal Transport and Related Areas , Skodsborg, Denmark.