3

建议使用跨度成本系数来最小化车辆之间的最大距离

# Try to minimize the max distance among vehicles.
# /!\ It doesn't mean the standard deviation is minimized
distance_dimension.SetGlobalSpanCostCoefficient(100)

取自https://developers.google.com/optimization/routing/vrp#example

当成本函数不是基于距离（即燃料使用）而是基于行驶时间并且目标是让最后一辆车尽早返回站点时，这尤其有用。

Q1：我可以将目标函数定义为车辆之间的最大成本（而不是总成本和全局跨度的总和）吗？

如果这是不可能的，我想知道原因是什么。我可以想象A）很难实现这样的约束或B）我错过了一些导致不良解决方案的隐含缺点（与使用跨度约束相比）。

我注意到全局跨度约束，即使我将其设置为 1000（但这意味着什么？），甚至不能保证所有车辆都在使用。当然，我可以通过使用更多车辆来改进该解决方案，对吧？

编辑：这是一个最小的工作示例。5 辆车可用于服务 20 个站点。我将停靠点之间的统一行驶时间定义为 1 小时，因此最佳解决方案是每条路线包含 4 个停靠点，并且所有车辆在 4 小时后返回站点。在没有全局跨度约束的情况下，一辆车完成所有工作的总时间为 20 小时。使用全局跨度约束（系数 = 1000），两辆车各服务 10 个站点。

import ortools.constraint_solver.pywrapcp
import ortools.constraint_solver.routing_enums_pb2

stops = 20
vehicles = 5
depot = 0

routing = ortools.constraint_solver.pywrapcp.RoutingModel(stops, vehicles, depot)

def cost_function(x,y):
    return 1

routing.SetArcCostEvaluatorOfAllVehicles(cost_function)

evaluator = cost_function
slack_max = 24
capacity = 24
fix_start_cumul_to_zero = True
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)

time_dimension = routing.GetDimensionOrDie("time")
time_dimension.SetGlobalSpanCostCoefficient(1000)

search_params = ortools.constraint_solver.pywrapcp.RoutingModel.DefaultSearchParameters()
assignment = routing.SolveWithParameters(search_params)

解决方案绘图仪的输出：

车辆 0 的路线：0 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 0 路线的持续时间：10 小时

车辆 1 的路线：0 -> 10 -> 0 路线 1 的持续时间：2 小时

车辆 2 的路线：0 -> 0 路线 2 的持续时间：1 小时

车辆 3 的路线：0 -> 0 路线 3 的持续时间：1 小时

车辆 4 的路线：0 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 路线 4 的持续时间：10 小时

所有路线的总时长：24 小时

4

0 回答 0