使用 SetGlobalSpanCostCoefficient 导致 OR-tools VRP 中的路由更差

Question

我正在使用 OR-tools VRP 创建配送路线。我将距离作为一个维度，一个维度来限制每条路线的交付点数量，我的代码与 https://developers.google.com/optimization/routing/vrp

中共享的指南非常相似

我遇到的问题是，当使用如下所示的 SetGlobalSpanCostCoefficient 时，生成的路线从仓库到第一个交货点以及从最后一个交货点到仓库的距离非常短，而是交货点之间的距离高。相反，当不使用此 SetGlobalSpanCostCoefficient 时，路线在交货点之间的距离非常短，但往返于仓库的距离更高。

distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

此外，当不使用跨度成本时，所有路由的距离总和较低。根据指标和路线在地图中的外观，我认为不使用跨度成本更好。见下图中的路线，首先不使用跨度成本，其次使用它。

我担心的是，如果我不使用跨度成本，我不知道求解器是在优化路线还是只是创建一个贪婪的解决方案（我首先使用 PATH_CHEAPEST_ARC解策略）。有人可以解释为什么我在这两种情况下都得到这些路由，并告诉我在不使用 span 时得到的路由是否是最佳的？

Answer 1

在这两种情况下，您总是将弧成本添加到 objective，全局跨度成本系数添加额外成本 coeff * (max_end - min_start)
注意：当使用系数 100 时，它只会使成本成为主导因素...

首先，求解器尝试使用第一个策略启发式创建初始解决方案。

然后如果启用本地搜索，解决方案可能会大大改善 -> 是否启用本地搜索？

    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.log_search = True
    search_parameters.time_limit.FromSeconds(20)

使用 SetGlobalSpanCostCoefficient 导致 OR-tools VRP 中的路由更差

Using SetGlobalSpanCostCoefficient lead to worse routes in OR-tools VRP

optimization

routes

or-tools