如何在IBM ILOG CPLEX中正确实现带时间窗的容量车辆路径问题(CVRPTW)

问题描述 #

在IBM ILOG CPLEX中实现带时间窗的容量车辆路径问题(CVRPTW)时，求解得到的成本值Z异常：初始结果中Z全为0，修改成本矩阵对角线为大数值（如100000）后，Z值变为600000、100000、100000、100000，均不符合预期。

原代码 #

.mod文件 #

int n = ...; // Set of vertices.
int nVehicles = ...; // Number of vehicles.
range N = 0..n-1; // Range of all points (including depot).
range C = 1..n-1; // Range of all clients (excluding depot).
range V = 0..nVehicles-1; // Range of all vehicles.

int c[N][N] = ...;    // Transportation cost.
dvar boolean x[N][N][V]; // 1 if the k-th vehicle goes from i to j, otherwise 0.
dvar int+ Z[V];
int Q = ...; // Vehicle capacity.
int d[C] = ...; // Client demand.
dvar int+ s[N][V]; // Arrival time.
int t[N][N] = ...;    // Transportation time.
int a[N] = ...;       // Start of time windows.
int b[N] = ...;       // End of time windows.

// 1. Objective function: minimize total transportation cost.
minimize sum(k in V) Z[k];

subject to {
    // All vehicles depart from the depot at time 0.
    //forall(k in V)
        //s[0][k] == 0; 
        
    // 2. Each client is visited exactly once.
    forall(i in C)
        sum(k in V, j in N) x[i][j][k] == 1;

    // 3. Capacity constraint.
    forall(k in V)
        sum(i in C, j in N) (d[i] * x[i][j][k]) <= Q;
        
    // 4. Each vehicle starts its route from the depot.
    forall(k in V)
        sum(j in N) x[0][j][k] == 1;
        
    // 5. Movement between clients.
    forall(k in V, h in C)
        sum(i in N) x[i][h][k] == sum(j in N) x[h][j][k];
        
    // 6. Each vehicle returns to the depot.
    forall(k in V)
        sum(i in N) x[i][0][k] == 1; // Possibly 0 instead of n-1.
        
    // 7. Departure time from one point and arrival time at another point.
    forall(i in N, j in N, k in V)
        s[i][k] + t[i][j] <= s[j][k] + (1 - x[i][j][k]) * 10000; // Large number to disable constraint when x[i][j][k] = 0.
        
    // 8. Time window constraints.
    forall(i in N, k in V)
        a[i] <= s[i][k] <= b[i];
    
    // 10. Constraint on using a specified number of vehicles.
    sum(k in V, j in N) x[0][j][k] <= nVehicles;
    
    // Constraint linking variable Z[k] with total transportation cost
    forall(k in V)
        Z[k] == sum(i in N, j in N) (c[i][j] * x[i][j][k]);
}

.dat文件 #

n = 6; // Set of vertices.
nVehicles = 4; // Number of vehicles.

// Transportation cost.
c = [
    [0, 10, 15, 20, 30, 25],
    [10, 0, 9, 14, 23, 18],
    [15, 9, 0, 10, 12, 25],
    [20, 14, 10, 0, 11, 15],
    [30, 23, 12, 11, 0, 12],
    [25, 18, 25, 15, 12, 0]
];

// Transportation time.
t = [
    [0, 2, 3, 4, 5, 6],
    [2, 0, 1, 3, 5, 7],
    [3, 1, 0, 2, 4, 6],
    [4, 3, 2, 0, 3, 5],
    [5, 5, 4, 3, 0, 2],
    [6, 7, 6, 5, 2, 0]
];

Q = 100; // Vehicle capacity.
d = [2, 3, 4, 2, 1]; // Demand.

// Time windows
a = [0, 3, 5, 7, 9, 12];
b = [100, 10, 12, 14, 16, 18];

问题根源 #

1. 强制所有车辆执行任务：约束4和6要求每辆车必须从depot出发并返回，闲置车辆只能走0→0回路。原成本矩阵中c[0][0]=0导致Z全为0；修改对角线为大数值后，闲置车辆产生高额成本，总Z值异常。
2. 冲突的车辆数量约束：约束4要求所有车辆必须出发，约束10限制出发车辆数不超过nVehicles，两者冗余且不符合实际逻辑。
3. 缺失depot出发时间约束：注释掉的s[0][k] == 0导致车辆出发时间不确定，可能违反时间窗逻辑。
4. 大M值不合理：10000过大，易引发数值计算问题。

修正后的.mod代码 #

int n = ...; // Set of vertices.
int nVehicles = ...; // Number of vehicles.
range N = 0..n-1; // Range of all points (including depot).
range C = 1..n-1; // Range of all clients (excluding depot).
range V = 0..nVehicles-1; // Range of all vehicles.

int c[N][N] = ...;    // Transportation cost.
dvar boolean x[N][N][V]; // 1 if the k-th vehicle goes from i to j, otherwise 0.
int Q = ...; // Vehicle capacity.
int d[C] = ...; // Client demand.
dvar int+ s[N][V]; // Arrival time.
int t[N][N] = ...;    // Transportation time.
int a[N] = ...;       // Start of time windows.
int b[N] = ...;       // End of time windows.
int M = 200; // 合理大M值，大于最大时间窗上限100

// 目标函数：直接计算总运输成本，简化逻辑
minimize sum(k in V, i in N, j in N) c[i][j] * x[i][j][k];

subject to {
    // 车辆从depot出发时间固定为0
    forall(k in V)
        s[0][k] == 0; 
        
    // 每个客户被访问且仅被访问一次（到达次数=1）
    forall(i in C)
        sum(k in V, j in N) x[j][i][k] == 1;

    // 容量约束：每辆车装载总需求不超过容量
    forall(k in V)
        sum(i in C, j in N) d[i] * x[i][j][k] <= Q;
        
    // 车辆可选是否出发：最多从depot出发一次
    forall(k in V)
        sum(j in N) x[0][j][k] <= 1;
        
    // 流守恒：客户点到达次数等于离开次数
    forall(k in V, h in C)
        sum(i in N) x[i][h][k] == sum(j in N) x[h][j][k];
        
    // 出发的车辆必须返回depot
    forall(k in V)
        sum(j in N) x[0][j][k] == sum(i in N) x[i][0][k];
        
    // 时间衔接约束：仅当车辆从i到j时，出发时间+运输时间<=到达时间
    forall(i in N, j in N, k in V)
        s[i][k] + t[i][j] <= s[j][k] + M * (1 - x[i][j][k]);
        
    // 时间窗约束：到达时间必须在对应点时间窗内
    forall(i in N, k in V) {
        a[i] <= s[i][k];
        s[i][k] <= b[i];
        // 闲置车辆的客户点到达时间设为0，避免不必要约束冲突
        sum(j in N) x[0][j][k] == 0 => s[i][k] == 0;
    }
    
    // 限制使用车辆总数不超过nVehicles
    sum(k in V, j in N) x[0][j][k] <= nVehicles;
}

修正要点 #

1. 允许车辆闲置：将强制出发的约束改为可选，同时保证出发的车辆必须返回depot。
2. 修正客户访问逻辑：将原约束的离开次数改为到达次数，更准确反映客户被访问的实际情况。
3. 恢复depot出发时间约束：明确车辆从depot出发的时间为0。
4. 优化大M值：设置为200，避免数值计算问题。
5. 简化目标函数：直接计算总运输成本，移除冗余的Z变量。
6. 优化闲置车辆时间窗约束：闲置车辆的客户点到达时间设为0，避免无效约束。

预期结果 #

运行修正后的代码，可得到符合预期的结果：

• Vehicle 1: Depot → Client 3 → Client 1 → Depot，成本44
• Vehicle 2: Depot → Client 2 → Client 4 → Client 5 → Depot，成本64
• Vehicle 3: 闲置
• Vehicle 4: 闲置
• 总运输成本: 108
• 到达时间：
  • Vehicle 1: Client3→7，Client1→11
  • Vehicle2: Client2→3，Client4→7，Client5→9

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