Home › Page › Romanian TSP instance and Swiss TSP instance

Romanian TSP instance and Swiss TSP instance

(Cerasela Crişan, Camelia Pintea)

Limba română

Also at the TSP main page.

The Romanian TSP instance with GPS coordinates is the first of this type. In the following it is defined, solved, and represented using GIS-based tools. We hope that this new approach will enhance the connections with research in Logistics, Transportation, Geoinformatics and Geoengineering.

The two variants for the Romanian instance

The traveling cost between cities is specified by the orthodromic (great-circle) distance rounded to the nearest whole number (the TSPLIB Geographical distance, page 7 in Documentation). The instance has 2950 human settlements with administrative autonomy in Romania. The data were derived from the on-line repository (in Romanian). The author Vasile Crăciunescu confirmed that the data can be used for research, as they are public, offered under the permissive license CC BY-SA 3.0.

The Romanian instance ro2950_geo.tsp follows the TSPLIB format, with only 2 digits for the minutes. The distances are integer kilometers. The instance ro2950_geom.tsp uses the GEOM norm, employed for the TSP World Instance, adjusted to handle decimal degrees and scaled to provide the distance in meters.

The GPSVisualizer tool was used to create the instance map. An image is here.

The exact solutions

The instances were solved using the public package Concorde. The integer solution for ro2950_geo.tsp is 21683 (kilometers), and the path is here. The integer solution for ro2950_geom.tsp is 20338171 (meters), and the path is here. The GEOM solution map is here. An image is here, and a GIF file is here.

p1p2

 

ro2950_geom.tsp instance                                                                                                                                                                      ro2950_geom.tsp solution

Earth_capture

Google Earth capture

The Swiss TSP instance

The Swiss TSP instance was designed and solved during a Swiss National Science Foundation Research project at IDSIA, Manno, Switzerland between 01.01.2017 and 28.02.2017. The instance has 4156 nodes, specified by the GPS coordinates of Swiss localities with postcodes.
The optimum path to the instance is:
Swiss_capture

Limba română


Semnalată de asemenea pe pagina principală TSP.

Instanţa TSP bazată pe coordonate GPS ale localităţilor din România este prima de acest fel din lume. În continuare este descrisă, rezolvată şi reprezentată folosind instrumente GIS. Prin această cercetare sperăm să realizăm noi conexiuni cu importante domenii precum Logistica, Transporturile, Geoinformatica şi Ingineria Geologică.

Cele două variante ale instanţei

Lungimea drumului dintre două noduri ale instanţei este distanţa geodezică, exprimată prin cel mai apropiat întreg (distanţa TSPLIB descrisă la pagina 7 din Documentaţie). Instanţa are 2950 localităţi cu autonomie administrativă din România, preluate din colecţie. Autorul Vasile Crăciunescu a confirmat că datele sunt libere pentru utilizare ştiinţifică, fiind puse la dispoziţie sub licenţa CC BY-SA 3.0.

Versiunea ro2950_geo.tsp respectă formatul TSPLIB, cu două zecimale pentru minute. Distanţa este exprimată in kilometri. Versiunea ro2950_geom.tsp foloseşte norma GEOM, utilizată pentru prima dată la World Instance, destinată coordonatelor zecimale şi exprimată în metri.

Aplicaţia GPSVisualizer a fost folosită pentru realizarea hărţii instanţei. O captură de ecran se află aici.

Soluţiile exacte

Pachetul public de aplicaţii Concorde a fost utilizat pentru rezolvarea celor două versiuni. Soluţia întreagă pentru ro2950_geo.tsp măsoară 21683 (kilometri), iar circuitul este aici. Soluţia întreagă pentru ro2950_geom.tsp are 20338171 (metri), circuitul corespunzător fiind aici. Harta versiunii GEOM este aici. O captură de ecran este aici, iar un fişier GIF este aici.

Flag Counter