Titel
Tourenplanung mit dem Ant System
Abstract
Das Ant System ist ein neues Verfahren in der Klasse der sog. Meta- oder general purpose Heuristiken, die insbesondere für komplexe kombinatorische Optimierungsprobleme eingesetzt werden. Zu den bekanntesten dieser Verfahren gehören Simulated Annealing, Tabu Search, Neuronale Netze und verschiedene Varianten, die unter dem Begriff "Evolutionäre Algorithmen" zusammengefaßt werden. Das Tourenplanungsproblem ist ein solches komplexes Problem der kombinatorischen Optimierung, zu dessen Lösung seit vielen Jahren sowohl problembezogene Methoden als auch general purpose Verfahren wie Tabu Search, Simulated Annealing, genetische Algorithmen und Neuronale Netze Verwendung finden. Der vorliegende Beitrag zeigt die Anwendung des Ant Systems auf das mengen- und streckenmäßig beschränkte Standardtourenplanungsproblem mit einem Depot und unbeschränktem, homogenem Fuhrpark. Dabei wird eingangs die Grundidee des Ant Systems vorgestellt und am Traveling Salesman Problem (TSP) verdeutlicht. Danach wird die Adaption des Verfahrens erst für das nur mengenmäßig beschränkte, dann für das auch streckenmäßig beschränkte Vehicle Routing Problem (VRP) erläutert. Ausgehend von einer "Basisversion" des adaptierten Verfahrens werden schrittweise Verbesserungen gezeigt. So gelingt es durch die Hybridisierung des Ant Systems mit dem 2-opt-Verfahren die Qualität der Ergebnisse erheblich zu steigern. Durch Einbindung problemspezifischer Eigenschaften in den Verfahrensablauf kann das gute Lösungsverhalten weiter verbessert werden. Die Eignung des Verfahrens zur Lösung von Tourenplanungsproblemen wird dabei anhand unterschiedlich strukturierter Aufgabenstellungen (gleichverteiltes 50-Städte-Problem und geclustertes 100-Städte-Problem) aus der Literatur verdeutlicht.
Stichwort
MetaheuristikTraveling Salesman ProblemTourenplanungkombinatorische OptimierungSimulationAnt SystemAmeisensystemVehicle Routing Problem2-opt-Verfahren
Objekt-Typ
Sprache
Deutsch [deu]
Persistent identifier
https://phaidra.univie.ac.at/o:1181301
Erschienen in
Titel
Forschungsberichte des Instituts für Betriebswirtschaftslehre der Universität Wien
Band
6
Erscheinungsdatum
1996-11
Seitenanfang
1
Seitenende
22
Erscheinungsdatum
1996-11
Zugänglichkeit

Herunterladen

Universität Wien | Universitätsring 1 | 1010 Wien | T +43-1-4277-0