Top

Published in:

2011 | OriginalPaper | Chapter

Autonomous Units for Solving the Traveling Salesperson Problem Based on Ant Colony Optimization

Authors : Sabine Kuske, Melanie Luderer, Hauke Tönnies

Published in: Dynamics in Logistics

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Communities of autonomous units are rule-based and graph-transformational systems with a well-defined formal semantics. The autonomous units of a community act and interact in a common environment while striving for their goals. Ant colony systems consist of a set of autonomously behaving ants and are often employed as a metaheuristics for NP-hard logistic problems. In this paper, we demonstrate how communities of autonomous units can be used as a formal graph-transformational framework for modeling ant colony systems. As a first example we model an ant colony system for the Traveling Salesperson Problem as a community of autonomous units.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Design Aspects of Cognitive Logistic Systems

next chapter Dynamic Management of Adaptor Threads for Supporting Scalable RFID Middleware

Corradini, A., Ehrig, H., Heckel, R., Löwe, M., Montanari, U., and Rossi, F. (1997). Algebraic approaches to graph transformation part I: Basic concepts and double pushout approach. In: G. Rozenberg (ed), Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1: Foundations. World Scientific, Singapore, pp. 163–245.

Dorigo, M., and Stützle, T. (2004). Ant Colony Optimization. MIT-Press.

Ermel, C., Rudolf, M., and Taentzer, G. (1999). The AGG-approach: Language and environment. In: H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg (eds) Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 2: Applications, Languages and Tools. World Scientific, Singapore, pp. 551–603.

Eyckelhof, C.J., and Snoek, M. (2002). Ant systems for a dynamic TSP - Ants caught in a traffic jam. In M. Dorigo, G. Di Caro, and M. Sampels (eds), Ant Algorithms - Third International Workshop, ANTS 2002, Volume 2462 of Lecture Notes in Computer Science, pp. 88–98.

Geiß, R., and Kroll, M. (2008). GrGen.NET: A fast, expressive, and general purpose graph rewrite tool. In A. Schürr, M. Nagl, and A. Zündorf (eds), Proc. 3rd Intl. Workshop on Applications of Graph Transformation with Industrial Relevance (AGTIVE ‘07), Volume 5088 of Lecture Notes in Computer Science, pp. 568–569.

Habel, A., Heckel, R., and Taentzer, G. (1996). Graph grammars with negative application conditions. Fundamenta Informaticae 26(34):287–313.

Hölscher, K. (2008). Autonomous Units as a Rule-based Concept for the Modeling of Autonomous and Cooperating Processes. Logos Verlag. PhD thesis.

Hölscher, K., Klempien-Hinrichs, R., Knirsch, P., Kreowski, H.-J., and Kuske, S. (2007). Autonomous units: Basic concepts and semantic foundation. In M. Hülsmann, and K. Windt (eds) Understanding Autonomous Cooperation and Control in Logistics. The Impact on Management, Information and Communication and Material Flow. Springer, Berlin Heidelberg New York, USA.

Hölscher, K., Knirsch, P., and Luderer, M. (2008). Autonomous units for communication-based dynamic scheduling. In H.-D. Haasis, H.-J. Kreowski, and B. Scholz-Reiter, Dynamics in Logistics, Proceedings of the First International Conference on Dynamics in Logistics (LDIC 2007) (pp. 331–339). Springer.

Hölscher, K., Kreowski, H.-J., and Kuske, S. (2009). Autonomous Units to Model Interacting Sequential and Parallel Processes. Fundamenta Informaticae, 92(3):233–257.

Kreowski, H.-J., and Kuske, S. (2008). Communities of autonomous units for pickup and delivery vehicle routing. In A. Schürr, M. Nagl, and A. Zündorf (eds), Proc. 3rd Intl. Workshop on Applications of Graph Transformation with Industrial Relevance (AGTIVE ‘07), Volume 5088 of Lecture Notes in Computer Science, pp. 281–296.

Montemanni, R., Gambardella, L., Rizzoli, A., and Donati, A. (2005). Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization 10(4):327–343.

Reimann, M., Doerner, K., and Hartl, R. F. (2004). D-Ants: Savings based ants divide and conquer the vehicle routing problem. Computers and Operations Research 31(4):563–591.

Rizzoli, A., Montemanni, R., Lucibello, E., and Gambardella, L. (2007). Ant colony optimization for real-world vehicle routing problems. Swarm Intelligence 1(2):135–151.

Rozenberg, G. (1997). Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1: Foundations. World Scientific, Singapore.

Title: Autonomous Units for Solving the Traveling Salesperson Problem Based on Ant Colony Optimization
Authors: Sabine Kuske
Melanie Luderer
Hauke Tönnies
Publisher: Springer Berlin Heidelberg
Book: Dynamics in Logistics
Print ISBN: 978-3-642-11995-8

Electronic ISBN: 978-3-642-11996-5

Copyright Year: 2011
DOI: https://doi.org/10.1007/978-3-642-11996-5_26