## Create a Bus Schedule/Math Puzzle

Computer science and mathematics have a wonderful problem called the Traveling Salesman Problem or TSP. There are variants, too, the Canadian Traveler Problem and the Chinese Postman Problem. All three problems are attempts to use math to solve ancient problems faced by people and their societies.

Imagine your name is Og and you have rocks to sell in nearby towns and villages. Your rocks are heavy and you do not want to be away from home longer than needed to sell all your rocks. Given the number of towns and villages, and the distances between each pair of villages, what would be the shortest route to visit each town or village once and return to your home?

Here is the easiest possible route if all the destinations are neatly laid out in a circle:

In this ideal world, Og can travel in a circle from A-Town to B-Town to C-Town. Or the reverse on days he (or she) gets bored.

However, this arrangement of villages is more likely:

If each dot represents a village or town, what is the shortest route Og can take to sell rocks? It’s not at all clear, is it?

Here is one way to describe the traveling salesman problem and narrow down the range of possible solutions:

In mathematical terms, the Traveling Salesman problem is a graph problem. While algorithms exist to help solve this problem, the ideal solution is difficult to find. There are so many possible alternate routes to be evaluated then compared to other routes.

Creating a bus schedule is one way to use the real world to solve these problems. Bus schedules also solve the Traveling Salesman Problem by using other data, for example, the distance people live from possible bus stops. The more dense a population of bus riders, the more likely bus stops (points on a graph, in Traveling Salesman terms) will be set up in those areas.

### How Hard is it to Create a Bus Schedule?

It’s not hard to create a bus schedule if all possible stops are in a straight line and all possible riders live along the straight line. But that’s rarely the case in any town or city, and not for long either. Study any bus line and you’ll see straight stretches alternate with diagonal stretches and a turn around at the ends of the line.

Indeed, it is good bus line design practice for the ends of your route to include bathrooms and comfortable areas to relax. Why? If you don’t, the bus driver may have to stop along the route to use the bathroom. It’s better to have lines end with rest areas.

### How do You Create a Bus Schedule?

In the real world, bus lines are designed by x using y.

### What are the Ingredients of a Bus Schedule?

Like any project, creating a bus line has a set of inputs and restraints you must account for as you design a route. Ideally the bus should be available to the most number of people and stop where people want to stop, for example, town or city centers, sports stadiums, and schools.

Here are some possible inputs:

Here are some possible restraints, conditions you might work around:

### An Example Bus Schedule

If you want to create your own bus schedule, by yourself or with your students in a classroom, you might follow these steps:

1. Interview a person in your town responsible for the design of bus schedules. Ask them how they design a schedule, where they get information used to design their schedule, and what trade-offs they have to make. It also might be interesting to ask what math they use and what software they use, if any, to design bus schedules.
2. Pick a city near you and use Google Maps or Mapquest to see the city street layouts. Population maps?
3. Using the map and other information, design a bus route from your location to at least one place you would like to go. Try to include as many people as possible who live near your bus stops. Where would they like to go on a bus?
4. Compare your bus map to any existing bus lines. If your stops are different, can you tell the reason you picked your stops and the town picked their stops?

### Can You Create a Perfect Bus Schedule?

Short answer: No. Perfection is unlikely and possibly not needed.

Creating a bus schedule is about meeting most needs rather than all needs. While your bus route may not reach every person within a quarter mile, some people will walk half a mile to their nearest bus stop. Other people may walk even more if the bus stop goes to places they really want. For example, people who live in apartments may not own a car and, therefore, may be happy to walk half a mile to the bus stop.

However, it’s also true an older person, or a person who uses a wheelchair, may need to have a bus stop within a quarter mile or less of where they live. It’s these trade-offs based on who your bus route serves that make creating a bus route an interesting challenge.

#### Transit Capacity and Quality of Service Manual

http://onlinepubs.trb.org/onlinepubs/tcrp/tcrp100/part%200.pdf