Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An Experimental Study on Exact Multi-constraint Shortest Path Finding

  • Conference paper
  • First Online:
Databases Theory and Applications (ADC 2021)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 12610))

Included in the following conference series:

Abstract

Given a directed graph with each edge has a weight and several criteria, a multi-constraint shortest path query (CSP) asks for the shortest path that satisfies the constraints on these criteria. It is a general routing problem and can be used to customise user’s routing requirements. However, only the single-constraint version has been well studied while the multi-constraint version is ignored due to its complexity. In this paper, we explore the multi-CSP problem by extending three existing single-CSP algorithms (Skyline-Dijkstra, sKSP, and eKSP) and experimentally study their performance and behaviours. Experiment results provides insights of how the query distance, constraint ratio, criteria number, strictness, and correlation influence the query performance.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 64.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 84.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    It was called MinSum-MinSum problem as the term skyline was not used in the 1980s.

  2. 2.

    http://users.diag.uniroma1.it/challenge9/download.shtml.

References

  1. Li, L., Hua, W., Du, X., Zhou, X.: Minimal on-road time route scheduling on time-dependent graphs. PVLDB 10(11), 1274–1285 (2017)

    Google Scholar 

  2. Li, L., Zheng, K., Wang, S., Hua, W., Zhou, X.: Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory. VLDB J. 27(3), 321–345 (2018)

    Google Scholar 

  3. Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries. In: SIGMOD, pp. 467–47 (2003)

    Google Scholar 

  4. Kriegel, H.-P., Renz, M., Schubert, M.: Route skyline queries: a multi-preference path planning approach. In: ICDE 2010, pp. 261–272. IEEE (2010)

    Google Scholar 

  5. Gong, Q., Cao, H., Nagarkar, P.: Skyline queries constrained by multi-cost transportation networks. In: ICDE, pp. 926–937. IEEE (2019)

    Google Scholar 

  6. Ouyang, D., Yuan, L., Zhang, F., Qin, L., Lin, X.: Towards efficient path skyline computation in bicriteria networks. In: Pei, J., Manolopoulos, Y., Sadiq, S., Li, J. (eds.) DASFAA 2018. LNCS, vol. 10827, pp. 239–254. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91452-7_16

    Chapter  Google Scholar 

  7. Hansen, P.: Bicriterion path problems. In: Multiple Criteria Decision Making Theory and Application, pp. 109–127. Springer (1980). https://doi.org/10.1007/978-3-642-48782-8_9

  8. Gao, J., Qiu, H., Jiang, X., Wang, T., Yang, D.: Fast top-k simple shortest paths discovery in graphs. In: CIKM, pp. 509–518 (2010)

    Google Scholar 

  9. Sedeño-Noda, A., Alonso-Rodríguez, S.: An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem. Appl. Math. Comput. 265, 602-618 (2015)

    Google Scholar 

  10. Kriegel, H.-P., Kröger, P., Kunath, P., Renz, M., Schmidt, T.: Proximity queries in large traffic networks. In: ACM GIS, pp. 1–8 (2007)

    Google Scholar 

  11. Joksch, H.C.: The shortest route problem with constraints. J. Math. Anal. Appl. 14(2), 191–197 (1966)

    Article  MathSciNet  Google Scholar 

  12. Handler, G.Y., Zang, I.: A dual algorithm for the constrained shortest path problem. Networks 10(4), 293–309 (1980)

    Article  MathSciNet  Google Scholar 

  13. Lozano, L., Medaglia, A.L.: On an exact method for the constrained shortest path problem. Comput. Oper. Res. 40(1), 378–384 (2013)

    Article  Google Scholar 

  14. Zhang, M., Li, L., Hua, W., Zhou, X.: Efficient 2-hop labeling maintenance in dynamic small-world networks. In: ICDE. IEEE (2021)

    Google Scholar 

  15. Li, L., Wang, S., Zhou, X.: Fastest path query answering using time-dependent hop-labeling in road network. In: TKDE (2020)

    Google Scholar 

  16. Li, L., Zhang, M., Hua, W., Zhou, X.: Fast query decomposition for batch shortest path processing in road networks. In: ICDE (2020)

    Google Scholar 

  17. Zhang, M., Li, L., Hua, W., Zhou, X.: Stream processing of shortest path query in dynamic road networks. In: TKDE (2020)

    Google Scholar 

  18. Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319–333. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68552-4_24

    Chapter  Google Scholar 

  19. Storandt, S.: Route planning for bicycles–exact constrained shortest paths made practical via contraction hierarchy. In: ICAPS (2012)

    Google Scholar 

  20. Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28(5), 213–219 (2001)

    Article  MathSciNet  Google Scholar 

  21. Juttner, A., Szviatovski, B., Mécs, I., Rajkó, Z.: Lagrange relaxation based method for the QoS routing problem. In: INFOCOM, vol. 2, pp. 859–868. IEEE (2001)

    Google Scholar 

  22. Kuipers, F., Orda, A., Raz, D., Van Mieghem, P.: A comparison of exact and \(\varepsilon \) -approximation algorithms for constrained routing. In: Boavida, F., Plagemann, T., Stiller, B., Westphal, C., Monteiro, E. (eds.) NETWORKING 2006. LNCS, vol. 3976, pp. 197–208. Springer, Heidelberg (2006). https://doi.org/10.1007/11753810_17

    Chapter  Google Scholar 

  23. Tsaggouris, G., Zaroliagis, C.: Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications. Theory Comput. Syst. 45(1), 162–186 (2009). https://doi.org/10.1007/s00224-007-9096-4

    Article  MathSciNet  MATH  Google Scholar 

  24. Wang, S., Xiao, X., Yang, Y., Lin, W.: Effective indexing for approximate constrained shortest path queries on large road networks. PVLDB 10(2), 61–72 (2016)

    Google Scholar 

  25. Li, L., Wang, S., Zhou, X.: Time-dependent hop labeling on road network. In: ICDE, pp. 902–913, April 2019

    Google Scholar 

  26. Jozefowiez, N., Semet, F., Talbi, E.-G.: Multi-objective vehicle routing problems. Eur. J. Oper. Res. 189(2), 293–309 (2008)

    Article  MathSciNet  Google Scholar 

  27. Shi, N., Zhou, S., Wang, F., Tao, Y., Liu, L.: The multi-criteria constrained shortest path problem. Transp. Res. Part E: Logist. Transp. Rev. 101, 13–29 (2017)

    Article  Google Scholar 

  28. Braekers, K., Caris, A., Janssens, G.K.: Bi-objective optimization of drayage operations in the service area of intermodal terminals. Transp. Res. Part E: Logist. Transp. Rev. 65, 50–69 (2014)

    Article  Google Scholar 

  29. Gandibleux, X., Beugnies, F., Randriamasy, S.: Martins’ algorithm revisited for multi-objective shortest path problems with a maxmin cost function. 4OR 4(1), 47–59 (2006). https://doi.org/10.1007/s10288-005-0074-x

    Article  MathSciNet  MATH  Google Scholar 

  30. Guerriero, F., Musmanno, R.: Label correcting methods to solve multicriteria shortest path problems. J. Optim. Theory Appl. 111(3), 589–613 (2001)

    Article  MathSciNet  Google Scholar 

  31. Skriver, A.J., Andersen, K.A.: A label correcting approach for solving bicriterion shortest-path problems. Comput. Oper. Res. 27(6), 507–524 (2000)

    Article  MathSciNet  Google Scholar 

  32. Yen, J.Y.: Finding the k shortest loopless paths in a network. Manage. Sci. 17(11), 712–716 (1971)

    Article  MathSciNet  Google Scholar 

  33. Meyer, U., Sanders, P.: \(\delta \)-stepping: a parallelizable shortest path algorithm. J. Algorithms 49(1), 114–152 (2003)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Queensland, Brisbane, Australia

    Xuanyi Zhang, Ziyi Liu, Mengxuan Zhang & Lei Li

Authors
  1. Xuanyi Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ziyi Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mengxuan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xuanyi Zhang .

Editor information

Editors and Affiliations

  1. University of Auckland, Auckland, New Zealand

    Miao Qiao

  2. University of Münster, Münster, Germany

    Gottfried Vossen

  3. The University of Queensland, St. Lucia, QLD, Australia

    Sen Wang

  4. University of Queensland, Brisbane, QLD, Australia

    Lei Li

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Zhang, X., Liu, Z., Zhang, M., Li, L. (2021). An Experimental Study on Exact Multi-constraint Shortest Path Finding. In: Qiao, M., Vossen, G., Wang, S., Li, L. (eds) Databases Theory and Applications. ADC 2021. Lecture Notes in Computer Science(), vol 12610. Springer, Cham. https://doi.org/10.1007/978-3-030-69377-0_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-69377-0_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-69376-3

  • Online ISBN: 978-3-030-69377-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation