小编最近在学习使用CPLEX,刚开始学习CPLEX看着那个官方的英文操作手册,看得头疼,于是在Github上找到了一份用CPLEX求VRPTW的代码,不过数据规模十分小,只有5个顾客。源代码链接为:https://github.com/afurculita/cplex-vrptw-implementation。
.mod文件代码如下。
1/*****************************************************************************
2 *
3 * DATA
4 *
5 *****************************************************************************/
6
7// Vehicles
8int v = ...;
9range Vehicles = 1..v;
10
11// Customers
12int CustomersNumber = ...;
13range Customers = 1..CustomersNumber;
14range CustomersAndDepots = 0..(CustomersNumber+1); // includes the starting depot and the returning depot
15
16// Capacity
17int Capacity = ...;
18
19// Demand
20int Demand[Customers] = ...;
21
22// Time windows
23int LBTW[CustomersAndDepots] = ...; // Lower Bound of the Time Window
24int UBTW[CustomersAndDepots] = ...; // Upper Bound of the Time Window
25
26int ServiceTime[CustomersAndDepots] = ...;
27int XCoord[CustomersAndDepots] = ...;
28int YCoord[CustomersAndDepots] = ...;
29float Distance[CustomersAndDepots][CustomersAndDepots]; // Cost or distance between i and j
30float Time[CustomersAndDepots][CustomersAndDepots]; // Cost or distance between i and j
31
32execute INITIALIZE {
33 for(var i in CustomersAndDepots) {
34 for (var j in CustomersAndDepots){
35 if (i == j) {
36 Distance[i][j] = 0;
37 Time[i][j] = 0;
38 } else {
39 Distance[i][j] = Math.floor(Math.sqrt(Math.pow(XCoord[i]-XCoord[j], 2) + Math.pow(YCoord[i]-YCoord[j], 2))*10)/10;
40 Time[i][j] = Distance [i][j] + ServiceTime[i];
41 }
42 }
43 }
44}
45
46// Decision variables
47dvar boolean x[Vehicles][CustomersAndDepots][CustomersAndDepots]; // 1 if a vehicle drives directly from vertex i to vertex j
48dvar int s[Vehicles][CustomersAndDepots]; // the time a vehicle starts to service a customer
49dexpr float maxTimeSpentBetweenTwoCustomers = max(a,b in CustomersAndDepots)(UBTW[a] + Time[a][b] - LBTW[b]);
50
51/*****************************************************************************
52 *
53 * MODEL
54 *
55 *****************************************************************************/
56minimize sum(k in Vehicles, i,j in CustomersAndDepots) (Distance[i][j]*x[k][i][j]);
57
58subject to {
59 forall(i in CustomersAndDepots, k in Vehicles)
60 x[k][i][i] == 0;
61
62 // Each customer is visited exactly once
63 forall (i in Customers)
64 sum(k in Vehicles, j in CustomersAndDepots) x[k][i][j] == 1;
65
66 // A vehicle can only be loaded up to it's capacity
67 forall(k in Vehicles)
68 sum(i in Customers, j in CustomersAndDepots)(Demand[i] * x[k][i][j]) <= Capacity;
69
70 // Each vehicle must leave the depot 0
71 forall(k in Vehicles)
72 sum (j in CustomersAndDepots)x[k][0][j] == 1;
73
74 // After a vehicle arrives at a customer it has to leave for another destination
75 forall(h in Customers, k in Vehicles)
76 sum(i in CustomersAndDepots)x[k][i][h] - sum(j in CustomersAndDepots)x[k][h][j] == 0;
77
78 // All vehicles must arrive at the depot n + 1
79 forall(k in Vehicles)
80 sum (i in CustomersAndDepots) x[k][i][CustomersNumber+1] == 1;
81
82 // The time windows are observed
83 forall(i in CustomersAndDepots, k in Vehicles)
84 LBTW[i] <= s[k][i] <= UBTW[i];
85
86 // From depot departs a number of vehicles equal to or smaller than v
87// forall(k in Vehicles, j in CustomersAndDepots)
88 sum (k in Vehicles, j in CustomersAndDepots) x[k][0][j] <= v;
89
90 // Vehicle departure time from a customer and its immediate successor
91 forall(i,j in CustomersAndDepots, k in Vehicles)
92 s[k][i] + Time[i][j] - maxTimeSpentBetweenTwoCustomers*(1 - x[k][i][j]) <= s[k][j];
93};
94
95execute DISPLAY {
96 writeln("Solutions: ");
97 for(var k in Vehicles)
98 for(var i in CustomersAndDepots)
99 for (var j in CustomersAndDepots)
100 if(x[k][i][j] == 1)
101 writeln("vehicle ", k, " from ", i, " to ", j);
102}
我想各位小伙伴对VRPTW的数学模型已经了熟于心了,下面对代码做一些解释:
7-30行是列出已知数据
32-44行计算出各个点之间的距离以及车辆在两个点之间需要行驶的时间
46-49行定义决策变量,其中maxTimeSpentBetweenTwoCustomers变量可以用一个大数进行替换,比如说定义成1e5
56行为目标函数,即使车辆行驶总距离最小
59-60行要求车辆不能在原地打转
62-64行要求每个顾客仅被访问一次
66-68行为容量限制约束,即每辆车的载重量不能超过容量限制
70-72行为每辆车必须从仓库0出发
74-76行为每辆车访问一个顾客后,必须前往下一个顾客
78-80行为所有车辆必须回到仓库n+1
82-84行为时间窗约束
86-88行要求使用的车辆数目必须小于等于初始在仓库车辆数目v
90-92行计算出在每个顾客的开始服务时间
95-102行打印出每辆车的所经过的顾客
上述代码求解的结果如下图所示:
车辆1路线:0-1-3-6
车辆2路线:0-6
车辆3路线:0-5-2-4-6
车辆4路线:0-6
车辆5路线:0-6
其中0和6代表仓库
数据文件.dat如下(各位如果想修改数据,可以修改此文件)
1v = 5;
2CustomersNumber = 5;
3Capacity = 200;
4
5Demand = #[
6 1: 10,
7 2: 7,
8 3: 13,
9 4: 19,
10 5: 26
11]#;
12
13ServiceTime = #[
14 0: 0,
15 1: 10,
16 2: 10,
17 3: 10,
18 4: 10,
19 5: 10,
20 6: 10
21]#;
22
23XCoord = #[
24 0: 35,
25 1: 41,
26 2: 35,
27 3: 55,
28 4: 55,
29 5: 15,
30 6: 65
31]#;
32
33YCoord = #[
34 0: 35,
35 1: 49,
36 2: 17,
37 3: 45,
38 4: 20,
39 5: 30,
40 6: 20
41]#;
42
43LBTW = #[
44 0: 0,
45 1: 0,
46 2: 0,
47 3: 0,
48 4: 0,
49 5: 0,
50 6: 0
51]#;
52
53UBTW = #[
54 0: 200,
55 1: 200,
56 2: 200,
57 3: 200,
58 4: 200,
59 5: 200,
60 6: 200
61]#;
各位小伙伴如果是刚开始学习CPLEX,可以CPLEX左上角文件-导入-现有OPL项目把文件导入进来,然后按以下操作步骤进行操作
小编也是刚学习CPLEX,欢迎各位与小编交流。
微博:随心390