Title
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.
Keywords
MetaheuristikTraveling Salesman ProblemTourenplanungkombinatorische OptimierungSimulationAnt SystemAmeisensystemVehicle Routing Problem2-opt-Verfahren
Object type
Language
German [deu]
Persistent identifier
https://phaidra.univie.ac.at/o:1181301
Appeared in
Title
Forschungsberichte des Instituts für Betriebswirtschaftslehre der Universität Wien
Volume
6
Issued
1996-11
From page
1
To page
22
Date issued
1996-11
Access rights

Download

University of Vienna | Universitätsring 1 | 1010 Vienna | T +43-1-4277-0