Math in… Road Trips

Planning a trip with multiple stops can be tricky. The order in which you visit each stop can significantly impact your travel time.

So how do you choose the best order?

One way is to write down every possible ordering of stops, and then calculate the trip time for each one. For a few stops, that's not too bad, but the number of calculations you'd need to do for your stops is:

n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1

By 20 stops, there are already 2.4 quintillion different orders!

Although there are faster algorithms, the computations are still slow. The Clay Mathematics Institute even offers a $1,000,000 prize for proving whether the problem’s computational complexity class, NP, differs from that of easier problems. This is commonly referred to as the “traveling salesperson” problem.

In the real world, delivery drivers often rely on software to plan their routes. This software may not always find the best route -- just a good enough one.

What’s the longest trip you’ve ever taken?