Der Artikel ist der erste Teil einer umfassenden Überblicksarbeit in zwei Teilen über Pickup- und Delivery-Probleme. Grundsätzlich können zwei Problemklassen unterschieden werden. Die erste Problemklasse, mit der sich dieser Artikel befasst, beinhaltet all jene Probleme, die Auslieferungen von einem Depot zu Auslieferungs-Kunden (linehaul customers) und Abholungen von Rückladungs- Kunden (backhaul customers) zu einem Depot behandeln. Diese Problemklasse wird im Folgenden als VRPB (Vehicle Routing Problems with Backhauls) bezeichnet. Vier verschiedene Problemtypen können weiters unterschieden werden: das VRCP (Vehicle Routing Problem with Clustered Backhauls), alle Auslieferungen müssen vor den Abholungen durchgeführt werden, das VRPMB (Vehicle Routing Problem with Mixed linehauls and Backhauls), gemischte Ausliefer- und Abholsequenzen sind gestattet, das VRPDDP (Vehicle Routing Problem with Divisible Delivery and Pickup), Kunden, die Ausliefer- und Abholservice verlangen, können zweimal besucht werden, und das VRPSDP (Vehicle Routing Problem with Simultaneous Delivery and Pickup), Kunden, die beide Services verlangen, können nur genau einmal angefahren werden. Die zweite Pickup- und Delivery-Problemklasse wird in Teil II dieser Arbeit behandelt. Sie beinhaltet all jene Problemtypen, die sich mit Transporten zwischen Abhol- und Auslieferungsorten befassen: das PDVRP (Pickup and Deliver Vehicle Routing Problem), ungepaarte Abhol- und Auslieferungsorte, das klassische PDP (Pickup and Delivery Problem), gepaarte Abhol- und Auslieferangsorte, und das DARP (Dial-A-Ride Problem), Personentransport zwischen gepaarten Abhol- und Ablieferungsorten unter Berücksichtigung von serviceorientierten Kriterien. Die jeweiligen Problemtypen werden zuerst anhand von mathematischen Einfahrzeug- und Mehrfahrzeugproblemformulierungen definiert. Im Anschluss werden die in der Literatur beschriebenen Lösungsmethoden diskutiert.
This paper is the first part of a comprehensive survey on pickup and delivery problems. Basically, two problem classes can be distinguished. The first class, discussed in this paper, deals with the transportation of goods from the depot to linehaul customers and from backhaul customers to the depot. This class is denoted as VRPB (vehicle routing problems with backhauls). Four subtypes can be considered, namely the VRPCB (vehicle routing problem with clustered backhauls), all linehauls before backhauls, the VRPMB (vehicle routing problem with mixed linehauls and backhauls), any sequence of linehauls and backhauls permitted, the VRPDDP (vehicle routing problem with divisible delivery and pickup), customers demanding delivery and pickup service can be visited twice, and the VRPSDP (vehicle routing problem with simultaneous delivery and pickup), customers demanding both services have to be visited exactly once. The second class, dealt with in the second part of this survey, refers to all those problems where goods are transported between pickup and delivery locations. These are the PDVRP (pickup and delivery vehicle routing problem), unpaired pickup and delivery points, the classical PDP (pickup and delivery problem), paired pickup and delivery points, and the DARP (dial-a-ride problem), passenger transportation between paired pickup and delivery points and user inconvenience taken into consideration. Single as well as multi vehicle versions of the mathematical problem formulations are given for all four VRPB types, the corresponding exact, heuristic, and metaheuristic solution methods are discussed.
A survey on pickup and delivery problems. Part I: Transporation between customers and depot
Journal für Betriebswirtschaft ; 58 , 1 ; 21-51
2008
31 Seiten, 1 Bild, 8 Tabellen, 109 Quellen
Article (Journal)
English