A chance-constrained dial-a-ride problem with utility-maximising demand and multiple pricing structures

Xiaotong Dong, Joseph Y.J. Chow, S. Travis Waller, David Rey

Research output: Contribution to journalArticlepeer-review


The classic Dial-A-Ride Problem (DARP) aims at designing the minimum-cost routing that accommodates a set of user requests under constraints at an operations planning level, where users’ preferences and revenue management are often overlooked. In this paper, we present a mechanism for accepting/rejecting user requests in a Demand Responsive Transportation (DRT) context based on the representative utilities of alternative transportation modes. We consider utility-maximising users and propose a mixed-integer programming formulation for a Chance Constrained DARP (CC-DARP), that captures users’ preferences via a Logit model. We further introduce class-based user groups and consider various pricing structures for DRT services. A customised local search based heuristic and a matheuristic are developed to solve the proposed CC-DARP. We report numerical results for both DARP benchmarking instances and a realistic case study based on New York City yellow taxi trip data. Computational experiments performed on 105 benchmarking instances with up to 96 nodes yield average profit gaps of 2.59% and 0.17% using the proposed local search heuristic and matheuristic, respectively. The results obtained on the realistic case study reveal that a zonal fare structure is the best strategy in terms of optimising revenue and ridership. The proposed CC-DARP formulation provides a new decision-support tool to inform on revenue and fleet management for DRT systems on a strategic planning level.

Original languageEnglish (US)
Article number102601
JournalTransportation Research Part E: Logistics and Transportation Review
StatePublished - Feb 2022


  • Chance constraint
  • Demand-responsive transportation
  • Dial-a-ride problem
  • Local search
  • Matheuristic
  • Mixed-integer programming

ASJC Scopus subject areas

  • Business and International Management
  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A chance-constrained dial-a-ride problem with utility-maximising demand and multiple pricing structures'. Together they form a unique fingerprint.

Cite this