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

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.

Researchers at NYU Tandon, including Joseph Chow, professor of civil and urban engineering and Deputy Director of the C2SMART Tier 1 University Transportation Center, have designed innovative solutions. In a paper in Elsevier’s Transportation Research, they present a mechanism for accepting and rejecting user requests in a Demand Responsive Transportation (DRT) context based on the representative utilities of alternative transportation modes. They consider utility-maximizing users and propose a mixed-integer programming formulation for a Chance Constrained DARP (CC-DARP), that captures users’ preferences.

They further introduce class-based user groups and consider various pricing structures for DRT services, and developed a local search based heuristic and a matheuristic to solve the proposed CC-DARP. The study includes numerical results for both DARP benchmarking instances and a realistic case study based on New York City yellow taxi trip data. They found, with computational experiments performed on 105 benchmarking instances with up to 96 nodes yielded average profit gaps of 2.59% and 0.17% using the proposed local search heuristic and matheuristic, respectively.

The based on the case study suggest that a zonal fare structure is the best strategy in terms of optimizing revenue and ridership. Their CC-DARP formulation provides a new decision-support tool to inform on revenue and fleet management for DRT systems on a strategic planning level.