Tourenplanung mit dem Ant System

Autor(en)

Bernd Bullnheimer, Christine Strauß

Abstrakt

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“ zusammengefasst werden. Das Tourenplanungsproblem ist ein solches komplexes Problem der kombinatorischen Optimierung, zu dessen Lösung sowohl problembezogene Methoden als auch general purpose Verfahren eingesetzt werden.

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 Travelling Salesman Problem (TSP) verdeutlicht. Danach wird die Adaption des Verfahrens erst für das nur mengenmäßig beschränkte, dann auch für das 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 einem 2-opt-Verfahren die Qualität der Ergebnisse erheblich zu steigern. Die Eignung des Verfahrens zur Lösung von Tourenplanungsproblemen wird dabei anhand von unterschiedlich strukturierter Aufgabenstellungen aus der Literatur (gleichverteiltes 50-Städte-Problem und geclustertes 100 -Städte-Problem) verdeutlicht.

Organisation(en)

Institut für Rechnungswesen, Innovation und Strategie

Anzahl der Seiten

23

Publikationsdatum

11-1996

ÖFOS 2012

502017 Logistik, 502052 Betriebswirtschaftslehre, 101015 Operations Research

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/5eadaf1b-6603-4ff0-b261-f649071055f9