01698250

Component

In this study, an optimal taxi routing problem is investigated for a single taxi that accounts for multiple cycles of pick-up and drop-off into the future to improve the utilization of taxis. The optimal taxi routing problem is formulated as a Markov Decision Process (MDP) with finite state and action spaces.Two approaches are proposed to solve the problem. One is the model-based approach where a model of the state transitions of the environment is obtained from queuing-theory based passenger arrival and competing taxi distribution processes. The other is the model-free learning approach, which learns action values (and from that, the best policy) directly from observed trajectory data. This method is model-free, in that no transition models are needed and the system dynamics are embedded in the observed trajectories. Both approaches are implemented and tested in a large-scale network, and results show that both policies from the two proposed approaches perform better than random walk despite not having any priori knowledge. Model-based method is more effective when the model perfectly matches the true dynamics but struggle on building accurate models for complex tasks, while model-free method are less efficient but could achieve good asymptotic performance especially where the true dynamics cannot be modeled accurately.

This paper was sponsored by TRB committee ADB30 Standing Committee on Transportation Network Modeling.

19-03142

English

7p

2019

Transportation Research Board 98th Annual Meeting

Digital/other

References

Markov processes; Optimization; Queuing theory; Routing; Taxicabs

Empty vehicles

Highways; Operations and Traffic Management; Planning and Forecasting; Public Transportation

Transportation Research Board Annual Meeting 2019 Paper #19-03142

TRIS, TRB, ATRI

Dec 7 2018 9:50AM