1

我想限制由同一辆车服务的位置。我使用容量限制来实现这一点。假设我们有l = [[1,2], [3,4]]这意味着位置 1、2 必须由同一辆车服务,3、4 也必须由同一辆车服务。所以 1, 2 结束route_1, 3, 4结束route_2

我实现这一目标的代码是:

for idx, route_constraint in enumerate(l):
    vehicle_capacities = [0] * NUM_VEHICLES
    vehicle_capacities[idx] = len(route_constraint)
    route_dimension_name = 'Same_Route_' + str(idx)

    def callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return 1 if from_node in route_constraint else 0

    same_routes_callback_index = routing.RegisterUnaryTransitCallback(callback)

    routing.AddDimensionWithVehicleCapacity(
        same_routes_callback_index,
        0,  # null capacity slack
        vehicle_capacities,  # vehicle maximum capacities
        True,  # start cumul to zero
        route_dimension_name)

这个想法是 1,2 每个 1 单位的容量需求(所有其他单位为零)。由于只有车辆 1 的容量为 2,因此它是唯一能够为 1,2 服务的车辆。

如果 len(l) == 1,这似乎工作正常。如果更大,如果我在没有上述代码的情况下放入 l 对位于同一路线上的位置(因此没有上述容量),则求解器无法找到解决方案约束。

  1. 有没有更优雅的方式来模拟我的需求?
  2. 为什么求解器找不到解决方案?

我还考虑了放弃访问的可能性(以高成本),以使求解器有可能从放弃访问的解决方案开始,这样它就会找到从这一点到没有任何放弃的解决方案的方法。我没有运气。

提前致谢。

4

1 回答 1

0

每个停靠点都有一个车辆变量,其值决定了允许哪些车辆访问停靠点。如果您想让车辆 0 为停靠点 1 和 2 提供服务,请对每个停靠点的车辆 var 使用成员约束并将其设置为[0]。由于您可能有其他使停止成为可选的约束,因此将值 -1 添加到列表中。这是一个特殊值,表示该站点没有由车辆服务。

在 Python 中:

n2x = index_manager.NodeToIndex
cpsolver = routing_model.solver()

for stop in [1,2]:
    vehicle_var = routing_model.VehicleVar(n2x(stop))
    values = [-1, 0]
    cpsolver.Add(cpsolver.MemberCt(vehicle_var, values))
于 2019-12-28T09:24:39.450 回答