谷歌用于CVRP的OR-Tools，同时最小化全球跨度

Question

我想知道如何在CVRP上下文中最小化全局跨度(makespan(。我指的是：

distance_dimension.SetGlobalSpanCostCoefficient(100)

作为一个非常简单的例子，我试图解决CVRP的例子(https://developers.google.com/optimization/routing/cvrp)具有上述SetGlobalSpanCostCoefficient(100(。

然而，无论是否使用SetGlobalSpanCostCoefficient(100(，结果都没有什么不同。

我增加了车辆数量来显示差异，但增加的车辆仍处于闲置状态。这不足以使全局跨度最小化。我还试图将大的数字(如100(增加到更大的数字，但解决方案仍然没有改变。

如何在最小化全局跨度的同时解决CVRP？

谢谢。

Answer 1

通过将非零系数(默认值(设置为全局跨度，您将其添加到目标成本函数中，该函数由解算器最小化，因此它是"已经"；如果它成为主要因素(与电弧成本之和相比(，则最小化

注意示例cvrp不使用本地搜索。。。

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

所以你应该先尝试启用它。

例如

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(30)
search_parameters.log_search = True