Document Open Access Logo

Speedups for Multi-Criteria Urban Bicycle Routing

Authors Jan Hrncir, Pavol Zilecky, Qing Song, Michal Jakob

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2015.16.pdf
  • Filesize: 3.03 MB
  • 13 pages

Document Identifiers

Author Details

Jan Hrncir
Pavol Zilecky
Qing Song
Michal Jakob

Cite As Get BibTex

Jan Hrncir, Pavol Zilecky, Qing Song, and Michal Jakob. Speedups for Multi-Criteria Urban Bicycle Routing. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 16-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/OASIcs.ATMOS.2015.16

Abstract

Increasing the adoption of cycling is crucial for achieving more sustainable urban mobility. Navigating larger cities on a bike is, however, often challenging due to cities’ fragmented cycling infrastructure and/or complex terrain topology. Cyclists would thus benefit from intelligent route planning that would help them discover routes that best suit their transport needs and preferences. Because of the many factors cyclists consider in deciding their routes, employing multi-criteria route search is vital for properly accounting for cyclists’ route-choice criteria. Direct application of optimal multi-criteria route search algorithms is, however, not feasible due to their prohibitive computational complexity. In this paper, we therefore propose several heuristics for speeding up multi-criteria route search. We evaluate our method on a real-world cycleway network and show that speedups of up to four orders of magnitude over the standard multi-criteria label-setting algorithm are possible with a reasonable loss of solution quality. Our results make it possible to practically deploy bicycle route planners capable of producing high-quality route suggestions respecting multiple real-world route-choice criteria.

Subject Classification

Keywords
  • bicycle routing
  • multi-criteria shortest path
  • heuristic speedups

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Bast, D. Delling, A. Goldberg, M. Muller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. Werneck. Route Planning in Transportation Networks. Technical report, Microsoft Research, 2014. Google Scholar
  2. Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result Diversity for Multi-Modal Route Planning. In Daniele Frigioni and Sebastian Stiller, editors, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, volume 33 of OpenAccess Series in Informatics (OASIcs), pages 123-136, Dagstuhl, Germany, 2013. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  3. J. Broach, J. Dill, and J. Gliebe. Where do cyclists ride? A route choice model developed with revealed preference GPS data. Transportation Research Part A: Policy and Practice, 46(10):1730 - 1740, 2012. Google Scholar
  4. D. W. Corne. The good of the many outweighs the good of the one: evolutionary multi-objective optimization. IEEE Connections Newsletter, pages 9-13, 2003. Google Scholar
  5. B. C. Dean. Continuous-time dynamic shortest path algorithms. Master’s thesis, Massachusetts Institute of Technology, 1999. Google Scholar
  6. D. Delling, J. Dibbelt, T. Pajor, D. Wagner, and R. F. Werneck. Computing and Evaluating Multimodal Journeys. Technical Report 2012-20, Faculty of Informatics, Karlsruhe Institut of Technology, 2012. Google Scholar
  7. D. Delling, J. Dibbelt, T. Pajor, D. Wagner, and R. F. Werneck. Computing multimodal journeys in practice. In SEA, pages 260-271, 2013. Google Scholar
  8. D. Delling and D. Wagner. Pareto paths with sharc. In Proceedings of the 8th International Symposium on Experimental Algorithms, volume 5526 of LNCS, pages 125-136. Springer, 2009. Google Scholar
  9. D. Delling and D. Wagner. Time-dependent route planning. In Robust and Online Large-Scale Optimization, pages 207-230. Springer, 2009. Google Scholar
  10. C. Dora and M. Phillips. Transport, environment and health. WHO Regional Office for Europe, Copenhagen, 2000. Google Scholar
  11. V. Filler. (AUTO*MAT) Private communication, 2013. Why cycle route planners are important for cyclists. Google Scholar
  12. L. Han, H. Wang, and W. Mackey Jr. Finding shortest paths under time-bandwidth constraints by using elliptical minimal search area. Transportation Research Record: Journal of the Transportation Research Board, No. 1977:225-233, 2006. Google Scholar
  13. D. Herlihy. Bicycle: the history. Yale University Press, 2004. Google Scholar
  14. H. H. Hochmair and J. Fu. Web Based Bicycle Trip Planning for Broward County, Florida. In ESRI User Conference, 2009. Google Scholar
  15. J. Hrncir, Q. Song, P. Zilecky, M. Nemet, and M. Jakob. Bicycle route planning with route choice preferences. In Prestigious Applications of Artificial Intelligence (PAIS), 2014. Google Scholar
  16. P. L. Jacobsen. Safety in numbers: more walkers and bicyclists, safer walking and bicycling. Injury Prevention, 9(3):205-209, 2003. Google Scholar
  17. E. Machuca and L. Mandow. Multiobjective heuristic search in road maps. Expert Systems with Applications, 39(7):6435-6445, 2012. Google Scholar
  18. L. Mandow and J. De La Cruz. Multiobjective A* search with consistent heuristics. J. ACM, 57(5), June 2008. Google Scholar
  19. E. Martins. On a multicriteria shortest path problem. European Journal of Operational Research, 16(2):236 - 245, 1984. Google Scholar
  20. M. Muller-Hannemann and M. Schnee. Finding all attractive train connections by multi-criteria pareto search. In ATMOS, pages 246-263, 2004. Google Scholar
  21. M. Müller-Hannemann and K. Weihe. On the cardinality of the pareto set in bicriteria shortest path problems. Annals of Operations Research, 147(1):269-286, 2006. Google Scholar
  22. P. Perny and O. Spanjaard. Near admissible algorithms for multiobjective search. In Proceedings of the 2008 Conference on ECAI 2008: 18th European Conference on Artificial Intelligence, pages 490-494, Amsterdam, The Netherlands, 2008. IOS Press. Google Scholar
  23. G. Sauvanet and E. Neron. Search for the best compromise solution on multiobjective shortest path problem. Electronic Notes in Discrete Mathematics, 36:615-622, 2010. Google Scholar
  24. Q. Song, P. Zilecky, M. Jakob, and J. Hrncir. Exploring pareto routes in multi-criteria urban bicycle routing. In Intelligent Transportation Systems (ITSC), 2014 IEEE 17th International Conference on, pages 1781-1787, Oct 2014. Google Scholar
  25. B. S. Stewart and Ch. C. White. Multiobjective A*. Journal of the ACM (JACM), 38(4):775-814, 1991. Google Scholar
  26. J. G. Su, M. Winters, M. Nunes, and M. Brauer. Designing a route planner to facilitate and promote cycling in Metro Vancouver, Canada. Transportation Research Part A: Policy and Practice, 44(7):495-505, 2010. Google Scholar
  27. R. J. Turverey, D. D. Cheng, O. N. Blair, J. T. Roth, G. M. Lamp, and R. Cogill. Charlottesville bike route planner. In Systems and Information Engineering Design Symposium (SIEDS), 2010. Google Scholar
  28. M. Winters, G. Davidson, D. Kao, and K. Teschke. Motivators and deterrents of bicycling: comparing influences on decisions to ride. Transportation, 38(1):153-168, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact