Abstract

A fluent economical collaboration between countries is a major need. European flows of trade and people are supported by efficient connections between main localities from a geographic region, in many cases overriding national borders. This paper introduces three traveling salesmen problem instances based on freely available geographic coordinates of the main cities of France, Portugal and Spain. These instances are unified, generating other four larger instances: three with all pairs of countries and one instance with the settlements from all the three countries. The study includes an analysis of quality of solutions for a version of branch & cut algorithm and some hybrid heuristics including the Lin–Kernighan algorithm. $Bor\mathring{u}vka$, Quick$Bor\mathring{u}vka$ and Greedy algorithms are also used in the hybrid approaches in order to obtain a potential beneficent initial solution for the Lin–Kernighan algorithm. Concorde solver, nowadays state-of-the-art exact software, together with the already mentioned algorithms, is used to test and furthermore analyze the new TSP instances. Some results are represented using online services such as Google Maps, showing the potential integration of the Concorde’s optimum results into commercial routing applications. The very good results provided by the Lin–Kernighan method allow its usage for real medium-sized routing instances.