This goes back a ways. In the late '80s, when I was in college, I saw a story in the local newspaper about the city school system. They were totally jammed up

This goes back a ways. In the late '80s, when I was in college, I saw a story in the local newspaper about the city school system. They were totally jammed up trying to make schedules for the school bus routes. I'm thinking they might have even delayed the opening of school a few days, but I might be misremembering that. I'd been studying algorithms and this was, to me, obviously a traveling salesman problem taken to the next level. I spent several months researching the problem. I met with the guy at city schools who ran the office that made the routes. I got a friend's brother who was a fireman to give me a whole stack of large extremely high-resolution blueprint street maps. I spent an astonishing number of hours encoding street intersections and soforth into coordinates (using yardstick and multicolor pencils) and entering them into a QBasic program I wrote running on a PC under DOS. I wrote a functioning routing program that, given the map data and a bunch of addresses, would create a reasonable set of routes. In the course of doing all of that work I really learned the meaning of tree-spanning algorithms, big O notation, and soforth - but I never created a usable SYSTEM. The map data was just too huge; I only encoded a small part of it. Also, the amount of computation required grew so fast that I realized if I ever did succeed in encoding the entire map the amount of computational time to produce usable routes would be impossibly huge. My grades suffered horribly and I found actual paying work writing software for an insurance company. There were other issues, too. Finally I had to just quit the whole thing. In hindsight, had I had access to Tiger/Line (I think it existed then but cost far more than I could afford) and been more advanced as a programmer and had more (any) support the problem could have been solved. Tom-Tom, Google Maps', et al route-finding fascinates me. It's obvious that they don't do a complete graph search - I think they use clever tricks like identify arterial roads limiting the graph search to those roads - things like that.