title: Is this output only strange because of heuristics?
body: <p>I'm currently programming a tool to find a path with a set amount of stops. For that I'm using <a href="https://or.stackexchange.com/a/3256">this</a> answer. But when trying the code with the below data, a very strange path is generated:
  <a href="https://i.stack.imgur.com/BRzXG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/BRzXG.png" alt="Path that is not optimal" /></a></p>
  <p>As easily seen in the image, this is by far the most optimal path, even between just the visible points.
  And so I was wondering whether this is just a problem of heuristics, or if there is anything wrong with my code (Note: The path starts and ends at a given point, in the image that is the leftmost point):</p>
  <pre class="lang-py prettyprint-override"><code>from __future__ import print_function
  from typing import List
  from ortools.constraint_solver import routing_enums_pb2
  from ortools.constraint_solver import pywrapcp
  import gpxpy
  import gpxpy.gpx
  from gpxpy.gpx import GPXWaypoint
  
  START_LOCATION = GPXWaypoint(38.892743662408584, -77.03258470988436, name=&quot;Start&quot;)
  
  def createOutputGpxRouteFile(stations:List):
      output = gpxpy.gpx.GPX()
      gpx_track = gpxpy.gpx.GPXTrack()
      output.tracks.append(gpx_track)
      gpx_segment = gpxpy.gpx.GPXTrackSegment()
      gpx_track.segments.append(gpx_segment)
      for station in stations:
          gpx_segment.points.append(gpxpy.gpx.GPXTrackPoint(latitude=station.latitude, longitude=station.longitude, name=station.name))
      print('Created GPX:', output.to_xml())
  
  def readGpxData():
      &quot;&quot;&quot;Reads the gpx data from a file and returns a list of the coordinates&quot;&quot;&quot;
      # Original code commented so it is reproducible
      #with open(&quot;Waypoints.gpx&quot;, &quot;r&quot;) as gpx_file:
      #    gpx = gpxpy.parse(gpx_file)
      #gpx.waypoints.insert(0, START_LOCATION)
      waypoints = [
          GPXWaypoint(38.91965, -76.99145, name='GC7J4FJ', description='Cache Store by Shalacknar (2/1,5)'),
          GPXWaypoint(38.90755, -76.989483,  name='GC7CYPZ', description='West Virginia Ave.: The 50 States Project by UrbanAdventureSquad (1,5/1,5)'),
          GPXWaypoint(38.9242, -77.008083,  name='GC7R9Z9', description='Stronghold neighborhood by mellow_cello (2/1,5)'),
          GPXWaypoint(38.89614, -76.97886,  name='GC9XVTY', description='Take Something, Leave Something by DCSunshine11 (1/1)'),
          GPXWaypoint(38.91295, -77.000967, name='GC7FC8C', description='DC Hidden Murals #30: 28 Blocks by exmachina (2/1)'),
          GPXWaypoint(38.921817, -77.011167,  name='GC7JHBD', description='Catlandia by mellow_cello (1,5/1,5)'),
          GPXWaypoint(38.9037, -76.992583, name='GC78CZD', description='Florida Ave.: The 50 States Project by UrbanAdventureSquad (1,5/1,5)'),
          GPXWaypoint(38.9, -76.988753,  name='GC3PBQ2', description='DC Hidden Murals #17: Dusk of H Street by exmachina (2/1)'),
          GPXWaypoint(38.901917, -76.99155, name='GC9AYCF', description='A DC Saint? by poli1136 (1/1,5)'),
          GPXWaypoint(38.916983, -77.007967,  name='GC7R8YH', description='Rhode Island Ave.: The 50 States Project by UrbanAdventureSquad (2/1,5)'),
          GPXWaypoint(38.895096, -76.985681,  name='GC9GBFY', description='Triangles and Tribulations by urbnX (1,5/1,5)'),
          GPXWaypoint(38.917633, -77.010833,  name='GC7KD9P', description='Bloomingdale: Crispus Attucks Park by mellow_cello (2/1,5)'),
          GPXWaypoint(38.934617, -77.028583, name='GC4KRFJ', description='I thought he made elevators by zdonb &amp; lilbru (1,5/1,5)'),
          GPXWaypoint(38.891967, -76.985233, name='GC9WRM2', description='Meet me at the crossroads by urbnX (1,5/1,5)'),
          GPXWaypoint(38.88075, -76.97475, name='GC6RP1W', description=&quot;Doug's Cache by puglisimclare (1,5/1,5)&quot;),
          GPXWaypoint(38.907475, -77.003103,  name='GC8AT5F', description='SideTracked - NoMa-Gallaudet U Station by mellow_cello (2/1,5)'),
          GPXWaypoint(38.896342, -76.992444,  name='GC7CYPA', description='Maryland Ave.: The 50 States Project by UrbanAdventureSquad (2,5/1,5)'),
          GPXWaypoint(38.89215, -76.988133, name='GC9EKPE', description='17 years underground by urbnX (2/1,5)'),
          GPXWaypoint(38.93015, -77.028083,  name='GC34NZ3', description='DC Hidden Murals #2: Wonderland by exmachina (2/1)'),
          GPXWaypoint(38.883071, -76.979078,  name='GC98F36', description='What’s Next? by alexcran421 (2/1,5)'),
          GPXWaypoint(38.917767, -77.0159, name='GC43T1F', description='DC Hidden Murals #22: How We Live by exmachina (2/1)'),
          GPXWaypoint(38.880617, -76.979417,  name='GC23GKB', description='SSB - Congressional Cemetery by Star-Spangled Banner (1,5/1,5)'),
          GPXWaypoint(38.879183, -76.979733, name='GC6RNVG', description=&quot;Bonaparte's Cache by puglisimclare (1,5/1,5)&quot;),
          GPXWaypoint(38.905583, -77.007567,  name='GC89MWE', description='DC Hidden Murals #31: AVA NoMa by exmachina (1,5/1,5)'),
          GPXWaypoint(38.89367, -76.99609,  name='GC9XBFP', description='Hais Market by NatsGeo6 (1,5/1,5)'),
          GPXWaypoint(38.889717, -76.996217,  name='GC9RQEP', description='16th and 44th by DCSunshine11 (1,5/1,5)'),
          GPXWaypoint(38.918983, -77.028,  name='GC37CJT', description='DC Hidden Murals #7: Scout by exmachina (2/1)'),
          GPXWaypoint(38.924896, -77.034439,  name='GC8ZXCP', description='Olive’s pipe by CharlesGeo8, Olive (1,5/1)'),
          GPXWaypoint(38.917467, -77.026933,  name='GC3VVZF', description='DC Hidden Murals #18: Bohemian Caverns by exmachina (2/1,5)'),   
           ]
      waypoints.insert(0, START_LOCATION)
      return waypoints
  
  def create2dDistanceMatrix(locations:List[GPXWaypoint]):
      &quot;&quot;&quot;Creates a distance matrix for the locations&quot;&quot;&quot;
      distance_matrix = []
      for i, location in enumerate(locations):
          distance_matrix.append([])
          for j, location_2 in enumerate(locations):
              distance_matrix[i].append(location.distance_2d(location_2))
      return distance_matrix
  
  def create_data_model():
      &quot;&quot;&quot;Stores the data for the problem.&quot;&quot;&quot;
      data = {}
      data['num_vehicles'] = 1
      data['depot'] = 0
      data['vehicle_capacities'] = [5]
      print(&quot;Using 2d distances.&quot;)
      locations = [point for point in readGpxData() if point.name[:2] == &quot;GC&quot;]
      data[&quot;distance_matrix&quot;] = create2dDistanceMatrix(locations)
      # Convert all distances to integers
      data[&quot;distance_matrix&quot;] = [[int(i) for i in row] for row in data[&quot;distance_matrix&quot;]]
      data['demands'] = [1]*len(data[&quot;distance_matrix&quot;])
      return data
  
  
  def print_solution(data, manager, routing, assignment):
      &quot;&quot;&quot;Prints assignment on console.&quot;&quot;&quot;
      total_distance = 0
      total_load = 0
      locations = readGpxData()
      stations = []
      for vehicle_id in range(data['num_vehicles']):
          index = routing.Start(vehicle_id)
          plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
          route_distance = 0
          route_load = 0
          while not routing.IsEnd(index):
              node_index = manager.IndexToNode(index)
              route_load += data['demands'][node_index]
              plan_output += ' {0} -&gt; '.format(locations[node_index].name)
              stations.append(locations[node_index])
              previous_index = index
              index = assignment.Value(routing.NextVar(index))
              route_distance += routing.GetArcCostForVehicle(
                  previous_index, index, vehicle_id)
          plan_output += ' {0} \n'.format(readGpxData()[data[&quot;depot&quot;]].name)
          stations.append(readGpxData()[data[&quot;depot&quot;]])
          plan_output += 'Distance of the route: {}m\n'.format(route_distance)
          print(plan_output)
          total_distance += route_distance
          total_load += route_load
      print('Total distance of all routes: {}m'.format(total_distance))
      createOutputGpxRouteFile(stations)
  
  def main():
      &quot;&quot;&quot;Entry point of the program.&quot;&quot;&quot;
      # Instantiate the data problem.
      data = create_data_model()
  
      # Create the routing index manager.
      manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                             data['num_vehicles'], data['depot'])
  
      # Create Routing Model.
      routing = pywrapcp.RoutingModel(manager)
  
      def distance_callback(from_index, to_index):
          &quot;&quot;&quot;Returns the distance between the two nodes.&quot;&quot;&quot;
          # Convert from routing variable Index to distance matrix NodeIndex.
          from_node = manager.IndexToNode(from_index)
          to_node = manager.IndexToNode(to_index)
          return data['distance_matrix'][from_node][to_node]
  
      transit_callback_index = routing.RegisterTransitCallback(distance_callback)
  
      # Define cost of each arc.
      routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
  
      def demand_callback(from_index):
          &quot;&quot;&quot;Returns the demand of the node.&quot;&quot;&quot;
          # Convert from routing variable Index to demands NodeIndex.
          from_node = manager.IndexToNode(from_index)
          return data['demands'][from_node]
  
      demand_callback_index = routing.RegisterUnaryTransitCallback(
          demand_callback)
      routing.AddDimensionWithVehicleCapacity(
          demand_callback_index,
          0,  # null capacity slack
          data['vehicle_capacities'],  # vehicle maximum capacities
          True,  # start cumul to zero
          'Capacity')
  
      penalty = 999999999
      for node in range(1, len(data['distance_matrix'])):
          routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
  
      # Setting first solution heuristic.
      search_parameters = pywrapcp.DefaultRoutingSearchParameters()
      search_parameters.first_solution_strategy = (
          routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
      search_parameters.local_search_metaheuristic = (
          routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
      search_parameters.time_limit.FromSeconds(1)
  
  
      # Solve the problem.
      assignment = routing.SolveWithParameters(search_parameters)
  
      # Print solution on console.
      if assignment:
          print_solution(data, manager, routing, assignment)
  
  
  if __name__ == '__main__':
      main()
  </code></pre>