我正在尝试解决车辆路线问题，其中只有一辆汽车携带多种产品，需要多次接送。在解决了这个问题后，我还将扩展到多种类型的汽车。
一个特殊的设置是它有一个起点和一个终点，不必相同。我假设不同并将 1 和 n 设置为开始和结束的虚拟节点。
我部分使用了 IBM 提供的示例 TSP 代码来解决 subtour 问题，并从 Internet 获得帮助以打印出最佳游览。
因为我需要找到一条通过所有点的最佳路径。这是 NP 难的。但是作为第一次使用 ILog，我想使用 MIP 来解决这个问题以进行练习。
我在跟踪每个弧线中拾取的产品和丢弃的产品时遇到了麻烦。
我正在努力将我设定的运输成本降到最低
// Decision variables
dvar boolean x[Edges]; //car goes through this arc?
dvar boolean y[Edges][Products]; //at each e, currently loaded products in the car
dvar boolean z[Cities][Products]; //at each cities, what products to load or unload?
// Cost function
// at each arc that car goes through (distance + sum(products in the car*their weights))
dexpr float cost = sum (e in Edges) x[e] *
(dist[e] + (sum (p in Products) y[e][p] * weight[p]));
y是将每个弧与当前加载的产品相关联的变量。z 说明在每个节点中加载或卸载的内容。由于只有一辆车，我认为实际上不需要 z，但对于多辆车的扩展，我认为这将是一件好事。
如果其中一些dvar不是必需的，请给我一些见解！下面是设置。
// Cities
int n = ...;
range Cities = 1..n;
range Cities1 = 2..n-1; //just for start/end restriction
range Pickups = 2..3;
range Dropoffs= 4..n-1;
// Edges -- sparse set
tuple edge {int i; int j;}
setof(edge) Edges = {<i,j> | ordered i,j in Cities};
int dist[Edges] = ...;
// Products
int p = ...;
range Products = 1..p;
float Pickup[Cities][Products] = ...;
float Dropoff[Cities][Products] = ...;
float weight[Products] = ...;
// Products in pickup and dropoff sums up to equal amount
assert
forall(p in Products)
sum(o in Cities) Pickup[o][p] == sum(d in Cities) Dropoff[d][p];
tuple Subtour { int size; int subtour[Cities]; }
{Subtour} subtours = ...;
对以下限制的任何帮助都将非常有帮助。特别是在跟踪沿途装载的产品时。
// Objective
minimize cost;
subject to {
// Each city is linked with two other cities
forall (j in Cities1)
sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;
// Must start at node 1 and end at node n
sum (e in Edges : e.i==1) x[e] == 1;
sum (e in Edges : e.j==n) x[e] == 1;
// no product remains at 1,n (not necessary?)
sum (p in Products, e in Edges : e.i==1) y[e][p] == 0;
sum (p in Products, e in Edges : e.j==n) y[e][p] == 0;
sum (p in Products) z[1][p] == 0;
sum (p in Products) z[n][p] == 0;
// must pickup all
forall (p in Products) {
sum(i in Pickups) z[i][p] == sum(i in Cities) Pickup[i][p];
sum(i in Dropoffs) z[i][p] == sum(i in Cities) Dropoff[i][p];
}
forall (i in Pickups, p in Products)
z[i][p] <= Pickup[i][p];
//tried to keep track of picked ups, but it is not working
forall (i in Pickups, j,k in Cities, p in Products : k < i < j)
y[<i,j>][p] == y[<k,i>][p] + z[i][p];
// forall (j in Cities, p in Products)
// ctDemand:
// sum(<i,j> in Edges) y[<i,j>][p] + sum(<j,i> in Edges) y[<j,i>][p] == z[j][p];
// tried keeping track of dropoffs. It is partially working but not sure of it
forall (i, k in Cities, j in Dropoffs, p in Products : i < j < k) (y[<i,j>][p] == 1)
=> y[<j,k>][p] == y[<i,j>][p] - Dropoff[j][p];
// Subtour elimination constraints.
forall (s in subtours)
sum (i in Cities : s.subtour[i] != 0)
x[<minl(i, s.subtour[i]), maxl(i, s.subtour[i])>] <= s.size-1;
};
并进行后期处理以找到子旅游
// POST-PROCESSING to find the subtours
// Solution information
int thisSubtour[Cities];
int newSubtourSize;
int newSubtour[Cities];
// Auxiliar information
int visited[i in Cities] = 0;
setof(int) adj[j in Cities] = {i | <i,j> in Edges : x[<i,j>] == 1} union
{k | <j,k> in Edges : x[<j,k>] == 1};
execute {
newSubtourSize = n;
for (var i in Cities) { // Find an unexplored node
if (visited[i]==1) continue;
var start = i;
var node = i;
var thisSubtourSize = 0;
for (var j in Cities)
thisSubtour[j] = 0;
while (node!=start || thisSubtourSize==0) {
visited[node] = 1;
var succ = start;
for (i in adj[node])
if (visited[i] == 0) {
succ = i;
break;
}
thisSubtour[node] = succ;
node = succ;
++thisSubtourSize;
}
writeln("Found subtour of size : ", thisSubtourSize);
if (thisSubtourSize < newSubtourSize) {
for (i in Cities)
newSubtour[i] = thisSubtour[i];
newSubtourSize = thisSubtourSize;
}
}
if (newSubtourSize != n)
writeln("Best subtour of size ", newSubtourSize);
}
main {
var opl = thisOplModel
var mod = opl.modelDefinition;
var dat = opl.dataElements;
var status = 0;
var it =0;
while (1) {
var cplex1 = new IloCplex();
opl = new IloOplModel(mod,cplex1);
opl.addDataSource(dat);
opl.generate();
it++;
writeln("Iteration ",it, " with ", opl.subtours.size, " subtours.");
if (!cplex1.solve()) {
writeln("ERROR: could not solve");
status = 1;
opl.end();
break;
}
opl.postProcess();
writeln("Current solution : ", cplex1.getObjValue());
if (opl.newSubtourSize == opl.n) {
// This prints the tour as a cycle
var c = 1; // current city
var lastc = -1; // city visited right before C
write(c);
while (true) {
var nextc = -1; // next city to visit
// Find the next city to visit. To this end we
// find the edge that leaves city C and does not
// end in city LASTC. We know that exactly one such
// edge exists, otherwise the solution would be infeasible.
for (var e in opl.Edges) {
if (opl.x[e] > 0.5) {
if (e.i == c && e.j != lastc) {
nextc = e.j;
break;
}
else if (e.j == c && e.i != lastc) {
nextc = e.i;
break;
}
}
}
// Stop if we are back at the origin.
if (nextc == -1) {
break;
}
// Write next city and update current and last city.
write(" -> ", nextc);
lastc = c;
c = nextc;
}
opl.end();
cplex1.end();
break; // not found
}
dat.subtours.add(opl.newSubtourSize, opl.newSubtour);
opl.end();
cplex1.end();
}
status;
}
这是我创建的示例数据集。我希望我的解释对每个人都有意义！非常感谢你！！
n = 10;
dist = [
633
257
91
412
150
80
134
259
505
390
661
227
488
572
530
555
289
228
169
112
196
154
372
262
383
120
77
105
175
476
267
351
309
338
196
63
34
264
360
29
232
444
249
402
495
];
// Products
p = 8;
Pickup = [
// 1,2,3,4,5,6,7,8 products
[0 0 0 0 0 0 0 0],//city1
[0 1 0 1 0 1 1 0],//city2
[1 0 1 0 1 0 0 1],//city3
[0 0 0 0 0 0 0 0],//city4
[0 0 0 0 0 0 0 0],//city5
[0 0 0 0 0 0 0 0],//city6
[0 0 0 0 0 0 0 0],//city7
[0 0 0 0 0 0 0 0],//city8
[0 0 0 0 0 0 0 0],//city9
[0 0 0 0 0 0 0 0] //city10
];
Dropoff = [
[0 0 0 0 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 1 0 0],
[0 0 0 0 0 0 1 0],
[1 0 0 0 0 0 0 1],//city6
[0 1 0 0 0 0 0 0],//city7
[0 0 1 0 0 0 0 0],//city8
[0 0 0 1 0 0 0 0],//city9
[0 0 0 0 0 0 0 0] //city10
];
weight = [1, 2, 3, 4, 5, 6, 7, 8];