Subway design in Utrecht

Silvia Cuadrado(1), Kim Feldhoff(2), Rafal Latkowski(3),
Tobias Werther(4) and Martijn Zegers(5)

(1) Universitat Autonoma de Barcelona.
(2) University of Kaiserslautern.
(3) Warsaw University.
(4) University of Vienna.
(5) Eindhoven University of Technology.

Abstract

This report is dealing with the design of a subway in Utrecht. The main
goal is to find a (sub)optimal subway track with respect to the travel
times. The problem is translated into a combinatorical optimization
problem.
Because of the complexity of the problem we think that the best
approach is to use local search methods. For evaluating the quality of
the subway one has to calculate the total travel time. We line out the
steps for computing or estimating this value. The local search
algorithms presented are Hill Climbing, Taboo Search and Simulated
Annealing. Furthermore, two possible neighbourhood structures are
defined, namely "Adding and deleting stops" and "Exchanging stops". To
improve the speed of the search we introduce a preselection of the
neighbourhood. Finally we give some conclusions and recommendations.