[Back]

B. Klocker:
"Optimierungsansätze zur Planung von Freizeit-Fahrradrouten";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2015; final examination: 2015-04.

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.

Körperliche Aktivität ist wichtig, um gesund zu bleiben. Deshalb entwickeln wir einen
Algorithmus, um schöne Freizeit-Fahrradrouten zu berechnen, mit dem Ziel, das Fahrradfahren
attraktiver zu machen.
Wir formulieren die Aufgabe als ein mathematisches Optimierungsproblem, welches
dem "arc orienteering problem" (AOP) ähnlich ist. Das Problem ist auf einem gerichteten
Multigraphen definiert und hat als Ziel, die Attraktivität einer Route zu maximieren,
während die Länge der Route beschränkt ist. Die mehrfache Verwendung einer Straße
ist erlaubt, führt aber zu einer Verringerung der Gesamtattraktivität. Das Problem
ist NP-schwer und daher ist die Entwicklung von Algorithmen, die in der Praxis in
akzeptabler Zeit gute Lösungen liefern, besonders wichtig.
Drei gemischt-ganzzahlige lineare Programme werden entwickelt, um das Problem
exakt zu lösen. Das erste Programm verwendet als Subtour-Eliminationsbedingungen eine
klassische Schnittformulierung, das zweite einen Flussansatz und das dritte Programm
die Kombination der ersten beiden Formulierungen.
Das Testen der Implementierungen der drei gemischt-ganzzahligen linearen Programme
unter der Benützung von CPLEX ergibt, dass die Flussformulierung für die meisten
Testinstanzen schneller ist als die anderen zwei Formulierungen. Beim Vergleich unserer
Implementierung der Flussformulierung mit anderen exakten Algorithmen, welche ähnliche
Probleme wie zum Beispiel das AOP behandeln, war unsere Implementierung bis zu 1000
Mal schneller. Verglichen mit heuristischen Lösungsansätzen ähnlicher Probleme erhalten
wir, dass für manche Instanzen unsere Implementierung in kurzer Zeit die optimale
Lösung findet, während die Heuristiken nur suboptimale Lösungen finden. Allerdings
skalieren die Heuristiken besser auf sehr große Instanzen. Unsere Implementierung ist in
ländlichen Gegenden für Routen bis zu 60km und in städtischen Bereichen für Routen bis
zu 13km gut anwendbar, was für die meisten praktischen Zwecke ausreichend erscheint.

http://publik.tuwien.ac.at/files/PubDat_247779.pdf