Amaze Me 2

I was riding the bus into work the other day when I realized that bus route calculations are kind of like the maze problem, only harder. Imagine that you live in a city (e.g. Seattle) and that you use buses to get everywhere and you want to be able to calculate the most efficient routes from any address to any other address. As data sets, you have all the bus timetables and their route maps, plus the input of starting time or finishing time, starting address, and ending address. Build an application that will show you the bus routes and schedules and overlay them onto a map.

This is a real app, by the way, only the Seattle one just gives you text as output.

I was thinking through this problem the other day and realized just how complicated it could be.

Comments (6)

  1. Ed Kaim says:

    I like question 6 from the app:

    "6. Do you require an accessible trip?"

    I suppose that if you don’t check the "Yes" box, they reserve the right to make your trip entirely inaccessible.

  2. Ed Kaim says:

    And yes, of course I know what they’re really asking 🙂

  3. johnmont says:

    Correct — if you don’t check the box, the default of "Please route my bus trip through Japan" is inserted.

  4. Jeff Parker says:

    Actually this is not all too difficult, I have done this before just for fun. Ok so I am a geek, because I do this stuff for fun. But the game Eve, one of the multitude of ways to make money in the game is discovering trade routes. Kind of similar to what your asking. Pick up Item A in One Solar System for a specific price and deliver it in another for a higher price. The game has a nice market feature where you can see things in your region and you can see the buying price and selling price. Which you might think was easy why not just look at it in your region and go.

    Well because much like a trucking company if you did that then your spending a lot of time empty and not making a lot of money. To find a really good trade route you not only need to find something to take from point A to Point B, but you have to find something to take from point B to either point A again or maybe point C. Then since you can only see in your current region I would also sign on another character located in other regions and then you have plot out all the routes. Plus a little more complicated beyond bus routes you have to plan on security issues and pirates and places where you are not welcome. So try to envision not only planning the most efficient bus route but also the safest and beying able to adjust it on the level of risk your willing to take.

    I still play eve on occasion as I love the game it gives me a ton of wierd problems to solve however I don’t trade much anymore. I made it too easy for myself.

  5. johnmont says:

    Cool. Personally, I find any system that can map a route over a real map (e.g. a street map) fascinating.

  6. Brian Keller says:

    Now consider an even tougher challenge – actually dictating the bus routes in the first place. Let’s say you have a fleet of 100 buses and let’s even assume you know the travel requirements for all 2 million people in King County – now develop a heuristic for calculating the optimum bus routes. All sorts of problems come up. Not the least of which – how do you decide who do you optimize for? The working class? The poor and unemployed? You could make strong moral and ethical arguments either way. Should you just optimize for an approach where you have a chance at moving the most number of people, regardless of status? How do you balance the ebb and flow of commute times and sporting/concert events? What do you do when there is a severe weather delay? It makes my head hurt, but I’m sure it would be a fun problem to work on.