我正在尝试解决仅由一辆车携带的多种产品的多次上门下车的车辆路径问题。解决此问题后，我还将扩展到多种类型的汽车。
一种特殊设置是它的起点和终点不必相同。我假设是不同的，并将1和n设置为开始和结束的虚拟节点。
我部分地使用了IBM提供的示例TSP代码来解决子行程问题，并从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];
最佳答案
好，我已经想了很长时间解决这个问题。最后，我用合理的运行时间解决了它。我将它分享给可能想要质疑我所做的事情或改善运行时间的人。同时，如果有人能够从逻辑上验证我的所作所为确实是正确的，那将是非常棒的。
哦，我已经解决了我计划的扩展，但有其他一些限制。我希望我的评论足以理解我的所作所为。
// 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 ellimination 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
];