小編最近在學習使用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