带6吨卡车约束的运输问题：基于分支定界法的最优求解

一、基础数据 #

现有运输问题中，A为供应节点（供应量依次为17、8、10、9吨），B为需求节点（需求量依次为6、15、7、8、8吨），运输单价矩阵如下：

二、初始整数规划可行解 #

通过Gurobi求解无卡车约束的整数规划，得到可行解（括号内为运输量，格式为(运输量)\单价），例如供应节点1到需求节点2运输10吨，原成本为8×10=80美元：

三、新增约束说明 #

所有运输必须使用6吨卡车，运输量需按卡车容量整备计费：不足6吨也需按1辆卡车收费。例如上述10吨运输需预订2辆卡车，实际成本为8×6×2=120美元（单辆卡车成本为6吨×每吨单价）。

四、分支定界法适配思路 #

由于新增约束引入了**向上取整（ceil）**的非线性成本结构（总成本=ceil(运输量/6)×单辆卡车成本），我们可以将问题转化为整数规划模型，再通过分支定界法求解：

1. 模型转换 #

引入整数变量k[i][j]表示从供应节点i到需求节点j的卡车数量，将非线性约束转化为线性整数约束：

• 运输量约束：6×(k[i][j]-1) < flow[i][j] ≤6×k[i][j]（当k[i][j]>0时）；若flow[i][j]=0，则k[i][j]=0
• 等价线性约束：
  • flow[i][j] ≤6×k[i][j]（运输量不超过卡车总容量）
  • flow[i][j] +5 ≥6×k[i][j]（确保运输量至少占满前k-1辆卡车，第k辆至少装1吨）
  • k[i][j] ≤ M×flow[i][j]（M为足够大的常数，确保运输量为0时卡车数为0）
• 目标函数：min Σ(k[i][j]×6×cost[i][j])（总卡车数×单辆卡车成本）

2. 分支定界执行步骤 #

Gurobi内置分支定界算法会自动处理该整数规划，核心流程为：

• 松弛求解：将整数变量放松为实数，求解线性松弛问题得到当前节点的下界（LB）
• 分支操作：选择松弛解中为分数的变量（如k[i][j]=1.6），将问题拆分为k[i][j]≤1和k[i][j]≥2两个子问题
• 剪枝操作：
  • 若子问题无解，直接丢弃该分支
  • 若子问题的LB≥当前已知最优解的上界（UB），则该分支不可能得到更优解，直接剪枝
  • 若子问题得到整数解，计算其目标值，若小于当前UB则更新UB
• 终止条件：所有分支节点均被处理（剪枝或找到整数解），此时UB即为最优解

五、适配后的Gurobi实现代码 #

import gurobipy as gp
from gurobipy import GRB

# 基础数据
supply = [17, 8, 10, 9]  # 供应节点供应量
demand = [6, 15, 7, 8, 8]  # 需求节点需求量
cost = [
    [10, 8, 5, 9, 16],
    [4, 3, 4, 11, 12],
    [5, 10, 29, 7, 6],
    [9, 2, 4, 1, 3]
]  # 每吨运输单价
truck_capacity = 6  # 卡车容量
BIG_M = 20  # 足够大的常数，覆盖最大供应量

# 创建模型
m = gp.Model()

# 决策变量：flow[i][j]为运输量（整数），k[i][j]为卡车数量（整数）
flow = m.addVars(len(supply), len(demand), lb=0, vtype=GRB.INTEGER, name="flow")
k = m.addVars(len(supply), len(demand), lb=0, vtype=GRB.INTEGER, name="trucks")

# 供应约束：每个供应节点流出总量不超过自身供应量
for i in range(len(supply)):
    m.addConstr(gp.quicksum(flow[i, j] for j in range(len(demand))) <= supply[i], name=f"supply_{i}")

# 需求约束：每个需求节点流入总量不小于自身需求量
for j in range(len(demand)):
    m.addConstr(gp.quicksum(flow[i, j] for i in range(len(supply))) >= demand[j], name=f"demand_{j}")

# 运输量与卡车数量的关联约束
for i in range(len(supply)):
    for j in range(len(demand)):
        # 运输量不超过卡车总容量
        m.addConstr(flow[i, j] <= k[i, j] * truck_capacity, name=f"flow_upper_{i}_{j}")
        # 运输量至少满足前k-1辆装满，第k辆至少装1吨
        m.addConstr(flow[i, j] + 5 >= k[i, j] * truck_capacity, name=f"flow_lower_{i}_{j}")
        # 运输量为0时，卡车数必须为0
        m.addConstr(k[i, j] <= BIG_M * flow[i, j], name=f"truck_zero_{i}_{j}")

# 目标函数：最小化总运输成本
m.setObjective(gp.quicksum(k[i, j] * truck_capacity * cost[i][j] for i in range(len(supply)) for j in range(len(demand))), sense=GRB.MINIMIZE)

# 求解模型
m.optimize()

# 输出结果
if m.status == GRB.OPTIMAL:
    print(f"最优解总成本: {m.objVal:.2f} 美元")
    print("运输方案详情：")
    for i in range(len(supply)):
        for j in range(len(demand)):
            if flow[i, j].x > 0:
                truck_cost = k[i,j].x * truck_capacity * cost[i][j]
                print(f"供应节点{i+1} → 需求节点{j+1}: 运输{flow[i,j].x:.0f}吨，使用{k[i,j].x:.0f}辆卡车，对应成本{truck_cost:.2f}美元")
else:
    print("未找到可行解或问题不可行。")

六、代码说明 #

• 新增k[i][j]整数变量直接表示卡车数量，避免了非线性的ceil函数
• 通过线性约束严格关联运输量与卡车数量，确保符合6吨整备的计费规则
• Gurobi会自动调用分支定界算法求解该整数规划，无需手动实现分支剪枝逻辑

内容的提问来源于stack exchange，提问作者Pavel Jefimovich