Restricted Dynamic Programming for the Dial-a-Ride Problem

Aktivität: Vortrag ohne Tagungsband / VorlesungPräsentation auf einer wissenschaftlichen Konferenz / Workshop


In the dial-a-ride problem (DARP), a number of transportation requests between given pickup and delivery locations have to be completed under user inconvenience considerations by a speci ed eet of vehicles. This problem arises for example in the context of patient transportation where patients are delivered to medical facilities or carried back home. Since there exist many variants of this problem depending on the speci c application there is no generic problem formulation [6]. Information on considered problem variants and existing solution methods can be found in Parragh et al. [5]. In contrast to our previous publication [7] where we considered the problem de nition as well as the benchmark data set introduced by Cordeau and Laporte [1] we adapt our restricted dynamic programming approach to real-world problem instances from Arbeiter Samariterbund (ASB) Vienna. In [7] we presented a restricted dynamic programming (DP) algorithm, based on an exact DP approach, for the DARP variant as de ned in [1]. In the restricted DP algorithm, not all possible paths are considered, but rather a promising subset, selected using a criterion function. With this approach, good solutions can be found for all instances of the benchmark data set in short computational time. To tackle the real-world problem instances from the ASB several constraints had to be adjusted and modi ed, a new objective function had to be de ned as well as a new criterion function for selecting a promising subset. With this approach we are able to generate a good starting solution for the static requests of the ASB.
Zeitraum2 Dez. 20113 Dez. 2011
EreignistitelYAMS 2nd Workshop on Young Academics' Management Science

Research Field

  • Ehemaliges Research Field - Mobility Systems