哈喽，大家好，好久不见，今天给大家分享一个团队小伙伴整理的一个C++调用Cplex求解VRPTW问题的源代码。
欢迎关注团队小伙伴的CSDN博客，博主名为“ZhaoDongqiang”
欢迎关注哔哩哔哩UP主：“我家公子Q”。
坚持、努力；你我同行！Born to fight!
VRPTW是个什么鬼呢？是VR嘛？要买3D眼镜才能搞的研究？
VRPTW的全称是vehicle routing problems with time windows，翻译为有时间窗的车辆路径问题，是VRP问题的变种。
简单描述一下：VRP是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。后面的时间窗就是指每位顾客的服务时间是有要求的，包括最早开始时间、最晚开始时间，二者之差就形成了服务的时间窗。
就像你有个快递，你给快递小哥哥打电话，（很傲娇）说：“快递我上午就要，送我宿舍来，9点到11点，要是晚了，本仙女就要生气了。”这样你服务的时间窗就是服务9点到11点这一段时间。（最好别这样昂，快递小哥也不容易，除非他是你男朋友）
好了，我知道这个问题的意思啦，然后呢？一脸懵逼啊。
然后当然是建模啊，建立该问题的数学模型。小编这里直接贴上了。
释义如下：
（1）目标函数为最小化成本或者时间。
（2）约束1：每个顾客只能被访问一次；约束2：车辆的载重限制。
（3）约束3-5：车辆从depot(0)出发回到depot(n+1)。
（4）约束6：车辆数量限制。
（5）约束7-8：时间窗约束。
就这？这还用什么Cplex？瞧着，本仙儿给你心算，叫你瞅瞅什么叫真正的实力。
。。。
心算中
。。。
emm...
那什么...
小编，你说到哪了？你接着说啊！
（小编：好的吧。。。）
其实也不咋难，我们需要先了解下C++调用Cplex时多维变量的创建。
(1)多维变量的创建
IloNumVarArray类，只能定义一维的数组，而这里的模型中需要用到三维和二维的变量。Cplex C++ 接口提供了一个lloArray类模版，我们可以利用此类模版定义多维数组。
比如二维变量数组，在头文件中做如下定义：
1typedef IloArray<IloNumVarArray> NumVarMatrix;
接下来，便可以用NumVarMatrix定义二维变量。
1NumVarMatrix s(env, v_num);
2for (IloInt k = 0; k < v_num; k++)
3{
4 s[k] = IloNumVarArray(env, c_num + 2);
5 for (IloInt i = 0; i < c_num + 2; i++)
6 {
7 s[k][i] = IloNumVar(env, ILOINT);
8 }
9}
三维数组也是同样的方法：
1typedef IloArray<IloNumVarArray> NumVarMatrix;
2typedef IloArray<NumVarMatrix> NumVar3Matrix;
(2)C++调用cplex求解VRPTW完整代码
1#include <ilcplex/ilocplex.h>
2#include <stdio.h>
3#include <cstdlib>
4#include <iostream>
5typedef IloArray<IloIntVarArray> IntVarMatrix;
6typedef IloArray<IloNumVarArray> NumVarMatrix;
7typedef IloArray<NumVarMatrix> NumVar3Matrix;
8typedef IloArray<IloIntArray> IntMatrix;
9typedef IloArray<IloNumArray> NumMatrix;
10typedef IloArray<NumMatrix> Num3Matrix;
11
12ILOSTLBEGIN //#define ILOSTLBEGIN using namespace std;
13
14int main(int argc, char **argv)
15{
16 IloEnv env;
17
18 IloModel model(env);
19
20 const int M = 10000;
21 const int v_num = 3, capacity = 500, c_num = 25;
22 float xcord[c_num + 2], ycord[c_num + 2], t_service[c_num + 2];
23 int demand[c_num + 2], lbtw[c_num + 2], ubtw[c_num + 2];
24
25 //从txt文件中读取客户信息_____x,ycord，demand，tw，time_service
26 ifstream inn;
27 inn.open("vrptw.txt");
28 if (inn)
29 {
30 for (int j = 0; j < c_num + 2; j++) {
31 inn >> xcord[j], inn >> ycord[j], inn >> demand[j], inn >> lbtw[j], inn >> ubtw[j], inn >> t_service[j];
32 }
33 }
34 inn.close();
35
36 float distance[c_num + 2][c_num + 2], time[c_num + 2][c_num + 2];
37
38 //数据初始化，计算客户之间的距离以及访问时长
39 for (int i = 0; i < c_num + 2; i++) {
40 for (int j = 0; j < c_num + 2; j++) {
41 if (i == j) {
42 distance[i][j] = 0;
43 time[i][j] = 0;
44 }
45 else{
46 distance[i][j] = floor(sqrt((xcord[i] - xcord[j]) * (xcord[i] - xcord[j]) + (ycord[i] - ycord[j]) * (ycord[i] - ycord[j]))*10)/10;
47 time[i][j] = distance[i][j] + t_service[i];
48 }
49 }
50 }
51
52 //三维决策变量x[k][i][j]，1 if a vehicle drives directly from customer i to customer j
53 NumVar3Matrix x(env, v_num);
54 for (IloInt k = 0; k < v_num; k++)
55 {
56 x[k] = NumVarMatrix(env, c_num + 2);
57 for (IloInt i = 0; i < c_num + 2; i++)
58 {
59 x[k][i] = IloNumVarArray(env, c_num + 2);
60 for (IloInt j = 0; j < c_num + 2; j++) {
61 x[k][i][j] = IloNumVar(env, 0, 1, ILOBOOL);
62 }
63 }
64 }
65
66 //二维决策变量s[k][i],the time a vehicle starts to service a customer
67 NumVarMatrix s(env, v_num);
68 for (IloInt k = 0; k < v_num; k++)
69 {
70 s[k] = IloNumVarArray(env, c_num + 2);
71 for (IloInt i = 0; i < c_num + 2; i++)
72 {
73 s[k][i] = IloNumVar(env, ILOINT);
74 }
75 }
76
77 //约束1 对角元素为0
78 for (int k = 0; k < v_num; k++) {
79 for (int i = 0; i < c_num + 2; i++) {
80 model.add(x[k][i][i] == 0);
81 }
82 }
83
84 //约束2 Each customer is visited exactly once
85 IloExpr sum_xkij(env);
86 for (int i = 1; i < c_num + 1; i++) {
87 sum_xkij.clear();
88 for (int k = 0; k < v_num; k++) {
89 for (int j = 0; j < c_num+2; j++) {
90 sum_xkij += (x[k][i][j]);
91 }
92 }
93 model.add(sum_xkij == 1);
94 }
95
96 //约束3 A vehicle can only be loaded up to it's capacity
97 IloExpr sum_demand(env);
98 for (int k = 0; k < v_num; k++) {
99 sum_demand.clear();
100 for (int i = 1; i < c_num+1; i++) {
101 for (int j = 0; j < c_num + 2; j++) {
102 sum_demand += (demand[i] * x[k][i][j]);
103 }
104 }
105 model.add(sum_demand <= capacity);
106 }
107
108 //约束4 Each vehicle must leave the depot 0
109 IloExpr sum_xk0j(env);
110 for (int k = 0; k < v_num; k++) {
111 sum_xk0j.clear();
112 for (int j = 0; j < c_num + 2; j++) {
113 sum_xk0j += (x[k][0][j]);
114 }
115 model.add(sum_xk0j == 1);
116 }
117
118 //约束5 After a vehicle arrives at a customer it has to leave for another destination
119 IloExpr sumxi(env), sumxj(env);
120 for (int h = 1; h < c_num + 1; h++) {
121 for (int k = 0; k < v_num; k++) {
122 sumxi.clear(); sumxj.clear();
123 for (int i = 0; i < c_num + 2; i++) {
124 sumxi += (x[k][i][h]);
125 sumxj += (x[k][h][i]);
126 }
127 model.add(sumxi - sumxj == 0);
128 }
129 }
130
131 //约束6 All vehicles must arrive at the depot n + 1
132 IloExpr sumxki(env);
133 for (int k = 0; k < v_num; k++) {
134 sumxki.clear();
135 for (int i = 0; i < c_num + 2; i++) {
136 sumxki += (x[k][i][c_num + 1]);
137 }
138 model.add(sumxki == 1);
139 }
140
141 //约束7 The time windows are observed
142 for (int i = 0; i < c_num + 2; i++) {
143 for (int k = 0; k < v_num; k++) {
144 model.add(s[k][i] <= ubtw[i]);
145 model.add(s[k][i] >= lbtw[i]);
146 }
147 }
148
149 //约束8 From depot departs a number of vehicles equal to or smaller than v
150 IloExpr s1(env);
151 for (int k = 0; k < v_num; k++) {
152 for (int j = 0; j < c_num + 2; j++) {
153 s1 += (x[k][0][j]);
154 }
155 }
156 model.add(s1 <= v_num);
157
158 //约束9 Vehicle departure time from a customer and its immediate successor
159 for (int i = 0; i < c_num + 2; i++) {
160 for (int j = 0; j < c_num + 2; j++) {
161 for (int k = 0; k < v_num; k++) {
162 model.add(s[k][i] + time[i][j] - M * (1 - x[k][i][j]) <= s[k][j]);
163 }
164 }
165 }
166
167 //目标函数
168 IloExpr obj(env);
169 for (int k = 0; k < v_num; k++) {
170 for (int i = 0; i < c_num + 2; i++) {
171 for (int j = 0; j < c_num + 2; j++) {
172 obj += distance[i][j] * x[k][i][j];
173 }
174 }
175 }
176 model.add(IloMinimize(env, obj));
177
178 //创建求解对象
179 IloCplex cplex(model);
180
181 //处理异常
182 cout << "begin to solve." << endl;
183
184 try
185 {
186 if (!cplex.solve())
187 {
188 cout << "求解失败" << endl;
189 if ((cplex.getStatus() == IloAlgorithm::Infeasible) ||
190 (cplex.getStatus() == IloAlgorithm::InfeasibleOrUnbounded))
191 {
192 cout << endl << "No solution - starting Conflict refinement" << endl;
193 }
194
195 env.error() << "Failed to optimize LP." << endl;
196 throw(-1);
197 }
198 cout << "异常处理完毕" << endl;
199
200 env.out() << "Solution status = " << cplex.getStatus() << endl;
201 env.out() << "Solution value = " << cplex.getObjValue() << endl;
202 }
203
204 catch (IloException& e)
205 {
206 cerr << "Concert exception caught: " << e << endl;
207 //save results
208 }
209 catch (...)
210 {
211 cerr << "Unknown exception caught" << endl;
212 }
213
214 //输出VRP路线
215 cout << "Solutions: " << endl;
216 for (int k = 0; k < v_num; k++)
217 {
218 cout << "vehicle " << k + 1 << " :" << endl;
219 for (int i = 0; i <= c_num + 1; i++)
220 {
221 for (int j = 0; j <= c_num + 1; j++)
222 {
223 IloInt c = cplex.getValue(x[k][i][j]);
224 if (c == 1) {
225 if (i == 0) cout << i << " --> " << j;
226 else if (i != 0) cout << " --> " << j;
227 i = j - 1;
228 break;
229 }
230 if (j == c_num + 1) { cout << endl; break; }
231 }
232 }
233 }
234
235 env.end();
236 //return 0;
237 system("PAUSE");
238 return EXIT_SUCCESS;
239}
(3)vrptw.txt 输入格式
小算例：25个客户，3辆车，载重上限500。
140 50 0 0 1236 0
245 68 10 912 967 90
345 70 30 825 870 90
442 66 10 65 146 90
542 68 10 727 782 90
642 65 10 15 67 90
740 69 20 621 702 90
840 66 20 170 225 90
938 68 20 255 324 90
1038 70 10 534 605 90
1135 66 10 357 410 90
1235 69 10 448 505 90
1325 85 20 652 721 90
1422 75 30 30 92 90
1522 85 10 567 620 90
1620 80 40 384 429 90
1720 85 40 475 528 90
1818 75 20 99 148 90
1915 75 20 179 254 90
2015 80 10 278 345 90
2130 50 10 10 73 90
2230 52 20 914 965 90
2328 52 20 812 883 90
2428 55 10 732 777 90
2525 50 10 65 144 90
2625 52 40 169 224 90
2740 50 0 0 1236 0
(4)该算例求解结果：
ok,今天的内容到此就大概结束了，希望对大家有帮助，欢迎点赞、转发哦！！
文章转载自运筹帷幄Q，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
