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

Determining structural route components from GPS traces

Author

Listed:
  • Knapen, Luk
  • Hartman, Irith Ben-Arroyo
  • Schulz, Daniel
  • Bellemans, Tom
  • Janssens, Davy
  • Wets, Geert

Abstract

Analysis of GPS traces shows that people often do not use the least cost path through the transportation network while making trips. This leads to the question which structural path characteristics can be used to construct realistic route choice sets for use in traffic simulation models. In this paper, we investigate the hypothesis that, for utilitarian trips, the route between origin and destination consists of a small number of concatenated least cost paths. The hypothesis is verified by analyzing routes extracted from large sets of recorded GPS traces which constitute revealed preference information. Trips have been extracted from the traces and for each trip the path in the transportation network is determined by map matching. This is followed by a path decomposition phase for which the algorithm constitutes the first contribution of this paper. There are multiple ways to split a given path in a directed graph into a minimal number of subpaths of minimal cost. By calculating two specific path splittings, it is possible to identify subsets of the vertices (splitVertexSuites) that can be used to generate every possible minimum path splitting by taking one vertex from each such subset. As a second contribution, we show how the extracted information is used in microscopic travel simulation. The distribution for the size of the minimum decomposition, extracted from the GPS traces, can be used in constrained enumeration methods for route choice set generation. The sets of vertices that can act as boundary vertices separating consecutive route parts contain way points (landmarks) having a particular meaning to their user. The paper explains the theoretical aspects of route splitting as well as the process to extract splitVertexSuites from big data. It reports statistical distributions extracted from sets of GPS traces for both multimodal person movements and unimodal car trips.

Suggested Citation

  • Knapen, Luk & Hartman, Irith Ben-Arroyo & Schulz, Daniel & Bellemans, Tom & Janssens, Davy & Wets, Geert, 2016. "Determining structural route components from GPS traces," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 156-171.
  • Handle: RePEc:eee:transb:v:90:y:2016:i:c:p:156-171
    DOI: 10.1016/j.trb.2016.04.019
    as

    Download full text from publisher

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

    File URL: https://libkey.io/10.1016/j.trb.2016.04.019?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. van der Zijpp, N.J. & Fiorenzo Catalano, S., 2005. "Path enumeration by finding the constrained K-shortest paths," Transportation Research Part B: Methodological, Elsevier, vol. 39(6), pages 545-563, July.
    2. Frejinger, E. & Bierlaire, M. & Ben-Akiva, M., 2009. "Sampling of alternatives for route choice modeling," Transportation Research Part B: Methodological, Elsevier, vol. 43(10), pages 984-994, December.
    3. Shlomo Bekhor & Moshe Ben-Akiva & M. Ramming, 2006. "Evaluation of choice set generation algorithms for route choice models," Annals of Operations Research, Springer, vol. 144(1), pages 235-247, 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. Jing-Xin Dong & Christian Hicks & Dongjun Li, 2020. "A heuristics based global navigation satellite system data reduction algorithm integrated with map-matching," Annals of Operations Research, Springer, vol. 290(1), pages 731-746, July.

    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. Evanthia Kazagli & Michel Bierlaire & Matthieu de Lapparent, 2020. "Operational route choice methodologies for practical applications," Transportation, Springer, vol. 47(1), pages 43-74, February.
    2. Kazagli, Evanthia & Bierlaire, Michel & Flötteröd, Gunnar, 2016. "Revisiting the route choice problem: A modeling framework based on mental representations," Journal of choice modelling, Elsevier, vol. 19(C), pages 1-23.
    3. Li, Dawei & Feng, Siqi & Song, Yuchen & Lai, Xinjun & Bekhor, Shlomo, 2023. "Asymmetric closed-form route choice models: Formulations and comparative applications," Transportation Research Part A: Policy and Practice, Elsevier, vol. 171(C).
    4. Hess, Stephane & Quddus, Mohammed & Rieser-Schüssler, Nadine & Daly, Andrew, 2015. "Developing advanced route choice models for heavy goods vehicles using GPS data," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 77(C), pages 29-44.
    5. Carlo Prato & Shlomo Bekhor & Cristina Pronello, 2012. "Latent variables and route choice behavior," Transportation, Springer, vol. 39(2), pages 299-319, March.
    6. Yao, Rui & Bekhor, Shlomo, 2022. "A variational autoencoder approach for choice set generation and implicit perception of alternatives in choice modeling," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 273-294.
    7. Hsueh, Chieh & Lin, Jen-Jia, 2023. "Influential factors of the route choices of scooter riders: A GPS-based data study," Journal of Transport Geography, Elsevier, vol. 113(C).
    8. Flötteröd, Gunnar & Bierlaire, Michel, 2013. "Metropolis–Hastings sampling of paths," Transportation Research Part B: Methodological, Elsevier, vol. 48(C), pages 53-66.
    9. Felipe González & Carlos Melo-Riquelme & Louis Grange, 2016. "A combined destination and route choice model for a bicycle sharing system," Transportation, Springer, vol. 43(3), pages 407-423, May.
    10. Lili Zheng & Tian Gao & Lin Meng & Tongqiang Ding & Wenhao Chen, 2024. "Research on the Route Choice Behavior of Urban Freight Vehicles Based on GPS Data," Mathematics, MDPI, vol. 12(2), pages 1-17, January.
    11. S. F. A. Batista & Ludovic Leclercq, 2019. "Regional Dynamic Traffic Assignment Framework for Macroscopic Fundamental Diagram Multi-regions Models," Transportation Science, INFORMS, vol. 53(6), pages 1563-1590, November.
    12. Dieter, Peter & Caron, Matthew & Schryen, Guido, 2023. "Integrating driver behavior into last-mile delivery routing: Combining machine learning and optimization in a hybrid decision support framework," European Journal of Operational Research, Elsevier, vol. 311(1), pages 283-300.
    13. Watling, David Paul & Rasmussen, Thomas Kjær & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2018. "Stochastic user equilibrium with a bounded choice model," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 254-280.
    14. Papola, Andrea & Tinessa, Fiore & Marzano, Vittorio, 2018. "Application of the Combination of Random Utility Models (CoRUM) to route choice," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 304-326.
    15. Rasmussen, Thomas Kjær & Watling, David Paul & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2015. "Stochastic user equilibrium with equilibrated choice sets: Part II – Solving the restricted SUE for the logit family," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 146-165.
    16. Tomhave, Benjamin J. & Khani, Alireza, 2022. "Refined choice set generation and the investigation of multi-criteria transit route choice behavior," Transportation Research Part A: Policy and Practice, Elsevier, vol. 155(C), pages 484-500.
    17. Ding-Mastera, Jing & Gao, Song & Jenelius, Erik & Rahmani, Mahmood & Ben-Akiva, Moshe, 2019. "A latent-class adaptive routing choice model in stochastic time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 124(C), pages 1-17.
    18. Selin Damla Ahipaşaoğlu & Uğur Arıkan & Karthik Natarajan, 2019. "Distributionally Robust Markovian Traffic Equilibrium," Transportation Science, INFORMS, vol. 53(6), pages 1546-1562, November.
    19. Bekhor, Shlomo & Prato, Carlo Giacomo, 2009. "Methodological transferability in route choice modeling," Transportation Research Part B: Methodological, Elsevier, vol. 43(4), pages 422-437, May.
    20. Rinaldi, Marco & Viti, Francesco, 2017. "Exact and approximate route set generation for resilient partial observability in sensor location problems," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 86-119.

    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:90:y:2016:i:c:p:156-171. 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.