Abstract
Exercising is important to stay healthy. Therefore, we develop an algorithm for finding nice
recreational bicycle tours with the goal of making exercising by cycling more attractive.
We formulate this challenge as a mathematical optimization problem similar to the
arc orienteering problem (AOP) on a directed multigraph. The objective is to maximize
the attractiveness of a route under the condition of not exceeding a maximal tour length.
It allows multiple usage of streets, but penalizes it such that the attractiveness or score
of the route decreases. The problem is NP-hard and developing practically effective
algorithms running in reasonable time is therefore crucial.
Three mixed integer linear programs are provided for solving the given problem
exactly. The first program uses a classical cut formulation as sub tour elimination, the
second a flow formulation and the third the combination of the first two.
Testing the implementations of the three mixed integer linear programs using CPLEX
reveals that the flow formulation is for our purposes more efficient than the other two
formulations. Compared to other exact algorithms solving similar problems like the AOP,
our implementation of the flow formulation is faster up to a factor of 1000. If we compare
our implementation with heuristic approaches for similar problems, we get the result
that for some instances our implementation finds the optimal solution in short time and
the heuristic approaches do not find the optimal solution. However, the heuristics scale
better for large instances. On the countryside the algorithm is applicable for routes up
to 60km and in urban areas for routes up to 13km, which seems to be enough for our
intended practical purposes.
Originalsprache | Englisch |
---|---|
Gradverleihende Hochschule |
|
Betreuer/-in / Berater/-in |
|
Datum der Bewilligung | 19 Mai 2015 |
Publikationsstatus | Veröffentlicht - 2015 |
Research Field
- Ehemaliges Research Field - Mobility Systems