The Dynamic Vehicle Routing Problem | Allan Larsen
| | Abstract | During recent years distribution systems have become increasingly complex. This development is partly due to the high number of company mergers which leave distribution planners with ever bigger and complex problems. Another fact complicating distribution is the increased focus on timeliness in the distribution chains, as intelligent planning offers potential savings in capital bindings in costs related to stock and distribution. In other words time has become an extremely valuable resource. Nowadays most distribution systems must operate under strict temporal restrictions. This fact has caused an increasing interest in dynamic transportation models and systems in which data are considered to be time-dependent.
In this thesis the dynamic counterpart of the conventional vehicle routing problem will be studied. The traditional vehicle routing problem (VRP) consists of constructing minimum cost routes for the vehicles to follow so that the set of customers are visited exactly once. The VRP is an important subproblem in a wide range of distribution systems and a lot of effort has been devoted to research on various aspects of the VRP. However, the vast part of this research has been dealing with static environments, which in this sense means that the problem data are assumed to be static and not subject to change during the planning horizon. The increased focus on just-in-time logistics has together with the rapid development within telecommunications and computer hardware implied that the study of the far more complex dynamic versions of the VRP has received increasing interest from the scientic community as well as from the potential users of these methods.
The thesis begins by introducing the dynamic vehicle routing problem and discusses the
differences between static and dynamic VRPs as well as provides some examples of real-life examples of DVRP. The existing literature dealing with the dynamic vehicle routing problem and related problems is reviewed in order to provide an overview of the richness of problems that have been investigated within this field.
The concept of measuring the dynamism within a dynamic vehicle routing problem is investigated and a framework for classifying dynamic routing applications according to their level of dynamism is proposed.
The Dynamic Traveling Repairman Problem (DTRP) proposed by Bertsimas and Van Ryzin is
extended to embrace advance request customers as well as immediate request customers.
Empirical analysis shows that the performance of the resulting problem has a linear relationship with the level of dynamism of the problem instances in question.
Next, the capacitated vehicle routing problem in the presence of time windows (DVRPTW) is examined under varying levels of dynamism. The performance of two simple batching strategies is examined in relation to the performance of a pure re-optimization strategy.
The A-priori Dynamic Traveling Salesman Problem with Time Windows (ADTSPTW) is introduced as an extension of the dynamic version of the well-known TSPTW. The extension consists in that a-priori information on future requests is included into the model.
Furthermore, a real-life instance of the dynamic vehicle routing problem originating from the pick-ups and deliveries of long-distance courier mail is examined using the algorithm proposed to solve the ADTSPTW.
Finally, the thesis discusses the present state of various DVRP methodologies and a number of different ideas for further research in this area are provided. The thesis concludes that more research on measures for the level of dynamism in a dynamic vehicle routing context is needed in order to provide more descriptive measures. Furthermore, the thesis concludes that using a-priori information in order to be able to reposition the vehicles expecting to receive new requests does not seem to offer significant performance improvements with respect to the lateness experienced by the customers. | | Keywords | Vehicle routing, dynamic vehicle routing | | Type | Ph.D. thesis [Academic thesis] | | Year | 2000 | | Publisher | Department of Mathematical Modelling, The Technical University of Denmark | | Address | Building 321, DTU, DK-2800 Kgs. Lyngby | | IMM no. | IMM-PHD-73 | | Electronic version(s) | [pdf] [ps] | | BibTeX data | [bibtex] | | IMM Group(s) | Operations Research |
|