When path finding goes wrong

Path finding is a fairly simple problem with well-known algorithms. When you're doing path-finding for a train route this is even easier: all you have to consider is the price and duration of the different possibilities (as well as convenience factors such as number of transfers if you want a really good result).

The website Hyperdia offers a convenient way to find train routes in Japan. When I was looking for a route from Higashi-kitazawa (the station nearest to my lab at Tokyo University) to Shinjuku, it makes sense that it comes up with this route:

The logical route

Note that I don't actually need Hyperdia to find this out; this route is simple and I've taken it many times (although usually not starting at Higashi-kitazawa but earlier down the line). I was mainly interested in the price from this station, and I wanted to see if it would be faster to walk to Yoyogi-Uehara instead and take an express train. But I digress.

Hyperdia always gives you several alternatives. Sometimes routes that are faster but more expensive, slower but cheaper, take more or less transfers, and, as I've found out today, sometimes it's routes that are slower, take more transfers, and are more expensive! This is the second option Hyperdia lists for this route:

The not-so-logical route

Uhm, ok? I've plotted these two routes on a map. As you can see they appear very similar in terms of distance covered. But the second route takes two transfers instead of zero, is more than twice as expensive, takes almost twice as long, and includes two minutes walking!

Some consolation can be found in the fact that this was at least not the first route it offered, so it does at least recognize that the other one makes more sense. But the fact that this route is offered at all makes you wonder what kind of weird weight-function is used to evaluate these routes? :P

Categories: General computing, Japan
Posted on: 2007-05-10 06:46 UTC.


No comments here...

Add comment

Comments are closed for this post. Sorry.

Latest posts




RSS Subscribe