nach oben

Erschienen in:

2011 | OriginalPaper | Buchkapitel

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

verfasst von : Sabine Kuske, Melanie Luderer, Hauke Tönnies

Erschienen in: Dynamics in Logistics

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Design Aspects of Cognitive Logistic Systems

Nächstes Kapitel 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.

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

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

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