Honey-Doing the Math

I don’t know about you, but I hate city driving. So when I have multiple errands to run, I like to combine them into one trip so I can get it over with. Now, since I hate city driving, I try to plan out my route so that:

a) I don’t hit any place more than once.

b) I minimize my total travel time.

It turns out there’s a math for that. It’s called graph theory. So each stop on my route would be considered a node or vertex. The routes between each stop would be considered edges. Each edge has a different weight which in this case is travel time. (NOT the same as distance!) My goal is to minimize my total travel time so that means the total weight of all of the edges I take when I go from place to place.

As you might expect, I’m not the first person to deal with this problem. In fact, this is a real-life version of a classic math problem known as the Travelling Salesman Problem. Like me, the travelling salesman has a number of cities on his route and he wants to minimize the total distance he travels and not have to hit any city more than once.

The Travelling Salesman Problem (or TSP) comes up in Operations Research, Combinatorics and Graph Theory as well as being a classic programming problem given to undergraduates. Not only that but it’s one of a class of math problems that are known as NP-Hard. In other words, there is no efficient way of solving the problem, ie you have to work through all of the possibilities. So the answers to NP-Hard problems are a lot of work to obtain but really easy to check.

What does this have to to with my running errands? The point is that math is not some Other, separate from normal human concerns, but is rather directly connected to who we are and what we do. When one of my students tells me that they ‘never use math in real life’, I pull up examples like this one.

We do math all the time. It is part of real life.