我最近一直致力于使用 Google 的 OR-Tools 寻找最佳路线以外的其他内容。我找到了example in the repo ,但这只能解决最佳路线,您知道如何为一组点生成多个解决方案吗?我目前正在使用该工具的 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);
}
}
最佳答案
使用底层 CP 求解器中的 AllSolutionCollector
。 python 代码:
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")
关于c# - Google OR-Tools TSP 返回几个解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52074537/