Vehicle-Routing Probleme. Eine Heuristik für die Lieferplanung von Paketdiensten

Studienarbeit aus dem Jahr 2015 im Fachbereich BWL - Beschaffung, Produktion, Logistik, Note: 1,0, Technische Universität Dresden (Institut für Wirtschaft und Verkehr), Sprache: Deutsch, Abstract: Paketlieferdienste sehen sich bei der Auslieferung von Paketen zum Endkunden dem Problem einer kostenminimalen Routenplanung gegenübergestellt. Die Auslieferung ist ein Problem der Tourenplanung, dessen Ziel die Bestimmung eines kostenminimalen Routennetzes ist, bei der eine gegebene Anzahl an Kunden mit bekannten Bedarfen bedient wird.

Stenger et al. (2013) beschreiben in ihrer Arbeit eine Erweiterung des Tourenplanungsproblems, das sich besser auf die realen Begebenheiten bei großen Paketdienstleistern bezieht. Dabei werden mehrere Depots betrachtet und darüber hinaus ein wichtiger Trend in der Auslieferung von Paketen einbezogen: Outsourcing von unprofitablen Kunden an Subunternehmen. Sie nennen dieses Problem ein Multi Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC). Die Bedienung der Kundenbedarfe erfolgt durch die Nutzung eigener Fahrzeug und Fahrzeuge der Subunternehmer, die an entsprechenden Depots stationiert sind. Es gilt somit zu entscheiden, ob ein Kunde an den Subunternehmer abgegeben oder einem eigenen Depot zugeordnet wird. Ferner müssen für die eigenen Depots entsprechende Auslieferungsrouten unter Berücksichtigung der Zeit- und Kapazitätsrestriktionen bestimmt werden. Ziel ist es, eine kostenminimale Zuordnung vorzunehmen.

Diese Arbeit stellt den Anspruch, eine Zusammenfassung des von Stenger et al. (2013) vorgestellten Lösungsalgorithmus für das oben definierte Problem zu geben. Dabei sollen das Prinzip und die Wirkungsweise der Problemlösung durch die Adaptive Variable Nachbarschaftssuche (AVNS) vorgestellt und durch eigene Beispiele verdeutlicht werden. Dazu gliedert sich das zweite Kapitel in die einzelnen Vorgehensschritte des Lösungsalgorithmus. Im dritten Kapitel werden eine Zusammenfassung sowie ein Fazit gegeben.