16 May 2008 in Journal für Betriebswirtschaft
This paper is the second part of a comprehensive survey on routing problems involving pickups and deliveries. Basically, two problem classes can be distinguished. The first part dealt with the transportation of goods from the depot to linehaul customers and from backhaul customers to the depot. The second part now considers all those problems where goods are transported between pickup and delivery locations, denoted as Vehicle Routing Problems with Pickups and Deliveries (VRPPD). These are the Pickup and Delivery Vehicle Routing Problem (PDVRP – unpaired pickup and delivery points), the classical Pickup and Delivery Problem (PDP – paired pickup and delivery points), and the Dial-A-Ride Problem (DARP – passenger transportation between paired pickup and delivery points and user inconvenience taken into consideration). Single as well as multi vehicle mathematical problem formulations for all three VRPPD types are given, and the respective exact, heuristic, and metaheuristic solution methods are discussed. Der vorliegende Artikel ist Teil II einer umfassenden Überblicksarbeit in zwei Teilen über pickup and delivery Probleme. Grundsätzlich können zwei Problemklassen unterschieden werden. Der erste Teil dieser Arbeit beschäftigte sich mit dem Transport von Gütern von einem Depot zu Auslieferungs-Kunden (linehaul customers) und von Rückladungs-Kunden (backhaul customers) zu einem Depot. Der zweite Teil behandelt nun all jene Probleme, die sich mit dem Transport zwischen Abhol- und Auslieferungsorten befassen, im Folgenden als Vehicle Routing Problems with Pickups and Deliveries (VRPPD) bezeichnet. Diese Problemklasse umfasst das Pickup and Delivery Vehicle Routing Problem , ungepaarte Abhol- und Auslieferungsorte, das klassische Pickup and Delivery (PDP), gepaarte Abhol- und Auslierferungsorte, und das Dial-A-Ride Problem (DARP), Personentransport zwischen gepaarten Abhol- und Ablieferungsorten unter Berück- sichtigung von serviceorientierten Kriterien. Die jeweiligen Problemtypen werden zuerst anhand von mathema- tischen Einfahrzeug- und Mehrfahrzeugproblemformulierungen definiert. Im Anschluss werden die in der Literatur beschriebenen Lösungsmethoden diskutiert.
13 March 2008 in Journal für Betriebswirtschaft
1 October 2004 in Annals of Operations Research
1 April 2004 in Computers & Operations Research
1 June 2009 in European Journal of Operational Research
1 December 2010 in European Journal of Operational Research
Emergency service providers are facing the following problem: how and where to locate vehicles in order to cover potential future demand effectively. Ambulances are supposed to be located at designated locations such that in case of an emergency the patients can be reached in a time-efficient manner. A patient is said to be covered by a vehicle if (s)he can be reached by an ambulance within a predefined time limit. Due to variations in speed and the resulting travel times it is not sufficient to solve the static ambulance location problem once using fixed average travel times, as the coverage areas themselves change throughout the day. Hence we developed a multi-period version, taking into account time-varying coverage areas, where we allow vehicles to be repositioned in order to maintain a certain coverage standard throughout the planning horizon. We have formulated a mixed integer program for the problem at hand, which tries to optimize coverage at various points in time simultaneously. The problem is solved metaheuristically using variable neighborhood search. We show that it is essential to consider time-dependent variations in travel times and coverage respectively. When ignoring them the resulting objective will be overestimated by more than 24%. By taking into account these variations explicitly the solution on average can be improved by more than 10%.