CPLEX Studio中MDCVRP建模求助：车辆未返回始发仓库

问题描述 #

在CPLEX Studio IDE 22.1.0中进行多仓库容量约束车辆路径问题（MDCVRP）建模，运行后能得到结果，但已使用的车辆并未返回其始发仓库。以下是当前代码及修复方案。

Dat文件 #

n = 9; // 客户+仓库总数
m = 3; // 仓库数量
v = 4; // 可用车辆数

// 每个节点的订单重量（包含仓库，仓库为0）
PO = [0, 0, 0, 20, 30, 25, 15, 35, 40 ];

// 每个节点的订单体积
VO = [0, 0, 0, 40, 50, 45, 35, 55, 60 ];

// 每个节点的订单金额（0表示仓库或无订单）
M = [0, 0, 0, 100, 150, 120, 130, 160, 180 ];

// 车辆的重量容量
CPO = [100, 100, 80, 120 ];

// 车辆的体积容量
CVO = [200, 220, 180, 240 ];

// 车辆启动的最小订单金额要求
MO = [300, 250, 200, 350 ];

// 节点间距离矩阵（客户+仓库）
D = [
    [0, 5, 8, 10, 15, 20, 25, 30, 35 ],
    [5, 0, 7, 10, 15, 20, 25, 30, 35 ],
    [8, 7, 0, 3, 8, 13, 18, 23, 28 ],
    [10, 10, 3, 0, 5, 10, 15, 20, 25 ],
    [15, 15, 8, 5, 0, 5, 10, 15, 20 ],
    [20, 20, 13, 10, 5, 0, 5, 10, 15],
    [25, 25, 18, 15, 10, 5, 0, 5, 10 ],
    [30, 30, 23, 20, 15, 10, 5, 0, 5 ],
    [35, 35, 28, 25, 20, 15, 10, 5, 0 ],
];

Mod文件 #

// 集合与索引声明
int n = ...;
int m = ...;
int v = ...;
// 定义集合范围
range Clients = 1..n;  // 包含仓库和客户
range Entrepots = 1..m;  // 前m个索引为仓库
range Vehicules = 1..v;

// 参数定义
int PO[Clients] = ...;  // 每个节点的订单重量
int VO[Clients] = ...;  // 每个节点的订单体积
int M[Clients] = ...;  // 每个节点的订单金额（仓库为0）
int CPO[Vehicules] = ...;  // 车辆重量容量
int CVO[Vehicules] = ...;  // 车辆体积容量
int MO[Vehicules] = ...;  // 车辆启动最小订单金额
float D[Clients][Clients] = ...;  // 节点间距离

// 决策变量
dvar boolean X[Clients][Clients][Vehicules];  // 车辆k是否行驶弧i->j
dvar boolean U[Vehicules];  // 车辆k是否被使用
dvar float+ W[Clients];  // 子消除变量
// 新增：记录车辆k的始发仓库
dvar boolean Origin[Entrepots][Vehicules];  // Origin[e][k]=1表示车辆k从仓库e出发

// 目标函数：最小化总行驶距离
minimize
    sum(i in Clients, j in Clients, k in Vehicules) D[i][j] * X[i][j][k];

修改后的约束条件 #

// 约束条件
subject to {
    // 车辆重量和体积容量约束
    forall(k in Vehicules)
        sum(i in Clients, j in Clients) PO[j] * X[i][j][k] <= CPO[k];
    forall(k in Vehicules)
        sum(i in Clients, j in Clients) VO[j] * X[i][j][k] <= CVO[k];

    // 有订单的客户必须被恰好服务一次
    forall(j in Clients : M[j] > 0)
        sum(i in Clients, k in Vehicules) X[i][j][k] == 1;

    // 行驶弧与车辆使用状态关联：只有使用的车辆才能行驶
    forall(i in Clients, j in Clients, k in Vehicules)
        X[i][j][k] <= U[k];

    // 子消除约束
    forall(i in Clients, j in Clients : i != j, k in Vehicules)
        W[i] - W[j] + n * X[i][j][k] <= n - 1;

    // 新增：每个使用的车辆只能从一个仓库出发
    forall(k in Vehicules)
        sum(e in Entrepots) Origin[e][k] == U[k];

    // 新增：车辆k从仓库e出发，则必须有弧从e出发
    forall(e in Entrepots, k in Vehicules)
        Origin[e][k] <= sum(j in Clients) X[e][j][k];

    // 修改：车辆k必须返回其始发仓库
    forall(e in Entrepots, k in Vehicules)
        sum(i in Clients) X[i][e][k] == Origin[e][k];
        
    // 禁止车辆自循环
    forall(i in Clients, k in Vehicules)
        X[i][i][k] == 0;
        
    // 流平衡约束：客户节点的流入等于流出
    forall(j in Clients : j > m, k in Vehicules)
        sum(i in Clients) X[i][j][k] == sum(i in Clients) X[j][i][k];

    // 车辆启动的最小订单金额约束
    forall(k in Vehicules)
      sum(i in Clients, j in Clients : M[j] > 0) M[j] * X[i][j][k] >= MO[k] * U[k];
}

显示函数 #

// 结果展示
execute {
    for(var k in Vehicules) {
        if (U[k].solutionValue > 0.5) {
            writeln("车辆", k, "的行驶路径：");
            var distanceTotale = 0;
            // 先找始发仓库
            var originE = 0;
            for(var e in Entrepots) {
                if (Origin[e][k].solutionValue > 0.5) {
                    originE = e;
                    break;
                }
            }
            writeln("  始发仓库：", originE);
            for(var i in Clients) {
                for(var j in Clients) {
                    if (X[i][j][k].solutionValue > 0.5) {
                        writeln("  从", i, "到", j, "，距离：", D[i][j]);
                        distanceTotale += D[i][j];
                    }
                }
            }
            writeln("车辆", k, "总行驶距离：", distanceTotale, "单位。");
        }
    }
}

修复说明 #

1. 核心问题：原约束仅要求车辆返回任意仓库，未限定返回始发仓库，且没有约束车辆必须从特定仓库出发。
2. 新增变量：添加Origin[Entrepots][Vehicules]布尔变量，标记车辆的始发仓库。
3. 约束调整：
   • 确保每个使用的车辆仅从一个仓库出发；
   • 绑定车辆始发仓库与出发弧的关系；
   • 强制车辆返回其始发仓库，替代原有的“返回任意仓库”约束。
4. 显示优化：在结果展示中添加始发仓库的输出，方便验证路径完整性。

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