Coverage for moptipyapps / tsp / tour_length.py: 79%

1""" 

2The tour length objective function for tours in path representation. 

3 

4A Traveling Salesperson Problem (TSP) instance is defined as a 

5fully-connected graph with 

6:attr:`~moptipyapps.tsp.instance.Instance.n_cities` nodes. Each edge in the 

7graph has a weight, which identifies the distance between the nodes. The goal 

8is to find the *shortest* tour that visits every single node in the graph 

9exactly once and then returns back to its starting node. Then nodes are 

10usually called cities. In this file, we present methods for loading instances 

11of the TSP as distance matrices `A`. In other words, the value at `A[i, j]` 

12identifies the travel distance from `i` to `j`. 

13 

14A tour can be represented in path representation, which means that it is 

15stored as a permutation of the numbers `0` to `n_cities-1`. The number at 

16index `k` identifies that `k`-th city to visit. So the first number in the 

17permutation identifies the first city, the second number the second city, 

18and so on. 

19 

20The length of the tour can be computed by summing up the distances from the 

21`k`-th city to the `k+1`-st city, for `k` in `0..n_cities-2` and then adding 

22the distance from the last city to the first city. This is what the function 

23:func:`tour_length` is doing. This function is then wrapped as objective 

24function object in :class:`TourLength`. 

25 

26Important initial work on this code has been contributed by Mr. Tianyu LIANG 

27(梁天宇), <liangty@stu.hfuu.edu.cn> a Master's student at the Institute of 

28Applied Optimization (应用优化研究所) of the School 

29of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei 

30University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the 

31supervision of Prof. Dr. Thomas Weise (汤卫思教授). 

32 

331. Gerhard Reinelt. TSPLIB - A Traveling Salesman Problem Library. 

34 *ORSA Journal on Computing* 3(4):376-384. November 1991. 

35 https://doi.org/10.1287/ijoc.3.4.376. 

36 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ 

372. Gerhard Reinelt. *TSPLIB95.* Heidelberg, Germany: Universität 

38 Heidelberg, Institut für Angewandte Mathematik. 1995. 

39 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf 

403. David Lee Applegate, Robert E. Bixby, Vašek Chvátal, and William John Cook. 

41 *The Traveling Salesman Problem: A Computational Study.* Second Edition, 

42 2007. Princeton, NJ, USA: Princeton University Press. Volume 17 of 

43 Princeton Series in Applied Mathematics. ISBN: 0-691-12993-2. 

444. Gregory Z. Gutin and Abraham P. Punnen. *The Traveling Salesman Problem and 

45 its Variations.* 2002. Kluwer Academic Publishers. Volume 12 of 

46 Combinatorial Optimization. https://doi.org/10.1007/b101971. 

475. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, Iñaki Inza, and 

48 Sejla Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A 

49 Review of Representations and Operators. *Artificial Intelligence Review* 

50 13(2):129-170. April 1999. https://doi.org/10.1023/A:1006529012972. 

516. Eugene Leighton Lawler, Jan Karel Lenstra, Alexander Hendrik George Rinnooy 

52 Kan, and David B. Shmoys. *The Traveling Salesman Problem: A Guided Tour of 

53 Combinatorial Optimization.* September 1985. Chichester, West Sussex, UK: 

54 Wiley Interscience. In Estimation, Simulation, and 

55 Control - Wiley-Interscience Series in Discrete Mathematics and 

56 Optimization. ISBN: 0-471-90413-9 

577. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. 

58 Solving the Traveling Salesperson Problem using Frequency Fitness 

59 Assignment. In *Proceedings of the IEEE Symposium on Foundations of 

60 Computational Intelligence (IEEE FOCI'22),* part of the *IEEE Symposium 

61 Series on Computational Intelligence (SSCI'22),* December 4-7, 2022, 

62 Singapore. Pages 360-367. IEEE. 

63 https://doi.org/10.1109/SSCI51031.2022.10022296. 

648. Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, 

65 Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization 

66 Algorithms: An Open Source Framework for the Traveling Salesman Problem. 

67 *IEEE Computational Intelligence Magazine.* 9(3):40-52. August 2014. 

68 https://doi.org/10.1109/MCI.2014.2326101. 

69""" 

70 

71from typing import Final 

72 

73import numba # type: ignore 

74import numpy as np 

75from moptipy.api.objective import Objective 

76from moptipy.utils.logger import KeyValueLogSection 

77from pycommons.types import type_error 

78 

79from moptipyapps.tsp.instance import Instance 

80from moptipyapps.utils.shared import SCOPE_INSTANCE 

81 

82 

83@numba.njit(cache=True, inline="always", fastmath=False, boundscheck=False) 

84def tour_length(instance: np.ndarray, x: np.ndarray) -> int: 

85 """ 

86 Compute the length of a tour. 

87 

88 :param instance: the distance matrix 

89 :param x: the tour 

90 :return: the length of the tour `x` 

91 """ 

92 result: int = 0 

93 last: int = x[-1] 

94 for cur in x: 

95 result += instance[last, cur] 

96 last = cur 

97 return result 

98 

99 

100class TourLength(Objective): 

101 """The tour length objective function.""" 

102 

103 def __init__(self, instance: Instance) -> None: 

104 """ 

105 Initialize the tour length objective function. 

106 

107 :param instance: the tsp instance 

108 """ 

109 if not isinstance(instance, Instance): 

110 raise type_error(instance, "instance", Instance) 

111 #: the TSP instance we are trying to solve 

112 self.instance: Final[Instance] = instance 

113 

114 def evaluate(self, x) -> int: 

115 """ 

116 Compute the length of a tour in path representation. 

117 

118 :param x: the tour in path representation 

119 :return: the tour length 

120 """ 

121 return tour_length(self.instance, x) 

122 

123 def lower_bound(self) -> int: 

124 """ 

125 Get the lower bound of the tour length. 

126 

127 :return: the lower bound of the tour length 

128 """ 

129 return self.instance.tour_length_lower_bound 

130 

131 def upper_bound(self) -> int: 

132 """ 

133 Get the upper bound of the tour length. 

134 

135 :return: the upper bound of the tour length 

136 """ 

137 return self.instance.tour_length_upper_bound 

138 

139 def __str__(self): 

140 """ 

141 Get the name of this objective function: always "tourLength". 

142 

143 :return: "tourLength" 

144 :retval "tourLength": always 

145 """ 

146 return "tourLength" 

147 

148 def log_parameters_to(self, logger: KeyValueLogSection) -> None: 

149 """ 

150 Log the parameters of the space to the given logger. 

151 

152 :param logger: the logger for the parameters 

153 """ 

154 super().log_parameters_to(logger) 

155 with logger.scope(SCOPE_INSTANCE) as kv: 

156 self.instance.log_parameters_to(kv)