时间戳

首页 > 解决方案 > Cplex 中的累积 VRP 模型

mathematical-optimization - Cplex 中的累积 VRP 模型

问题描述

我是 Cplex IBM ILOG CPLEX Optimization Studio 的新手，我目前正在编写一个 Cumulative VRP 模型（参考：DOI：10.5772/5812），如下所示：

在此处输入图像描述

这是我的代码：

{string} CIUDADES = ...;
 int READY_TIME[CIUDADES] = ...;
 int DUE_TIME[CIUDADES] = ...;
 int SERVICETIME[CIUDADES] = ...;
 int DISTANCIA[CIUDADES, CIUDADES] = ...;
 int CLIENTES=11;
 int Penalizacion = 10;
 int DEMANDAS[CIUDADES] = ...;
 int NROCIUDADES[CIUDADES] = ...;
int PESO_VACIO = 6350;
int PESO_LLENO = 3650;
int VELOCIDAD_MINIMA = 20;
int VELOCIDAD_MAXIMA = 90;
int UMBRAL_RETRASO = 300;
int aux = 0;
int CARGAT = sum(ci in CIUDADES) DEMANDAS[ci];
int vehiculos =1;

//DV
dvar int X[CIUDADES,CIUDADES] in 0..1;
dvar int Y[CIUDADES, CIUDADES] in 0..(CARGAT+PESO_VACIO);

minimize
    sum(ci in CIUDADES) 
        sum(cj in CIUDADES)
          DISTANCIA[ci,cj]*Y[ci,cj];

subject to {
    restriccion1: 
            sum(ci in CIUDADES) 
                X["Kingston_upon_Hull",ci]==1;  

    restriccion2: 
            sum(ci in CIUDADES) 
                X[ci,"Kingston_upon_Hull"]==1;

    forall(cj in CIUDADES) {
    restriccion3: 
            sum(ci in CIUDADES: ci!=cj) 
                (X[ci,cj])==1;
}

    forall(ci in CIUDADES) {
    restriccion4: 
            sum(cj in CIUDADES: ci!=cj) 
                (X[ci,cj])==1;
}   

forall(ci in CIUDADES) {
    restriccion5: 
            ((sum(cj in CIUDADES: ci!=cj) 
                (Y[cj,ci]))
                -
            (sum(cj in CIUDADES: ci!=cj) 
                (Y[ci,cj])))
            == DEMANDAS[ci];

}   

forall(ci in CIUDADES) {
    restriccion6:
     Y[ci,"Kingston_upon_Hull"]== PESO_VACIO*X[ci,"Kingston_upon_Hull"];
}   

forall(ci in CIUDADES, cj in CIUDADES) {
    restriccion7:
     Y[ci,cj] <= ((77777777)-DEMANDAS[ci])*X[ci,cj];

}

forall(ci in CIUDADES, cj in CIUDADES) {
    restriccion8:
     Y[ci,cj] >= ((PESO_VACIO)-DEMANDAS[cj])*X[ci,cj];
}

forall(ci in CIUDADES) {
    restriccion9:
     Y["Kingston_upon_Hull",ci]== (PESO_VACIO+CARGAT)*X["Kingston_upon_Hull",ci];
}
}

但是使用 CPLEX 编译我得到以下结果：

/ solution (feasible relaxed sum of infeasibilities) with objective 5671
// Quality Incumbent solution:
// MILP objective                                 6.6464998100e+09
// MILP solution norm |x| (Total, Max)            1.02485e+05  1.20210e+04
// MILP solution error (Ax=b) (Total, Max)        0.00000e+00  0.00000e+00
// MILP x bound error (Total, Max)                0.00000e+00  0.00000e+00
// MILP x integrality error (Total, Max)          0.00000e+00  0.00000e+00
// MILP slack bound error (Total, Max)            5.67100e+03  5.67100e+03
Y = [[0
             0 0 0 0 0 0 0 0 0 12021]
             [0 0 10186 0 0 0 0 0 0 0 0]
             [0 0 0 9372 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0 8752 0 0]
             [0 10907 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 11218 0 0 0 0 0 0]
             [6350 0 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 6863 0 0 0 0]
             [0 0 0 0 0 0 0 0 0 7989 0]
             [0 0 0 0 0 0 0 7431 0 0 0]
             [0 0 0 0 0 11385 0 0 0 0 0]];
X = [[0 0 0 0 0 0 0 0 0 0 1]
             [0 0 1 0 0 0 0 0 0 0 0]
             [0 0 0 1 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0 1 0 0]
             [0 1 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 1 0 0 0 0 0 0]
             [1 0 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 1 0 0 0 0]
             [0 0 0 0 0 0 0 0 0 1 0]
             [0 0 0 0 0 0 0 1 0 0 0]
             [0 0 0 0 0 1 0 0 0 0 0]];

并在windows中通过cmd编译oplrun -p folder，我得到以下信息：

Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de2ae    
Infeasibility row 'restriccion1':  0  = 1.
Presolve time = 0.02 sec. (0.76 ticks)

我的程序对变量 Xij 和 Yij 进行了赋值，但没有优化目标函数。我会在哪里出错？您的帮助将不胜感激。

谢谢！

标签： mathematical-optimizationcplex

解决方案

在 IDE 中，您会感到放松，因为您的模型不可行，而使用命令行时，您只会收到一条很小的消息。

如果您想使用命令行查看放松，请执行 oplrun -relax

很简单的例子。

让我们继续

https://www.linkedin.com/pulse/what-optimization-how-can-help-you-do-more-less-zoo-buses-fleischer/

并解决一个新的问题：不可行！

让我们假设我们有一个新的挑战：总共使用少于 7 辆公共汽车。

然后我们写

int nbKids=300;
float costBus40=500;
float costBus30=400;

dvar int+ nbBus40;
dvar int+ nbBus30;

minimize
 costBus40*nbBus40  +nbBus30*costBus30;

subject to
{
 ctAllKidsNeedToGo:
     40*nbBus40+nbBus30*30>=nbKids;

 ctMaxTotalBuses:
     nbBus30+nbBus40<=7;
}

ctAllKidsNeedToGo 和 ctMaxTotalBus 是约束的标签。

但随后问题变得不可行，因为即使有 7 辆公共汽车和 40 个座位，您也只能带 280=7*40 个孩子，少于 300 个孩子。

当我们启动这个模型时，我们会遇到冲突

这意味着我们在这两个约束中存在冲突和放松，这意味着如果我们将 7 辆公共汽车放松到 8 辆公共汽车，那么我们就有一个可行的解决方案。

这对于这个小例子来说不是很有用，但对于真实模型来说，这可能是关键。

有关更多信息，请参阅 CPLEX 文档中的 IDE 教程中的放宽不可行模型

注意：

您还可以通过脚本中的流控制获取该信息：

int nbKids=300;
float costBus40=500;
float costBus30=400;

dvar int+ nbBus40;
dvar int+ nbBus30;

minimize
 costBus40*nbBus40  +nbBus30*costBus30;

subject to
{
 ctAllKidsNeedToGo:
     40*nbBus40+nbBus30*30>=nbKids;

 ctMaxTotalBuses:
     nbBus30+nbBus40<=7;
}

main
{
thisOplModel.generate();
if (!cplex.solve())
{
writeln(thisOplModel.printRelaxation());
writeln(thisOplModel.printConflict());
}
}

给

ctMaxTotalBuses
    relax [-Infinity,7] to [-Infinity,8] value is -Infinity

ctAllKidsNeedToGo
  is in conflict
ctMaxTotalBuses
  is in conflict

推荐阅读