## 6 Computational Results
### TSP Implementation in GAMS
The optimal route can be seen in Figure 4.

Finally, GAMS for the kroA100.tsp benchmark stopped the computation at 1000.02 s by exceeding the time limit, but the intermediate result of the path length 21282 and its traversal through positions 1, 47, 93, 28, 67, 58, 61, 51, 87, 25, 81, 69, 64, 40, 54, 2, 44, 50, 73, 68, 85, 82, 95, 13, 76, 33, 37, 5, 52, 78, 96, 39, 30, 48, 100, 41, 71, 14, 3, 43, 46, 29, 34, 83, 55, 7, 9, 57, 20, 12, 27, 86, 35, 62, 60, 77, 23, 98, 91, 45, 32, 11, 15, 17, 59, 74, 21, 72, 10, 84, 36, 99, 38, 24, 18, 79, 53, 88, 16, 94, 22, 70, 66, 26, 65, 4, 97, 56, 80, 31, 89, 42, 8, 92, 75, 19, 90, 49, 6, 63, 1 corresponds to the known optimal solution for this benchmark. The optimal route is in Figure 5.

For instances with more than 100 positions, it would be necessary to search for an approximation of the optimum using one of the heuristic methods. One of the first was the use of the so-called _Lin-2-Opt change operator_[8], see Figure 6. Here, two elements are added to the permutation of \(n\) cities to visit (into positions 0 and \(n+1\)), and then the starting city is assigned to those positions to simulate a cyclic tour. Two 'edges' (pairs of neighbouring elements in permutation) are randomly chosen \(((p_{1},p_{2})\) and

Figure 4: The optimal route for the berlin52.tsp benchmark. Figure 5: The optimal route for the kroA100.tsp benchmark. \((q_{1},q_{2})\) say), the inner elements \(p_{2}\), \(q_{1}\) are swapped and the elements between \(p_{2}\) and \(q_{1}\) are reversed. Positions 0 and \(n+1\) with the fixed value of the starting city can also be used to expand the individuals in the population of the genetic algorithm and then apply the operations presented for the PFSSP. However, we no longer investigate this for extremely large instances of the TSP problem because heuristics do not guarantee finding an optimal solution, which often is not even known here, and the aim was to find bounds for which we still obtain the precise solution in reasonable time using a 'normal' computer. In the case of GAMS, this bound is an instance with 100 cities. ### Data, Changes in Time, Uncertainty

Data from OR-Library and TSPLIB are related to a specific point in time, in reality they may change over time or may not be completely known. A more general case of the Travelling Salesman Problem is the _Canadian Traveller Problem_ (CTP) [84; 85]. Here, the distance matrix may change over time due to the occurrence of events that make some parts of the route inaccessible so that an adaptive strategy must be found. These events are random in nature, which corresponds to the problems of robot navigation in environments where the distribution of obstacles is only discovered as the robot moves through the environment; moreover, the obstacles may move, and thus the locations of potential collisions change dynamically. In transport tasks, the values of some parameters can change over time, the fuel price is not constant, and the vehicle consumption can only be estimated because it can change according to the traffic situation and the season, which will affect, e.g., the calculation of the objective function (69). Similarly, in the crop problem, we can only estimate crop yields. In location-based tasks, the problem may arise of adding another center to an existing network of centers to improve the coverage of an area. An example might be an expansion of the existing supermarket network of a chain store. Here it is suggested to use one of the properties of the Voronoi diagram [86; 87], a data structure known from computational geometry: Assume a Voronoi diagram with its sites represented by the current centers. The point \(q\) is the vertex of the Voronoi diagram if and only if the _largest empty circle_\(C(q)\) contains three (or more in a degenerate case) sites on its boundary and none inside.