Tourenplanung mit dem Ant System

Bernd Bullnheimer, Christine Strauß

Veröffentlichungen: Working Paper

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“ 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.
OriginalspracheDeutsch
ErscheinungsortWien
HerausgeberUniversität Wien
Seitenumfang23
PublikationsstatusVeröffentlicht - Nov. 1996

Publikationsreihe

ReiheForschungsberichte des Instituts für Betriebswirtschaftslehre der Universität Wien
Band6

ÖFOS 2012

  • 502017 Logistik
  • 502052 Betriebswirtschaftslehre
  • 101015 Operations Research

Zitationsweisen