home/Research Interests/Dial-a-Ride Problem

Dial-a-Ride Problem and Demand Responsive Transport

Demand responsive transport (DRT) refers to an advanced public transport mode, where vehicles (e.g., mini-vans) are routed according to customers' trip request without any predefined schedules. The corresponding dynamic optimization problem is known as the dial-a-ride problem:
  • Trip requests (s,d,n) arrive dynamically, where (s,d) denote the pickup and delivery locations and n the number of passengers
  • Operator has a fleet of m vehicles with capacity of c seats per vehicle
  • For each trip request:
    1. Assign the trip request to some vehicle
    2. Update the corresponding vehicle's route appropriately by including also the new trip
  • Typical objectives include i) the (mean) travel time and ii) the total distance the vehicles drive
  • Extensions include various constraints such as the time-windows for pickup and delivery
Challenges:
  • Static problem, allocate a given set of trips to m vehicles, is already a NP-hard combinatorial problem
  • In dynamic problem, the dispatching and routing policy should also take into account the anticipated [1]
    1. future trip requests
    2. traffic conditions
    3. human errors
  • Can be tackled within the MDP framework, but the huge state-space defies the straightforward approach
  • Greedy heuristics (e.g., first-fit) neglect the future, which can lead to very poor performance [3]
    dial-a-ride problem
Figure: A single vehicle in a dial-a-ride problem.

Our publications

[1]  E. Hyytiä, A. Penttinen and R. Sulonen Non-Myopic Vehicle and Route Selection in Dynamic DARP with Travel Time and Workload Objectives, Computers & Operations Research, Elsevier, vol. 39, no. 12, pp. 3021-3030, December 2012. (pdf)
[2] E. Hyytiä, S. Aalto, A. Penttinen and R. Sulonen, A stochastic model for a vehicle in a dial-a-ride system, Operations Research Letters, vol. 38, no. 5, pp. 432-435, Elsevier, 2010. (pdf)
[3] E. Hyytiä, A. Penttinen and R. Sulonen, Congestive Collapse and Its Avoidance in a Dynamic Dial-a-Ride System with Time Windows, in Analytical and Stochastic Modeling Techniques and Applications, pp. 397-408, Springer Berlin, LNCS 6148, 2010, Cardiff, Wales, United Kingdom. (pdf)
[4]  E. Hyytiä, L. Häme, A. Penttinen and R. Sulonen, Simulation of a large scale dynamic pickup and delivery problem, in SIMUTools'10, 2010, Malaga, Spain. (pdf)
[5] J. Jokinen, T. Sihvola, E. Hyytiä and R. Sulonen, Why Urban Mass Demand Responsive Transport?, in IEEE Forum on Integrated and Sustainable Transportation Systems (FISTS), pp. 317-322, 2011, Vienna, Austria. (pdf)
[6] E. Hyytiä, A. Penttinen and R. Sulonen, Congestive Collapse Avoidance in a Dynamic Dial-a-Ride System, WIPO Patent Application, WO/2011/154613, 2011, Espoo, Finland.

Some other references:

  1. Paolo Toth and Daniele Vigo, The Vehicle Routing Problem, SIAM, 2001.
  2. H.N. Psaraftis, Dynamic Vehicle Routing Problems, in Vehicle Routing: Methods and Studies, pp. 223-248, B.L. Golden and A.A. Assad eds., North Holland, 1988.
  3. Jean-François Cordeau and Gilbert Laporte, The dial-a-ride problem: models and algorithms, Annals of Operations Research, vol. 153, no. 1, pp. 29-46, Springer, September 2007.
  4. G. Berbeglia and J.-F. Cordeau and G. Laporte, Dynamic Pickup and Delivery Problems, European Journal of Operational Research, vol. 202, no.1, pp. 8-15, Elsevier, April 2010.