Browse:

The university is member of the Confederation of Open Access Repositories (COAR)

More information about Open Acces at open-acces.net

Neue Tabusuche-Heuristiken für die logistische Tourenplanung bei restringierendem Anhängereinsatz, mehreren Depots und Planungsperioden

URN to cite this document: urn:nbn:de:bvb:355-opus-3764

Scheuerer, Stephan (2004) Neue Tabusuche-Heuristiken für die logistische Tourenplanung bei restringierendem Anhängereinsatz, mehreren Depots und Planungsperioden. PhD, Universität Regensburg

Preview

Publishing license for publications excluding print on demand
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1774Kb

Abstract (German)

Primäres Ziel dieser Arbeit war die Entwicklung neuer heuristischer Lösungsverfahren für die logistische Tourenplanung bei restringierendem Anhängereinsatz (engl. Truck and Trailer Routing Problem). Kennzeichnend für dieses kombinatorische Optimierungsproblem ist, dass Fahrzeuge einen Anhänger mitführen, jedoch ein Teil der Kunden nur ohne Anhänger angefahren werden kann. Dies erfordert das An- und Abkoppeln von Anhängern im Verlauf einer Fahrzeugroute. Dadurch stellt sich bei der Tourenplanung zugleich die Frage nach den optimalen Anhängerstellplätzen, nach der Anzahl an An- und Abkoppelvorgängen sowie nach der optimalen Bedienreihenfolge für die Kunden unterschiedlichen Typs auf einer Fahrzeugroute.
Die Arbeit präsentiert für diese Problemstellung zwei neue Konstruktionsheuristiken sowie eine Tabusuche-Heuristik zur weiteren Lösungsverbesserung. Ein Vergleich auf bekannten Benchmarkproblemen verdeutlicht, dass die neuen Verfahren mit existierenden Algorithmen konkurrieren können. Die neue Tabusuche konnte zu allen 21 Benchmarkproblemen eine neue beste Lösung finden.
Erstmals wurden im Rahmen dieser Arbeit auch zwei Erweiterungen des Tourenplanungsproblems bei restringierendem Anhängereinsatz betrachtet. Dies ist zum einen eine Erweiterung des Problems um mehrere Fahrzeug-Depots, zum anderen die Betrachtung eines mehrtägigen Planungshorizonts. Bei letzterem ist jedem Kunden eine Menge an gewünschten Bedienmustern zugeteilt, die jeweils bestimmen, an welchen Tagen des Planungshorizonts die Bedienung des Kunden zu erfolgen hat. Diese beiden Erweiterungen fügen dem zugrunde liegenden Tourenplanungsproblem bei restringierendem Anhängereinsatz eine zusätzliche Entscheidungsstufe hinzu, indem es zusätzlich eine optimale Zuordnung der Kunden zu den Depots bzw. ein optimales Bedienmuster für jeden Kunden zu bestimmen gilt. Für jedes dieser Probleme wurde ebenfalls eine Tabusuche-Heuristik entwickelt und auf existierenden und neuen Benchmarkproblemen getestet. Für die bekannten Benchmarkprobleme der Multi-Depot und periodischen Tourenplanung konnten neue beste Lösungen gefunden werden.

Translation of the abstract (English)

Many real-life vehicle routing applications include the use of trailers. Whenever a truck and a trailer can be treated as a single vehicle, that is the trailer is never uncoupled, a normal vehicle routing problem can be solved. However, as it is the case in the truck and trailer routing problem, customers may exist that are not reachable by trailer. For this reason, the trailer has to be uncoupled and left behind at a parking place and has to be picked up again at a later point in time on the route. Besides routing, the problem therefore includes also the decision of determining the best parking place and the number of times a trailer should be uncoupled.
The purpose of this thesis is to introduce two construction heuristics for this problem and to present a tabu search heuristic for further improvement. Computational results indicate that the new heuristics are competitive to existing approaches. The tabu search algorithm obtained better solutions for each of 21 benchmark problems.
Furthermore, two extensions to the truck and trailer routing problem are examined. The first extension considers multiple depots, while the second reflects a planning horizon of several days. For the latter, every customer has assigned a set of feasible visit day combinations that each specify the days a service has to take place. Both problems ask for an additional decision through finding the best assignment from the customers to the depots, respectively through determing the best visit day combination for each customer. For each problem a new tabu search heuristic is proposed and tested on existing and new benchmark problems. New best solutions have been found for the well-known benchmark problems to multi-depot and periodic vehicle routing.

Item Type:

Thesis of the University of Regensburg (PhD)

Referee:

Helmut (Prof. Dr.) Steckhan

Date of exam:

02 April 2004

Institutions:

Business, Economics and Information Systems

Classification:

Notation	Type
68W25	MSC
90C59	MSC
90C27	MSC
90B06	MSC
90Bxx	MSC

Keywords:

Heuristik , Tabusuche , Tourenplanung , Operations Research , Metaheuristik , heuristic , metaheuristic , tabu search , vehicle routing , operations research

Subjects:

300 Social sciences > 330 Economics

Status:

Published

Refereed:

Yes, this version has been refereed

Created at the University of Regensburg:

Yes

Owner:

Universitätsbibliothek Regensburg

Deposited On:

26 Oct 2009 16:34