Zusammenfassung

In der Literatur zu Vehicle-Routing- oder Scheduling-Problemen werden vorwiegend Modelle für spezifische Problemstellungen wie das kapazitierte VRP mit Zeitfenstern VRPTW, das Pickup-and-Delivery-Problem VRPPD oder das ressourcenbeschränkte Projektplanungsproblem RCPSP betrachtet. Bei der operativen Produktions- und Distributionsplanung in Supply Chains bestehen jedoch häufig starke Abhängigkeiten zwischen den Scheduling- und den Routing-Problemen, und es existieren typischerweise Anforderungen, die mithilfe von Grundmodellen nicht abgebildet werden können. Beispiele weiterer Anwendungsgebiete, bei denen Routing- und Scheduling-Entscheidungen gemeinsam getroffen werden sollten, sind ambulante Pflegedienste oder räumlich verteilte Projekte.

Das im Rahmen dieses Promotionsvorhabens entwickelte Ressourcentransferproblem (RTP) bietet einen generischen Modellierungsrahmen für integrierte Routing- und Scheduling-Probleme. Hierzu betrachten wir Aktivitäten, die an verschiedenen Orten in einem Netzwerk unter Einsatz von Potentialfaktoren wie Menschen, Maschinen und Fahrzeugen oder Repetierfaktoren wie Vor- und Zwischenprodukten auszuführen sind. Die Aktivitäten entsprechen beispielsweise Produktionsprozessen, Lieferungen zwischen Produktionsstandorten, Auslieferungen an Kunden, ambulanten Pflegedienstleistungen oder Vorgängen eines Projektes. Die benötigten Ressourcen können zwischen den Orten im Netzwerk transferiert werden, wobei reihenfolge- und ressourcenabhängige Transferzeiten auftreten. Im RTP-Modell wird jede Aktivität als ein Paar aus einem Start- und einem Endereignis dargestellt. Zwischen den Ereignissen sind vorgegebene zeitliche Mindest- und Höchstabstände zu beachten. Für jedes Ereignis ist neben dem Eintrittszeitpunkt auch ein Eintrittsmodus festzulegen, der die Ressourcenbedarfe sowie die Transferzeiten und Zeitabstände beeinflusst. Die Problemstellung des RTP besteht darin, den Ereignissen die jeweils allozierten bzw. freigegebenen Ressourceneinheiten zuzuordnen und sie unter Beachtung der begrenzten Verfügbarkeit der Ressourcen, der Transferzeiten und der zeitlichen Mindest- und Höchstabstände zu terminieren. Für die den Ereignissen zugeordneten Mengen an Ressourceneinheiten können bei der Modellierung Inklusions- oder Inkompatibilitätsbedingungen formuliert werden, die bei der Ressourcenallokation zu berücksichtigen sind.

Mithilfe des RTP können eine Vielzahl verschiedener Probleme aus den Bereichen der Tourenplanung, der Maschinenbelegungsplanung und der ressourcenbeschränkten Projektplanung sowie deren Kombinationen abgebildet werden. Darüber hinaus ist es möglich, zahlreiche Anforderungen praktischer Routing- und Scheduling-Probleme zu berücksichtigen. Hierzu gehören im Bereich der Tourenplanung bspw. räumliche und zeitliche Synchronisationsbedingungen, heterogene Fahrzeugflotten, gemischte Auftragstypen oder inkompatible Güterarten. Im Hinblick auf die Scheduling-Aspekte der Problemstellung können neben den zeitlichen Mindest- und Höchstabständen alternative Ausführungsmodi der Aktivitäten, reihenfolgeabhängige Umrüstzeiten der Ressourceneinheiten oder räumlich verteilte Projekte modelliert werden. Als Solver für das RTP wird ein zeitorientierter Branch-and-Bound-Algorithmus eingesetzt, bei dem die Suchräume der Knoten durch leistungsfähige Constraint-Propagation-Techniken reduziert werden.