IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v121y2019icp114-134.html
   My bibliography  Save this article

A Markov decision process approach to vacant taxi routing with e-hailing

Author

Listed:
  • Yu, Xinlian
  • Gao, Song
  • Hu, Xianbiao
  • Park, Hyoshin

Abstract

The optimal routing of a vacant taxi is formulated as a Markov Decision Process (MDP) problem to account for long-term profit over the full working period. The state is defined by the node at which a vacant taxi is located, and action is the link to take out of the node. State transition probabilities depend on passenger matching probabilities and passenger destination probabilities. The probability that a vacant taxi is matched with a passenger during the traversal of a link is calculated based on temporal Poisson arrivals of passengers and spatial Poisson distributions of competing vacant taxis. Passenger destination probabilities are calculated directly using observed fractions of passengers going to destinations from a given origin. The MDP problem is solved by value iteration resulting in an optimal routing policy, and the computational efficiency is improved by utilizing parallelized matrix operations.

Suggested Citation

  • Yu, Xinlian & Gao, Song & Hu, Xianbiao & Park, Hyoshin, 2019. "A Markov decision process approach to vacant taxi routing with e-hailing," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 114-134.
    • Handle: RePEc:eee:transb:v:121:y:2019:i:c:p:114-134
    DOI: 10.1016/j.trb.2018.12.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261518303837
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2018.12.013?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yang, Lin & Kwan, Mei-Po & Pan, Xiaofang & Wan, Bo & Zhou, Shunping, 2017. "Scalable space-time trajectory cube for path-finding: A study using big taxi trajectory data," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 1-27.
    2. Yang, Hai & Yang, Teng, 2011. "Equilibrium properties of taxi markets with search frictions," Transportation Research Part B: Methodological, Elsevier, vol. 45(4), pages 696-713, May.
    3. Yang, Hai & Leung, Cowina W.Y. & Wong, S.C. & Bell, Michael G.H., 2010. "Equilibria of bilateral taxi-customer searching and meeting on networks," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1067-1083, September.
    4. Long, Jiancheng & Szeto, W.Y. & Du, Jie & Wong, R.C.P., 2017. "A dynamic taxi traffic assignment model: A two-level continuum transportation system approach," Transportation Research Part B: Methodological, Elsevier, vol. 100(C), pages 222-254.
    5. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    6. Xie, Jun & (Marco) Nie, Yu & Liu, Xiaobo, 2017. "Testing the proportionality condition with taxi trajectory data," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 583-601.
    7. Wai Yuen Szeto & Ryan Cheuk Pong Wong & Sze Chun Wong & Hai Yang, 2013. "A time-dependent logit-based taxi customer-search model," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 17(2), pages 184-198, July.
    8. Wong, K. I. & Wong, S. C. & Yang, Hai, 2001. "Modeling urban taxi services in congested road networks with elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 35(9), pages 819-842, November.
    9. Qian, Xinwu & Zhang, Wenbo & Ukkusuri, Satish V. & Yang, Chao, 2017. "Optimal assignment and incentive design in the taxi group ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 208-226.
    10. Allan Larsen & Oli B. G. Madsen & Marius M. Solomon, 2004. "The A Priori Dynamic Traveling Salesman Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 459-472, November.
    11. Hai Yang & Min Ye & Wilson Hon-Chung Tang & Sze Chun Wong, 2005. "A Multiperiod Dynamic Model of Taxi Services with Endogenous Service Intensity," Operations Research, INFORMS, vol. 53(3), pages 501-515, June.
    12. Ferrucci, Francesco & Bock, Stefan & Gendreau, Michel, 2013. "A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods," European Journal of Operational Research, Elsevier, vol. 225(1), pages 130-141.
    13. Hosni, Hadi & Naoum-Sawaya, Joe & Artail, Hassan, 2014. "The shared-taxi problem: Formulation and solution methods," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 303-318.
    14. Mitrovic-Minic, Snezana & Krishnamurti, Ramesh & Laporte, Gilbert, 2004. "Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(8), pages 669-685, September.
    15. Yang, Hai & Wong, S. C., 1998. "A network model of urban taxi services," Transportation Research Part B: Methodological, Elsevier, vol. 32(4), pages 235-246, May.
    16. Yang, Hai & Ye, Min & Tang, Wilson H. & Wong, S.C., 2005. "Regulating taxi services in the presence of congestion externality," Transportation Research Part A: Policy and Practice, Elsevier, vol. 39(1), pages 17-40, January.
    17. Wong, K.I. & Wong, S.C. & Yang, Hai & Wu, J.H., 2008. "Modeling urban taxi services with multiple user classes and vehicle modes," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 985-1007, December.
    18. Lee, Alan & Savelsbergh, Martin, 2015. "Dynamic ridesharing: Is there a role for dedicated drivers?," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 483-497.
    19. Masoud, Neda & Jayakrishnan, R., 2017. "A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 218-236.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Andres Fielbaum & Maximilian Kronmueller & Javier Alonso-Mora, 2022. "Anticipatory routing methods for an on-demand ridepooling mobility system," Transportation, Springer, vol. 49(6), pages 1921-1962, December.
    2. Jinchun Zhang & Shiheng Guan & Jinxiu Hou & Zichuan Zhang & Zhaoqian Li & Xiangzhong Meng & Chao Wang, 2019. "Markov Chain Simulation of Coal Ash Melting Point and Stochastic Optimization of Operation Temperature for Entrained Flow Coal Gasification," Energies, MDPI, vol. 12(22), pages 1-23, November.
    3. Zhu, Zheng & Ke, Jintao & Wang, Hai, 2021. "A mean-field Markov decision process model for spatial-temporal subsidies in ride-sourcing markets," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 540-565.
    4. Wang, Hai & Yang, Hai, 2019. "Ridesourcing systems: A framework and review," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 122-155.
    5. Yuebing Liang & Zhan Zhao & Xiaohu Zhang, 2024. "Modeling taxi cruising time based on multi-source data: a case study in Shanghai," Transportation, Springer, vol. 51(3), pages 761-790, June.
    6. Rathore, Bhawana & Sengupta, Pooja & Biswas, Baidyanath & Kumar, Ajay, 2024. "Predicting the price of taxicabs using Artificial Intelligence: A hybrid approach based on clustering and ordinal regression models," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    7. Aleksander Król & Małgorzata Król, 2019. "A Stochastic Simulation Model for the Optimization of the Taxi Management System," Sustainability, MDPI, vol. 11(14), pages 1-22, July.
    8. Wang, Jianbiao & Miwa, Tomio & Morikawa, Takayuki, 2023. "Recursive decomposition probability model for demand estimation of street-hailing taxis utilizing GPS trajectory data," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 171-195.
    9. Hashemi-Petroodi, S. Ehsan & Thevenin, Simon & Kovalev, Sergey & Dolgui, Alexandre, 2023. "Markov decision process for multi-manned mixed-model assembly lines with walking workers," International Journal of Production Economics, Elsevier, vol. 255(C).
    10. Minghong Ma & Fei Yang, 2024. "Dynamic migratory beekeeping route recommendation based on spatio-temporal distribution of nectar sources," Annals of Operations Research, Springer, vol. 341(2), pages 1075-1105, October.
    11. Beojone, Caio Vitor & Geroliminis, Nikolas, 2023. "A dynamic multi-region MFD model for ride-sourcing with ridesplitting," Transportation Research Part B: Methodological, Elsevier, vol. 177(C).
    12. Legros, Benjamin & Fransoo, Jan C., 2024. "Admission and pricing optimization of on-street parking with delivery bays," European Journal of Operational Research, Elsevier, vol. 312(1), pages 138-149.
    13. Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2022. "A Multi-Depot Dynamic Vehicle Routing Problem with Stochastic Road Capacity: An MDP Model and Dynamic Policy for Post-Decision State Rollout Algorithm in Reinforcement Learning," Mathematics, MDPI, vol. 10(15), pages 1-70, July.
    14. Zhang, Kenan & Mittal, Archak & Djavadian, Shadi & Twumasi-Boakye, Richard & Nie, Yu (Marco), 2023. "RIde-hail vehicle routing (RIVER) as a congestion game," Transportation Research Part B: Methodological, Elsevier, vol. 177(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Baicheng & Szeto, W.Y., 2019. "Taxi service area design: Formulation and analysis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 308-333.
    2. Li, Baicheng & Szeto, W.Y., 2021. "Modeling and analyzing a taxi market with a monopsony taxi owner and multiple rentee-drivers," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 1-22.
    3. Nourinejad, Mehdi & Ramezani, Mohsen, 2020. "Ride-Sourcing modeling and pricing in non-equilibrium two-sided markets," Transportation Research Part B: Methodological, Elsevier, vol. 132(C), pages 340-357.
    4. Wong, R.C.P. & Szeto, W.Y. & Wong, S.C., 2014. "Bi-level decisions of vacant taxi drivers traveling towards taxi stands in customer-search: Modeling methodology and policy implications," Transport Policy, Elsevier, vol. 33(C), pages 73-81.
    5. Wong, R.C.P. & Szeto, W.Y., 2018. "An alternative methodology for evaluating the service quality of urban taxis," Transport Policy, Elsevier, vol. 69(C), pages 132-140.
    6. Szeto, W.Y. & Wong, R.C.P. & Yang, W.H., 2019. "Guiding vacant taxi drivers to demand locations by taxi-calling signals: A sequential binary logistic regression modeling approach and policy implications," Transport Policy, Elsevier, vol. 76(C), pages 100-110.
    7. Ting Wang & Yong Zhang & Meiye Li & Lei Liu, 2019. "How Do Passengers with Different Using Frequencies Choose between Traditional Taxi Service and Online Car-Hailing Service? A Case Study of Nanjing, China," Sustainability, MDPI, vol. 11(23), pages 1-18, November.
    8. Di, Xuan & Ban, Xuegang Jeff, 2019. "A unified equilibrium framework of new shared mobility systems," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 50-78.
    9. Wong, R.C.P. & Szeto, W.Y., 2022. "The effects of peak hour and congested area taxi surcharges on customers’ travel decisions: Empirical evidence and policy implications," Transport Policy, Elsevier, vol. 121(C), pages 78-89.
    10. Fabien Leurent, 2019. "Microeconomics of a taxi service in a ring-shaped city," Working Papers hal-02047269, HAL.
    11. Wenbo Zhang & Satish V. Ukkusuri & Chao Yang, 2018. "Modeling the Taxi Drivers’ Customer-Searching Behaviors outside Downtown Areas," Sustainability, MDPI, vol. 10(9), pages 1-23, August.
    12. Yang, Hai & Yang, Teng, 2011. "Equilibrium properties of taxi markets with search frictions," Transportation Research Part B: Methodological, Elsevier, vol. 45(4), pages 696-713, May.
    13. Chen, Xiqun (Michael) & Zheng, Hongyu & Ke, Jintao & Yang, Hai, 2020. "Dynamic optimization strategies for on-demand ride services platform: Surge pricing, commission rate, and incentives," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 23-45.
    14. Ke, Jintao & Yang, Hai & Zheng, Zhengfei, 2020. "On ride-pooling and traffic congestion," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 213-231.
    15. Sathaye, Nakul, 2014. "The optimal design and cost implications of electric vehicle taxi systems," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 264-283.
    16. Thorsten Heilker & Gernot Sieg, 2017. "A duopoly of transportation network companies and traditional radio-taxi dispatch service agencies," Working Papers 24, Institute of Transport Economics, University of Muenster.
    17. Wang, Hai & Yang, Hai, 2019. "Ridesourcing systems: A framework and review," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 122-155.
    18. Wong, K.I. & Wong, S.C. & Yang, Hai & Wu, J.H., 2008. "Modeling urban taxi services with multiple user classes and vehicle modes," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 985-1007, December.
    19. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    20. Yang, Hai & Leung, Cowina W.Y. & Wong, S.C. & Bell, Michael G.H., 2010. "Equilibria of bilateral taxi-customer searching and meeting on networks," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1067-1083, September.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:121:y:2019:i:c:p:114-134. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.