Abstract
In the context of recreational routing, the problem of finding a route which starts and ends in the same location (while achieving a length between specified upper and lower boundaries) is a common task, especially for tourists or cyclists who want to exercise. The topic of finding a tour between a specified starting and ending location while minimizing one or multiple criteria is well covered in literature. In contrast to this, the route planning task in which a pleasant tour with length between a maximum and a minimum boundary needs to be found is relatively underexplored. In this paper, we provide a formal definition of this problem, taking into account the existing literature on which route attributes influence cyclists in their route choice. We show that the resulting problem is NP-hard and devise a branch-and-bound algorithm that is able to provide a bound on the quality of the best solution in pseudo-polynomial time. Furthermore, we also create an efficient heuristic to tackle the problem and we compare the quality of the solutions that are generated by the heuristic with the bounds provided by the branch-and-bound algorithm. Also, we thoroughly discuss the complexity and running time of the heuristic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alivand M, Hochmair HH (2015) Choice set generation for modeling scenic route choice behavior with geographic information systems. Trans Res Rec J Trans Res Board 2495:101–111. https://doi.org/10.3141/2495-11, ISSN 0361-1981
Alivand M, Hochmair H, Srinivasan S (2015) Analyzing how travelers choose scenic routes using route choice models. Comput Environ Urban Syst 50:41–52. https://doi.org/10.1016/j.compenvurbsys.2014.10.004
Bast H, Delling D, Goldberg A, Müller-Hannemann M, Thomas P, Peter S, Dorothea W, Werneck RF (2014) Route planning in transportation networks. Technical report, April 2015. http://arxiv.org/abs/1504.05140
Dees J, Geisberger R, Sanders P, Bader R (2010) Defining and computing alternative routes in road networks. CoRR, abs/1002.4, February 2010. http://arxiv.org/abs/1002.4330
Demeyer S, Audenaert P, Pickavet M, Demeester P (2014) Dynamic and stochastic routing for multimodal transportation systems. IET Intell Transp Syst 8(2):112–123. https://doi.org/10.1049/iet-its.2012.0065, ISSN 1751-956X
Fu ZJ, Hochmair H (2009) Web based bicycle trip planning for broward county, Florida. GIS Center, 31
Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Experimental algorithms, vol 5038 LNCS, pp 319–333. Springer, Berlin. https://doi.org/10.1007/978-3-540-68552-4_24, ISBN 3540685480
Gemsa A, Pajor T, Wagner D, Zündorf T (2013) Efficient computation of jogging routes. In: Lecture Notes in Computer Science, vol 7933 LNCS, pp 272–283. https://doi.org/10.1007/978-3-642-38527-8_25, ISBN 9783642385261
Gutman R (2004) Reach-based routing: a new approach to shortest path algorithms optimized for road networks. In: Proceedings 6th workshop on algorithm engineering and experiments, pp 100–111, Philadelphia, 2004. Society for Industrial and Applied Mathematics. http://www.siam.org/meetings/alenex04/abstacts/rgutman1.pdf, ISBN 0-89871-564-4
Hochmair H (2004) Decision support for bicycle route planning in urban environments. In: Proceedings of the 7th AGILE conference on geographic information science, pp 697–706. Association of Geographic Information Laboratories in Europe
Hrncir J, Nemet M, Hrncir J, Song Q, Zilecky P, Nemet M, Jakob M (2014) Bicycle route planning with route choice preferences. In: Proceedings of the twenty-first European conference on artificial intelligence, pp 1149–1154. Elsevier and Springer. https://doi.org/10.3233/978-1-61499-419-0-1149, ISBN 9781614994190
Hrncir J, Zilecky P, Song Q, Jakob M (2015) Speedups for multi-criteria urban bicycle routing. OASIcs: OpenAccess Series in Informatics 48:28. https://doi.org/10.4230/OASIcs.ATMOS.2015.16, ISSN 2190-6807. http://drops.dagstuhl.de/opus/volltexte/2015/5458/
Karp RM (1978) A characterization of the minimum cycle mean in a digraph. Discrete Math 23(3):309–311. https://doi.org/10.1016/0012-365X(78)90011-0, ISSN 0012365X. http://linkinghub.elsevier.com/retrieve/pii/0012365X78900110
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems, 1st edn. Springer, Berlin. https://doi.org/10.1007/978-3-540-24777-7, ISBN 3642073115
Lawler EL, Wood DE (1966) Branch-and-bound methods: a survey. Oper Res 14(4):699–719. https://doi.org/10.1287/opre.14.4.699, ISSN 0030-364X
Loiola EM, de Abreu NMM, Boaventura-Netto PO, Hahn P, Querido T (2007) A survey for the quadratic assignment problem. Eur J Oper Res 176(2):657–690. https://doi.org/10.1016/j.ejor.2005.09.032, ISSN 03772217
Paraskevopoulos A, Zaroliagis C (2013) Improved alternative route planning. In: 13th Workshop on algorithmic approaches for transportation modelling, optimization, and systems, vol 33, pp 108–122. Optimization and Systems, 2013. http://hal.archives-ouvertes.fr/hal-00871739/
Pucher J, Buehler R, Merom D, Bauman A (2011) Walking and cycling in the United States, 2001–2009: evidence from the national household travel surveys. Am J Public Health 101(Suppl. 1):310–317. https://doi.org/10.2105/AJPH.2010.300067, ISSN 00900036
Rostami B, Chassein A, Hopf M, Frey D, Buchheim C, Malucelli F, Goerigk M (2016) The quadratic shortest path problem: complexity, approximability, and solution methods. Technical report, 2016. http://www.optimization-online.org/DB_HTML/2016/02/5341.html
Schieferdecker D, Kobitzsch M, Radermacher M (2013) Evolution and evaluation of the penalty method for alternative graphs. In: Proceedings of the 13th workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS’13), vol 33, pp 94–107. https://doi.org/10.4230/OASIcs.ATMOS.2013.94. http://drops.dagstuhl.de/opus/volltexte/2013/4247, ISBN 9783939897583
Song Q, Zilecky P, Jakob M, Hrncir J (2014) Exploring pareto routes in multi-criteria urban bicycle routing. In: 17th international IEEE conference on intelligent transportation systems (ITSC), pp 1781. IEEE Intelligent Transportation Systems Society, 2014. https://doi.org/10.1109/ITSC.2014.6957951, ISBN 2153-0009;21530009. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6957951
Storandt S (2012) Route planning for bicycles—exact constrained shortest paths made practical via contraction hierarchy. In: Proceedings of the twenty-second international conference on automated planning and scheduling, pp 234–242, ISBN 9781577355625
Su JG, Winters M, Nunes M, Brauer M (2010) Designing a route planner to facilitate and promote cycling in Metro Vancouver, Canada. Transp Res A Policy Pract 44(7):495–505. https://doi.org/10.1016/j.tra.2010.03.015, ISSN 09658564
Turverey RJ, Cheng DD, Blair ON, Roth JT, Lamp GM (2010) Charlottesville bike route planner. In: 2010 IEEE systems and information engineering design symposium, SIEDS10, pp 68–72. https://doi.org/10.1109/SIEDS.2010.5469679
Acknowledgements
We wish to thank the reviewers for their valuable comments and their constructive input in improving our work. Pieter Stroobant is funded by a Ph.D. grant of Ghent University, Special Research Fund (BOF). The authors wish to thank Ghent University–IMEC for their support and their funding through the IOP research project “Modelling uncertainty in hub location planning through interdisciplinary research”.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Rights and permissions
About this article
Cite this article
Stroobant, P., Audenaert, P., Colle, D. et al. Generating constrained length personalized bicycle tours. 4OR-Q J Oper Res 16, 411–439 (2018). https://doi.org/10.1007/s10288-018-0371-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-018-0371-9