Dynamic Routing of Automated Guided Vehicles in Real-time
Automated Guided Vehicles (AGVs) are state-of-the-art technology for optimizing large scale production systems and are used in a wide range of application areas. A standard task in this context is to find efficient routing schemes, i.e., algorithms that r
- PDF / 385,392 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 69 Downloads / 258 Views
Technische Universit¨ at Berlin, Institut f¨ ur Mathematik, MA 6–1, Straße des 17. Juni 136, 10623 Berlin, Germany {gawrilow,moehring,stenzel}@math.tu-berlin.de Brandenburgische Technische Universit¨ at Cottbus, Institut f¨ ur Mathematik, Postfach 10 13 44, 03013 Cottbus, Germany [email protected]
Summary. Automated Guided Vehicles (AGVs) are state-of-the-art technology for optimizing large scale production systems and are used in a wide range of application areas. A standard task in this context is to find efficient routing schemes, i.e., algorithms that route these vehicles through the particular environment. The productivity of the AGVs is highly dependent on the used routing scheme. In this work we study a particular routing algorithm for AGVs in an automated logistic system. For the evaluation of our algorithm we focus on Container Terminal Altenwerder (CTA) at Hamburg Harbor. However, our model is appropriate for an arbitrary graph. The key feature of this algorithm is that it avoids collisions, deadlocks and livelocks already at the time of route computation (conflict-free routing), whereas standard approaches deal with these problems only at the execution time of the routes. In addition, the algorithm considers physical properties of the AGVs and certain safety aspects implied by the particular application.
1 Introduction Automation of large scale logistic systems is an important method for improving productivity. Often, in such automated logistic systems Automated Guided Vehicles (AGVs) are used for transportation tasks. Especially, so called free-ranging AGVs are more and more used since they add a high flexibility to the system. The control of these AGVs is the key to an efficient transportation system that aims at maximizing its throughput. In this work we focus on the problem of routing AGVs. This means we study how to compute good routes on the one hand and how to avoid collisions on the other hand. Note that dispatching of AGVs, i.e., the assignment of transportation tasks to AGVs, is not part of the routing and therefore not considered in this paper.
166
E. Gawrilow et al.
c Fig. 1. The HHLA Container Terminal Altenwerder (CTA). HHLA
Our application is the Container Terminal Altenwerder (see Fig. 1), which is operated by our industrial partner, the Hamburger Hafen und Logistik AG (HHLA). We represent the AGV network by a particular grid-like graph that consists of roughly 10,000 arcs. and models the underlying street network of a traffic system consisting of a fleet of AGVs. The task of the AGVs is to transport containers between large container bridges for loading and unloading ships and a number of container storage areas. The AGVs navigate through the harbor area using a transponder system and the routes are sent to them from a central control unit. AGVs are symmetric, i.e., they can travel in both of the two driving directions equally well and can also change directions on a route. Previous Work First ideas for free-ranging AGV systems were introduced by Broadbent et al. [2]. Since then,
Data Loading...
