时间戳

首页 > 解决方案 > OR-Tools VRP：限制同一车辆服务的位置

modeling - OR-Tools VRP：限制同一车辆服务的位置

问题描述

我想限制由同一辆车服务的位置。我使用容量限制来实现这一点。假设我们有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. 为什么求解器找不到解决方案？

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

提前致谢。

标签： modelingor-toolsvehicle-routing

解决方案

每个停靠点都有一个车辆变量，其值决定了允许哪些车辆访问停靠点。如果您想让车辆 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))

推荐阅读