[Zurück]

P. Gebhard:
"The vehicle routing problem with compartments";
Betreuer/in(nen): G. Raidl, S. Pirkwieser; Institut für Computergraphik und Algorithmen, 2012; Abschlussprüfung: 10/2012.

Das Vehicle Routing Problem with Compartments (VRPC) beschreibt ein generalisiertes
Routingproblem mit einer homogenen Flotte an Fahrzeugen mit mehreren Abteilungen, die
Bestellungen von Kunden kostenminimal ausliefern sollen.Weiteres gibt es unterschiedliche
Produkttypen, die entweder nur in gewisse Abteilungen oder nicht mit anderen Produkttypen
ins gleiche Abteil geladen werden dürfen. Diese Arbeit behandelt zwei leicht unterschiedliche
Problemdefinitionen die auf Anforderungen aus der Öl- und Nahrungsmittelindustrie
eingehen. Die Fahrzeuge, die zum Transport unterschiedlicher Kraftstoffe von einer Raffinerie
zu den einzelnen Tankstellen eingesetzt werden, haben typischerweise mehrere Abteilungen
mit einer fixen Größe. Die verschiedenen Kraftstoffe dürfen in beliebige Abteile
geladen, aber nicht miteinander vermischt werden. Fahrzeuge, die für den Transport von
Nahrungsmitteln eingesetzt werden, haben oft mehrere Abteilungen, die durch eine verstellbare
Trennwand, variabel in ihrer Größe sind. Eine optimale Lösung für Routingprobleme ist
meist nur mit großem Aufwand zu finden, da das zugehörige Entschiedungsproblem zu den
sogenannten NP-schweren Problemen gehört.
In dieser Arbeit werden zwei heuristische Algorithmen vorgestellt: ein randomisierter Clarke
and Wright Savings Algorithmus und eine auf Schwarmintelligenz beruhende Verbesserungsheuristik.
Des Weiteren wird ein exakter Branch and Price Ansatz präsentiert, der
mittels Spaltengenerierung das Problem in unabhängige Teilprobleme aufteilt und löst. Das
verschachtelte Packproblem wird einerseits heuristisch mit Konstruktionsalgorithmen und
andererseits mit einem Constraint Programming Modell gelöst. Die Effektivität der Modelle
und Algorithmen wurden auf drei verschiedenen Testdatensätzen evaluiert. Das exakte
Verfahren kann, wie auch bei verwandten generalisierten Routingproblemen, nur auf relativ
kleinen Probleminstanzen angewendet werden, während die heuristischen Ansätze in der
Lage sind alle gegebenen Probleminstanzen relativ gut zu lösen.

The Vehicle Routing Problem with Compartments (VRPC) deals with solving a generalized
vehicle routing problem with a homogeneous fleet of vehicles having multiple compartments
as well as additional constraints on the commodities loaded in each compartment: i.e. incompatibilities
between different products in one compartment and between products and
compartments. Two slightly different problem formulations, which where inspired by the
petrol and food delivery industries, are considered in this work. The vehicles delivering different
petrol types, are typically divided into several compartments with a fixed size where
different petrol types are not allowed to be loaded into the same compartment as they would
agitate. The vehicles in the food distribution industry consist of different compartments with
flexible core walls where the products must be loaded into a certain, pre-defined compartment.
Routing problems are typically hard to solve as the corresponding decision problems
often are members of the so called NP-hard problems.
This work presents two heuristic algorithms to solve the VRPC, which are a randomized
Clarke and Wright Savings construction algorithm and an improvement algorithm based on
swarm intelligence. Further an exact branch and price approach using column generation
is presented, which divides the problem into several independent subproblems that can be
solved individually. The cascaded binpacking like problem is solved using a heuristic algorithm
and a constraint programming model. The performance of the algorithms is evaluated
on three different sets of test instances. The exact approach for the VRPC, like other exact
approaches for similar routing problems, is able to solve instances to optimality with a very
limited size. In contrast the heuristic approaches where able to solve any instance within a
reasonably small gap compared to other algorithms.

http://publik.tuwien.ac.at/files/PubDat_213000.pdf