The New York Subway Challenge is a competition where participants must pass through all the New York Subway stations in the shortest time possible. Each station has been considered as a node of a graph, and the time needed to travel between stations as the arc weights. The main issue of this graph approach has been the systematic generation of subtours, due to the special characteristics of the graph and the inability to find proper constraints. In order to deal with this, in this work we propose the creation of the directed line graph of the original network. With this procedure and by means of the linear optimization methods, we have found the optimal solution for the New York Subway Challenge.
New York subway challenge
Date |
Jun 2015
Technologies |
matlab
·
cplex
·
latex
·
