我目前正在致力于优化废物收集,并尝试创建一个包含收集点的旅行商问题(TSP)模型。
该代码的主要目标是使用单一车辆有效地收集所有普通垃圾箱中的废物。当车辆达到其容量时,应将废物卸载到最近的收集点垃圾箱,然后继续收集过程,直到所有普通垃圾箱都已完成服务。
如果您对如何解决这个问题有任何见解或建议,我将不胜感激。
我的代码和数据文件如下所示;
我的代码;
int N = 5;
int Q = 10;
{int} nodei = ...;
{int} nodej = ...;
{int} collection = ...;
float d[nodei][nodej] = ...;
float Node_i_to_c[nodei][collection] = ...;
float w[nodei]= ...;
float Capacity[nodei]= ...;
// Decision variables
dvar boolean x[nodei][nodej];
dvar boolean y[nodei][collection];
dvar boolean v[collection];
dvar int+ u[nodei];
// Objective function
minimize
sum(i in nodei, j in nodej) d[i][j] * x[i][j];
// Constraints
subject to {
// Each customer visited exactly once
forall(i in nodei)
sum(j in nodej: i != j) x[i][j] == 1;
forall(j in nodej)
sum(i in nodei: i != j) x[i][j] == 1;
// Unloading constraints
forall(i in nodei: i != 1, b in collection)
u[i] - u[b] + (N - 1)*y[i][b] <= N - 2;
forall(i in nodei: i != 1, b in collection)
u[i] <= N*(1-v[b]);
// Capacity constraints
forall(i in nodei)
sum(b in collection) w[i]*y[i][b] <= Q;
forall(b in collection)
sum(i in nodei) w[i]*y[i][b] <= Capacity[b];
// Visit sequence constraints
forall(i in nodei: i != 1)
N>=u[i]>=2;
u[1] == 1;
}
我的数据文件;
nodei = {1, 2, 3, 4, 5};
nodej = {1, 2, 3, 4, 5};
collection = {1, 2};
w = [0, 5, 6, 8, 4];
Capacity = [15, 18];
d =
[[0.0, 0.5, 0.0765, 0.0758, 0.1],
[0.5, 0.0 , 0.4, 0.5, 0.4],
[0.0765, 0.4, 0.0 , 0.0447, 0.017],
[0.0758, 0.5, 0.0447, 0.0, 0.0739],
[0.1 , 0.4, 0.017, 0.0739, 0.0]];
Node_i_to_c =
[[0.0047, 0.0047],
[0.5, 0.5],
[0.0621, 0.0839],
[0.0701, 0.0729],
[0.0902, 0.1]];
我尝试实现这段代码,答案似乎不对,答案如下;
// solution (optimal) with objective 0.9686
// Quality Incumbent solution:
// MILP objective 9.6860000000e-01
// MILP solution norm |x| (Total, Max) 1.40000e+01 2.00000e+00
// 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) 0.00000e+00 0.00000e+00
//
x = [[0
0 0 1 0]
[0 0 0 0 1]
[0 1 0 0 0]
[1 0 0 0 0]
[0 0 1 0 0]];
u = [1 2 2 2 2];
y = [[0 0]
[0 0]
[0 0]
[0 0]
[0 0]];
v = [0 0];
我需要专家的帮助才能朝正确的方向修改代码。 提前谢谢你。