## The traveling salesman

As school opened yesterday, Jaimie and I had additional traffic to deal with. School buses!

Last year, there was one Public School bus, one Catholic School bus, and one little bus that used to share the road with us. Yesterday, as we did our morning walk, we counted and there were four big buses and two little buses. This morning, there were three and three. We only noticed a couple of stops so it appears that there is one student going to a Public School and one to the Catholic School.

It’s a reality when you live on a concession road. It ups the ante for our safety when you walk pass a bus that has stopped to take on passengers. When the lights go off and the little stop sign closes, the cars that had been stopped often floor it to get around the bus and it can be scarey if you’re walking the same direction, alongside the bus.

I don’t know, but I attribute the increase in traffic due to the bridge reconstruction on the next concession. It was supposed to be done by now but they found a human bone during the work and that seems to have extended the work and I am guessing, affected the bus routes.

That got me thinking of the company that runs the buses and the infamous Traveling Salesman Problem. Put simply, the problem is solved if you can set up a path that minimizes the amount of travel and still allows the saleman to visit every location that he is supposed to. So, you essentially have a start, a finish, and then various stops to make along the way to pick up riders.

I remember addressing this problem at university. It’s not a simple problem and there are all kinds of serious algorithms to consider.

One of the solutions is the brute force method which means trying all possible solutions and finding the optimum one. There are other, more elegant solutions, and they are a lot of fun. Nearest neighbour is one to consider – the link above is a great discussion of the topic.

The brute force one intrigues me as a problem solving, collaborative activity for students and a map of your school area. Given the desire to keep maintenance to buses to a minimum and the price of gas purchased down, it makes sense to optimize the route the bus takes.

Some things to consider:

• where does the bus start? Bus depot or at the driver’s home?
• where does the bus end up? (of course at the school)
• what route should the bus take to get from starting point to finishing point?
• how long does it take for a person to get on the bus?
• how long does it take to travel between student house to student house?
• can two or more students be picked up at one stop?
• are there any one way streets?
• if your school starts at 9:00 (or whatever your time is), what time does the bus have to leave in the morning to get everyone on board and then dropped off at school?
• what happens to the plan if a road construction occurs?
• if your school ends at 3:00 (or whatever your real time is), what time does the last student get home?
• wouldn’t life be so much simpler if everyone walked?

There’s a lot of great thinking and problem solving in something as simple as just getting on the bus.