Exploring pareto routes in multi-criteria urban bicycle routing

Abstract

To properly account for a broad range of routechoice factors in bicycle route planning, a multi-criteria optimization framework is needed. Unfortunately, in contrast to other categories of routing problems, optimal multi-criteria search has not yet been developed for bicycle routing. In this paper, we address this gap and provide a multi-criteria formulation of the bicycle routing problem and an optimum multi-label correcting algorithm for finding a full set of Pareto routes. To reduce the potentially very large number of Pareto solutions, we introduce a route selection algorithm, based on hierarchical clustering, for extracting a small representative subset of Pareto routes. We empirically evaluate our approach on a real-world cycleway network. We explore the size and structure of the set of Pareto routes and demonstrate the capability of our method to generate a practical set of bicycle routes in realistic conditions.