If you have a free couple of years, you like walking, you like good snack food, and you like Japan, then we have a tour for you. We have solved a traveling salesman problem (TSP) to walk to 40,426 Japanese convenience stores. The total time for the round trip is 35,578,434 seconds, or 411 days, 18 hours, 53 minutes, and 54 seconds. It's not likely you would count every second on such a journey, but this level of precision makes the point that this not just a good route, it is an optimal solution to the 40,426-stop TSP.

The problem itself was created using the Open Source Routing Machine (OSRM) to build a table of 817,110,525 store-to-store travel times, one for each pair of stores. Our computation produced a tour together with a proof that is optimal, that is, we have a guarantee that the tour is shortest possible when measured with the OSRM travel times.

It was a difficult computation. A very rough estimate is that if we had only a single processor core (in our case, part of an Intel Xeon Gold 5218 CPU @ 2.30GHz) then the total running time would have been around 43 years. A discussion can be found on the Computation page.

"Take a stroll through any Japanese city-you'll be hard-pressed to go a few blocks without passing a convenience store. The one-stop shops dot streetscapes everywhere. So ubiquitous are konbini, as they are known to locals, that it's difficult to imagine life in Japan without them."

"For many residents, the more than 55,000 cheerful, jingle-filled stores, known as konbini, are an indispensable part of daily life. Millions flock to the stores daily to pick up food, send packages and pay bills."

"Life in Japan is deeply tied to ubiquitous konbiniensu sutoa (convenience stores), better known as konbini. They can be found at around 55,600 locations across the country."

The great Homemate web site lists 45,485 shops in the convenience store category. From these, we extracted the locations of 40,426 konbini for which the listing included walking directions, combining the major chains 7-Eleven, FamilyMart, Lawson, Ministop, Daily Yamazaki, and Seicomart. It is a pity not to have the full 55,000+ locations mentioned in the news stories, but still a really nice selection for a tour around the country.

You can find a list of the latitude-longitude coordinates for the 40,426 konbini on the Data page.

The figure below is a screen shot of an interactive map of the konbini40426 tour. The menu on the left-hand-side lets you select one of nine regions to view. At the top right-hand-side you can choose to have either a colored street map or a grayscale map without street labels. Just below this menu you can select whether or not to display the stop markers, or to display the tour edges, or to display both. You can view the map by clicking on the image.

Here is a key to the point markers used in the various map drawings displayed throughout the site.

If you have trouble viewing the interactive map, you can click on the drawings below to see high-resolution images of the tour. For close-up views of city regions, please see the Cities page.

Newspapers, popular journals, blogs, and scientific press releases regularly report that solving even tiny instances of the TSP is impossible with the current generation of computers. A typical example is the following quote from the Washington Post.

"It would take a laptop computer 1,000 years to compute the most efficient route between 22 cities, for example."

Statements such as this assume the only way to solve the TSP is to check each possible tour, one-by-one. That is definitely not going to work for our 40,426 stops. The number of tours in this case is roughly 1.5 followed by 168670 zeroes.

This huge number of possible solutions is frightening, but it doesn't mean we can't solve this large example of the TSP. Our attack combined the LKH code for computing extremely good TSP solutions and the Concorde code for applying what is known as the "cutting-plane method" for producing quality guarantees. You can see a short discussion of how we apply these tools on the Computation page.

For a quick glimpse of the cutting-plane method, here is how I describe the process in a short piece in Scientific American

"The idea is to follow Yogi Berra's advice `When you come to a fork in the road, take it.' A tool called linear programming allows us to do just this, assigning fractions to roads joining pairs of cities, rather than deciding immediately whether to use a road or not. It is perfectly fine, in this model, to send half a salesman along both branches of the fork."

"The process begins with the requirement that, for every city, the fractions assigned to the arriving and departing roads each sum to one. Then, step-by-step, further restrictions are added, each involving sums of fractions assigned to roads. Linear programming eventually points us to the best decision for each road, and thus the shortest possible route."

If you have a few minutes, you can check out the video of the talk Optimal Tours given at the National Museum of Mathematics, where the method is described in detail.

A great discussion can be found in Lance Fortnow's article Fifty Years of P vs. NP and the Possibility of the Impossible.

We use large examples of the traveling salesman problem as a means for developing and testing general-purpose optimization methods. The world has limited resources and the aim of the applied mathematics fields of mathematical optimization and operations research is to create tools to help us to use these resources as efficiently as possible.

For general information on mathematical modeling and its impact on industry, commerce, medicine, and the environment, we point you to a number of societies that support mathematics research and education: American Mathematical Society, Mathematical Association of America, Mathematical Optimization Society, INFORMS (operations research), and SIAM (applied mathematics).

In Japan, a major 5-year research project, AFSA, includes the study of Innovative Algorithms and Optimization, covering tools that are critical for successful applications of computational discrete optimization.

William Cook, Combinatorics and Optimization, University of Waterloo, Canada
Daniel Espinoza, Google, Research and Development, USA
Marcos Goycoolea, School of Business, Universidad Adolfo Ibanez, Chile
Keld Helsgaun, Computer Science, Roskilde University, Denmark

The huge number of linear-programming models that arose in the computation were solved with the IBM CPLEX Optimizer. Many thanks to IBM for making their great software freely available for academic research.

The map drawings of the tour were created with the Leaflet open-source JavaScript library for mobile-friendly interactive maps and make use of map tiles built by OpenStreetMap, by Carto Basemaps and by Stadia Maps.

The locations of the convenience stores were obtained from the Homemate web site that allows you to search for retail stores throughout Japan.

The table of point-to-point walking times was created with the Open Source Routing Machine (OSRM).