We also computed optimal walking tours through the locations of each of the six chains of convenience stores in our data set, as well as an optimal driving tour to visit every Michi-no-Eki roadside station in Japan. The results are summarized in the following table.

Chain	# Stops	Tour Length	Computation Time
7-Eleven	13571	23207346	208393.7 seconds
FamilyMart	12949	21404135	58867.1 seconds
Lawson	9933	21414566	14576.4 seconds
Ministop	1628	6145162	77.5 seconds
Daily Yamazaki	1518	9344332	20.6 seconds
Seicomart	752	2381530	3.5 seconds
Michi-no-Eki	1204	2494610	316943.2 seconds

The computations were carried out on a single core of a Linux server equipped with a 2.10 GHz Intel Xeon Gold 6238 CPU. This machine was purchased in 2019 and it is a workhorse for our TSP research.

Note that the travel time for the Michi-no-Eki tour is much less than that of the other all-Japan tours. For long distances, driving is indeed faster than walking. But note also that the computation time for this example is much longer than that for the other computations. This is due to the fact that we handle driving times with asymmetric data. For driving, the time to travel from stop A to stop B may be quite different than the time to travel from B back to A. The Concorde solver is designed for symmetric data, so asymmetric instances must be handled with a special transformation. We discuss this in the Michi-no-Eki section below.

The tours for five of the six individual chains of convenience stores visit all of the stops included in konbini40426. For the Seicomart tour we restricted the tour to Hokaiddo, to avoid a long ferry trip to pick up the small number of shops outside the island. If you are interested in seeing the optimal routes, use the buttons in the blocks below to view interactive maps and high-resolution images.

The Map button will bring up an interactive map-drawing of the tour, allowing you to pan and zoom. But note that there may be considerable lag when you navigate the large 7-Eleven, FamilyMart, and Lawson tours. For these you may want to use the Lite button for a simpler map drawing, where stops are indicated by cirles. The Lite maps should load more easily than the full maps.

In the full-map drawing you will see a menu in the top left-corner with buttons to zoom into regions of Japan. The top right-corner of the map contains a small menu for modifying the drawing, and the bottom right-corner has buttons for zooming in or out. Clicking on a location marker will display a menu to allow you to zoom into the shop location or to pan to the next stop in the tour.

Clicking the tour image in one of the blocks will bring up a high-resolution image. Please use this if you have trouble loading the map drawings.

Links to data sets for the six konbini instances are given in the following table. The Lat-Lng sets give the (latitude-longitude) locations for each shop. For the three smaller instances, the TSP sets give the tables of walking times in TSPLIB format format. The Tour entries list the order the stops appear in the optimal tours; these files are also in TSPLIB format.

Chain	Lat-Lng	TSP	Tour
7-Eleven	seven13571.xy	---	seven13571.tour
FamilyMart	famima12949.xy	---	famima12949.tour
Lawson	lawson9933.xy	---	lawson9933.tour
Ministop	mini1628.xy	mini1628.tsp.gz	mini1628.tour
Daily Yamazaki	yama1518.xy	yama1518.tsp.gz	yama1518.tour
Seicomart	seico752.xy	seico752.tsp.gz	seico752.tour

The full table of travel times for the 7-Eleven, FamilyMart, and Lawson problems are too large to post on the web server. Like in the full konbini40426 problem, the tables for the these examples were created by finding point-to-point routes with the Open Source Routing Machine (OSRM). For a discussion, please see the Data page.

"As you traverse Japan's vast road network, you may find yourself in need of rest. Michi-no-Eki, which means roadside station in Japanese, are the ideal way to recharge your batteries and learn about the area you're passing through on your journey. These roadside stations offer far more than service stations you may be used to, usually showcasing their area with a sampling of delicious regional produce. They can be found in every prefecture, from Okinawa to Hokkaido, and number more than 1,000 in total. If you intend to get behind the wheel in the Land of the Rising Sun, these pit stops will be indispensable."

We obtained a list of 1204 stations from the official Michi-no-Eki web site. The latitude-longitude coordinates for the stations are given in the following file.

• michi1204.xy

Walking distances were the choice for the closely packed konbini locations, but for a Michi-no-Eki tour we want to take to the highways. For this we adopt OSRM point-to-point driving times in our TSP instance.

• michi1204.atsp, distance table in TSPLIB format.

Note the "atsp" suffix, rather than our usual "tsp". This indicates an asymmetric instance of the traveling salesman problem. We are, in this case, not assuming the travel time from point A to point B is the same as the travel time from B back to A. The direction of the tour matters. Think of divided highways, one-way streets, and no-left-turn-allowed signs.

There is a standard transformation of the ATSP to the TSP, splitting each stop into a pair of stops, one for incoming links and the other for outgoing links. The LKH code handles this transformation internally and is very effective in producing high-quality ATSP tours. To obtain an optimality proof, we modified Concorde to also handle the transformation. This allowed us to solve michi1204, but it was a more difficult computation then the similar-sized Ministop and Daily Yamazaki tours.

The order of the stops in the optimal tour is contained in the following file.

• michi1204.tour, tour in TSPLIB format.

The figure below is a screen shot of an interactive map of the 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. Hovering over a marker will display a small photo of the stop (if available) and the stop's position in the tour. Clicking on a marker will display a larger photo, the stop number, a link to the stop's web page, and buttons to allow you to zoom in or to move to the neighboring stops on the tour. Keep in mind that an ATSP tour is directed — the stop numbers and Next and Previous buttoms allow you to see the direction of each link.

You can view the map by clicking on the image.

Alternatively, you can click on the tour drawings below to see high-resolution images.

Point-to-point travel times and path polygons were generated with the Open Source Routing Machine (OSRM) using OpenStreetMap data.

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

The locations of the roadside stations were obtained from the official Michi-no-Eki web site.