.. note:: :class: sphx-glr-download-link-note Click :ref:`here ` to download the full example code .. rst-class:: sphx-glr-example-title .. _sphx_glr_source_auto_examples_permutation_plot_tsp.py: ================================= Travelling salesman problem (TSP) ================================= .. note::example taken from `Google OR-Tools `_ The travelling salesman problem (TSP) concerns on finding the shortest possible route linking a given list of cities and their distances. The TSP is one of the most famous problems in computer science and it belongs to the class of NP-Complete problems. The Travelling salesman problem have many important applications, from route planning to the manufacture of microchips. But, in essence, it can be formulated as to find the minimum path that links each node in a weighted graph. .. image:: /images/tsp.svg Using ``psopt.Permutation`` we can generate many instances that use different paths. Then, those paths that have yielded the best results guide the other particles on finding better results throughout iterations. Below we see the progress of the algorithm: .. image:: /source/auto_examples/permutation/images/sphx_glr_plot_tsp_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out Out: .. code-block:: none Iteration 0: global_best: 9575.000 iteration_best: 9575.000 Iteration 1: global_best: 9575.000 iteration_best: 10765.000 Iteration 2: global_best: 9482.000 iteration_best: 9482.000 Iteration 3: global_best: 9482.000 iteration_best: 10256.000 Iteration 4: global_best: 9269.000 iteration_best: 9269.000 Iteration 5: global_best: 8446.000 iteration_best: 8446.000 Iteration 6: global_best: 8083.000 iteration_best: 8083.000 Iteration 7: global_best: 8083.000 iteration_best: 8083.000 Iteration 8: global_best: 8083.000 iteration_best: 8232.000 Iteration 9: global_best: 8083.000 iteration_best: 8083.000 Iteration 10: global_best: 7755.000 iteration_best: 7755.000 Iteration 11: global_best: 7755.000 iteration_best: 7888.000 Iteration 12: global_best: 7698.000 iteration_best: 7698.000 Iteration 13: global_best: 7578.000 iteration_best: 7578.000 Iteration 14: global_best: 7578.000 iteration_best: 8597.000 Iteration 15: global_best: 7578.000 iteration_best: 8155.000 Iteration 16: global_best: 7578.000 iteration_best: 8160.000 Iteration 17: global_best: 7578.000 iteration_best: 7578.000 Iteration 18: global_best: 7578.000 iteration_best: 7716.000 Iteration 19: global_best: 7578.000 iteration_best: 7658.000 Iteration 20: global_best: 7578.000 iteration_best: 8503.000 Iteration 21: global_best: 7310.000 iteration_best: 7310.000 Iteration 22: global_best: 7310.000 iteration_best: 7618.000 Iteration 23: global_best: 7310.000 iteration_best: 7310.000 Iteration 24: global_best: 7310.000 iteration_best: 7310.000 Iteration 25: global_best: 7310.000 iteration_best: 7310.000 Iteration 26: global_best: 7310.000 iteration_best: 8187.000 Iteration 27: global_best: 6652.000 iteration_best: 6652.000 Iteration 28: global_best: 6652.000 iteration_best: 7433.000 Iteration 29: global_best: 6652.000 iteration_best: 7391.000 Iteration 30: global_best: 6652.000 iteration_best: 6796.000 Iteration 31: global_best: 6652.000 iteration_best: 6652.000 Iteration 32: global_best: 6652.000 iteration_best: 6652.000 Iteration 33: global_best: 6332.000 iteration_best: 6332.000 Iteration 34: global_best: 6332.000 iteration_best: 6332.000 Iteration 35: global_best: 6332.000 iteration_best: 7056.000 Iteration 36: global_best: 6332.000 iteration_best: 6574.000 Iteration 37: global_best: 6329.000 iteration_best: 6329.000 Iteration 38: global_best: 6329.000 iteration_best: 6652.000 Iteration 39: global_best: 6329.000 iteration_best: 6897.000 Iteration 40: global_best: 6329.000 iteration_best: 6329.000 Iteration 41: global_best: 6323.000 iteration_best: 6323.000 Iteration 42: global_best: 6323.000 iteration_best: 6323.000 Iteration 43: global_best: 6245.000 iteration_best: 6245.000 Iteration 44: global_best: 6245.000 iteration_best: 6323.000 Iteration 45: global_best: 6245.000 iteration_best: 6323.000 Iteration 46: global_best: 6245.000 iteration_best: 6245.000 Iteration 47: global_best: 6245.000 iteration_best: 6751.000 Iteration 48: global_best: 6245.000 iteration_best: 6525.000 Iteration 49: global_best: 6245.000 iteration_best: 6245.000 Iteration completed ========================== Exit code 0: Algortihm reached the maximum limit of 50 iterations Elapsed time 0.138 50 iterations Best selection: [7, 0, 2, 9, 3, 10, 5, 4, 11, 1, 8, 12, 6] Best evaluation: 6245.0 | .. code-block:: default import functools from psopt import Permutation def main(): def get_route_cost(x, initial_cost, distance_matrix): # define initial route cost route_cost = initial_cost for i in range(len(x) - 1): route_cost += distance_matrix[x[i]][x[i + 1]] return route_cost # define distances between 13 cities distance_matrix = [ [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972], [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579], [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260], [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987], [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371], [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999], [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701], [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099], [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600], [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162], [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200], [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504], [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0], ] obj_func = functools.partial( get_route_cost, initial_cost=0, distance_matrix=distance_matrix ) candidates = list(range(len(distance_matrix))) # instantiate the optimizer opt = Permutation(obj_func, candidates) # minimize the obj function solution = opt.minimize( verbose=1, max_iter=50, population=15, early_stop=25, seed=0 ) solution.history.plot("global_best") if __name__ == "__main__": main() .. rst-class:: sphx-glr-timing **Total running time of the script:** ( 0 minutes 0.298 seconds) .. _sphx_glr_download_source_auto_examples_permutation_plot_tsp.py: .. only :: html .. container:: sphx-glr-footer :class: sphx-glr-footer-example .. container:: sphx-glr-download :download:`Download Python source code: plot_tsp.py ` .. container:: sphx-glr-download :download:`Download Jupyter notebook: plot_tsp.ipynb ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_