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:
- 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.
- Pick a city near you and use Google Maps or Mapquest to see the city street layouts. Population maps?
- 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?
- 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.
How Bus Routes Get Designed
Transit Capacity and Quality of Service Manual
The Traveling Salesman Problem
Canadian Traveler Problem
Chinese Postman Problem
Also In The May 2013 Issue
What are the differences between high level languages and machine languages? And how do these differences impact coding?
Learn how a humanities PhD became a software programmer who builds online communities for universities, as well as Lead Developer for BuddyPress and helping to create WordPress plugins like Anthologize and Participad.
With this issue, you will find some articles require subscription. Here's an explanation and how you can help add writers and voices to future issues of this magazine.
Links from the bottom of all the December 2013/January 2014 articles, collected in one place for you to print, share, or bookmark.
Here are a few places where you can recycle your old electronics safely.
A few great ideas on how to make New Year's resolution you might actually keep, and have fun doing so. Whether you like structure or hate it, here are a few approaches and a number of resources to help.
Interesting stories about computer science, software programming, and technology for the month of November 2013. More stories can be found at the News Wire link at the top of every page of this site.
How many measures of grain can one camel eat while delivering grain, before the camel runs out of grain to deliver? A fun math problem at least 1,000 years old.
Almost all programming languages include the ability to add comments and other notes in your code. Here's how several languages work with comments.
In the same way your bedroom may be impossible to enter if you let dirty clothes pile up, computers can crash and refuse to operate if their memory is stuffed with unused data.
Go is an open source programming environment that makes it easy to build simple, reliable, and efficient software.
The Linux directory structure looks confusing compared to Windows. Here are the names and purpose of each directory.
Localhost is available on most computers, usually to display web pages. It's also useful to use to learn coding on your computer.
They talk about how they started and run iDTech summer camps together and how parents can evaluate tech summer camps.
With a wave of kids with special needs graduating high school, how can technology help them with resumes, college, jobs, and careers?
A clever technique to speed up database searches also is an interesting concept.
Here are some videos, and links to even more videos, to learn how to use your Raspberry Pi and have all kinds of fun with Pi projects.
Interesting stories about computer science, software programming, and technology for the month of October 2013. More stories can be found at the Software Programming and Computer Science News Wire link at the top of every page of this site.
With a bubble sort, numbers sort themselves as they bubble to the left of a group of numbers. Here's a fun catchy video to explain.
This month's math puzzle dates back to 1735 when it was first solved by Leonhard Euler, a Swiss mathematician and physicist.
Links from the bottom of all the November 2013 articles, collected in one place for you to print, share, or bookmark.
A balance of flexible and inflexible qualities make Haskell a fascinating programming language to learn and use.
The release this fall of Apple's iOS7 operating system is a great opportunity to explore the history of computer interface design.
Managing inputs and outputs is a key problem programming languages face. Here's how a few languages use functions to manage and transform data.
Open source hardware geared towards artists, hobbyists, designers, and students, is a viable and far less expensive alternative to build your own computers.
How to code an HTML email like the ones you open every day turns out to be an offbeat software coding challenge.
How to tell if a web page is secure is one of the most basic yet least obvious ways to protect your data online.
One key computing skill is the ability to use command line interface (CLI) software to enter commands to control a computer. Here are some options.
Lua is a comparatively simple programming language used in a wide range of places, from digital TVs to video games to phone applications. It's also designed to be simple to use and lightweight.
Here is how three programming languages handle a common problem: how do you organize and keep track of useful data?