Waiting or Moving? A Crossroad Network-Based Markov Decision Process Approach to Catch Vacant Taxis

Rong, Huigui; Zhang, Xudong; Li, Zhuo; Ai, Zhaoyang · 2020 · Crossref

DOI: 10.1109/access.2020.2965171

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of recommending optimal waiting locations for passengers seeking to catch vacant taxis, particularly in unfamiliar urban areas where random waiting often leads to long delays and poor user experiences. While existing research typically recommends a single static location, this approach fails to account for scenarios where no taxi arrives within a reasonable timeframe. To resolve this, the authors propose a Crossroad Network-based Markov Decision Process (CN-MDP) scheme that recommends a dynamic sequence of waiting locations. The method shifts focus from road segments to crossroads, leveraging the observation that crossroads connected to multiple road segments offer higher probabilities of encountering vacant taxis. Additionally, the model incorporates a multi-passenger competition strategy by dynamically updating the "pass rate" of vacant taxis to reflect real-time availability. The study utilizes large-scale GPS trajectory data from over 1,400 taxis in Changsha, China, collected over a 24-hour period. The authors processed this data using map-matching algorithms to align taxi locations with a network of 821 major urban roads and 1,633 crossroads. The core methodology models the passenger’s decision-making process as a Markov Decision Process (MDP), where states represent waiting locations, actions represent moving to adjacent crossroads, and rewards are defined by the probability of catching a taxi. The authors employ a Non-Homogeneous Poisson Process (NHPP) to simulate the arrival of vacant taxis and calculate the expected waiting time at each location. The algorithm recommends a sequence of crossroads that maximizes the cumulative probability of catching a taxi, subject to practical constraints. These constraints include a distance threshold of 750 meters (based on road segment lengths) and a time threshold derived from historical waiting time distributions and average walking speeds. Experimental evaluations on the real-world dataset demonstrate that the CN-MDP scheme significantly outperforms previous single-location recommendation methods and the authors' earlier road-segment-based approach. The proposed method achieves a higher probability of successfully catching a vacant taxi by guiding passengers through a sequence of high-probability crossroads rather than a single static spot. The inclusion of the multi-passenger competition mechanism further refines recommendations by adjusting pass rates based on concurrent demand. The results indicate that the scheme effectively balances the trade-off between walking distance and waiting time, providing a robust solution for improving taxi-hailing efficiency. The significance of this work lies in its practical application to urban mobility and user experience enhancement. By moving beyond static recommendations to a dynamic, sequential approach, the CN-MDP model offers a more reliable strategy for passengers, reducing uncertainty and wait times. The integration of crossroad networks and competitive dynamics provides a more realistic simulation of urban taxi flows. This approach contributes to the field of intelligent transportation systems by demonstrating how historical trajectory data and probabilistic modeling can be combined to optimize real-time decision-making for public transportation users.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• gap acceptance