Nachbarschaftssucheverfahren für dynamische Pickup- und Delivery-Probleme

Krypczyk, Veikko GND

Im Fokus der Arbeit steht die Entwicklung eines Lösungsverfahrens für das Pickup- and Delivery Problem mit Zeitfenstern und sukzessiven Auftragseingang. Die Tourenplanung ist ein Teilgebiet der Logistik, speziell der Distributionslogistik. Tourenplanungsprobleme sind dadurch gekennzeichnet, dass eine größere Zahl von Transportaufträgen durch eine vorgegebene Anzahl an Transportfahrzeugen zu bedienen ist. Angestrebt wird dabei oft eine Minimierung der entstehenden Transportkosten, wobei Restriktionen (zum Beispiel Zeitfenstergrenzen an den Kundenstandorten) zu beachten sind. Erwerbswirtschaftliche Unternehmen verfolgen im Regelfall das Ziel der Gewinnmaximierung. Die Tourenplanung unterstützt als operatives Planungsinstrument unmittelbar dieses Ziel, in dem es zur Minimierung entstehender Kosten beiträgt. Zunehmend ist ein Bedarf an Lösungsverfahren für dynamische Tourenplanungsprobleme auszumachen. Diese zeichnen sich dadurch aus, auch während der laufenden Planausführung Änderungen in den Planungsdaten, zum Beispiel zusätzliche Aufträge, zu berücksichtigen. Auch die Zahl der Aufträge nimmt zu. Beiden Anforderungen wird das entwickelte Lösungsverfahren gerecht. Erstellt wurde ein allgemeingültiges Strukturkonzept für die Analyse bestehender bzw. die Entwicklung neuer Lösungsverfahren für dynamische Tourenplanungsprobleme. Orientiert an diesen Strukturkonzept konnte ein Verfahren zur Lösung des dynamischen Pickup- and Delivery-Problems erstellt werden. Kernelemente sind eine schnell arbeitende Einfügeheursitik sowie ein angepasstes Nachbarschaftssucheverfahren. Dieses wird durch eine Simulated Annealing-Metaheuristik gesteuert. Dabei wird im besonderen Maße auf die existierende Unsicherheitssituation des dynamischen Tourenplanungsproblems eingegangen, in dem mögliche künftig eintreffende Transportaufträge bereits im Vorfeld ihres Eintreffens antizipiert werden. Das Lösungsverfahren wurde innerhalb einer entwickelten Test- und Simulationsumgebung zur Anwendung gebracht. Im Rahmen der Evaluierung konnte die Leistungsfähigkeit des entwickelten Verfahrens gezeigt werden. Dynamische Pickup- und Delivery Probleme mit bis zu 500 Aufträgen können auf einem herkömmlichen Personalcomputer berechnet werden. Dazu wurde eine Reihe von Testinstanzen erzeugt, welche die o.g. Problemstellung simulieren. Die numerischen Ergebnisse konnten überzeugen, d.h. existierende Lösungswerte anderer Autoren konnten verbessert werden. Das vorgestellte Strukturkonzept hat sich bewährt und bietet Ansatzpunkte für Modifikationen und Erweiterungen des Verfahrens. Einzelne Komponenten können ausgetauscht bzw. modifiziert werden, ohne eine Anpassung das gesamte Lösungsverfahren vorzunehmen. Die vorliegende Arbeit leistet damit auch einen Beitrag für künftige Forschungs- und Entwicklungstätigkeiten

The core point of the present work is devoted to the solution methods of a dynamic pickup- and delivery problem with time windows. The route planning is a part of logistics, namely distribution logistics. The problems are marked by a greater number of orders. A typical goal is to minimize the costs of transportation. The route planning is an operative planning instrument which helps to minimize the variable costs. Increasingly stands a need for solution of dynamic vehicle routing problems. In dynamic vehicle routing problem information can be chanced during the planning period. A general structure conception was elaborated in this work. With this structure conception existing solutions methods can be analysed and it helps to develop new solutions for dynamic vehicle routing problems. The solution which is developed in this thesis is also oriented on the structure conception. The core elements are fast insertion heuristic and special neighbourhood search. It is coordinated by a simulated annealing metaheuristic. The efficiency of the developed solution method can be displayed within the evaluation. Dynamic pickup- and delivery problems with about 500 orders can be calculated with the help of usual PC. The numerical value of the results convince, means that the existing solution values can be still improved. The above considered structure conception has proved itself and can serve as a starting point for the future modifications and method broadening. Some of the components can undergo changes and modifications, without matching of the whole solution method. The present thesis serves as a contribution for the future research and development occupation.

Vorschau

Zitieren

Zitierform:

Krypczyk, Veikko: Nachbarschaftssucheverfahren für dynamische Pickup- und Delivery-Probleme. Hagen 2010. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe