A chance-constrained dial-a-ride problem with utility-maximising demand and multiple pricing structures. (February 2022)

• Record Type: Journal Article
• Authors: Dong, Xiaotong; Chow, Joseph Y.J.; Waller, S. Travis; Rey, David
• Is Part Of: Transportation research. Volume 158(2022)
• Publication Date: 2022-02
• Subjects: Dial-a-ride problem -- Demand-responsive transportation -- Chance constraint -- Mixed-integer programming -- Local search -- Matheuristic; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2021.102601
• Languages: English
• ISSNs: 1366-5545

Abstract

Abstract: 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. Highlights: Develop a revenue management approach for DARPs that captures users' preferences. MILP formulations for chance-constrained, class-based DARP with pricing structures. Customised local search heuristics and a matheuristic are proposed. Numerical results are reported on DARP instances and a NYC case study. Results reveal that zonal pricing is best at revenue and ridership optimisation.