Non-myopic vehicle and route selection in dynamic DARP with travel time and workload objectives

Esa Hyytiä*, Aleksi Penttinen, Reijo Sulonen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)


In dial-a-ride problems, a fleet of n vehicles is routed to transport people between pick-up and delivery locations. We consider an elementary version of the problem where trip requests arrive in time and require an immediate vehicle assignment (which triggers an appropriate route update of the selected vehicle). In this context, a relatively general objective can be stated as a weighted sum of the systems effort and the customers inconvenience. However, optimizing almost any objective in this immensely complex stochastic system is prohibitively difficult. Thus the earlier work has largely resorted to heuristic cost functions that arise, e.g., from the corresponding static systems. By using the framework of Markov decision processes and the classical M/M/1 queue as a highly abstract model for a single vehicle, we explain why certain intuitive cost functions indeed give satisfactory results in the dynamic system, and also give an explicit interpretation of different components appearing in a general cost function. The resulting family of heuristic control policies is demonstrated to offer a desired type of performance thus justifying the assumed analogy between a multi-queue and dial-a-ride systems.

Original languageEnglish
Pages (from-to)3021-3030
Number of pages10
JournalComputers and Operations Research
Issue number12
Publication statusPublished - Dec 2012

Bibliographical note

Funding Information:
This work was supported by the Finnish Funding Agency for Technology and Innovation, Finnish Ministry of Transport and Communications, Helsinki Metropolitan Area Council and Helsinki City Transport . The authors would also like to thank Prof. Samuli Aalto for his invaluable comments during the preparation of this article.

Other keywords

  • Dynamic DARP
  • M/M/1 queue
  • MDP
  • Vehicle routing


Dive into the research topics of 'Non-myopic vehicle and route selection in dynamic DARP with travel time and workload objectives'. Together they form a unique fingerprint.

Cite this