Model not solving all instances
AnsweredHello,
I have a problem with my model, while it solves some instances of solomons 56 PDPTW like lc101,lc105 etc. some others like lc102,lc103 etc is incapable of solving it and it runs for hours without finding a feasible solution what is wrong here? Perhaps numerical issues or wrong dataset? Here is the constraints of my model
typedef std::vector<double> float_vec;
typedef std::vector<std::vector<double>> matrix;
typedef std::vector<std::pair<double, double>> vec_pair;
namespace PDPTW_Constraints {
int customers;
int vehicles;
int M = pow(10, 7);
void no_return_back(GRBVar*** x, GRBModel& model) {
for (int i = 0; i < customers; i++) {
for (int k = 0; k < vehicles; k++) {
x[i][i][k].set(GRB_DoubleAttr_UB, 0);
}
}
}
void visit_once_constr(GRBVar*** x, GRBModel& model) {
for (int i = 1; i < customers; i++) {
GRBLinExpr expr = 0.0;
for (int k = 0; k < vehicles; k++) {
for (int j = 0; j < customers; j++) {
if (i != j)
expr += x[i][j][k];
}
}
model.addConstr(expr == 1);
}
}
void arrives_at_depot(GRBVar*** x, GRBModel& model) {
for (int k = 0; k < vehicles; k++) {
GRBLinExpr expr = 0.0;
for (int i = 1; i < customers; i++) {
expr += x[i][0][k];
}
model.addConstr(expr == 1);
}
}
void no_return(GRBVar*** x, GRBModel& model) {
for (int i = 0; i < customers; i++) {
for (int j = 0; j < customers; j++) {
if (i == j)
continue;
for (int k = 0; k < vehicles; k++) {
model.addGenConstrIndicator(x[i][j][k], true, x[j][i][k] == 0);
// model.addConstr(x[i][j][k] - x[j][i][k] == 0);
}
}
}
}
void departs_from_depot(GRBVar*** x, GRBModel& model) {
for (int k = 0; k < vehicles; k++) {
GRBLinExpr expr = 0.0;
for (int j = 1; j < customers; j++) {
expr += x[0][j][k];
}
model.addConstr(expr == 1);
}
}
void arrives_depart_same(GRBVar*** x, GRBModel& model) {
for (int h = 1; h < customers; h++) {
for (int k = 0; k < vehicles; k++) {
GRBLinExpr expr1 = 0.0;
GRBLinExpr expr2 = 0.0;
GRBLinExpr expr3 = 0.0;
for (int i = 0; i < customers; i++) {
if (i != h)
expr1 += x[i][h][k];
}
for (int j = 0; j < customers; j++) {
if (j != h)
expr2 += x[h][j][k];
}
expr3 = expr1 - expr2;
model.addConstr(expr3 == 0, "c4");
}
}
}
void pickup_delivery_same(GRBVar*** x, int_vec_2d z, GRBModel& model) {
for (int i = 0; i < customers; i++) {
for (int j = 0; j < customers; j++) {
for (int k = 0; k < vehicles; k++) {
GRBLinExpr expr1 = 0.0;
GRBLinExpr expr2 = 0.0;
GRBLinExpr expr3 = 0.0;
if (z[i][j] == 1) {
for (int l = 0; l < customers; l++) {
if (l != i)
expr1 += x[l][i][k];
}
for (int p = 1; p < customers; p++) {
if (p != j)
expr2 += x[p][j][k];
}
}
expr3 = expr1 - expr2;
model.addConstr(expr3 == 0);
}
}
}
}
void capacity_hold(GRBVar* y, GRBModel& model) {
GRBLinExpr expr = 0.0;
for (int i = 1; i < customers; i++) {
model.addConstr(y[i] <= 1000);
}
}
void capacity_next_node(
GRBVar*** x,
GRBVar* y,
const float_vec q,
GRBModel& model) {
for (int i = 1; i < customers; i++) {
for (int j = 1; j < customers; j++) {
for (int k = 0; k < vehicles; k++) {
if (i != j)
model.addGenConstrIndicator(x[i][j][k], true, y[i] + q[i] == y[j]);
}
}
}
}
void depart_arrival(
GRBVar*** x,
const matrix c_matrix,
const vec_pair time_window,
GRBVar* arrival,
GRBVar* depart,
const float_vec service_time,
GRBModel& model)
{
depart[0].set(GRB_DoubleAttr_UB, 0);
for (int i = 1; i < customers; i++) {
depart[i].set(GRB_DoubleAttr_LB, time_window[i].first + service_time[i]);
depart[i].set(GRB_DoubleAttr_UB, time_window[i].second + service_time[i]);
arrival[i].set(GRB_DoubleAttr_LB, 0.0);
arrival[i].set(GRB_DoubleAttr_UB, time_window[i].second);
}
for (int i = 0; i < customers; i++) {
for (int j = 0; j < customers; j++) {
for (int k = 0; k < vehicles; k++) {
if (i != j) {
model.addGenConstrIndicator(
x[i][j][k], true, (depart[i] + c_matrix[i][j]) <= arrival[j]);
if (j != 0) {
model.addGenConstrIndicator(
x[i][j][k], true, depart[i] <= depart[j]);
model.addGenConstrIndicator(
x[i][j][k], true, arrival[j] + service_time[j] == depart[j]);
}
}
}
}
}
}
void time_interv_hold(int_vec_2d z, GRBVar* arrival, GRBModel& model) {
model.addConstr(arrival[0] <= 300000);
for (int i = 0; i < customers; i++) {
for (int j = 0; j < customers; j++) {
for (int k = 0; k < vehicles; k++) {
if (z[i][j] == 1) {
model.addConstr(arrival[i] <= arrival[j]);
}
}
}
}
}
} // namespace PDPTW_Constraints
It is remarkable that if i remove the time window constraints the model is solved effectivelly but i cannot find the fault in time window constraints.
Best Regards,
0
-
Hi,
If you are correctly solving smaller instances it is possible that the problem is just hard.
You can try alternative formulations for this problem to see if that helps, or also provide a feasible solution as a warm-start.Cheers,
David0
Please sign in to leave a comment.
Comments
1 comment