{"id":212,"date":"2021-01-23T22:24:31","date_gmt":"2021-01-23T22:24:31","guid":{"rendered":"https:\/\/www.kindsonthegenius.com\/data-science\/?p=212"},"modified":"2021-01-23T22:25:17","modified_gmt":"2021-01-23T22:25:17","slug":"solving-the-travelling-salesman-problem-tsp-with-python","status":"publish","type":"post","link":"https:\/\/www.kindsonthegenius.com\/data-science\/solving-the-travelling-salesman-problem-tsp-with-python\/","title":{"rendered":"Solving the Travelling Salesman Problem (TSP) with Python"},"content":{"rendered":"

In this tutorial, we would see how to solve the TSP problem in Python. The following sections are covered.<\/p>\n

    \n
  1. Approach to Solving the TSP Problem<\/a><\/li>\n
  2. The Routing Model and Index Manager<\/a><\/li>\n
  3. The Distance Callback<\/a><\/li>\n
  4. Travel Cost and Search Parameters<\/a><\/li>\n
  5. Function to the Print the Solution<\/a><\/li>\n
  6. Putting it all Together<\/a><\/li>\n<\/ol>\n

     <\/p>\n

    1. Approach to Solving the TSP Problem<\/strong><\/h4>\n

    To be able to solve a TSP problem in Python, we need the following items:<\/p>\n

      \n
    • List of cities<\/li>\n
    • List of distances between the cities<\/li>\n
    • Number of vehicles<\/li>\n
    • Starting location of the vehicles<\/li>\n<\/ul>\n

      List of Cities<\/strong><\/p>\n

      In this problem we have a list of 12 cities. They are listed below. The indices of the cities are provided against the name.<\/p>\n

      0. New York – 1. Los Angeles – 2. Chicago – 3. Minneapolis – 4. Denver – 5. Dallas – 6. Seattle – 7. Boston – 8. San Francisco – 9. St. Louis – 10. Houston – 11. Phoenix – 12. Salt Lake City<\/em><\/p>\n

       <\/p>\n

      List of Distances<\/strong><\/p>\n

      It is normally better to represent the list of distances as a square matrix with intersecting cells holding distance between the row and column headers. If we use indexes i and j for this matrix, then data[i][j] is the distance between city i and city j.<\/p>\n

      data['distance_matrix'<\/span>] =<\/span> [\r\n    [0<\/span>, 2451<\/span>, 713<\/span>, 1018<\/span>, 1631<\/span>, 1374<\/span>, 2408<\/span>, 213<\/span>, 2571<\/span>, 875<\/span>, 1420<\/span>, 2145<\/span>, 1972<\/span>],\r\n    [2451<\/span>, 0<\/span>, 1745<\/span>, 1524<\/span>, 831<\/span>, 1240<\/span>, 959<\/span>, 2596<\/span>, 403<\/span>, 1589<\/span>, 1374<\/span>, 357<\/span>, 579<\/span>],\r\n    [713<\/span>, 1745<\/span>, 0<\/span>, 355<\/span>, 920<\/span>, 803<\/span>, 1737<\/span>, 851<\/span>, 1858<\/span>, 262<\/span>, 940<\/span>, 1453<\/span>, 1260<\/span>],\r\n    [1018<\/span>, 1524<\/span>, 355<\/span>, 0<\/span>, 700<\/span>, 862<\/span>, 1395<\/span>, 1123<\/span>, 1584<\/span>, 466<\/span>, 1056<\/span>, 1280<\/span>, 987<\/span>],\r\n    [1631<\/span>, 831<\/span>, 920<\/span>, 700<\/span>, 0<\/span>, 663<\/span>, 1021<\/span>, 1769<\/span>, 949<\/span>, 796<\/span>, 879<\/span>, 586<\/span>, 371<\/span>],\r\n    [1374<\/span>, 1240<\/span>, 803<\/span>, 862<\/span>, 663<\/span>, 0<\/span>, 1681<\/span>, 1551<\/span>, 1765<\/span>, 547<\/span>, 225<\/span>, 887<\/span>, 999<\/span>],\r\n    [2408<\/span>, 959<\/span>, 1737<\/span>, 1395<\/span>, 1021<\/span>, 1681<\/span>, 0<\/span>, 2493<\/span>, 678<\/span>, 1724<\/span>, 1891<\/span>, 1114<\/span>, 701<\/span>],\r\n    [213<\/span>, 2596<\/span>, 851<\/span>, 1123<\/span>, 1769<\/span>, 1551<\/span>, 2493<\/span>, 0<\/span>, 2699<\/span>, 1038<\/span>, 1605<\/span>, 2300<\/span>, 2099<\/span>],\r\n    [2571<\/span>, 403<\/span>, 1858<\/span>, 1584<\/span>, 949<\/span>, 1765<\/span>, 678<\/span>, 2699<\/span>, 0<\/span>, 1744<\/span>, 1645<\/span>, 653<\/span>, 600<\/span>],\r\n    [875<\/span>, 1589<\/span>, 262<\/span>, 466<\/span>, 796<\/span>, 547<\/span>, 1724<\/span>, 1038<\/span>, 1744<\/span>, 0<\/span>, 679<\/span>, 1272<\/span>, 1162<\/span>],\r\n    [1420<\/span>, 1374<\/span>, 940<\/span>, 1056<\/span>, 879<\/span>, 225<\/span>, 1891<\/span>, 1605<\/span>, 1645<\/span>, 679<\/span>, 0<\/span>, 1017<\/span>, 1200<\/span>],\r\n    [2145<\/span>, 357<\/span>, 1453<\/span>, 1280<\/span>, 586<\/span>, 887<\/span>, 1114<\/span>, 2300<\/span>, 653<\/span>, 1272<\/span>, 1017<\/span>, 0<\/span>, 504<\/span>],\r\n    [1972<\/span>, 579<\/span>, 1260<\/span>, 987<\/span>, 371<\/span>, 999<\/span>, 701<\/span>, 2099<\/span>, 600<\/span>, 1162<\/span>, 1200<\/span>, 504<\/span>, 0<\/span>],\r\n] \r\n<\/pre>\n
       <\/p>\n
      Number of Vehicles<\/strong><\/p>\n
      In this case, since it a TSP, the number of vehicles is 1. The Python code is<\/p>\n
      data['no_of_vehicles'<\/span>] =<\/span> 1<\/span>\r\n<\/pre>\n
       <\/p>\n
      Starting Point<\/strong><\/p>\n
      In this example, the starting point or ‘depot’ is location 0, that is New York.<\/p>\n
      data['depot'<\/span>] =<\/span> 0<\/span>\r\n<\/pre>\n
       <\/p>\n
      2. The Routing Model and Index Manager<\/strong><\/h4>\n
      To solve the TSP in Python, you need to create the RoutingIndexManager and the RoutingModel. The RoutingIndexManager manages conversion between the internal solver variables and NodeIndexes. In this way, we can simply use the NodeIndex in our programs.<\/p>\n
      The RoutingIndexManager takes three parameters:<\/p>\n
        \n
      • number of location, including the depot (number of rows of the distance matrix<\/li>\n
      • number of vehicles<\/li>\n
      • the starting node (depot node)<\/li>\n<\/ul>\n
        The code below creates the\u00a0 routing model and index manager<\/p>\n
        data =<\/span> create_data_model() # call the create_data_model() function<\/span>\r\n\r\nmanager =<\/span> pywrapcp.<\/span>RoutingIndexManager(\r\n    len<\/span>(data['distance_matrix'<\/span>]), \r\n    data['no_of_vehicles'<\/span>],\r\n    data['depot'<\/span>])\r\n\r\nrouting =<\/span> pywrapcp.<\/span>RoutingModel(manager)\r\n<\/pre>\n
         <\/p>\n
        3. The Distance Callback<\/strong><\/h4>\n
        To be able to use the solver,\u00a0 we need to create a distance callback. What is a distance callback? This is a function that takes two locations and returns the distance between them. Since these distances are available in the distance matrix, then we can use the distance matrix. The two functions passed to the distance callback are routing variable indexes, so we need to convert them to distance matrix NodeIndex using IndexToNode() method from the RoutingIndexManager.<\/p>\n
        The code below does that<\/p>\n
        # Gives the distance between two nodes<\/span>\r\ndef<\/span> distance_callback<\/span>(from_index, to_index):\r\n    \r\n    # Convert routing variable Index to distance matrix NodeIndex.<\/span>\r\n    from_node =<\/span> manager.<\/span>IndexToNode(from_index)\r\n    to_node =<\/span> manager.<\/span>IndexToNode(to_index)\r\n    return<\/span> data['distance_matrix'<\/span>][from_node][to_node]\r\n\r\ntransit_callback_index =<\/span> routing.<\/span>RegisterTransitCallback(distance_callback)\r\n<\/pre>\n
         
        \n<\/p>\n
        4. The Travel Cost and Search Parameters<\/h4>\n
        <\/strong>
        \nThe cost of travel is the cost to travel the distance between two nodes. In the case of the solver, you need to set an arc cost evaluator function that does this calculation. This function takes as parameter the transit_callback_index returned by the distance_callback. In our case, the travel cost is simply the distance between the locations.<\/p>\n
        However, in a real world scenario, there may be other factors to be considered.<\/p>\n
        routing.<\/span>SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\r\n<\/pre>\n
         <\/p>\n
        We also need to set the search parameters as well as the heuristic for finding the first solution. In this case, the strategy is PATH_CHEAPEST_ARCH. This heuristic repeatedly adds edge with the least weight that don’t lead to a previously visited node..<\/p>\n
        search_parameters =<\/span> pywrapcp.<\/span>DefaultRoutingSearchParameters()\r\nsearch_parameters.<\/span>first_solution_strategy =<\/span> (\r\n    routing_enums_pb2.<\/span>FirstSolutionStrategy.<\/span>PATH_CHEAPEST_ARC)\r\n<\/pre>\n
         <\/p>\n
        5. Function to Print the Solution<\/strong><\/h4>\n
        The function below prints out the solution to the screen by extracting the route from the solution<\/p>\n
        # Displays the solution to the output<\/span>\r\ndef<\/span> print_solution<\/span>(manager, routing, solution):\r\n    print<\/span>('Objective: {} miles'<\/span>.<\/span>format(solution.<\/span>ObjectiveValue()))\r\n    index =<\/span> routing.<\/span>Start(0<\/span>)\r\n    \r\n    plan_output =<\/span> 'Best route found for vehicle 0:<\/span>\\n<\/span>'<\/span>\r\n    route_distance =<\/span> 0<\/span>\r\n    \r\n    while<\/span> not<\/span> routing.<\/span>IsEnd(index):\r\n        plan_output +=<\/span> ' {} ->'<\/span>.<\/span>format(manager.<\/span>IndexToNode(index))\r\n        previous_index =<\/span> index\r\n        index =<\/span> solution.<\/span>Value(routing.<\/span>NextVar(index))\r\n        route_distance +=<\/span> routing.<\/span>GetArcCostForVehicle(previous_index, index, 0<\/span>)\r\n    plan_output +=<\/span> ' {}<\/span>\\n<\/span>'<\/span>.<\/span>format(manager.<\/span>IndexToNode(index))\r\n    \r\n    print<\/span>(plan_output)\r\n    plan_output +=<\/span> 'Total distance for route: {}miles<\/span>\\n<\/span>'<\/span>.<\/span>format(route_distance)\r\n<\/pre>\n
         <\/p>\n
        6. Putting it all together<\/strong><\/h4>\n
        Finally, call the SolveWithParameters()<\/em> method of the routing model and then call the print_solution function.<\/p>\n
        # Call the SolveWithParameters() and print the solution<\/span>\r\nsolution =<\/span> routing.<\/span>SolveWithParameters(search_parameters)\r\nif<\/span> solution:\r\n    print_solution(manager, routing, solution)\r\n<\/pre>\n
        The final output of the program is given below:<\/p>\n
        Objective: 6465 miles\r\nBest route found for vehicle 0:\r\n 0 -> 7 -> 2 -> 3 -> 9 -> 10 -> 5 -> 4 -> 12 -> 11 -> 1 -> 8 -> 6 -> 0\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
        In this tutorial, we would see how to solve the TSP problem in Python. The following sections are covered. Approach to Solving the TSP Problem … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[35],"tags":[],"class_list":["post-212","post","type-post","status-publish","format-standard","hentry","category-vehicle-routing"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/212","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/comments?post=212"}],"version-history":[{"count":4,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/212\/revisions"}],"predecessor-version":[{"id":217,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/212\/revisions\/217"}],"wp:attachment":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/media?parent=212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/categories?post=212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/tags?post=212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}