title: Shortest path between many 2D points (travelling salesman within Shapely LineString?)
body: <p>I was trying to create river cross-section profiles based on the point terrestical measurements. When trying to create a Shapely <code>LineString</code> from a Series of points with the common id, I realized that the order of given points really matters as the <code>LineString</code> would just connect given points 'indexwise' (<em>connect points in the list-given order</em>). The below code illustrates the default behaviour:</p>
  
  <pre><code>from shapely.geometry import Point, LineString
  import geopandas as gpd
  import numpy as np
  import matplotlib.pyplot as plt
  
  # Generate random points
  x=np.random.randint(0,100,10)
  y=np.random.randint(0,50,10)
  data = zip(x,y)
  
  # Create Point and default LineString GeoSeries
  gdf_point = gpd.GeoSeries([Point(j,k) for j,k in data])
  gdf_line = gpd.GeoSeries(LineString(zip(x,y)))
  
  # plot the points and "default" LineString
  ax = gdf_line.plot(color='red')
  gdf_point.plot(marker='*', color='green', markersize=5,ax=ax)
  </code></pre>
  
  <p>That would produce the image:</p>
  
  <p><a href="https://i.stack.imgur.com/hm1Db.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/hm1Db.png" alt="Default LineString"></a></p>
  
  <p><strong>Question:</strong> Is there any built-in method within Shapely that would automatically create the <em>most logical</em> (a.k.a.: the shortest, the least complicated, the least criss-cross,...) line through the given list of random 2D points?</p>
  
  <p>Below can you find the desired line (green) compared to the default (red). </p>
  
  <p><a href="https://i.stack.imgur.com/jKLJb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/jKLJb.png" alt="Desired LineString"></a></p>