Using simulated annealing, Schneider's app solves traveling salesman problem for 48 U.S. state capitals. Todd Schneider

What's the shortest route, if you're visiting each city exactly once and then returning to the point of origin?

When he's not designing software for a living, Todd Schneider makes weird and wonderful apps for fun. In his latest effort, if you enter any list of cities—in the U.S. or anywhere in the world—the app will solve the famous "traveling salesman problem", which you may remember from your college math courses. It asks: what's the shortest route, if you're visiting each city exactly once and then returning to the point of origin?

"I don't think there is any practical application (for the app)," Schneider says. It's just something cool for people, especially math students, to play around and have some fun with, he says.

The app uses "simulated annealing," a method that finds answers to problems that have a really, really large number of possible solutions—so many, that it would take forever to try every single possibility on your own.

The first phase of calculations (called "high temperature") tries only a few solutions. In this phase, the app is trying possibilities randomly. Sometimes, it accepts a solution that may take it further from the right answer. As more and more tries go by, or "temperature" gets lower, the simulation starts choosing only those possible solutions that help it find the shortest route.

It sounds counter-intuitive and confusing. But picture a marble rolling down a hilly landscape, Schneider explains. To get to the lowest point in the valley, it may have to climb up a hill first. Similarly, to get to the shortest route, it has to try the longer routes first.

"Simulated annealing" accepts worse solutions in the first phase, and then only those that help it reach the correct answer.

Invoking the wisdom of Chief Wiggum, Schneider explains that behind the complicated math is a very simple idea: sometimes things have to get worse before they get better.

About the Author

Most Popular

  1. Two different Eiffel Towers rise above manicured lawns. The one on the left is an image from Tianducheng, a city in China, and the one on the right is an image from Paris.
    Photos

    Which One Is Paris?

    Francois Prost’s new photo series looks at Tianducheng, a town built to look exactly like the City of Lights.

  2. 1970s apartment complex in downtown Buffalo
    Equity

    The Last Man Standing in a Doomed Buffalo Housing Complex

    After a long fight between tenants and management, John Schmidt is waiting for U.S. Marshals to drag him out of Shoreline apartments, a Brutalist project designed by Paul Rudolph.

  3. Transportation

    How Toronto Turned an Airport Rail Failure Into a Commuter Asset

    The Union Pearson Express launched with expensive rides and low ridership. Now, with fares slashed in half and a light rail connection in the works, it’s a legitimate transit alternative for workers.

  4. Transportation

    The Automotive Liberation of Paris

    The city has waged a remarkably successful effort to get cars off its streets and reclaim walkable space. But it didn’t happen overnight.

  5. A small accessory dwelling unit—known as an ADU—is attached to an older single-family home in a Portland, Oregon, neighborhood.
    Design

    The Granny Flats Are Coming

    A new book argues that the U.S. is about to see more accessory dwelling units and guides homeowners on how to design and build them.