License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2015.16
URN: urn:nbn:de:0030-drops-54584
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5458/
Go to the corresponding OASIcs Volume Portal

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

Speedups for Multi-Criteria Urban Bicycle Routing

pdf-format:
9.pdf (3 MB)

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.

BibTeX - Entry

@InProceedings{hrncir_et_al:OASIcs:2015:5458,
  author =	{Jan Hrncir and Pavol Zilecky and Qing Song and Michal Jakob},
  title =	{{Speedups for Multi-Criteria Urban Bicycle Routing}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{16--28},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5458},
  URN =		{urn:nbn:de:0030-drops-54584},
  doi =		{10.4230/OASIcs.ATMOS.2015.16},
  annote =	{Keywords: bicycle routing, multi-criteria shortest path, heuristic speedups}
}

Keywords: bicycle routing, multi-criteria shortest path, heuristic speedups
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI