Generating constrained length personalized bicycle tours

P. Stroobant (), P. Audenaert (), D. Colle () and M. Pickavet ()
Additional contact information
P. Stroobant: Ghent University, imec, IDLab, iGent Tower
P. Audenaert: Ghent University, imec, IDLab, iGent Tower
D. Colle: Ghent University, imec, IDLab, iGent Tower
M. Pickavet: Ghent University, imec, IDLab, iGent Tower

4OR, 2018, vol. 16, issue 4, No 4, 439 pages

Abstract: 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.

Keywords: Constrained bicycle routing; Branch-and-bound algorithm; Reach-based routing; Primary 05C38; Secondary 68R10; 94C15 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-018-0371-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:16:y:2018:i:4:d:10.1007_s10288-018-0371-9

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-018-0371-9

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().