An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services

Michael Wilbur, Salah Uddin Kadir, Youngseo Kim, Geoffrey Pettet, Ayan Mukhopadhyay, Philip Pugliese, Samitha Samaranayake, Aron Laszka, Abhishek Dubey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Many transit agencies operating paratransit and microtransit ser-vices have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to signifi-cant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse-our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.

Original languageEnglish (US)
Title of host publicationProceedings - 13th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages147-158
Number of pages12
ISBN (Electronic)9781665409674
DOIs
StatePublished - 2022
Event13th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2022 - Virtual, Online, Italy
Duration: May 4 2022May 6 2022

Publication series

NameProceedings - 13th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2022

Conference

Conference13th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2022
Country/TerritoryItaly
CityVirtual, Online
Period5/4/225/6/22

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Optimization
  • Artificial Intelligence
  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services'. Together they form a unique fingerprint.

Cite this