moptipyapps.tsp package

Experiments with the Traveling Salesperson Problem (TSP).

A Traveling Salesperson Problem (TSP) is defined as a fully-connected graph with n_cities nodes. Each edge in the graph has a weight, which identifies the distance between the nodes. The goal is to find the shortest tour that visits every single node in the graph exactly once and then returns back to its starting node. Then nodes are usually called cities. In this file, we present methods for loading instances of the TSP as distance matrices A. In other words, the value at A[i, j] identifies the travel distance from i to j. Such instance data can be loaded via class instance.

In this package, we provide the following tools:

  • instance allows you to load instance data in the TSPLib format and it provides several instances from TSPLib as resources.

  • known_optima provides known optimal solutions for some of the TSPLib instances. These should mainly be used for testing purposes.

  • tour_length is an objective function that can efficiently computed the length of a tour in path representation.

  • tsplib is just a dummy package holding the actual TSPLib data resources.

Important initial work on this code has been contributed by Mr. Tianyu LIANG (梁天宇), <liangty@stu.hfuu.edu.cn> a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

Subpackages

Submodules

moptipyapps.tsp.ea1p1_revn module

A (1+1) EA for the TSP using the reversal move.

A (1+1) EA is basically a local search rls algorithm that starts with a random solution as the current solution x. In each iteration, it samples one new solution from the neighborhood of x and accepts it (as the new x), if it is better or equally good. The algorithm here applies the reversal move, i.e., a two-opt move, as the unary search operator used for sampling the neighborhood of x. The interesting thing about this operator, when applied to the TSP, is that we can compute the tour length of the new solution in O(1) from the tour length of the current solution. This means we can very quickly decide whether the move would be acceptable - and only apply it (in O(n)) if its.

The algorithm implemented here is the same as the basic (1+1) EA with rev operator in the paper [1].

The original version of this code has been contributed by Mr. Tianyu LIANG (梁天宇), <liangty@stu.hfuu.edu.cn> a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

  1. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. In Hisao Ishibuchi, Chee-Keong Kwoh, Ah-Hwee Tan, Dipti Srinivasan, Chunyan Miao, Anupam Trivedi, and Keeley A. Crockett, editors, Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI’22), part of the IEEE Symposium Series on Computational Intelligence (SSCI 2022). December 4-7, 2022, Singapore, pages 360-367. IEEE. https://doi.org/10.1109/SSCI51031.2022.10022296.

  2. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, Iñaki Inza, and S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, 13(2):129-170, April 1999. Kluwer Academic Publishers, The Netherlands. https://doi.org/10.1023/A:1006529012972.

class moptipyapps.tsp.ea1p1_revn.TSPEA1p1revn(instance)[source]

Bases: Algorithm

A (1+1) EA using the reversal operator for the TSP.

log_parameters_to(logger)[source]

Log the parameters of the algorithm to the given logger.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

solve(process)[source]

Apply an RLS = (1+1) EA optimization process with reversing operator.

Parameters:

process (Process) – the process instance which provides random numbers, functions for creating, copying, and evaluating solutions, as well as the termination criterion

Return type:

None

moptipyapps.tsp.ea1p1_revn.rev_if_not_worse(i, j, n_cities, dist, x, y)[source]

Check a reversal move, apply it if it is better, return new tour length.

Parameters:

  • i (int) – the first, smaller index

  • j (int) – the second, larger index

  • n_cities (int) – the number of cities

  • dist (ndarray) – the problem instance

  • x (ndarray) – the candidate solution

  • y (int) – the tour length

Return type:

int

moptipyapps.tsp.fea1p1_revn module

A (1+1) FEA for the TSP using the reversal move.

A (1+1) FEA is the same as the (1+1) EA with Frequency Fitness Assignment. The (1+1) EA using the same search operator as this algorithm here is implemented in module ea1p1_revn. The algorithm implemented here is the same as the basic (1+1) FEA with rev operator in the paper [1].

The original version of this code has been contributed by Mr. Tianyu LIANG (梁天宇), <liangty@stu.hfuu.edu.cn> a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

  1. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. In Hisao Ishibuchi, Chee-Keong Kwoh, Ah-Hwee Tan, Dipti Srinivasan, Chunyan Miao, Anupam Trivedi, and Keeley A. Crockett, editors, Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI’22), part of the IEEE Symposium Series on Computational Intelligence (SSCI 2022). December 4-7, 2022, Singapore, pages 360-367. IEEE. https://doi.org/10.1109/SSCI51031.2022.10022296.

  2. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, Iñaki Inza, and S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, 13(2):129-170, April 1999. Kluwer Academic Publishers, The Netherlands. https://doi.org/10.1023/A:1006529012972.

class moptipyapps.tsp.fea1p1_revn.TSPFEA1p1revn(instance, do_log_h=False)[source]

Bases: Algorithm

A (1+1) FEA using the reversal operator for the TSP.

do_log_h: Final[bool]

shall we log the h-table`?

instance: Final[Instance]

the instance

log_parameters_to(logger)[source]

Log the parameters of the algorithm to the given logger.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

solve(process)[source]

Apply a (1+1) FEA optimization process with reversing operator.

Parameters:

process (Process) – the process instance which provides random numbers, functions for creating, copying, and evaluating solutions, as well as the termination criterion

Return type:

None

moptipyapps.tsp.fea1p1_revn.rev_if_h_not_worse(i, j, n_cities, dist, h, x, y)[source]

Apply a reversal move if its tour length frequency is not worse.

Parameters:

  • i (int) – the first, smaller index

  • j (int) – the second, larger index

  • n_cities (int) – the number of cities

  • dist (ndarray) – the problem instance

  • h (ndarray) – the frequency table

  • x (ndarray) – the candidate solution

  • y (int) – the tour length

Return type:

int

moptipyapps.tsp.instance module

An instance of the Traveling Salesperson Problem (TSP) as distance matrix.

An instance of the Traveling Salesperson Problem (TSP) is defined as a fully-connected graph with Instance.n_cities nodes. Each edge in the graph has a weight, which identifies the distance between the nodes. The goal is to find the shortest tour that visits every single node in the graph exactly once and then returns back to its starting node. Then nodes are usually called cities. In this file, we present methods for loading instances of the TSP as distance matrices A. In other words, the value at A[i, j] identifies the travel distance from i to j.

We can load files in a subset of the TSPLib format [1, 2] and also include the instances of TSPLib with no more than 2000 cities. We load instances as full distance matrices, which makes writing algorithms to solve them easier but handling instances with more than 2000 cities problematic due to the high memory consumption. Of course, you could still load them, but it would be ill-advised to do so on a normal PC (at the time of this writing).

The TSPLib contains many instances of the symmetric TSP, where the distance A[i, j] from city i to city j is the same as the distance A[j, i] from j to i. Here, we provide 111 of them as resource. The cities of some of these instances are points in the Euclidean plain and the distances are the (approximate) Euclidean distances. Others use geographical coordinates (longitude/latitude), and yet others are provides as distances matrices directly. We also provide 19 of the asymmetric TSPLib instances, where the distance A[i, j] from i to j may be different from the distance A[j, i] from j to i.

You can obtain lists of either all, only the symmetric, or only the asymmetric instance resources via

>>> print(Instance.list_resources()[0:10])  # get all instances (1..10)
('a280', 'ali535', 'att48', 'att532', 'bayg29', 'bays29', 'berlin52', 'bier127', 'br17', 'brazil58')

>>> print(Instance.list_resources(asymmetric=False)[0:10])  # only symmetric
('a280', 'ali535', 'att48', 'att532', 'bayg29', 'bays29', 'berlin52', 'bier127', 'brazil58', 'brg180')

>>> print(Instance.list_resources(symmetric=False)[0:10])  # only asymmetric
('br17', 'ft53', 'ft70', 'ftv170', 'ftv33', 'ftv35', 'ftv38', 'ftv44', 'ftv47', 'ftv55')

You can load any of these instances from the resources via Instance.from_resource() as follows:

>>> inst = Instance.from_resource("a280")
>>> print(inst.n_cities)
280

If you want to read an instance from an external TSPLib file, you can use Instance.from_file(). Be aware that not the whole TSPLib standard is supported right now, but only a reasonably large subset.

Every TSP instance automatically provides a lower bound Instance.tour_length_lower_bound and an upper bound Instance.tour_length_upper_bound of the lengths of valid tours. For the TSPLib instances, the globally optimal solutions and their tour lengths are known, so we can use them as lower bounds directly. Otherwise, we currently use a very crude approximation: We assume that, for each city i, the next city j to be visited would be the nearest neighbor of i. Of course, in reality, such a tour may not be feasible, as it could contain disjoint sets of loops. But no tour can be shorter than this. As upper bound, we do the same but assume that j would be the cities farthest away from i.

>>> print(inst.tour_length_lower_bound)
2579
>>> print(inst.tour_length_upper_bound)
65406

It should be noted that all TSPLib instances by definition have integer distances. This means that there are never floating point distances and, for example, Euclidean distances are rounded and are only approximate Euclidean. Then again, since floating point numbers could also only represent things such as sqrt(2) approximately, using integers instead of floating point numbers does not really change anything - distances would be approximately Euclidean or approximately geographical either way.

TSPLib also provides some known optimal solutions in path representation, i.e., as permutations of the numbers 0 to n_cities-1. The optimal solutions corresponding to the instances provides as resources can be obtained via known_optima.

>>> inst = Instance.from_resource("si175")
>>> print(inst.n_cities)
175
>>> inst[0, 1]
113
>>> inst[173, 174]
337
>>> inst[1, 174]
384
>>> inst[2, 174]
384
>>> inst[2, 3]
248
>>> inst[3, 5]
335
>>> inst[4, 6]
134

The original data of TSPLib can be found at <http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/>. Before doing anything with these data directly, you should make sure to read the FAQ <http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html> and the documentation <http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf>.

On 2024-10-18, we added a small eleven city instance based on the car travel distances in km between the Chinese cities Shanghai (上海), Beijing (北京), Nanjing (南京), Hefei (合肥), Harbin (哈尔滨), Kunming (昆明), Wuhan (武汉), Xi’an (西安), Chongqing (重庆), Changsha (长沙), and Hong Kong (香港), determined using BaiDu Maps on 2024-10-18. The optimal solution for this instance has length 9547 (km) and visits the cities in the following order: Shanghai (上海), Nanjing (南京), Hefei (合肥), Wuhan (武汉), Changsha (长沙), Hong Kong (香港), Kunming (昆明), Chongqing (重庆), Xi’an (西安), Beijing (北京), Harbin (哈尔滨). This instance can be used to validate and santity-test algorithms, as its solution can easily be determined using exhaustive enumeration.

Interestingly, it holds that the calculated travel distance from Harbin (哈尔滨) to Kunming (昆明) is longer than the travel distance from Harbin (哈尔滨) to Xi’an (西安) and then from Xi’an (西安) to Kunming (昆明).

  • Harbin (哈尔滨) - Kunming (昆明) = 3781 km

  • Harbin (哈尔滨) - Xi’an (西安) = 2291 km

  • Xi’an (西安) - Kunming (昆明) = 1483 km

  • 2291 km + 1483 km = 3774 km, which is less than 3781 km

This may be because BaiduMaps ranked the paths by travel time and not travel distance, or by any other strange effect I cannot account for. Maybe it is related to which lane of a road one would naturally drive on or lengths of intersections depending on the direction one is coming from. Either way, this shows that this simple instance cn11 may already have interesting properties. It violates the triangle equation and it is non-Euclidean. It is also not based on Geo-coordinates, but on actual street distances and times.

>>> inst = Instance.from_resource("cn11")
>>> inst[0, 0]
0
>>> inst[1, 2]
1007
>>> inst[1, 3]
1017
>>> inst[9, 10]
830
>>> inst[5, 6]
1560

Important initial work on this code has been contributed by Mr. Tianyu LIANG (梁天宇), <liangty@stu.hfuu.edu.cn> a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

  1. Gerhard Reinelt. TSPLIB - A Traveling Salesman Problem Library. ORSA Journal on Computing 3(4):376-384. November 1991. https://doi.org/10.1287/ijoc.3.4.376. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

  2. Gerhard Reinelt. TSPLIB95. Heidelberg, Germany: Universität Heidelberg, Institut für Angewandte Mathematik. 1995. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf

  3. David Lee Applegate, Robert E. Bixby, Vašek Chvátal, and William John Cook. The Traveling Salesman Problem: A Computational Study. Second Edition, 2007. Princeton, NJ, USA: Princeton University Press. Volume 17 of Princeton Series in Applied Mathematics. ISBN: 0-691-12993-2.

  4. Gregory Z. Gutin and Abraham P. Punnen. The Traveling Salesman Problem and its Variations. 2002. Kluwer Academic Publishers. Volume 12 of Combinatorial Optimization. https://doi.org/10.1007/b101971.

  5. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, Iñaki Inza, and Sejla Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review 13(2):129-170. April 1999. https://doi.org/10.1023/A:1006529012972.

  6. Eugene Leighton Lawler, Jan Karel Lenstra, Alexander Hendrik George Rinnooy Kan, and David B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. September 1985. Chichester, West Sussex, UK: Wiley Interscience. In Estimation, Simulation, and Control - Wiley-Interscience Series in Discrete Mathematics and Optimization. ISBN: 0-471-90413-9

  7. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. In Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI’22), part of the IEEE Symposium Series on Computational Intelligence (SSCI’22), December 4-7, 2022, Singapore. Pages 360-367. IEEE. https://doi.org/10.1109/SSCI51031.2022.10022296.

  8. Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. IEEE Computational Intelligence Magazine. 9(3):40-52. August 2014. https://doi.org/10.1109/MCI.2014.2326101.

class moptipyapps.tsp.instance.Instance(name: str, tour_length_lower_bound: int, matrix: ndarray, upper_bound_range_multiplier: int = 1)[source]

Bases: Component, ndarray

An instance of the Traveling Salesperson Problem.

static from_file(path, lower_bound_getter=<built-in method __getitem__ of dict object>)[source]

Read a TSP Lib instance from a TSP-lib formatted file.

Parameters:

  • path (str) – the path to the file

  • lower_bound_getter (Optional[Callable[[str], int]], default: <built-in method __getitem__ of dict object at 0x7f2d51cf11c0>) – a function returning a lower bound for an instance name, or None to use a simple lower bound approximation

Return type:

Instance

Returns:

the instance

>>> from os.path import dirname
>>> inst = Instance.from_file(dirname(__file__) + "/tsplib/br17.atsp")
>>> inst.name
'br17'
static from_resource(name)[source]

Load a TSP instance from a resource.

Parameters:

name (str) – the name string

Return type:

Instance

Returns:

the instance

>>> Instance.from_resource("br17").n_cities
17
is_symmetric: bool

is the TSP instance symmetric?

static list_resources(symmetric=True, asymmetric=True)[source]

Get a tuple of all the TSP instances available as resource.

Parameters:

  • symmetric (bool, default: True) – include the symmetric instances

  • asymmetric (bool, default: True) – include the asymmetric instances

Return type:

tuple[str, ...]

Returns:

the tuple with the instance names

>>> a = len(Instance.list_resources(True, True))
>>> print(a)
111
>>> b = len(Instance.list_resources(True, False))
>>> print(b)
92
>>> c = len(Instance.list_resources(False, True))
>>> print(c)
19
>>> print(a == (b + c))
True
>>> print(len(Instance.list_resources(False, False)))
0
log_parameters_to(logger)[source]

Log the parameters of the instance to the given logger.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

>>> from moptipy.utils.logger import InMemoryLogger
>>> with InMemoryLogger() as l:
...     with l.key_values("I") as kv:
...         Instance.from_resource("kroE100").log_parameters_to(kv)
...     print(repr('@'.join(l.get_log())))
'BEGIN_I@name: kroE100@class: moptipyapps.tsp.instance.Instance@nCities: 100@tourLengthLowerBound: 22068@tourLengthUpperBound: 330799@symmetric: T@dtype: i@END_I'
n_cities: int

the number of cities

name: str

the name of the instance

to_stream(collector, comments=())[source]

Convert this instance to a stream.

Parameters:
Return type:

None

>>> orig = Instance.from_resource("br17")
>>> text = []
>>> orig.to_stream(text.append)
>>> reload = _from_stream(iter(text),
...     lambda _: orig.tour_length_lower_bound)
>>> orig.n_cities == reload.n_cities
True
>>> orig.name == reload.name
True
>>> list(orig.flatten()) == list(reload.flatten())
True

>>> orig = Instance.from_resource("att48")
>>> text = []
>>> orig.to_stream(text.append)
>>> reload = _from_stream(iter(text),
...     lambda _: orig.tour_length_lower_bound)
>>> orig.n_cities == reload.n_cities
True
>>> orig.name == reload.name
True
>>> list(orig.flatten()) == list(reload.flatten())
True

>>> orig = Instance.from_resource("berlin52")
>>> text = []
>>> orig.to_stream(text.append)
>>> reload = _from_stream(iter(text),
...     lambda _: orig.tour_length_lower_bound)
>>> orig.n_cities == reload.n_cities
True
>>> orig.name == reload.name
True
>>> list(orig.flatten()) == list(reload.flatten())
True

>>> orig = Instance.from_resource("ft53")
>>> text = []
>>> orig.to_stream(text.append)
>>> reload = _from_stream(iter(text),
...     lambda _: orig.tour_length_lower_bound)
>>> orig.n_cities == reload.n_cities
True
>>> orig.name == reload.name
True
>>> list(orig.flatten()) == list(reload.flatten())
True
tour_length_lower_bound: int

the lower bound of the tour length

tour_length_upper_bound: int

the upper bound of the tour length

moptipyapps.tsp.instance.ncities_from_tsplib_name(name)[source]

Compute the instance scale from the instance name.

Parameters:

name (str) – the instance name

Return type:

int

Returns:

the instance scale

moptipyapps.tsp.known_optima module

A set of tools to load known optima in the TSPLib format.

The TSPLib provides benchmark instances for the Traveling Salesperson Problem (TSP). We provide a subset of these instances with up to 2000 cities as resources in instance. Additionally, TSPLib provides the optimal solutions for a subset of these instances. Within this module here, we provide methods for reading the optimal solution files in the TSPLib format. We also include as resources the optimal solutions to the instances that our package provide as resources as well.

You can get the list of instance names for which the optimal tours are included in this package via list_resource_tours() and then load a tour from a resource via opt_tour_from_resource(). If you want to read a tour from an external file that obeys the TSPLib format, you can do so via opt_tour_from_file().

  1. Gerhard Reinelt. TSPLIB - A Traveling Salesman Problem Library. ORSA Journal on Computing 3(4):376-384. November 1991. https://doi.org/10.1287/ijoc.3.4.376. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

  2. Gerhard Reinelt. TSPLIB95. Heidelberg, Germany: Universität Heidelberg, Institut für Angewandte Mathematik. 1995. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf

moptipyapps.tsp.known_optima.list_resource_tours()[source]

Get a tuple of the names of the optimal tours in the resources.

>>> list_resource_tours()
('a280', 'att48', 'bayg29', 'bays29', 'berlin52', 'brg180', 'ch130', 'ch150', 'cn11', 'eil101', 'eil51', 'eil76', 'fri26', 'gr120', 'gr202', 'gr24', 'gr48', 'gr666', 'gr96', 'kroA100', 'kroC100', 'kroD100', 'lin105', 'pcb442', 'pr1002', 'pr76', 'rd100', 'st70', 'tsp225', 'ulysses16', 'ulysses22')
Return type:

tuple[str, ...]

Returns:

the tuple

moptipyapps.tsp.known_optima.opt_tour_from_file(path)[source]

Read a known optimal tour from a file.

Parameters:

path (str) – the path to the file

Return type:

ndarray

Returns:

the tour

moptipyapps.tsp.known_optima.opt_tour_from_resource(name)[source]

Load an optimal tour from a resource.

>>> np.array2string(opt_tour_from_resource("ulysses16"))
'[ 0 13 12 11  6  5 14  4 10  8  9 15  2  1  3  7]'

>>> np.array2string(opt_tour_from_resource("cn11"))
'[ 0  2  3  6  9 10  5  8  7  1  4]'
Parameters:

name (str) – the name string

Return type:

ndarray

Returns:

the optimal tour

moptipyapps.tsp.tour_length module

The tour length objective function for tours in path representation.

A Traveling Salesperson Problem (TSP) instance is defined as a fully-connected graph with n_cities nodes. Each edge in the graph has a weight, which identifies the distance between the nodes. The goal is to find the shortest tour that visits every single node in the graph exactly once and then returns back to its starting node. Then nodes are usually called cities. In this file, we present methods for loading instances of the TSP as distance matrices A. In other words, the value at A[i, j] identifies the travel distance from i to j.

A tour can be represented in path representation, which means that it is stored as a permutation of the numbers 0 to n_cities-1. The number at index k identifies that k-th city to visit. So the first number in the permutation identifies the first city, the second number the second city, and so on.

The length of the tour can be computed by summing up the distances from the k-th city to the k+1-st city, for k in 0..n_cities-2 and then adding the distance from the last city to the first city. This is what the function tour_length() is doing. This function is then wrapped as objective function object in TourLength.

Important initial work on this code has been contributed by Mr. Tianyu LIANG (梁天宇), <liangty@stu.hfuu.edu.cn> a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

  1. Gerhard Reinelt. TSPLIB - A Traveling Salesman Problem Library. ORSA Journal on Computing 3(4):376-384. November 1991. https://doi.org/10.1287/ijoc.3.4.376. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

  2. Gerhard Reinelt. TSPLIB95. Heidelberg, Germany: Universität Heidelberg, Institut für Angewandte Mathematik. 1995. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf

  3. David Lee Applegate, Robert E. Bixby, Vašek Chvátal, and William John Cook. The Traveling Salesman Problem: A Computational Study. Second Edition, 2007. Princeton, NJ, USA: Princeton University Press. Volume 17 of Princeton Series in Applied Mathematics. ISBN: 0-691-12993-2.

  4. Gregory Z. Gutin and Abraham P. Punnen. The Traveling Salesman Problem and its Variations. 2002. Kluwer Academic Publishers. Volume 12 of Combinatorial Optimization. https://doi.org/10.1007/b101971.

  5. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, Iñaki Inza, and Sejla Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review 13(2):129-170. April 1999. https://doi.org/10.1023/A:1006529012972.

  6. Eugene Leighton Lawler, Jan Karel Lenstra, Alexander Hendrik George Rinnooy Kan, and David B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. September 1985. Chichester, West Sussex, UK: Wiley Interscience. In Estimation, Simulation, and Control - Wiley-Interscience Series in Discrete Mathematics and Optimization. ISBN: 0-471-90413-9

  7. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. In Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI’22), part of the IEEE Symposium Series on Computational Intelligence (SSCI’22), December 4-7, 2022, Singapore. Pages 360-367. IEEE. https://doi.org/10.1109/SSCI51031.2022.10022296.

  8. Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. IEEE Computational Intelligence Magazine. 9(3):40-52. August 2014. https://doi.org/10.1109/MCI.2014.2326101.

class moptipyapps.tsp.tour_length.TourLength(instance)[source]

Bases: Objective

The tour length objective function.

evaluate(x)[source]

Compute the length of a tour in path representation.

Parameters:

x – the tour in path representation

Return type:

int

Returns:

the tour length

instance: Final[Instance]

the TSP instance we are trying to solve

log_parameters_to(logger)[source]

Log the parameters of the space to the given logger.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

lower_bound()[source]

Get the lower bound of the tour length.

Return type:

int

Returns:

the lower bound of the tour length

upper_bound()[source]

Get the upper bound of the tour length.

Return type:

int

Returns:

the upper bound of the tour length

moptipyapps.tsp.tour_length.tour_length(instance, x)[source]

Compute the length of a tour.

Parameters:
Return type:

int

Returns:

the length of the tour x