Monday, June 04, 2007

Computer Programs and the (now) 63-Bus Ride

Yes, the new METRO schedule change is out, and they split Bus 8 (South Main/Yale) into Bus 8 South Main to the south and Bus 66 Yale to the north. So now that makes 63 buses I have to ride. I had better get going on this before they change it again!

I managed to get all the bus times (post-bus 8 split) and threw them all into a database. I've been trying my hardest to use this data to my advantage to find an optimal route. In my mind, an optimal route would be one where I would have at least a 10 minute wait between buses (to avoid the late bus factor) and no more than a 30 minute wait between buses.

My first script did just that. You gave it a starting spot and how long you wanted to wait, and it spit out a route for you. You could either have it spit out the first route found or the fastest route found. The problem with this is processing speed. In order to find every bus route possible, it is a worst case of 63! calculations (63! means 63 factorial, or 63*62*61*60* ... *3*2*1). If you throw that into a calculator, it comes back with 2 X 10^82, or a 2 with 82 zeros after it. This means that even if I had a super computer that could do a billion checks a second (which is unreal speed), it would take 3 X 10^67 years to calculate a solution. So... that won't work.

My second script was to cut it down into little pieces to aid in a human-aided search. You could put in point A and point B and it would try to find the best path between them. The script works, to a point. The problem is that it usually skips over some crosstown buses that you need to get, because it would take too long to get them later. But it does very good at finding quickly the fastest path using 3-4 buses between two points. At least that's something. I also added a user-input variable for a "first bus" that you have to take, as well as an exclusion list of buses that you may not take on your trip. Another problem with the script is that there is no advanced string matching for the starting point, so if you don't spell the street name exactly like it is in the database, it won't know what you're talking about.

My next script is going to be 100% user input. I think this will be the best help in finding a good route. When you give it a starting point, it will spit back at you all the routes that go through that point. When you pick one of those routes, it will spit out every stop along that route, including what times it will get to that route, and which buses intersect it at that route and how long you'd have to wait at that stop to hit that bus. Then you click one of those stops and the process repeats. It will keep a running tab of what buses you've taken to get to where you're going and let you back up as many spots as you need. Unfortunately, I probably won't get to this until after my vacation next week.

No comments: