A distributed routing concept for vehicle routing problems
- PDF / 447,625 Bytes
- 8 Pages / 595.276 x 790.866 pts Page_size
- 22 Downloads / 186 Views
ORIGINAL PAPER
A distributed routing concept for vehicle routing problems Henning Rekersbrink Æ Thomas Makuschewitz Æ Bernd Scholz-Reiter
Received: 19 March 2008 / Accepted: 6 October 2008 / Published online: 4 November 2008 Springer-Verlag 2008
Abstract Traditional solution concepts for the vehicle routing problem (VRP) are pushed to their limits, when applied on dynamically changing vehicle routing scenarios—which are more close to reality than the static formulation. By contrast, the introduced distributed routing concept is designed to match packages and vehicles and to continuously make route decisions especially within a dynamic environment. In this autonomous control concept, each of these objects makes its own decisions. The developed algorithm was entitled Distributed Logistics Routing Protocol (DLRP). But in spite of the restricted suitability of the traditional VRP concepts for dynamic environments, they are still the benchmark for any VRPsimilar task. Therefore, we first present a description of the developed DLRP. Then an adapted vehicle routing problem is defined, which both sides, static and dynamic concepts, can cope with. Finally, both concepts are compared using a tabu search algorithm as a well working instance of traditional VRP-concepts. For a quantitative comparison, four solutions are given for the same adapted problem: the optimal solution as a lower bound, the DLRP solution, a tabu search solution and a random-like solution as an upper bound. Keywords Vehicle routing problem (VRP) Autonomous control Distributed logistics routing protocol (DLRP) Tabu search Optimisation Routing algorithm Transport logistic
H. Rekersbrink (&) T. Makuschewitz B. Scholz-Reiter BIBA an der Universita¨t Bremen, Hochschulring 20, 28359 Bremen, Germany e-mail: [email protected] URL: www.biba.uni-bremen.de
1 Introduction One opportunity to handle growing dynamics and complexity of logistics systems is to shift from central planning to decentral, autonomous control strategies. The concept of autonomous control is the research area of the German Collaborative Research Centre (CRC) 637 ‘Autonomous Cooperating Logistic Processes—A Paradigm Shift and its Limitations’. This CRC develops a new concept for dynamic transport networks, which is designed to match goods and vehicles and to continuously make route decisions within a dynamic transport environment. Here, each object makes its own decisions. It is called Distributed Logistics Routing Protocol (DLRP). In order to evaluate this new concept, we compare it to the traditional solutions for the vehicle routing problem (VRP), shown in this article. To describe the different approach of autonomous control to transport problems, the developed DLRP is described at first. In contrast to traditional algorithms for the VRP problem, which do static optimisation, this approach tries to control an ongoing dynamic transport process. Therefore the problem definitions of both sides are different in principal. One basic point is that the VRP is a static probl
Data Loading...
