如何在OR-Tools的带容量车辆路径问题(CVRP)中添加多维度约束

你可以直接复用OR-Tools路由库的多容量维度能力，在现有单容量约束的基础上，分别为重量、长、宽、高添加独立的容量约束，同时通过预处理长宽取值的方式兼容货物横竖旋转的需求。

1 数据结构调整 #

首先在你现有的data字典中补充以下字段：

• 货物维度属性：weight_demands（各节点货物重量）、length_demands（各节点货物原始长度）、width_demands（各节点货物原始宽度）、height_demands（各节点货物高度）
• 车辆装载上限：vehicle_weight_limits（各车辆最大载重）、vehicle_length_limits（各车辆货箱长度）、vehicle_width_limits（各车辆货箱宽度）、vehicle_height_limits（各车辆货箱高度）
• 旋转开关：allow_rotation（布尔值，为True时允许货物水平旋转，长宽互换）

2 兼容货物旋转逻辑 #

针对货物可横竖放置的需求，不需要额外引入复杂逻辑，仅需要在计算长宽约束时，对货物长宽取极值匹配即可：

• 允许旋转时，取单货物长宽的最大值和车辆长宽的最大值比对，最小值和车辆长宽的最小值比对，即可覆盖所有水平旋转的可行场景。比如你举的例子：货箱10x10x10，货物12x1x1，货物长宽最大值为12，大于货箱长宽最大值10，会直接触发约束不满足，符合实际装载要求。

3 新增多维度约束代码 #

在你原有单容量约束代码的基础上，新增四个独立的容量维度即可：

重量约束 #

def weight_callback(from_index):
    """返回节点的货物重量需求"""
    from_node = manager.IndexToNode(from_index)
    return data['weight_demands'][from_node]

weight_callback_index = routing.RegisterUnaryTransitCallback(weight_callback)
routing.AddDimensionWithVehicleCapacity(
    weight_callback_index,
    0,
    data['vehicle_weight_limits'],
    True,
    'Weight'
)

长度约束 #

def length_callback(from_index):
    """返回节点货物的长度约束值（自动处理旋转逻辑）"""
    from_node = manager.IndexToNode(from_index)
    l = data['length_demands'][from_node]
    w = data['width_demands'][from_node]
    return max(l, w) if data['allow_rotation'] else l

length_callback_index = routing.RegisterUnaryTransitCallback(length_callback)
# 车辆端同步取长宽最大值做匹配
vehicle_max_length = [max(l, w) for l, w in zip(data['vehicle_length_limits'], data['vehicle_width_limits'])]
routing.AddDimensionWithVehicleCapacity(
    length_callback_index,
    0,
    vehicle_max_length,
    True,
    'Length'
)

宽度约束 #

def width_callback(from_index):
    """返回节点货物的宽度约束值（自动处理旋转逻辑）"""
    from_node = manager.IndexToNode(from_index)
    l = data['length_demands'][from_node]
    w = data['width_demands'][from_node]
    return min(l, w) if data['allow_rotation'] else w

width_callback_index = routing.RegisterUnaryTransitCallback(width_callback)
# 车辆端同步取长宽最小值做匹配
vehicle_min_width = [min(l, w) for l, w in zip(data['vehicle_length_limits'], data['vehicle_width_limits'])]
routing.AddDimensionWithVehicleCapacity(
    width_callback_index,
    0,
    vehicle_min_width,
    True,
    'Width'
)

高度约束 #

def height_callback(from_index):
    """返回节点的货物高度需求"""
    from_node = manager.IndexToNode(from_index)
    return data['height_demands'][from_node]

height_callback_index = routing.RegisterUnaryTransitCallback(height_callback)
routing.AddDimensionWithVehicleCapacity(
    height_callback_index,
    0,
    data['vehicle_height_limits'],
    True,
    'Height'
)

注意事项 #

• 上述长宽约束的处理逻辑默认是单辆车每次仅装载一个货物的场景，如果你需要支持单辆车装载多个货物的堆叠排布，需要额外结合三维装箱算法，在路由的约束回调中嵌入装箱可行性校验逻辑。
• 所有维度的slack参数设置为0，代表不允许超过任何一个维度的装载上限，你可以根据实际业务需求调整该参数。

内容的提问来源于stack exchange，提问作者Prashanth Thugaiah