Gurobi 模型最优但违反约束
Gurobi model optimal but constraints violated
我正在使用 Gurobi 在 JAVA 中编写车辆路径问题 (VRP) 的扩展。我遇到的问题是，当我 运行 我的代码时，JAVA 说它是最优的 objective 值为零。这不应该是这种情况，因为：
VRP 适用于弧和节点。是否使用弧线由 Xijk 变量指示（您是否乘坐车辆 k 从节点 i 到节点 j）。在 VRP 中，一个约束尤其是每个客户都需要访问一次。这意味着客户 j 的至少一个 Xijk 需要是一个。使用了哪辆车 k 以及之前访问过的节点 i 是什么，这些都是你要求 Gurobi 找出的。
因此只有当 Xijk 变量在 objective 函数中具有零成本因子时，objective 值等于零似乎是合乎逻辑的。然而，对我来说情况并非如此，因为我在代码末尾（重新）编写了 objective 函数，并使用节点 i 到 j 之间的距离作为成本因子。即使当我查看由 "model.write("constraintOutput.lp")" 检索的模型公式时，我也会看到一个 objective 函数，其中包含成本因子 >0 的 Xijk 变量。
所以，我四处寻找解决方案，有人提到问题可能是：
一个。 初始化变量时，第三个参数不应该为零，因为它说明变量的 "cost-factor" 应该在 objective 函数中。 因为我写了我的在优化我的模型之前在我的代码的最后部分进行约束，我相信这应该无关紧要。虽然我在初始化Xijk变量的时候把这个参数从0改成了1，但是问题依旧。
b。 我应该在初始化我的变量和约束后更新我的模型。我已经这样做了，但问题仍然存在。
我什至通过删除一些约束来减少我的模型，但这没有帮助。
有人知道如何解决这个问题吗？
我的代码：
import java.util.ArrayList;
import gurobi.GRB;
import gurobi.GRBEnv;
import gurobi.GRBException;
import gurobi.GRBLinExpr;
import gurobi.GRBModel;
import gurobi.GRBVar;
public class VRP {
public int M; //big number
public int speed; //speed km/h
public int nDepots; //number of depots
public int nCustomers; //number of customers to be visited
public ArrayList<Node> allLocations; //All locations
public ArrayList<Vehicle> vehicleList; //Vehicles
public double [][] dm; //distance matrix
public VRP(ArrayList<Node> n, ArrayList<Node> d, ArrayList<Node> dummyd, ArrayList<Vehicle> v, double [][] distanceMatrix) throws Exception {
this.M = 1000;
this.speed = 60000;
this.vehicleList = v;
this.allLocations = new ArrayList<Node>();
this.allLocations.addAll(d);
this.allLocations.addAll(n);
this.nDepots = d.size();
this.nCustomers = n.size();
this.dm = distanceMatrix;
}
public void solution() throws Exception{
Functions f = new Functions();
// 1. DEFINE MODEL -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
try{
GRBEnv env = new GRBEnv ();
env.set(GRB.IntParam.OutputFlag, 0); //set to 1 to get constraint overview
GRBModel model = new GRBModel(env);
model.set ( GRB.StringAttr.ModelName, "VRP" );
// 2. DEFINE VARIABLES -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//Xijqk
GRBVar[][][] x = new GRBVar[this.allLocations.size()][this.allLocations.size()][this.vehicleList.size()];
for (int i = 0; i<this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
for (int k = 0; k < this.vehicleList.size(); k++){
double dij = f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID);
//get.Distance retrieves the distance between two nodes that are indicated by their IDs
x[i][j][k] = model.addVar(0.0, 1.0, dij, GRB.BINARY, "X" + i + j + k); //arc between node i and j used by vehicle k or not
}//k
}//j
}//i
//aik: arival time at customer i by vehicle k
GRBVar[][] a = new GRBVar[this.allLocations.size()][this.vehicleList.size()];
for (int i = 0; i<this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
a[i][k] = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "a" + i + k); //arival time at node i by vehicle k
}//k
}//i
//dep: departure time from customer i by vehicle k
GRBVar[][] dep = new GRBVar[nDepots][this.vehicleList.size()];
for (int i = 0; i < nDepots; i++){
for (int k = 0; k < this.vehicleList.size(); k++){
dep[i][k] = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "dep" + i + k); //departure time from depot i by vehicle k
}//k
}//i
model.update();
//3. DEFINE CONSTRAINTS
//Constraint 1
for (int j = nDepots; j < this.allLocations.size(); j++){
GRBLinExpr lhs = new GRBLinExpr();
for(int i = 0; i < this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//k
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.EQUAL, rhs, "Constraint 1");
}//j
//Constraint 2
for (int i = nDepots; i < this.allLocations.size(); i++){
GRBLinExpr lhs = new GRBLinExpr();
for(int j = 0; j < this.allLocations.size(); j++){
for (int k = 0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//k
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.EQUAL, rhs, "Constraint 2:");
}//j
//Constraint 3
for (int s = nDepots; s < this.allLocations.size(); s++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = 0; i < this.allLocations.size(); i++){
lhs.addTerm(1, x[i][s][k]);
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 3");
}//k
}//s
//Constraint 4
for (int s = nDepots; s < this.allLocations.size(); s++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int j = 0; j < this.allLocations.size(); j++){
lhs.addTerm(1, x[s][j][k]);
}//j
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 4");
}//k
}//s
//Constraint 5
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = 0; i < nDepots; i++){
for (int j = nDepots; j < this.allLocations.size(); j++){
lhs.addTerm(1, x[i][j][k]);
}//j
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 5:");
}//k
//Constraint 6
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int j = 0; j < nDepots; j++){
lhs.addTerm(1, x[i][j][k]);
}//j
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 6:");
}//k
//Constraint 7: Capacity constraints of vehicles
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i =0; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
lhs.addTerm(2, x[i][j][k]);
}//j
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(20);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 7: Capacity");
}//k
//Constraint 8: #vehicles entering depot cannot exceed depot capacity
for (int j=0; j < nDepots; j++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int k=0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//for k
}// for i
GRBLinExpr rhs = new GRBLinExpr();
int pj = this.allLocations.get(j).vehicleCapacity;
rhs.addConstant(pj);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 8");
}//i
//Constraint 9: TimeWindow
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[i][k]);
GRBLinExpr rhs = new GRBLinExpr();
double stwi = this.allLocations.get(i).startTime;
rhs.addConstant(stwi);
model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 9: ");
}//k
}//i
//Constraint 10: TimeWindow
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[i][k]);
GRBLinExpr rhs = new GRBLinExpr();
double etw = this.allLocations.get(i).endTime;
rhs.addConstant(etw);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 10:");
}//for k
}//i
//Constraint 11: determine departure vehicle from depot
for (int i = 0; i < nDepots; i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
double eid = this.allLocations.get(i).startTime;
lhs.addConstant(eid);
GRBLinExpr rhs = new GRBLinExpr();
rhs.addTerm(1, dep[i][k]);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 11:" );
}//k
}//i
//Constraint 12: determine returning time to depot
for (int i = 0; i < nDepots; i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[i][k]);
GRBLinExpr rhs = new GRBLinExpr();
double lid = this.allLocations.get(i).returningTime;
rhs.addConstant(lid);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 12: " );
}//k
}//i
//Constraint 13: precedence constraint 1
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
if (i != j){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[j][k]);
GRBLinExpr rhs = new GRBLinExpr();
rhs.addTerm(1, a[i][k]);
double si = this.allLocations.get(i).serviceTime;
rhs.addConstant(si);
double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
rhs.addConstant(dtij);
rhs.addConstant(-M);
rhs.addTerm(M, x[i][j][k]);
model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 13: ");
}//k
}//if
}//j
}//i
//Constraint 14: precedence constraint 2 - if previous node was depot
for (int i = 0; i < nDepots; i++){
for (int j = nDepots; j < this.allLocations.size(); j++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[j][k]);
GRBLinExpr rhs = new GRBLinExpr();
rhs.addTerm(1, dep[i][k]);
double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
rhs.addConstant(dtij);
rhs.addConstant(-M);
rhs.addTerm(M, x[i][j][k]);
model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 14: ");
}//for k
}//for j
}//for i
model.update();
//4. SET OBJECTIVE ---------------------------------------------------------------------------------------------------------------------------------------
GRBLinExpr expr = new GRBLinExpr();
for (int i = 0; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
if (i != j){
for (int k = 0; k < this.vehicleList.size(); k++){
double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
expr.addTerm(dtij, x[i][j][k]);
}//k
}//if
}//j
}//i
model.setObjective(expr, GRB.MINIMIZE);
model.update();
model.optimize();
System.out.println("is the solution feasible? " + model.get(GRB.IntAttr.Status));
model.write("constraintOutput.lp");
//5. CONSTRUCT SOLUTION ---------------------------------------------------------------------------------------------------------------------------------------------
double obj = model.get(GRB.DoubleAttr.ObjVal);
for (int i = 0; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
if (i != j){
for (int k = 0; k < this.vehicleList.size(); k++){
if (x[i][j][k].get(GRB.DoubleAttr.X) > 0){
System.out.println(x[i][j][k].get(GRB.StringAttr.VarName) + " " + x[i][j][k].get(GRB.DoubleAttr.X));
System.out.println("Node: " + (i+1) + " goes to node: " + (j+1) + " by vehicle: " + (k+1));
}//if
}//k
}//if
}//j
}//i
System.out.println("The objective value is: " + obj);
//6. DISPOSE OF MODEL AND ENVIRONMENT
model.dispose();
env.dispose();
}catch (GRBException e ){
e.printStackTrace();
}//catch
}//solution
}//public主要问题
arc (depot,j), j customer 的值是多少？
我有一个观察：var x[i][j][k] 的定义，当你定义二进制时，把 (0 和 1)，而不是 (0.0 和 1.0) 像这样：
x[i][j][k] = model.addVar(0, 1, dij, GRB.BINARY, "X" + i + j + k)
所以我找到了解决方案：
//Constraint 1
for (int j = nDepots; j < this.allLocations.size(); j++){
GRBLinExpr lhs = new GRBLinExpr();
for(int i = 0; i < this.allLocations.size(); i++){
if(i != j) {
for (int k = 0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//k
}
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.EQUAL, rhs, "C1 - j"+j);
}//j
我没有在我的 objective 函数中包含 Xijk 变量，其中 i = j。因为我事先知道这些变量是无效的答案。但是，我忘了对约束做同样的事情。意思是，我必须添加一个带有 (i!=j) 的 if 循环，如上例所示。现在我的代码可以运行了！
我正在使用 Gurobi 在 JAVA 中编写车辆路径问题 (VRP) 的扩展。我遇到的问题是，当我 运行 我的代码时，JAVA 说它是最优的 objective 值为零。这不应该是这种情况，因为：
VRP 适用于弧和节点。是否使用弧线由 Xijk 变量指示（您是否乘坐车辆 k 从节点 i 到节点 j）。在 VRP 中，一个约束尤其是每个客户都需要访问一次。这意味着客户 j 的至少一个 Xijk 需要是一个。使用了哪辆车 k 以及之前访问过的节点 i 是什么，这些都是你要求 Gurobi 找出的。
因此只有当 Xijk 变量在 objective 函数中具有零成本因子时，objective 值等于零似乎是合乎逻辑的。然而，对我来说情况并非如此，因为我在代码末尾（重新）编写了 objective 函数，并使用节点 i 到 j 之间的距离作为成本因子。即使当我查看由 "model.write("constraintOutput.lp")" 检索的模型公式时，我也会看到一个 objective 函数，其中包含成本因子 >0 的 Xijk 变量。
所以，我四处寻找解决方案，有人提到问题可能是：
一个。 初始化变量时，第三个参数不应该为零，因为它说明变量的 "cost-factor" 应该在 objective 函数中。 因为我写了我的在优化我的模型之前在我的代码的最后部分进行约束，我相信这应该无关紧要。虽然我在初始化Xijk变量的时候把这个参数从0改成了1，但是问题依旧。
b。 我应该在初始化我的变量和约束后更新我的模型。我已经这样做了，但问题仍然存在。
我什至通过删除一些约束来减少我的模型，但这没有帮助。
有人知道如何解决这个问题吗？
我的代码：
import java.util.ArrayList;
import gurobi.GRB;
import gurobi.GRBEnv;
import gurobi.GRBException;
import gurobi.GRBLinExpr;
import gurobi.GRBModel;
import gurobi.GRBVar;
public class VRP {
public int M; //big number
public int speed; //speed km/h
public int nDepots; //number of depots
public int nCustomers; //number of customers to be visited
public ArrayList<Node> allLocations; //All locations
public ArrayList<Vehicle> vehicleList; //Vehicles
public double [][] dm; //distance matrix
public VRP(ArrayList<Node> n, ArrayList<Node> d, ArrayList<Node> dummyd, ArrayList<Vehicle> v, double [][] distanceMatrix) throws Exception {
this.M = 1000;
this.speed = 60000;
this.vehicleList = v;
this.allLocations = new ArrayList<Node>();
this.allLocations.addAll(d);
this.allLocations.addAll(n);
this.nDepots = d.size();
this.nCustomers = n.size();
this.dm = distanceMatrix;
}
public void solution() throws Exception{
Functions f = new Functions();
// 1. DEFINE MODEL -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
try{
GRBEnv env = new GRBEnv ();
env.set(GRB.IntParam.OutputFlag, 0); //set to 1 to get constraint overview
GRBModel model = new GRBModel(env);
model.set ( GRB.StringAttr.ModelName, "VRP" );
// 2. DEFINE VARIABLES -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//Xijqk
GRBVar[][][] x = new GRBVar[this.allLocations.size()][this.allLocations.size()][this.vehicleList.size()];
for (int i = 0; i<this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
for (int k = 0; k < this.vehicleList.size(); k++){
double dij = f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID);
//get.Distance retrieves the distance between two nodes that are indicated by their IDs
x[i][j][k] = model.addVar(0.0, 1.0, dij, GRB.BINARY, "X" + i + j + k); //arc between node i and j used by vehicle k or not
}//k
}//j
}//i
//aik: arival time at customer i by vehicle k
GRBVar[][] a = new GRBVar[this.allLocations.size()][this.vehicleList.size()];
for (int i = 0; i<this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
a[i][k] = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "a" + i + k); //arival time at node i by vehicle k
}//k
}//i
//dep: departure time from customer i by vehicle k
GRBVar[][] dep = new GRBVar[nDepots][this.vehicleList.size()];
for (int i = 0; i < nDepots; i++){
for (int k = 0; k < this.vehicleList.size(); k++){
dep[i][k] = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "dep" + i + k); //departure time from depot i by vehicle k
}//k
}//i
model.update();
//3. DEFINE CONSTRAINTS
//Constraint 1
for (int j = nDepots; j < this.allLocations.size(); j++){
GRBLinExpr lhs = new GRBLinExpr();
for(int i = 0; i < this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//k
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.EQUAL, rhs, "Constraint 1");
}//j
//Constraint 2
for (int i = nDepots; i < this.allLocations.size(); i++){
GRBLinExpr lhs = new GRBLinExpr();
for(int j = 0; j < this.allLocations.size(); j++){
for (int k = 0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//k
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.EQUAL, rhs, "Constraint 2:");
}//j
//Constraint 3
for (int s = nDepots; s < this.allLocations.size(); s++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = 0; i < this.allLocations.size(); i++){
lhs.addTerm(1, x[i][s][k]);
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 3");
}//k
}//s
//Constraint 4
for (int s = nDepots; s < this.allLocations.size(); s++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int j = 0; j < this.allLocations.size(); j++){
lhs.addTerm(1, x[s][j][k]);
}//j
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 4");
}//k
}//s
//Constraint 5
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = 0; i < nDepots; i++){
for (int j = nDepots; j < this.allLocations.size(); j++){
lhs.addTerm(1, x[i][j][k]);
}//j
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 5:");
}//k
//Constraint 6
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int j = 0; j < nDepots; j++){
lhs.addTerm(1, x[i][j][k]);
}//j
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 6:");
}//k
//Constraint 7: Capacity constraints of vehicles
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i =0; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
lhs.addTerm(2, x[i][j][k]);
}//j
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(20);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 7: Capacity");
}//k
//Constraint 8: #vehicles entering depot cannot exceed depot capacity
for (int j=0; j < nDepots; j++){
GRBLinExpr lhs = new GRBLinExpr();
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int k=0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//for k
}// for i
GRBLinExpr rhs = new GRBLinExpr();
int pj = this.allLocations.get(j).vehicleCapacity;
rhs.addConstant(pj);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 8");
}//i
//Constraint 9: TimeWindow
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[i][k]);
GRBLinExpr rhs = new GRBLinExpr();
double stwi = this.allLocations.get(i).startTime;
rhs.addConstant(stwi);
model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 9: ");
}//k
}//i
//Constraint 10: TimeWindow
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[i][k]);
GRBLinExpr rhs = new GRBLinExpr();
double etw = this.allLocations.get(i).endTime;
rhs.addConstant(etw);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 10:");
}//for k
}//i
//Constraint 11: determine departure vehicle from depot
for (int i = 0; i < nDepots; i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
double eid = this.allLocations.get(i).startTime;
lhs.addConstant(eid);
GRBLinExpr rhs = new GRBLinExpr();
rhs.addTerm(1, dep[i][k]);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 11:" );
}//k
}//i
//Constraint 12: determine returning time to depot
for (int i = 0; i < nDepots; i++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[i][k]);
GRBLinExpr rhs = new GRBLinExpr();
double lid = this.allLocations.get(i).returningTime;
rhs.addConstant(lid);
model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 12: " );
}//k
}//i
//Constraint 13: precedence constraint 1
for (int i = nDepots; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
if (i != j){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[j][k]);
GRBLinExpr rhs = new GRBLinExpr();
rhs.addTerm(1, a[i][k]);
double si = this.allLocations.get(i).serviceTime;
rhs.addConstant(si);
double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
rhs.addConstant(dtij);
rhs.addConstant(-M);
rhs.addTerm(M, x[i][j][k]);
model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 13: ");
}//k
}//if
}//j
}//i
//Constraint 14: precedence constraint 2 - if previous node was depot
for (int i = 0; i < nDepots; i++){
for (int j = nDepots; j < this.allLocations.size(); j++){
for (int k = 0; k < this.vehicleList.size(); k++){
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1, a[j][k]);
GRBLinExpr rhs = new GRBLinExpr();
rhs.addTerm(1, dep[i][k]);
double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
rhs.addConstant(dtij);
rhs.addConstant(-M);
rhs.addTerm(M, x[i][j][k]);
model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 14: ");
}//for k
}//for j
}//for i
model.update();
//4. SET OBJECTIVE ---------------------------------------------------------------------------------------------------------------------------------------
GRBLinExpr expr = new GRBLinExpr();
for (int i = 0; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
if (i != j){
for (int k = 0; k < this.vehicleList.size(); k++){
double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
expr.addTerm(dtij, x[i][j][k]);
}//k
}//if
}//j
}//i
model.setObjective(expr, GRB.MINIMIZE);
model.update();
model.optimize();
System.out.println("is the solution feasible? " + model.get(GRB.IntAttr.Status));
model.write("constraintOutput.lp");
//5. CONSTRUCT SOLUTION ---------------------------------------------------------------------------------------------------------------------------------------------
double obj = model.get(GRB.DoubleAttr.ObjVal);
for (int i = 0; i < this.allLocations.size(); i++){
for (int j = 0; j < this.allLocations.size(); j++){
if (i != j){
for (int k = 0; k < this.vehicleList.size(); k++){
if (x[i][j][k].get(GRB.DoubleAttr.X) > 0){
System.out.println(x[i][j][k].get(GRB.StringAttr.VarName) + " " + x[i][j][k].get(GRB.DoubleAttr.X));
System.out.println("Node: " + (i+1) + " goes to node: " + (j+1) + " by vehicle: " + (k+1));
}//if
}//k
}//if
}//j
}//i
System.out.println("The objective value is: " + obj);
//6. DISPOSE OF MODEL AND ENVIRONMENT
model.dispose();
env.dispose();
}catch (GRBException e ){
e.printStackTrace();
}//catch
}//solution
}//public主要问题
arc (depot,j), j customer 的值是多少？ 我有一个观察：var x[i][j][k] 的定义，当你定义二进制时，把 (0 和 1)，而不是 (0.0 和 1.0) 像这样：
x[i][j][k] = model.addVar(0, 1, dij, GRB.BINARY, "X" + i + j + k)
所以我找到了解决方案：
//Constraint 1
for (int j = nDepots; j < this.allLocations.size(); j++){
GRBLinExpr lhs = new GRBLinExpr();
for(int i = 0; i < this.allLocations.size(); i++){
if(i != j) {
for (int k = 0; k < this.vehicleList.size(); k++){
lhs.addTerm(1, x[i][j][k]);
}//k
}
}//i
GRBLinExpr rhs = new GRBLinExpr();
rhs.addConstant(1);
model.addConstr(lhs, GRB.EQUAL, rhs, "C1 - j"+j);
}//j
我没有在我的 objective 函数中包含 Xijk 变量，其中 i = j。因为我事先知道这些变量是无效的答案。但是，我忘了对约束做同样的事情。意思是，我必须添加一个带有 (i!=j) 的 if 循环，如上例所示。现在我的代码可以运行了！