konbini40426 Data

The konbini40426 TSP instance consists of walking times, measured in seconds, between 40,426 convenience stores Japan. We will refer to the walking times as "distances", to match the usual TSP language. The distances in konbini40426 are symmetric, that is, for any pair of shops A and B, the distance from A to B is the same as the distance from B back to A.

The first step in building an example of the TSP is to collect the locations of the points to visit. 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.

The latitude-longitude coordinates for the 40,426 locations are given in the following file

  • konbini40426.xy

Click here for a full image of the point set.

We adopt the Open Source Routing Machine (OSRM) to obtain point-to-point walking times between the konbini locations. A nice set of instructions for running the OSRM can be found on the Project-OSRM GitHub page. In building the konbini40426 distance table, we made the following adjustments.

• We used a modified profile to permit walking on "trunk" roads. This was needed to handle walks in the rural areas of southwest Hokkaido.
• We adopted the alternative Construction Hierarchies (CH) setting for preprocessing. On our large example, this was much faster than the default Multi-Level Dijkstra (MLD) setting.
• We used the --max-table-size argument to handle rows of the full matrix, setting this value to 50000 rather than the default 10000.

The full data set, in TSPLIB format, is a 5.5 GByte file. This is too large to store on our university server. But if you would like to carry out experiments on konbini40424, please write to bico@uwaterloo.ca and I'll attempt to place the file temporarily at a public location.

Click on the images to see high-resolution snapshots.

Our optimal konbini40426 tour is listed in the following TSPLIB-format file.

  • konbini40426.tour

The TSPLIB format for a tour lists in the "TOUR_SECTION" the indices of the points from the Lat-Lng file as they appear in the tour; so a permutation of the numbers from 1 to n.

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).

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, by Carto Basemaps and by Stadia Maps.