使用 MIP 接送车辆的车辆路线
Vehicle Routing with Pickup and Dropoffs with MIP
我正在尝试解决一个车辆路径问题，该问题涉及多个接送点，且仅由一辆车承载多种产品。解决完这个问题我也打算扩展到多种车型。
一个特殊的设置是它有一个起点和一个终点，不需要相同。我假设不同并将 1 和 n 设置为开始和结束的虚拟节点。
我部分使用了IBM提供的示例TSP代码来解决subtour问题，并通过互联网帮助打印出最佳路线。
因为我需要找到一条经过所有点的最佳路径。这是 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处理寻找子行程
// 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];
好的，想了很久解决这个问题。最后，我用合理的 运行 时间解决了它。我会将它分享给可能想要质疑我所做的事情或改善 运行 时间的人。同时，如果有人能验证我所做的在逻辑上确实是正确的，那就太棒了。
哦，我已经解决了我计划的带有额外几个限制的扩展。我希望我的评论足以理解我所做的事情。
// Constants
int TotalTimeLimit = ...;
int LoadTime = ...;
int UnloadTime = ...;
int TransitCost = ...;
int MaxTransit = ...;
// Cities
int n = ...;
int pickupN= ...; //4
range Cities = 1..n;
range Cities1 = 2..n-1; //just for start/end restriction
range Pickups = 2..pickupN+1; //2-5
range Dropoffs= pickupN+2..n-1; //7-17
// Edges -- sparse set
tuple edge {int i; int j;}
setof(edge) Edges = {<i,j> | i,j in Cities};
int dist[Edges] = ...;
int time[Edges] = ...;
// Products
int P = ...;
range Products = 1..P;
int Pickup[Cities][Products] = ...;
int Dropoff[Cities][Products] = ...;
int weight[Products] = ...;
int volume[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];
//Trucks
{string} Type = ...;
int Max[Type] = ...;
int c = sum(t in Type) Max[t];
range Cars= 1..c;
int VolumeCapacity[Cars] = ...;
int WeightCapacity[Cars] = ...;
int NumberCapacity[Cars] = ...;
int FixedCost[Cars] = ...;
int forbid[Cities][Cars] = ...;
// Decision variables
dvar boolean x[Cars][Edges];
dvar boolean y[Cars][Edges][Products];
dvar boolean z[Cars][Cities][Products];
dvar boolean isCarUsed[Cars];
// Cost function
dexpr float cost = sum (c in Cars) (isCarUsed[c]*FixedCost[c] +
(sum(e in Edges) (x[c][e]*(dist[e] + TransitCost) + (sum (p in Products) y[c][e][p] * weight[p]))))
- 30 - sum(p in Products) weight[p];
// Objective
minimize cost;
subject to {
// Total pickups for each p equal the total sum of each colum of z in pickups
forall (p in Products)
sum(i in Pickups, c in Cars) z[c][i][p] == sum(i in Pickups) Pickup[i][p];
// For each node, each car can pick at most the node's stock
forall(i in Pickups, p in Products, c in Cars)
z[c][i][p] <= Pickup[i][p];
// For each car, picked up products should be smaller than car's capacities
forall (c in Cars, e in Edges) {
sum(p in Products) y[c][e][p] <= NumberCapacity[c];
sum(p in Products) y[c][e][p]*weight[p] <= WeightCapacity[c];
sum(p in Products) y[c][e][p]*volume[p] <= VolumeCapacity[c];
}
// For each car and product, its picked up amount should equal dropped off amount
forall (c in Cars, p in Products)
sum(i in Pickups) z[c][i][p] == sum(i in Dropoffs) z[c][i][p];
// Total dropoffs for each p equal the total sum of each column of z in dropoffs
forall (p in Products)
sum(i in Dropoffs, c in Cars) z[c][i][p] == sum(i in Dropoffs) Dropoff[i][p];
// For each node, each car can drop at most its needs
forall(i in Dropoffs, p in Products, c in Cars)
z[c][i][p] <= Dropoff[i][p];
// For each car, it cannot stay at one place
forall (c in Cars)
sum(i in Cities) x[c][<i,i>] == 0;
// Prevents looping, must start at node 1 and end at node n
forall (c in Cars) {
sum (e in Edges : e.i==n) x[c][e] == 0;
sum (e in Edges : e.j==1) x[c][e] == 0;
}
// For each car, it cannot go back and forth
forall (c in Cars, i,j in Cities)
x[c][<i,j>]+x[c][<j,i>] <= 1;
// Each city is linked with two other cities
forall (j in Cities1, c in Cars)
sum (<i,j> in Edges) x[c][<i,j>] - sum (<j,k> in Edges) x[c][<j,k>] == 0;
// If car is used, must start at node 1 and end at node n
forall(c in Cars) {
100*sum(e in Edges : e.i==1) x[c][e] >= sum (p in Products, i in Cities1) z[c][i][p];
100*sum(e in Edges : e.j==n) x[c][e] >= sum (p in Products, i in Cities1) z[c][i][p];
100*isCarUsed[c] >= sum(p in Products, i in Cities1) z[c][i][p];
}
forall (c in Cars) {
sum(e in Edges : e.i==1) x[c][e] <= 1;
sum(e in Edges : e.j==n) x[c][e] <= 1;
}
// For each car, it needs to cross nodes that picks or drops something
forall (c in Cars, i in Cities)
100*sum (j in Cities) x[c][<i,j>] >= sum (p in Products) z[c][i][p];
// For each car, its transit count <= maxTransit
forall (c in Cars)
sum(e in Edges) x[c][e] <= MaxTransit;
// For each car, and for each node, we need to check whether time took is <= totalTimeLimit
forall(c in Cars)
sum(e in Edges : e.i in Pickups || e.i in Dropoffs) x[c][e]*time[e]
+ LoadTime*sum(i in Pickups, p in Products) z[c][i][p] + UnloadTime*sum(i in Dropoffs, p in Products) z[c][i][p]
<= TotalTimeLimit;
// Certain type of cars cannot go to certain city
forall (c in Cars, i in Cities)
if (forbid[i][c] == 1)
sum(j,k in Cities) (x[c][<i,j>] + x[c][<k,i>]) == 0;
// Keeps culmulated pacakges through each arcs
forall (c in Cars, i in Pickups, p in Products)
sum(k in Cities) y[c][<i,k>][p] == sum(j in Cities) y[c][<j,i>][p] + z[c][i][p];
forall (c in Cars, i in Pickups, j in Cities)
100*x[c][<i,j>] >= sum(p in Products) y[c][<i,j>][p];
// MTZ subtour elimination constraints
forall (c in Cars, j in Dropoffs, i,k in Cities, p in Products : j != i && j != k)
y[c][<i,j>][p] - y[c][<j,k>][p] >= z[c][j][p] - 100*(1-x[c][<i,j>]);
};
这是一个示例数据。我做了这样的设置，我们先上车，然后再下车。我还为开始和结束以及上车和下车之间的中转位置制作了 3 个虚拟变量。
n = 12;
pickupN = 3;
dist = [
9999999
0
0
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
390
661
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
390
9999999
228
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
661
228
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
63
34
264
360
208
329
9999999
9999999
9999999
9999999
9999999
9999999
9999999
232
444
292
297
47
0
9999999
9999999
9999999
9999999
9999999
232
9999999
29
232
444
292
0
9999999
9999999
9999999
9999999
9999999
444
29
9999999
249
402
250
0
9999999
9999999
9999999
9999999
9999999
292
232
249
9999999
495
352
0
9999999
9999999
9999999
9999999
9999999
297
444
402
495
9999999
154
0
9999999
9999999
9999999
9999999
9999999
47
292
250
352
154
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
];
time = [
9999999
0
0
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
20
52
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
14
9999999
26
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
43
31
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
12
31
10
17
26
26
9999999
9999999
9999999
9999999
9999999
9999999
9999999
21
19
20
18
7
0
9999999
9999999
9999999
9999999
9999999
35
9999999
6
13
30
28
0
9999999
9999999
9999999
9999999
9999999
39
23
9999999
38
23
38
0
9999999
9999999
9999999
9999999
9999999
23
32
20
9999999
45
17
0
9999999
9999999
9999999
9999999
9999999
28
35
37
24
9999999
24
0
9999999
9999999
9999999
9999999
9999999
2
39
8
37
21
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
];
TotalTimeLimit = 150;
LoadTime = 10;
UnloadTime = 10;
TransitCost = 10;
//DropoffTransitCost = 10;
MaxTransit = 10;
// Products
P = 12;
Pickup = [
// 1,2,3,4,5,6,7,8 9 101112 products
[0 0 0 0 0 0 0 0 0 0 0 0],//city1 pickstart
[0 0 0 1 0 0 1 0 1 1 0 0],//city2
[1 1 0 0 0 0 0 1 0 0 1 0],//city3
[0 0 1 0 1 1 0 0 0 0 0 1],//city4
[0 0 0 0 0 0 0 0 0 0 0 0],//city5 pickend & dropstart
[0 0 0 0 0 0 0 0 0 0 0 0],//city6
[0 0 0 0 0 0 0 0 0 0 0 0],//city7
[0 0 0 0 0 0 0 0 0 0 0 0],//city8
[0 0 0 0 0 0 0 0 0 0 0 0],//city9
[0 0 0 0 0 0 0 0 0 0 0 0],//city10
[0 0 0 0 0 0 0 0 0 0 0 0],//city11
[0 0 0 0 0 0 0 0 0 0 0 0]//city12
];
Dropoff = [
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],//city5 pickend & dropstart
[0 0 0 0 1 0 0 0 0 0 0 1],//city6
[1 0 0 0 0 0 0 0 0 0 0 0],//city7
[0 1 0 0 0 0 1 0 0 0 0 0],//city8
[0 0 0 0 0 1 0 0 1 0 0 0],//city9
[0 0 0 1 0 0 0 0 0 1 0 0],//city10
[0 0 1 0 0 0 0 1 0 0 1 0],//city11
[0 0 0 0 0 0 0 0 0 0 0 0]//city12 dropend
];
weight = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
volume = [20, 500, 30, 20, 60, 100, 300, 50, 10, 400, 1, 15];
//Cars
Type ={"SmallTruck", "MiddleTruck", "BigTruck"};
Max = #[
SmallTruck : 2,
MiddleTruck : 2,
BigTruck : 2
]#;
VolumeCapacity = [100, 100, 500, 500, 1000, 1000];
WeightCapacity = [10, 10, 30, 30, 50, 50];
NumberCapacity = [4, 4, 6, 6, 12, 12];
FixedCost = [100, 100, 200, 200, 300, 300];
forbid = [
[0 0 0 0 0 0],//city1
[0 0 0 0 0 0],//city2
[0 0 0 0 0 0],//city3
[0 0 0 0 0 0],//city4 pickend & dropstart
[0 0 0 0 0 0],//city5
[0 0 0 0 0 0],//city6
[0 0 0 0 0 0],//city7
[0 0 0 0 0 0],//city8
[0 0 0 0 0 0],//city9
[0 0 0 0 1 1],//city10
[0 0 0 0 0 0],//city11
[0 0 0 0 0 0]//city12
];
我正在尝试解决一个车辆路径问题，该问题涉及多个接送点，且仅由一辆车承载多种产品。解决完这个问题我也打算扩展到多种车型。
一个特殊的设置是它有一个起点和一个终点，不需要相同。我假设不同并将 1 和 n 设置为开始和结束的虚拟节点。
我部分使用了IBM提供的示例TSP代码来解决subtour问题，并通过互联网帮助打印出最佳路线。
因为我需要找到一条经过所有点的最佳路径。这是 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处理寻找子行程
// 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];
好的，想了很久解决这个问题。最后，我用合理的 运行 时间解决了它。我会将它分享给可能想要质疑我所做的事情或改善 运行 时间的人。同时，如果有人能验证我所做的在逻辑上确实是正确的，那就太棒了。
哦，我已经解决了我计划的带有额外几个限制的扩展。我希望我的评论足以理解我所做的事情。
// Constants
int TotalTimeLimit = ...;
int LoadTime = ...;
int UnloadTime = ...;
int TransitCost = ...;
int MaxTransit = ...;
// Cities
int n = ...;
int pickupN= ...; //4
range Cities = 1..n;
range Cities1 = 2..n-1; //just for start/end restriction
range Pickups = 2..pickupN+1; //2-5
range Dropoffs= pickupN+2..n-1; //7-17
// Edges -- sparse set
tuple edge {int i; int j;}
setof(edge) Edges = {<i,j> | i,j in Cities};
int dist[Edges] = ...;
int time[Edges] = ...;
// Products
int P = ...;
range Products = 1..P;
int Pickup[Cities][Products] = ...;
int Dropoff[Cities][Products] = ...;
int weight[Products] = ...;
int volume[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];
//Trucks
{string} Type = ...;
int Max[Type] = ...;
int c = sum(t in Type) Max[t];
range Cars= 1..c;
int VolumeCapacity[Cars] = ...;
int WeightCapacity[Cars] = ...;
int NumberCapacity[Cars] = ...;
int FixedCost[Cars] = ...;
int forbid[Cities][Cars] = ...;
// Decision variables
dvar boolean x[Cars][Edges];
dvar boolean y[Cars][Edges][Products];
dvar boolean z[Cars][Cities][Products];
dvar boolean isCarUsed[Cars];
// Cost function
dexpr float cost = sum (c in Cars) (isCarUsed[c]*FixedCost[c] +
(sum(e in Edges) (x[c][e]*(dist[e] + TransitCost) + (sum (p in Products) y[c][e][p] * weight[p]))))
- 30 - sum(p in Products) weight[p];
// Objective
minimize cost;
subject to {
// Total pickups for each p equal the total sum of each colum of z in pickups
forall (p in Products)
sum(i in Pickups, c in Cars) z[c][i][p] == sum(i in Pickups) Pickup[i][p];
// For each node, each car can pick at most the node's stock
forall(i in Pickups, p in Products, c in Cars)
z[c][i][p] <= Pickup[i][p];
// For each car, picked up products should be smaller than car's capacities
forall (c in Cars, e in Edges) {
sum(p in Products) y[c][e][p] <= NumberCapacity[c];
sum(p in Products) y[c][e][p]*weight[p] <= WeightCapacity[c];
sum(p in Products) y[c][e][p]*volume[p] <= VolumeCapacity[c];
}
// For each car and product, its picked up amount should equal dropped off amount
forall (c in Cars, p in Products)
sum(i in Pickups) z[c][i][p] == sum(i in Dropoffs) z[c][i][p];
// Total dropoffs for each p equal the total sum of each column of z in dropoffs
forall (p in Products)
sum(i in Dropoffs, c in Cars) z[c][i][p] == sum(i in Dropoffs) Dropoff[i][p];
// For each node, each car can drop at most its needs
forall(i in Dropoffs, p in Products, c in Cars)
z[c][i][p] <= Dropoff[i][p];
// For each car, it cannot stay at one place
forall (c in Cars)
sum(i in Cities) x[c][<i,i>] == 0;
// Prevents looping, must start at node 1 and end at node n
forall (c in Cars) {
sum (e in Edges : e.i==n) x[c][e] == 0;
sum (e in Edges : e.j==1) x[c][e] == 0;
}
// For each car, it cannot go back and forth
forall (c in Cars, i,j in Cities)
x[c][<i,j>]+x[c][<j,i>] <= 1;
// Each city is linked with two other cities
forall (j in Cities1, c in Cars)
sum (<i,j> in Edges) x[c][<i,j>] - sum (<j,k> in Edges) x[c][<j,k>] == 0;
// If car is used, must start at node 1 and end at node n
forall(c in Cars) {
100*sum(e in Edges : e.i==1) x[c][e] >= sum (p in Products, i in Cities1) z[c][i][p];
100*sum(e in Edges : e.j==n) x[c][e] >= sum (p in Products, i in Cities1) z[c][i][p];
100*isCarUsed[c] >= sum(p in Products, i in Cities1) z[c][i][p];
}
forall (c in Cars) {
sum(e in Edges : e.i==1) x[c][e] <= 1;
sum(e in Edges : e.j==n) x[c][e] <= 1;
}
// For each car, it needs to cross nodes that picks or drops something
forall (c in Cars, i in Cities)
100*sum (j in Cities) x[c][<i,j>] >= sum (p in Products) z[c][i][p];
// For each car, its transit count <= maxTransit
forall (c in Cars)
sum(e in Edges) x[c][e] <= MaxTransit;
// For each car, and for each node, we need to check whether time took is <= totalTimeLimit
forall(c in Cars)
sum(e in Edges : e.i in Pickups || e.i in Dropoffs) x[c][e]*time[e]
+ LoadTime*sum(i in Pickups, p in Products) z[c][i][p] + UnloadTime*sum(i in Dropoffs, p in Products) z[c][i][p]
<= TotalTimeLimit;
// Certain type of cars cannot go to certain city
forall (c in Cars, i in Cities)
if (forbid[i][c] == 1)
sum(j,k in Cities) (x[c][<i,j>] + x[c][<k,i>]) == 0;
// Keeps culmulated pacakges through each arcs
forall (c in Cars, i in Pickups, p in Products)
sum(k in Cities) y[c][<i,k>][p] == sum(j in Cities) y[c][<j,i>][p] + z[c][i][p];
forall (c in Cars, i in Pickups, j in Cities)
100*x[c][<i,j>] >= sum(p in Products) y[c][<i,j>][p];
// MTZ subtour elimination constraints
forall (c in Cars, j in Dropoffs, i,k in Cities, p in Products : j != i && j != k)
y[c][<i,j>][p] - y[c][<j,k>][p] >= z[c][j][p] - 100*(1-x[c][<i,j>]);
};
这是一个示例数据。我做了这样的设置，我们先上车，然后再下车。我还为开始和结束以及上车和下车之间的中转位置制作了 3 个虚拟变量。
n = 12;
pickupN = 3;
dist = [
9999999
0
0
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
390
661
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
390
9999999
228
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
661
228
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
63
34
264
360
208
329
9999999
9999999
9999999
9999999
9999999
9999999
9999999
232
444
292
297
47
0
9999999
9999999
9999999
9999999
9999999
232
9999999
29
232
444
292
0
9999999
9999999
9999999
9999999
9999999
444
29
9999999
249
402
250
0
9999999
9999999
9999999
9999999
9999999
292
232
249
9999999
495
352
0
9999999
9999999
9999999
9999999
9999999
297
444
402
495
9999999
154
0
9999999
9999999
9999999
9999999
9999999
47
292
250
352
154
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
];
time = [
9999999
0
0
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
20
52
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
14
9999999
26
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
43
31
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
12
31
10
17
26
26
9999999
9999999
9999999
9999999
9999999
9999999
9999999
21
19
20
18
7
0
9999999
9999999
9999999
9999999
9999999
35
9999999
6
13
30
28
0
9999999
9999999
9999999
9999999
9999999
39
23
9999999
38
23
38
0
9999999
9999999
9999999
9999999
9999999
23
32
20
9999999
45
17
0
9999999
9999999
9999999
9999999
9999999
28
35
37
24
9999999
24
0
9999999
9999999
9999999
9999999
9999999
2
39
8
37
21
9999999
0
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
9999999
];
TotalTimeLimit = 150;
LoadTime = 10;
UnloadTime = 10;
TransitCost = 10;
//DropoffTransitCost = 10;
MaxTransit = 10;
// Products
P = 12;
Pickup = [
// 1,2,3,4,5,6,7,8 9 101112 products
[0 0 0 0 0 0 0 0 0 0 0 0],//city1 pickstart
[0 0 0 1 0 0 1 0 1 1 0 0],//city2
[1 1 0 0 0 0 0 1 0 0 1 0],//city3
[0 0 1 0 1 1 0 0 0 0 0 1],//city4
[0 0 0 0 0 0 0 0 0 0 0 0],//city5 pickend & dropstart
[0 0 0 0 0 0 0 0 0 0 0 0],//city6
[0 0 0 0 0 0 0 0 0 0 0 0],//city7
[0 0 0 0 0 0 0 0 0 0 0 0],//city8
[0 0 0 0 0 0 0 0 0 0 0 0],//city9
[0 0 0 0 0 0 0 0 0 0 0 0],//city10
[0 0 0 0 0 0 0 0 0 0 0 0],//city11
[0 0 0 0 0 0 0 0 0 0 0 0]//city12
];
Dropoff = [
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 0 0 0 0],//city5 pickend & dropstart
[0 0 0 0 1 0 0 0 0 0 0 1],//city6
[1 0 0 0 0 0 0 0 0 0 0 0],//city7
[0 1 0 0 0 0 1 0 0 0 0 0],//city8
[0 0 0 0 0 1 0 0 1 0 0 0],//city9
[0 0 0 1 0 0 0 0 0 1 0 0],//city10
[0 0 1 0 0 0 0 1 0 0 1 0],//city11
[0 0 0 0 0 0 0 0 0 0 0 0]//city12 dropend
];
weight = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
volume = [20, 500, 30, 20, 60, 100, 300, 50, 10, 400, 1, 15];
//Cars
Type ={"SmallTruck", "MiddleTruck", "BigTruck"};
Max = #[
SmallTruck : 2,
MiddleTruck : 2,
BigTruck : 2
]#;
VolumeCapacity = [100, 100, 500, 500, 1000, 1000];
WeightCapacity = [10, 10, 30, 30, 50, 50];
NumberCapacity = [4, 4, 6, 6, 12, 12];
FixedCost = [100, 100, 200, 200, 300, 300];
forbid = [
[0 0 0 0 0 0],//city1
[0 0 0 0 0 0],//city2
[0 0 0 0 0 0],//city3
[0 0 0 0 0 0],//city4 pickend & dropstart
[0 0 0 0 0 0],//city5
[0 0 0 0 0 0],//city6
[0 0 0 0 0 0],//city7
[0 0 0 0 0 0],//city8
[0 0 0 0 0 0],//city9
[0 0 0 0 1 1],//city10
[0 0 0 0 0 0],//city11
[0 0 0 0 0 0]//city12
];