| Subject: | Map::Tube::Route::preferred() may produce counter-intuitive results |
When using the above-mentioned method on Map::Tube::KoelnBonn to find the preferred route between, say, Juridicum and Vilich, it seems that one has to change lines three times, when in fact there is a single line (running through the same stations, so same path length) connecting the two.
The result is:
---
Juridicum (16),
Universität / Markt (16),
Bonn Hbf (16),
Stadthaus (61),
Bertha-von-Suttner-Platz / Beethovenhaus (62),
Konrad-Adenauer-Platz (62),
Adelheidisstr. (66),
Vilich (66)
---
In fact, line 66 runs through from Juridicum to Vilich through exactly the same stations. So, while the result is a correct route, it would probably not be called "preferred" due to the number of unnessessary changes.
The problem is that in case of multiple lines, the current algorithm picks one line per link at random (the one that happens to be first in the array of common lines of the two neighbouring stations involved). This is repeated for every pair of adjacent stations.
This purely local choice of lines leads to the sub-optimal end result. I think the algorithm should try harder to pick a "good" line. Picking an optimal one may actually be computationally hard (NP?), but it should be feasible to pick a route that has as long runs as possible without line change. (I could provide some ideas on this if desired.)