title: Optimizing a Traveling Salesman Algorithm (Time Traveler Algorithm)
body: <p>I try to optimize a simple python algorithm I made that approximately solve the Traveling Salesman Problem :</p>
  <pre><code>import math
  import random
  import matplotlib.pyplot as plt
  import datetime
  
  
  #Distance between two point
  def distance(point1, point2):
      return math.sqrt((point2[0]-point1[0])**2+(point2[1]-point1[1])**2)
  
  #TSP TimeTraveler Algorithm
  def TSP_TimeTraveler(Set_Points):
      print(&quot;Solving TSP&quot;)
  
      #For calculating execution time
      time_start = datetime.datetime.now()
  
      #Copy the set points
      points = Set_Points.copy()
      route = []
  
      #Take 3 points at random
      route.append(points.pop(random.randint(0,len(points)-1)))
      route.insert(0,points.pop(random.randint(0,len(points)-1)))
      route.insert(1,points.pop(random.randint(0,len(points)-1)))
  
      #Calulating the initial route length
      Length = distance(route[0],route[1]) + distance(route[1],route[-1]) + distance(route[-1],route[0])
  
      #Time Traveler Algorithm
      while len(points)&gt;0 :
          print(&quot;Points left : &quot;, len(points),'              ', end=&quot;\r&quot;)
  
          #Take a random point from the Set
          point = points.pop(random.randint(0,len(points)-1))
  
          ###############################################################################################################
          #### Finding the closest route segment by calculation all lengths posibilities and finding the minimum one ####
          ###############################################################################################################
          Set_Lengths = []
          for i in range(1,len(route)):
              #Set of Lengths when the point is on each route segment except the last one
              L = Length - distance(route[i-1],route[i]) + distance(route[i-1],point) + distance(point, route[i])
              Set_Lengths.append((i,L))
  
          #Adding the last length when the point is on the last segement
          L = Length - distance(route[-1],route[0]) + distance(route[-1],point) + distance(point, route[0])
          Set_Lengths.append((0,L))
          ###############################################################################################################
          ###############################################################################################################
  
          #Sorting the set of lengths
          Set_Lengths.sort(key=lambda k: k[1])
  
          #Inserting the point on the minimum length segment
          route.insert(Set_Lengths[0][0], point)
  
          #Updating the new route length
          Length = Set_Lengths[0][1]
  
      #Connecting the start point with the finish point
      route.append(route[0])
  
      #For calculating execution time
      time_end = datetime.datetime.now()
      delta = (time_end-time_start).total_seconds()
  
      print(&quot;Points left : &quot;, len(points),' Done              ',)
      print(&quot;Execution time : &quot;, delta, &quot;secs&quot;)
  
      return route
  
  #######################
  #Testing the Algorithm#
  #######################
  
  #Size of the set
  size = 2520
  
  #Generating a set of random 2D points
  points = []
  for i in range(size):
      points.append([random.uniform(0, 100),random.uniform(0, 100)])
  
  #Solve TSP
  route = TSP_TimeTraveler(points)
  
  #Plot the solution
  plt.scatter(*zip(*points),s=5)
  plt.plot(*zip(*route))
  plt.axis('scaled')
  plt.show()
  </code></pre>
  <p>The algorithm operate in 3 simple steps :</p>
  <p>1/ First step I take 3 points at random from the points set and connect them as the initial route.</p>
  <p>2/ Then each next step, I take a point at random from the set of points left. And try to find the closest segment of the route i have and connect it to it.</p>
  <p>3/ I keep repeating step 2/ until the set of points left is empty.</p>
  <p>Here is a gif of how the algorithm solve a set of 120 points : <a href="https://i.stack.imgur.com/tZYUX.gif" rel="nofollow noreferrer">TimeTravelerAlgorithm.gif</a></p>
  <p>I give it the name &quot;Time Traveler&quot; because it's operate like a greedy salesman algorithm. But instead traveling to the closest new city in the present, the greedy salesman time travel to the past to the closest city he had already visited and go visit that new city then continue his normal route.</p>
  <p>The time traveler start a route of 3 cities, and the traveler add a new city each step in his past, until he reach a present where he visited all the cities and returned to his home city.</p>
  <p>The algorithm give decent solutions fast for small set of points. Here is the execution time for each number of sets, all are made on a 2.6GHz dual-core Intel Core i5 processor Macbook :</p>
  <ul>
  <li>120 points in around 0.03 secs</li>
  <li>360 points in around 0.23 secs</li>
  <li>2520 points in around 10 secs</li>
  <li>10 000 points in around 3 mins</li>
  <li>100 000 points in around 5 hours (<a href="https://i.ibb.co/j3y1bbV/image100small.png" rel="nofollow noreferrer">Solution Map</a>)</li>
  </ul>
  <p>The algorithm is far from being optimized, because in some cases it gives cross routes which is suboptimal. And It's all made in pure python. Maybe using numpy or some advance library or even GPU can speed up the program.</p>
  <p>I want your review and help on how to optimize it. I try to approximately solve without cross routes for set of points that can be extremely large (from 1 million to 100 billions points).</p>
  <p>PS: My algorithm and codes are open. People from internet, feel free to use it in any project or any research you have.</p>