Optimization methods to improve the quality of a cycling network under budget constraints

A well-designed cycling network is fundamental to stimulating bicycle use. The evaluation of the network quality is a complex process, that involves multiple criteria, such as the connectivity of cycling paths, road safety, and other factors. An ideal cycling network provides cycle paths along all roads, completely separated from car traffic, and built with high-quality materials. However, in practice, achieving this is very difficult due to budget constraints. In this paper, we propose an optimization strategy to select the best interventions to be applied to achieve the highest possible improvement in cycling network quality, as perceived by users, taking into account budget constraints. A Mixed-Integer Linear Programming (MILP) formulation and three solution methods are proposed. The first method consists of enumerating feasible solutions with respect to budget constraints, where each solution is associated with a subset of interventions. Although this method is more efficient in terms of memory usage than the commercial CPLEX solver to solve the MILP problem, its computation times increase exponentially with the number of interventions. Therefore, to improve computational time, we propose two heuristics based on the solution of knapsack problems, which are solved using dynamic programming. Although optimality cannot be guaranteed, these approximations are capable of providing high-quality solutions while being efficient in both computational time and memory usage.