(Cerasela Crişan, Camelia Pintea)
Limba română
Also at the TSP main page.
NEWS!
A tentative world-record based on data here presented was successfully performed and is expecting the validation:
radio digi24 newspaper
The Romanian tour with an electric car is presented at Electric Tour
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.
ro2950_geom.tsp instance ro2950_geom.tsp solution
Google Earth caption
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:
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.