can i use OR-tools for TSP with partial distance matrix (for a huge set of nodes)?

363 views Asked by At

i'm trying to solve tsp with OR-tools for a problem of something like 80,000 nodes, the problem is, I need a huge distance matrix that takes to much memory ,so its infeasible and i don't get a solution.

so:

  1. is there an option to work with partial distance matrix in or-tools?
  2. if not is there a way to improve my code?
  3. is there another external solver that can work for this task in python?
    import math
    from collections import namedtuple
    import random
    import time
    from collections import namedtuple
    from sklearn.metrics.pairwise import euclidean_distances
    import numpy as np
    import numba
    from scipy.spatial import distance_matrix
    from sklearn.metrics.pairwise import euclidean_distances
    from math import sqrt


    Point = namedtuple("Point", ['x', 'y'])

    def solve_it(input_data):
       # Modify this code to run your optimization algorithm
       global POINTS
       # parse the input
       lines = input_data.split('\n')

    nodeCount = int(lines[0])

    points = []
    for i in range(1, nodeCount+1):
        line = lines[i]
        parts = line.split()
        points.append(Point(float(parts[0]), float(parts[1])))

   

    #2.routing with or tools

    def dist_matrix(nodeCount,points):
        data=[]
        for k in range(len(points)):
            data.append([int(points[k].x),int(points[k].y)])
        
        D=euclidean_distances(data, data)
        return D


    def create_data_model(D):
        """Stores the data for the problem."""
        data = {}
        data['distance_matrix'] = D # yapf: disable
        data['num_vehicles'] = 1
        data['depot'] = 0
        return data

    def print_solution(manager, routing, solution):
        index = routing.Start(0)
        plan_output = []#Route for vehicle 0:\n'
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        return plan_output

    def or_main(nodeCount,points):
        from ortools.constraint_solver import routing_enums_pb2
        from ortools.constraint_solver import pywrapcp

        """Entry point of the program."""
        # Instantiate the data problem.
        global sol
        D=dist_matrix(nodeCount,points)
        data = create_data_model(D)

        # 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):
            """Returns the distance between the two nodes."""
            # 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)

        # Setting first solution heuristic.
        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
        k = 100
        if nodeCount <= 100:
            k = 30
        elif 100 <= nodeCount <= 1000:
            k = 300
        elif nodeCount > 1000:
            k = 17000
        search_parameters.time_limit.seconds =k
        search_parameters.log_search = True


        # Solve the problem.
        solution = routing.SolveWithParameters(search_parameters)

        # #print solution on console.
        if solution:
            sol=print_solution(manager, routing, solution)
        return sol

    
    ######################################################################
    
    solution=or_main(nodeCount,points)
    

    # calculate the length of the tour
    obj = length(points[solution[-1]], points[solution[0]])
    for index in range(0, nodeCount-1):
        obj += length(points[solution[index]], points[solution[index+1]])

    # prepare the solution in the specified output format
    output_data = '%.2f' % obj + ' ' + str(0) + '\n'
    output_data += ' '.join(map(str, solution))

    return output_data




    if __name__ == '__main__':
      import sys
      if len(sys.argv) > 1:
          file_location = sys.argv[1].strip()
          with open(file_location, 'r') as input_data_file:
            input_data = input_data_file.read()
        #print(solve_it(input_data))
      else:
          print('This test requires an input file.  Please select one from the data directory. (i.e. python solver.py ./data/tsp_51_1)')
0

There are 0 answers