The Vehicle Routing Problem with Compartments : exact and metaheuristic approaches

Abstract

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.<br />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.<br />

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.<br />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.<br />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.