Google OR-Tools TSP возвращает несколько решений

Question

Недавно я работал над поиском не только оптимального маршрута, используя Google OR-Tools. Я нашел пример в репозитории , но это решает только оптимальный маршрут, есть идеи, как создать более одного решения для набора точек? В настоящее время я работаю с версией этого инструмента для DotNet, любое решение на любом другом языке будет полезным!

public class tspParams : NodeEvaluator2
{
    public static int[,] distanceMatrix =
    {
        {   0,  20,  40,   10   },
        {   20,  0,   4,   55   },
        {   40,  4,   0,   2    },
        {   10, 55,   2,   0    }
    };

    public static int tsp_size
    {
        get { return distanceMatrix.GetUpperBound(0) + 1; }
    }

    public static int num_routes
    {
        get { return 1; }
    }

    public static int depot
    {
        get { return 0; }
    }

    public override long Run(int FromNode, int ToNode)
    {
        return distanceMatrix[FromNode, ToNode];
    }
}

public class TSP
{
    public static void PrintSolution(RoutingModel routing, Assignment solution)
    {
        Console.WriteLine("Distance of the route: {0}", solution.ObjectiveValue());

        var index = routing.Start(0);

        Console.WriteLine("Route for Vehicle 0:");
        while (!routing.IsEnd(index))
        {
            Console.Write("{0} -> ", routing.IndexToNode(index));
            var previousIndex = index;
            index = solution.Value(routing.NextVar(index));
        }
        Console.WriteLine("{0}", routing.IndexToNode(index));
        //Console.WriteLine("Calculated optimal route!");
    }

    public static void Solve()
    {
        // Create Routing Model
        RoutingModel routing = new RoutingModel(
            tspParams.tsp_size, 
            tspParams.num_routes, 
            tspParams.depot);

        // Define weight of each edge
        NodeEvaluator2 distanceEvaluator = new tspParams();

        //protect callbacks from the GC
        GC.KeepAlive(distanceEvaluator);
        routing.SetArcCostEvaluatorOfAllVehicles(distanceEvaluator);

        // Setting first solution heuristic (cheapest addition).
        RoutingSearchParameters searchParameters = RoutingModel.DefaultSearchParameters();
        searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;

        Assignment solution = routing.SolveWithParameters(searchParameters);
        PrintSolution(routing, solution);
    }
}

Answer 1

Используйте AllSolutionCollector из базового решателя CP. код питона:

    solver = routing.solver()
    collector = solver.AllSolutionCollector()

    for location_idx in range(len(data['time_windows'])):
        index = manager.NodeToIndex(location_idx)
        time_var = time_dimension.CumulVar(index)
        next_var = routing.NextVar(index)
        collector.Add(time_var)
        collector.Add(next_var)
    for v in range(data['num_vehicles']):
        index = routing.Start(v)
        time_var = time_dimension.CumulVar(index)
        next_var = routing.NextVar(index)
        collector.Add(time_var)
        collector.Add(next_var)

        index = routing.End(v)
        time_var = time_dimension.CumulVar(index)
        collector.Add(time_var)

    routing.AddSearchMonitor(collector)

    assignment = routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)
    if assignment:
        logger.info("solution count: %d", collector.SolutionCount())
        for index in range(collector.SolutionCount()):
            logger.info("solution index: %d", index)
            self.print_solution(data, manager, routing, collector.Solution(index))
        logger.info('final solution:')
        self.print_solution(data, manager, routing, assignment)
    else:
        raise OptimizationInternalException("no solution found")