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

Scalable space-time trajectory cube for path-finding: A study using big taxi trajectory data

Author

Listed:
  • Yang, Lin
  • Kwan, Mei-Po
  • Pan, Xiaofang
  • Wan, Bo
  • Zhou, Shunping

Abstract

Route planning is an important daily activity and has been intensively studied owing to their broad applications. Extracting the driving experience of taxi drivers to learn about the best routes and to support dynamic route planning can greatly help both end users and governments to ease traffic problems. Travel frequency representing the popularity of different road segments plays an important role in experience-based path-finding models and route computation. However, global frequency used in previous studies does not take into account the dynamic space-time characteristics of origins and destinations and the detailed travel frequency in different directions on the same road segment. This paper presents the space-time trajectory cube as a framework for dividing and organizing the trajectory space in terms of three dimensions (origin, destination, and time). After that, space-time trajectory cube computation and origin-destination constrained experience extraction methods are proposed to extract the fine-grained experience of taxi drivers based on a dataset of real taxi trajectories. Finally, space-time constrained graph was generated by merging drivers’ experience with the road network to compute optimal routes. The framework and methods were implemented using a taxi trajectory dataset from Shenzhen, China. The results show that the proposed methods effectively extracted the driving experience of the taxi drivers and the entailed trade-off between route length and travel time for routes with high trajectory coverage. They also indicate that road segment global frequency is not appropriate for representing driving experience in route planning models. These results are important for future research on route planning or path finding methods and their applications in navigation systems.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:transb:v:101:y:2017:i:c:p:1-27
    DOI: 10.1016/j.trb.2017.03.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261516305410
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.trb.2017.03.010?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. Srinivasan, Karthik K. & Prakash, A.A. & Seshadri, Ravi, 2014. "Finding most reliable paths on networks with correlated and shifted log–normal travel times," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 110-128.
    2. Khani, Alireza & Boyles, Stephen D., 2015. "An exact algorithm for the mean–standard deviation shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 252-266.
    3. Jenelius, Erik & Koutsopoulos, Haris N., 2013. "Travel time estimation for urban road networks using low frequency probe vehicle data," Transportation Research Part B: Methodological, Elsevier, vol. 53(C), pages 64-81.
    4. Chen, Peng & Nie, Yu (Marco), 2013. "Bicriterion shortest path problem with a general nonadditive cost," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 419-435.
    5. Liu, Siyuan & Qu, Qiang, 2016. "Dynamic collective routing using crowdsourcing data," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 450-469.
    6. Yang, Lixing & Zhou, Xuesong, 2014. "Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 22-44.
    7. Zhang, Yuli & Shen, Zuo-Jun Max & Song, Shiji, 2016. "Parametric search for the bi-attribute concave shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 150-168.
    8. Bates, John & Polak, John & Jones, Peter & Cook, Andrew, 0. "The valuation of reliability for personal travel," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 37(2-3), pages 191-229, April.
    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. Liu, Shan & Jiang, Hai, 2022. "Personalized route recommendation for ride-hailing with deep inverse reinforcement learning and real-time traffic conditions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    2. Xiaofang Pan & Mei-Po Kwan & Lin Yang & Shunping Zhou & Zejun Zuo & Bo Wan, 2018. "Evaluating the Accessibility of Healthcare Facilities Using an Integrated Catchment Area Approach," IJERPH, MDPI, vol. 15(9), pages 1-21, September.
    3. Liu, Shan & Jiang, Hai & Chen, Shuiping & Ye, Jing & He, Renqing & Sun, Zhizhao, 2020. "Integrating Dijkstra’s algorithm into deep inverse reinforcement learning for food delivery route planning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    4. Zhang Sen & Zhang Ke & Liu Xiaoyang & Zeng Jian & Liu Yan & Zhao Lian, 2022. "Characterisation of elderly daily travel behaviour in Tianjin using a space–time cube," Environment and Planning B, , vol. 49(2), pages 603-618, February.
    5. 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.
    6. Shuxin Jin & Juan Su & Zhouhao Wu & Di Wang & Ming Cai, 2022. "What Makes a Good Cabman? Behavioral Patterns Correlated with High-Earning and Low-Earning Taxi Driving," Sustainability, MDPI, vol. 14(22), pages 1-16, November.
    7. 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.
    8. Park, Chung & Lee, Jungpyo & Sohn, So Young, 2019. "Recommendation of feeder bus routes using neural network embedding-based optimization," Transportation Research Part A: Policy and Practice, Elsevier, vol. 126(C), pages 329-341.
    9. Li, Xijing & Ma, Xinlin & Wilson, Bev, 2021. "Beyond absolute space: An exploration of relative and relational space in Shanghai using taxi trajectory data," Journal of Transport Geography, Elsevier, vol. 93(C).
    10. Jinlei Zhang & Feng Chen & Zijia Wang & Rui Wang & Shunwei Shi, 2018. "Spatiotemporal Patterns of Carbon Emissions and Taxi Travel Using GPS Data in Beijing," Energies, MDPI, vol. 11(3), pages 1-22, February.
    11. Yang, Lin & Zhang, Fayong & Kwan, Mei-Po & Wang, Ke & Zuo, Zejun & Xia, Shaotian & Zhang, Zhiyong & Zhao, Xinpei, 2020. "Space-time demand cube for spatial-temporal coverage optimization model of shared bicycle system: A study using big bike GPS data," Journal of Transport Geography, Elsevier, vol. 88(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. A. Arun Prakash & Karthik K. Srinivasan, 2017. "Finding the Most Reliable Strategy on Stochastic and Time-Dependent Transportation Networks: A Hypergraph Based Formulation," Networks and Spatial Economics, Springer, vol. 17(3), pages 809-840, September.
    2. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    3. Khani, Alireza & Boyles, Stephen D., 2015. "An exact algorithm for the mean–standard deviation shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 252-266.
    4. Shen, Liang & Shao, Hu & Wu, Ting & Fainman, Emily Zhu & Lam, William H.K., 2020. "Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    5. Chen, Bi Yu & Li, Qingquan & Lam, William H.K., 2016. "Finding the k reliable shortest paths under travel time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 189-203.
    6. Zhang, Yuli & Max Shen, Zuo-Jun & Song, Shiji, 2017. "Lagrangian relaxation for the reliable shortest path problem with correlated link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 501-521.
    7. Chen, Bi Yu & Chen, Xiao-Wei & Chen, Hui-Ping & Lam, William H.K., 2020. "Efficient algorithm for finding k shortest paths based on re-optimization technique," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    8. Liang Shen & Feiran Wang & Yueyuan Chen & Xinyi Lv & Zongliang Wen, 2022. "A Reliability-Based Stochastic Traffic Assignment Model for Signalized Traffic Network with Consideration of Link Travel Time Correlations," Sustainability, MDPI, vol. 14(21), pages 1-18, November.
    9. Prakash, A. Arun, 2018. "Pruning algorithm for the least expected travel time path on stochastic and time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 127-147.
    10. Prakash, A. Arun & Seshadri, Ravi & Srinivasan, Karthik K., 2018. "A consistent reliability-based user-equilibrium problem with risk-averse users and endogenous travel time correlations: Formulation and solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 171-198.
    11. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    12. A. Arun Prakash & Karthik K. Srinivasan, 2018. "Pruning Algorithms to Determine Reliable Paths on Networks with Random and Correlated Link Travel Times," Transportation Science, INFORMS, vol. 52(1), pages 80-101, January.
    13. Zhang, Yuli & Shen, Zuo-Jun Max & Song, Shiji, 2016. "Parametric search for the bi-attribute concave shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 150-168.
    14. Zhang, Yufeng & Khani, Alireza, 2019. "An algorithm for reliable shortest path problem with travel time correlations," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 92-113.
    15. Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
    16. Bergström, Anna & Krüger, Niclas A., 2013. "Modeling passenger train delay distributions: evidence and implications," Working papers in Transport Economics 2013:3, CTS - Centre for Transport Studies Stockholm (KTH and VTI).
    17. Peer, Stefanie & Knockaert, Jasper & Koster, Paul & Tseng, Yin-Yen & Verhoef, Erik T., 2013. "Door-to-door travel times in RP departure time choice models: An approximation method using GPS data," Transportation Research Part B: Methodological, Elsevier, vol. 58(C), pages 134-150.
    18. Bhat, Chandra R. & Sardesai, Rupali, 2006. "The impact of stop-making and travel time reliability on commute mode choice," Transportation Research Part B: Methodological, Elsevier, vol. 40(9), pages 709-730, November.
    19. Li, Baibing, 2019. "Measuring travel time reliability and risk: A nonparametric approach," Transportation Research Part B: Methodological, Elsevier, vol. 130(C), pages 152-171.
    20. Chica-Olmo, Jorge & Gachs-Sánchez, Héctor & Lizarraga, Carmen, 2018. "Route effect on the perception of public transport services quality," Transport Policy, Elsevier, vol. 67(C), pages 40-48.

    More about this item

    Keywords

    Path-finding; Road network; Taxi trajectory; Space-time constraint; Driver's experience; Navigation system;
    All these keywords.

    JEL classification:

    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • R41 - Urban, Rural, Regional, Real Estate, and Transportation Economics - - Transportation Economics - - - Transportation: Demand, Supply, and Congestion; Travel Time; Safety and Accidents; Transportation Noise
    • R42 - Urban, Rural, Regional, Real Estate, and Transportation Economics - - Transportation Economics - - - Government and Private Investment Analysis; Road Maintenance; Transportation Planning

    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:101:y:2017:i:c:p:1-27. 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.