Kapazitierte Tourenplanungsprobleme bei vager Nachfrage

Modellierung und heuristische Lösungsverfahren

Tourenplanungsprobleme treten als logistische Fragestellung vielfältig auf. Sie stellen sich bei der Einsatzplanung von Fahrzeugen, wenn Transportaufträge vorliegen, die zu Touren zusammengefasst werden können. Ziel ist häufig die Festlegung der Reihenfolge, in der die Kunden aufgesucht werden, so dass die Kosten der Belieferung möglichst gering sind, gemessen an der zurückzulegenden Entfernung.

Ein wesentlicher Gesichtspunkt sind Kapazitätsbeschränkungen der Transportmittel. Diese charakterisieren die Klasse der Capacitated Vehicle Routing Probleme (CVRP). Entsprechend ihrer jeweiligen Nachfragen sind die Kunden derart zu gruppieren, dass jeweils ein Transportmittel aufgrund seiner verfügbaren Kapazität ausreicht, die entsprechenden Bedarfe dieser Kundengruppe aufzunehmen und die Kunden nacheinander anzufahren. Zu optimieren sind dann simultan die Routen- und die Tourenplanung.

Ist in der Planungssituation die Nachfrage noch nicht genau bekannt, sind dennoch a priori Routen und Tourenvorschläge so zu planen, dass sie im späteren Einsatz zu einer möglichst guten Lösung führen.

In dieser Studie wird aufgezeigt, wie die Unsicherheit der Nachfrage mittels der Fuzzy Set-Theorie in entsprechenden Optimierungsmodellen angemessen abzubilden ist und welche Anforderungen an die Zielkriterien zu stellen sind, wenn aufgrund der Unsicherheit nicht immer alle Kundenbedarfe erfüllt werden können. Diese kapazitierten Tourenplanungs­probleme bei vager Nachfrage CVRPFD (CVRP with Fuzzy Demand) werden je nach Kontext unterschiedlich behandelt.

Da bereits die deterministische Fragestellung schwierig zu lösen ist, sind für die Ermittlung guter Lösungen der neuen Modelle auch neue Algorithmen, insbesondere Heuristiken, zu entwickeln und einzusetzen. Der Autor schlägt hierzu unterschiedliche, an die verschiedenen Gegebenheiten angepasste Heuristiken vor. Deren Vorgehen begründet und illustriert er anhand eines übersichtlichen Beispiels. Die realisierte Implementierung belegt an einem erweiterten umfangreichen Datensatz die Eignung der selbstentwickelten Heuristiken, so dass die hohe Qualität der Algorithmen sichtbar wird.

 

Drawe, Michael (2010): Kapazitierte Tourenplanungsprobleme bei vager Nachfrage, Modellierung und heuristische Lösungsverfahren, Hamburg 2010, zugl. Diss. Ruhr-Universität Bochum, 2009.

 

Nützliche Links