EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1408. Greedy heuristic for solving real size instances of the bicycle network improvement problem

Invited abstract in session TA-18: Optimization of sustainable urban mobility, stream Sustainable Cities.

Tuesday, 8:30-10:00
Room: 42 (building: 116)

Authors (first author is the speaker)

1. Emmanuel Neron
Polytech Tours, University of Tours
2. Felix repusseau
Polytech Tours, University of Tours
3. Tifenn Rault
Polytech Tours, University of Tours
4. Matteo Doyen
Polytech Tours, University of Tours

Abstract

We are interested in the bicycle network improvement problem. Let a set of paths obtained from GPS traces represent the cyclist's path on a graph. This graph consists of nodes, i.e. intersections, and arcs, i.e. roads with or without bicycle facilities. Thus, for each arc, we get the danger as a function of its length, the bicycle facilities, and the maximum car speed. A user's cost is given by the cost of his best path, while the cost of an arc is given by a linear combination of its distance and its danger, depending on his own preference. The user's preference between danger and distance is also given.
We focus on where cycling facilities must be placed to minimize the sum of users' costs. Each time a cycling facility is decided, it costs money (depending on the length of the arc to be improved), and the total budget is limited. This problem is NP-hard. We present a greedy heuristic.
At each step of the algorithm, we evaluate for each arc the impact on each user of upgrading that arc. We choose the arc that maximizes this impact on the sum of the users' costs. Using two Dijkstra algorithms (one forward, one backward) per user allows us to compute this impact efficiently.
Moreover, this algorithm can be easily parallelized (the phase of computing the two Dijkstra algorithms per user) using multithreading. Some real instances (40 000 nodes and more that 20 km of plant proposal) can be treated in a few seconds on some classical desktop computer.

Keywords

Status: accepted

Back to the list of papers