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. A photo of a cyclist on the streets of Chicago's Pilsen neighborhood.
    Equity

    Can Historic Preservation Cool Down a Hot Neighborhood?

    The new plan to landmark Chicago’s Pilsen neighborhood aims to protect more than just buildings: It’s designed to curb gentrification.

  2. a photo of a highway
    Transportation

    Americans Are Spending Billions on Bad Highway Expansions

    PIRG’s annual list of “highway boondoggles” includes nine transportation projects that will cost a total of $25 billion while driving up emissions.

  3. A cat lays flat on a bench at a park on the outskirts of Tokyo.
    Life

    Why Don't Americans Use Their Parks at Night?

    Most cities aren’t fond of letting people use parks after dark. But there are good lifestyle, environmental, and safety reasons to reconsider.

  4. Rows of machinery with long blue tubes and pipes seen at a water desalination plant.
    Environment

    A Water-Stressed World Turns to Desalination

    Desalination is increasingly being used to provide drinking water around the globe. But it remains expensive and creates its own environmental problems.

  5. Brick apartment buildings in Stuyvesant Town, New York City
    Equity

    No Wonder Big Real Estate Is Fighting New York's New Rent Law

    Previously unreleased data shows that large landlords who own multiple buildings have a stranglehold over housing—and evictions—in New York City.

×