2-opt algorithm to solve the Travelling Salesman Problem in Python

Multi tool use
Multi tool use












1















I couldn't find any complete implementation of the 2-opt algorithm in Python so I am trying to add the missing parts to the code found here, which I present below.



def two_opt(route):
best = route
improved = True
while improved:
improved = False
for i in range(1, len(route)-2):
for j in range(i+1, len(route)):
if j-i == 1: continue # changes nothing, skip then
new_route = route[:]
new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
if cost(new_route) < cost(best): # what should cost be?
best = new_route
improved = True
route = best
return best


In order to complete this code, I made a small program to extract long/lat co-ords from a text file and fill in an adjacency matrix with the cost for each point. Full code, including samples of input co-ordinates and adjacency matrix may be found on Code Review.



Since I do not know what the cost function is from the code above, my idea was to work out all the costs from one point to another and placed in an adjacency matrix: adj_matrix. This represents how far each point is from the others.



I tried passing my cost/adjacency matrix to the function to use that, however I am unable to calculate the cost given my adjacency matrix.



def main():
# code to read from file
# code to append co-ordinates to points and calculate the haversine distance between each point
route = random.sample(range(10), 10)
best = two_opt(route, adj_matrix) # passing my adjacency matrix
print(best)



ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()




Another Python 2-opt question: Generate all neighbors for 2OPT in python



Any suggestions on how I can find the correct cost from the adjacency matrix would be appreciated.










share|improve this question





























    1















    I couldn't find any complete implementation of the 2-opt algorithm in Python so I am trying to add the missing parts to the code found here, which I present below.



    def two_opt(route):
    best = route
    improved = True
    while improved:
    improved = False
    for i in range(1, len(route)-2):
    for j in range(i+1, len(route)):
    if j-i == 1: continue # changes nothing, skip then
    new_route = route[:]
    new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
    if cost(new_route) < cost(best): # what should cost be?
    best = new_route
    improved = True
    route = best
    return best


    In order to complete this code, I made a small program to extract long/lat co-ords from a text file and fill in an adjacency matrix with the cost for each point. Full code, including samples of input co-ordinates and adjacency matrix may be found on Code Review.



    Since I do not know what the cost function is from the code above, my idea was to work out all the costs from one point to another and placed in an adjacency matrix: adj_matrix. This represents how far each point is from the others.



    I tried passing my cost/adjacency matrix to the function to use that, however I am unable to calculate the cost given my adjacency matrix.



    def main():
    # code to read from file
    # code to append co-ordinates to points and calculate the haversine distance between each point
    route = random.sample(range(10), 10)
    best = two_opt(route, adj_matrix) # passing my adjacency matrix
    print(best)



    ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()




    Another Python 2-opt question: Generate all neighbors for 2OPT in python



    Any suggestions on how I can find the correct cost from the adjacency matrix would be appreciated.










    share|improve this question



























      1












      1








      1


      3






      I couldn't find any complete implementation of the 2-opt algorithm in Python so I am trying to add the missing parts to the code found here, which I present below.



      def two_opt(route):
      best = route
      improved = True
      while improved:
      improved = False
      for i in range(1, len(route)-2):
      for j in range(i+1, len(route)):
      if j-i == 1: continue # changes nothing, skip then
      new_route = route[:]
      new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
      if cost(new_route) < cost(best): # what should cost be?
      best = new_route
      improved = True
      route = best
      return best


      In order to complete this code, I made a small program to extract long/lat co-ords from a text file and fill in an adjacency matrix with the cost for each point. Full code, including samples of input co-ordinates and adjacency matrix may be found on Code Review.



      Since I do not know what the cost function is from the code above, my idea was to work out all the costs from one point to another and placed in an adjacency matrix: adj_matrix. This represents how far each point is from the others.



      I tried passing my cost/adjacency matrix to the function to use that, however I am unable to calculate the cost given my adjacency matrix.



      def main():
      # code to read from file
      # code to append co-ordinates to points and calculate the haversine distance between each point
      route = random.sample(range(10), 10)
      best = two_opt(route, adj_matrix) # passing my adjacency matrix
      print(best)



      ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()




      Another Python 2-opt question: Generate all neighbors for 2OPT in python



      Any suggestions on how I can find the correct cost from the adjacency matrix would be appreciated.










      share|improve this question
















      I couldn't find any complete implementation of the 2-opt algorithm in Python so I am trying to add the missing parts to the code found here, which I present below.



      def two_opt(route):
      best = route
      improved = True
      while improved:
      improved = False
      for i in range(1, len(route)-2):
      for j in range(i+1, len(route)):
      if j-i == 1: continue # changes nothing, skip then
      new_route = route[:]
      new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
      if cost(new_route) < cost(best): # what should cost be?
      best = new_route
      improved = True
      route = best
      return best


      In order to complete this code, I made a small program to extract long/lat co-ords from a text file and fill in an adjacency matrix with the cost for each point. Full code, including samples of input co-ordinates and adjacency matrix may be found on Code Review.



      Since I do not know what the cost function is from the code above, my idea was to work out all the costs from one point to another and placed in an adjacency matrix: adj_matrix. This represents how far each point is from the others.



      I tried passing my cost/adjacency matrix to the function to use that, however I am unable to calculate the cost given my adjacency matrix.



      def main():
      # code to read from file
      # code to append co-ordinates to points and calculate the haversine distance between each point
      route = random.sample(range(10), 10)
      best = two_opt(route, adj_matrix) # passing my adjacency matrix
      print(best)



      ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()




      Another Python 2-opt question: Generate all neighbors for 2OPT in python



      Any suggestions on how I can find the correct cost from the adjacency matrix would be appreciated.







      python python-3.x algorithm adjacency-matrix traveling-salesman






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Nov 13 '18 at 8:31







      Rrz0

















      asked Nov 13 '18 at 6:48









      Rrz0Rrz0

      4971618




      4971618
























          2 Answers
          2






          active

          oldest

          votes


















          1














          First of all, an adjacency matrix is typically a (0, 1)-matrix. What you have here is variously referred to as the cost, weight or distance matrix.



          Now to your question.



          The cost function can be as simple as:



          def cost(cost_mat, route):
          return cost_mat[np.roll(route, 1), route].sum()


          Here, np.roll() "rotates" the route by one position to make it easy to use it with route to index into the cost matrix. The sum() simply adds up the costs of the individual segment to compute the total cost of the route.



          (If at some point you decide to look at the Asymmetric TSP, you'll need to make sure the row/column order matches how cost_mat is constructed; for the Euclidean TSP this doesn't matter as the cost matrix is symmetric.)



          Example of use:



          cost_mat = np.array([
          [0, 1, 2, 3],
          [1, 0, 4, 5],
          [2, 4, 0, 7],
          [3, 5, 7, 0],
          ])

          route = np.array([2, 1, 3, 0])

          print(cost(cost_mat, route))





          share|improve this answer


























          • Many thanks for your suggestions, that helped me understand much better. I am still going through the docs to understand what [np.roll(route, 1), route] is actually doing... couldn't we have done without it? Thanks

            – Rrz0
            Nov 13 '18 at 8:59













          • @Rrz0: My pleasure!

            – NPE
            Nov 13 '18 at 9:04











          • So, you are shifting by 1 along the route array, which allows for easier indexing. For example, [1,2,3,4,5] comes out to [5,1,2,3,4]

            – Rrz0
            Nov 13 '18 at 9:07








          • 1





            @Rrz0: Exactly. If you put the two arrays side by side and look at the pairs of elements (zeroth, first etc), that gives you pairs of cities that your route connects. Those pairs are the row/column indices of your cost matrix that you're interested in.

            – NPE
            Nov 13 '18 at 9:09



















          0














          2-opt deletes two edges and creates two new ones (assuming the cost matrix is symmetric), so the cost function can be simplified to consider only the edges that change. For large arrays this is much faster than enumerating over the whole route.



          import numpy as np

          def cost_change(cost_mat, n1, n2, n3, n4):
          return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]


          def two_opt(route, cost_mat):
          best = route
          improved = True
          while improved:
          improved = False
          for i in range(1, len(route) - 2):
          for j in range(i + 1, len(route)):
          if j - i == 1: continue
          if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
          best[i:j] = best[j - 1:i - 1:-1]
          improved = True
          route = best
          return best


          if __name__ == '__main__':
          nodes = 1000
          init_route = list(range(nodes))
          print(init_route)
          cost_mat = np.random.randint(100, size=(nodes, nodes))
          cost_mat += cost_mat.T
          np.fill_diagonal(cost_mat, 0)
          cost_mat = list(cost_mat)
          best_route = two_opt(init_route, cost_mat)
          print(best_route)





          share|improve this answer

























            Your Answer






            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "1"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53275314%2f2-opt-algorithm-to-solve-the-travelling-salesman-problem-in-python%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1














            First of all, an adjacency matrix is typically a (0, 1)-matrix. What you have here is variously referred to as the cost, weight or distance matrix.



            Now to your question.



            The cost function can be as simple as:



            def cost(cost_mat, route):
            return cost_mat[np.roll(route, 1), route].sum()


            Here, np.roll() "rotates" the route by one position to make it easy to use it with route to index into the cost matrix. The sum() simply adds up the costs of the individual segment to compute the total cost of the route.



            (If at some point you decide to look at the Asymmetric TSP, you'll need to make sure the row/column order matches how cost_mat is constructed; for the Euclidean TSP this doesn't matter as the cost matrix is symmetric.)



            Example of use:



            cost_mat = np.array([
            [0, 1, 2, 3],
            [1, 0, 4, 5],
            [2, 4, 0, 7],
            [3, 5, 7, 0],
            ])

            route = np.array([2, 1, 3, 0])

            print(cost(cost_mat, route))





            share|improve this answer


























            • Many thanks for your suggestions, that helped me understand much better. I am still going through the docs to understand what [np.roll(route, 1), route] is actually doing... couldn't we have done without it? Thanks

              – Rrz0
              Nov 13 '18 at 8:59













            • @Rrz0: My pleasure!

              – NPE
              Nov 13 '18 at 9:04











            • So, you are shifting by 1 along the route array, which allows for easier indexing. For example, [1,2,3,4,5] comes out to [5,1,2,3,4]

              – Rrz0
              Nov 13 '18 at 9:07








            • 1





              @Rrz0: Exactly. If you put the two arrays side by side and look at the pairs of elements (zeroth, first etc), that gives you pairs of cities that your route connects. Those pairs are the row/column indices of your cost matrix that you're interested in.

              – NPE
              Nov 13 '18 at 9:09
















            1














            First of all, an adjacency matrix is typically a (0, 1)-matrix. What you have here is variously referred to as the cost, weight or distance matrix.



            Now to your question.



            The cost function can be as simple as:



            def cost(cost_mat, route):
            return cost_mat[np.roll(route, 1), route].sum()


            Here, np.roll() "rotates" the route by one position to make it easy to use it with route to index into the cost matrix. The sum() simply adds up the costs of the individual segment to compute the total cost of the route.



            (If at some point you decide to look at the Asymmetric TSP, you'll need to make sure the row/column order matches how cost_mat is constructed; for the Euclidean TSP this doesn't matter as the cost matrix is symmetric.)



            Example of use:



            cost_mat = np.array([
            [0, 1, 2, 3],
            [1, 0, 4, 5],
            [2, 4, 0, 7],
            [3, 5, 7, 0],
            ])

            route = np.array([2, 1, 3, 0])

            print(cost(cost_mat, route))





            share|improve this answer


























            • Many thanks for your suggestions, that helped me understand much better. I am still going through the docs to understand what [np.roll(route, 1), route] is actually doing... couldn't we have done without it? Thanks

              – Rrz0
              Nov 13 '18 at 8:59













            • @Rrz0: My pleasure!

              – NPE
              Nov 13 '18 at 9:04











            • So, you are shifting by 1 along the route array, which allows for easier indexing. For example, [1,2,3,4,5] comes out to [5,1,2,3,4]

              – Rrz0
              Nov 13 '18 at 9:07








            • 1





              @Rrz0: Exactly. If you put the two arrays side by side and look at the pairs of elements (zeroth, first etc), that gives you pairs of cities that your route connects. Those pairs are the row/column indices of your cost matrix that you're interested in.

              – NPE
              Nov 13 '18 at 9:09














            1












            1








            1







            First of all, an adjacency matrix is typically a (0, 1)-matrix. What you have here is variously referred to as the cost, weight or distance matrix.



            Now to your question.



            The cost function can be as simple as:



            def cost(cost_mat, route):
            return cost_mat[np.roll(route, 1), route].sum()


            Here, np.roll() "rotates" the route by one position to make it easy to use it with route to index into the cost matrix. The sum() simply adds up the costs of the individual segment to compute the total cost of the route.



            (If at some point you decide to look at the Asymmetric TSP, you'll need to make sure the row/column order matches how cost_mat is constructed; for the Euclidean TSP this doesn't matter as the cost matrix is symmetric.)



            Example of use:



            cost_mat = np.array([
            [0, 1, 2, 3],
            [1, 0, 4, 5],
            [2, 4, 0, 7],
            [3, 5, 7, 0],
            ])

            route = np.array([2, 1, 3, 0])

            print(cost(cost_mat, route))





            share|improve this answer















            First of all, an adjacency matrix is typically a (0, 1)-matrix. What you have here is variously referred to as the cost, weight or distance matrix.



            Now to your question.



            The cost function can be as simple as:



            def cost(cost_mat, route):
            return cost_mat[np.roll(route, 1), route].sum()


            Here, np.roll() "rotates" the route by one position to make it easy to use it with route to index into the cost matrix. The sum() simply adds up the costs of the individual segment to compute the total cost of the route.



            (If at some point you decide to look at the Asymmetric TSP, you'll need to make sure the row/column order matches how cost_mat is constructed; for the Euclidean TSP this doesn't matter as the cost matrix is symmetric.)



            Example of use:



            cost_mat = np.array([
            [0, 1, 2, 3],
            [1, 0, 4, 5],
            [2, 4, 0, 7],
            [3, 5, 7, 0],
            ])

            route = np.array([2, 1, 3, 0])

            print(cost(cost_mat, route))






            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Nov 13 '18 at 8:54

























            answered Nov 13 '18 at 8:37









            NPENPE

            350k63750879




            350k63750879













            • Many thanks for your suggestions, that helped me understand much better. I am still going through the docs to understand what [np.roll(route, 1), route] is actually doing... couldn't we have done without it? Thanks

              – Rrz0
              Nov 13 '18 at 8:59













            • @Rrz0: My pleasure!

              – NPE
              Nov 13 '18 at 9:04











            • So, you are shifting by 1 along the route array, which allows for easier indexing. For example, [1,2,3,4,5] comes out to [5,1,2,3,4]

              – Rrz0
              Nov 13 '18 at 9:07








            • 1





              @Rrz0: Exactly. If you put the two arrays side by side and look at the pairs of elements (zeroth, first etc), that gives you pairs of cities that your route connects. Those pairs are the row/column indices of your cost matrix that you're interested in.

              – NPE
              Nov 13 '18 at 9:09



















            • Many thanks for your suggestions, that helped me understand much better. I am still going through the docs to understand what [np.roll(route, 1), route] is actually doing... couldn't we have done without it? Thanks

              – Rrz0
              Nov 13 '18 at 8:59













            • @Rrz0: My pleasure!

              – NPE
              Nov 13 '18 at 9:04











            • So, you are shifting by 1 along the route array, which allows for easier indexing. For example, [1,2,3,4,5] comes out to [5,1,2,3,4]

              – Rrz0
              Nov 13 '18 at 9:07








            • 1





              @Rrz0: Exactly. If you put the two arrays side by side and look at the pairs of elements (zeroth, first etc), that gives you pairs of cities that your route connects. Those pairs are the row/column indices of your cost matrix that you're interested in.

              – NPE
              Nov 13 '18 at 9:09

















            Many thanks for your suggestions, that helped me understand much better. I am still going through the docs to understand what [np.roll(route, 1), route] is actually doing... couldn't we have done without it? Thanks

            – Rrz0
            Nov 13 '18 at 8:59







            Many thanks for your suggestions, that helped me understand much better. I am still going through the docs to understand what [np.roll(route, 1), route] is actually doing... couldn't we have done without it? Thanks

            – Rrz0
            Nov 13 '18 at 8:59















            @Rrz0: My pleasure!

            – NPE
            Nov 13 '18 at 9:04





            @Rrz0: My pleasure!

            – NPE
            Nov 13 '18 at 9:04













            So, you are shifting by 1 along the route array, which allows for easier indexing. For example, [1,2,3,4,5] comes out to [5,1,2,3,4]

            – Rrz0
            Nov 13 '18 at 9:07







            So, you are shifting by 1 along the route array, which allows for easier indexing. For example, [1,2,3,4,5] comes out to [5,1,2,3,4]

            – Rrz0
            Nov 13 '18 at 9:07






            1




            1





            @Rrz0: Exactly. If you put the two arrays side by side and look at the pairs of elements (zeroth, first etc), that gives you pairs of cities that your route connects. Those pairs are the row/column indices of your cost matrix that you're interested in.

            – NPE
            Nov 13 '18 at 9:09





            @Rrz0: Exactly. If you put the two arrays side by side and look at the pairs of elements (zeroth, first etc), that gives you pairs of cities that your route connects. Those pairs are the row/column indices of your cost matrix that you're interested in.

            – NPE
            Nov 13 '18 at 9:09













            0














            2-opt deletes two edges and creates two new ones (assuming the cost matrix is symmetric), so the cost function can be simplified to consider only the edges that change. For large arrays this is much faster than enumerating over the whole route.



            import numpy as np

            def cost_change(cost_mat, n1, n2, n3, n4):
            return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]


            def two_opt(route, cost_mat):
            best = route
            improved = True
            while improved:
            improved = False
            for i in range(1, len(route) - 2):
            for j in range(i + 1, len(route)):
            if j - i == 1: continue
            if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
            best[i:j] = best[j - 1:i - 1:-1]
            improved = True
            route = best
            return best


            if __name__ == '__main__':
            nodes = 1000
            init_route = list(range(nodes))
            print(init_route)
            cost_mat = np.random.randint(100, size=(nodes, nodes))
            cost_mat += cost_mat.T
            np.fill_diagonal(cost_mat, 0)
            cost_mat = list(cost_mat)
            best_route = two_opt(init_route, cost_mat)
            print(best_route)





            share|improve this answer






























              0














              2-opt deletes two edges and creates two new ones (assuming the cost matrix is symmetric), so the cost function can be simplified to consider only the edges that change. For large arrays this is much faster than enumerating over the whole route.



              import numpy as np

              def cost_change(cost_mat, n1, n2, n3, n4):
              return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]


              def two_opt(route, cost_mat):
              best = route
              improved = True
              while improved:
              improved = False
              for i in range(1, len(route) - 2):
              for j in range(i + 1, len(route)):
              if j - i == 1: continue
              if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
              best[i:j] = best[j - 1:i - 1:-1]
              improved = True
              route = best
              return best


              if __name__ == '__main__':
              nodes = 1000
              init_route = list(range(nodes))
              print(init_route)
              cost_mat = np.random.randint(100, size=(nodes, nodes))
              cost_mat += cost_mat.T
              np.fill_diagonal(cost_mat, 0)
              cost_mat = list(cost_mat)
              best_route = two_opt(init_route, cost_mat)
              print(best_route)





              share|improve this answer




























                0












                0








                0







                2-opt deletes two edges and creates two new ones (assuming the cost matrix is symmetric), so the cost function can be simplified to consider only the edges that change. For large arrays this is much faster than enumerating over the whole route.



                import numpy as np

                def cost_change(cost_mat, n1, n2, n3, n4):
                return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]


                def two_opt(route, cost_mat):
                best = route
                improved = True
                while improved:
                improved = False
                for i in range(1, len(route) - 2):
                for j in range(i + 1, len(route)):
                if j - i == 1: continue
                if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
                best[i:j] = best[j - 1:i - 1:-1]
                improved = True
                route = best
                return best


                if __name__ == '__main__':
                nodes = 1000
                init_route = list(range(nodes))
                print(init_route)
                cost_mat = np.random.randint(100, size=(nodes, nodes))
                cost_mat += cost_mat.T
                np.fill_diagonal(cost_mat, 0)
                cost_mat = list(cost_mat)
                best_route = two_opt(init_route, cost_mat)
                print(best_route)





                share|improve this answer















                2-opt deletes two edges and creates two new ones (assuming the cost matrix is symmetric), so the cost function can be simplified to consider only the edges that change. For large arrays this is much faster than enumerating over the whole route.



                import numpy as np

                def cost_change(cost_mat, n1, n2, n3, n4):
                return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]


                def two_opt(route, cost_mat):
                best = route
                improved = True
                while improved:
                improved = False
                for i in range(1, len(route) - 2):
                for j in range(i + 1, len(route)):
                if j - i == 1: continue
                if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
                best[i:j] = best[j - 1:i - 1:-1]
                improved = True
                route = best
                return best


                if __name__ == '__main__':
                nodes = 1000
                init_route = list(range(nodes))
                print(init_route)
                cost_mat = np.random.randint(100, size=(nodes, nodes))
                cost_mat += cost_mat.T
                np.fill_diagonal(cost_mat, 0)
                cost_mat = list(cost_mat)
                best_route = two_opt(init_route, cost_mat)
                print(best_route)






                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited Dec 30 '18 at 12:06

























                answered Dec 30 '18 at 11:46









                FradgeFradge

                412




                412






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Stack Overflow!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53275314%2f2-opt-algorithm-to-solve-the-travelling-salesman-problem-in-python%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    GIrF1dV3KvJGaS9 eaPrOnxkYgoi9lkGu mjLFFxB
                    7YddOAnV,8

                    Popular posts from this blog

                    Monofisismo

                    Angular Downloading a file using contenturl with Basic Authentication

                    Olmecas