历尽千辛万苦&＃xff0c;外加外援帮助&＃xff0c;本辣鸡小编终于搞定了这个大坑-用分支定界法(Branch and bound, B&B)解带时间窗的车辆路径规划问题(VRPTW)。
预备知识
前面的推文中有提到过&＃xff0c;分支定界法是一种精确解算法&＃xff0c;之前推文“运筹学教学|分枝定界求解旅行商问题”中对于分支定界的基本思想进行了详细的阐述&＃xff0c;有不记得的小伙伴可以点击上面的链接传送到之前推文。
带时间窗的车辆路径规划问题(下简称&＃xff1a;VRPTW)在之前的推文中已经被详细的介绍过了&＃xff0c;为了方便读者的阅读&＃xff0c;我们在这里给出传送门
干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)
除此之外还要先学习一种数据结构叫做优先队列。优先队列(priority queue)是一种常用的数据结构&＃xff0c;在这种数据结构中&＃xff0c;队头永远是存储优先级最高的元素&＃xff0c;取队头和插入元素的操作的时间复杂度都是O(logn)。在JAVA和C&＃43;&＃43;中都内置了这一种数据结构&＃xff0c;因此&＃xff0c;亲爱的读者们不要害怕。当然如果有代码实现能力强的读者想要手工实现优先队列&＃xff0c;也是可以的&＃xff0c;想要学习优先队列以事先学习堆(heap)这种数据结构&＃xff0c;可以完美的实现优先队列的功能。
当你仔细的阅读了上面两篇推文并理解了优先队列的原理之后&＃xff0c;小编相信聪明的你一定不会对于接下来要讲的内容感到陌生。
代码以及解释
代码共分为4个类包括&＃xff1a;
BaB_Vrptw &＃xff1a;主类&＃xff0c;用于建模以及分支定界求解VRPTW。
Check &＃xff1a; 解的可行性判断
Data &＃xff1a; 定义参数
Node &＃xff1a; 定义分支定界的节点
01
Data 类
Data类的作用就是读入数据以及数据预处理&＃xff0c;在这里我们便不做过多的解释&＃xff0c;为了方便后面的阅读以及篇幅限制&＃xff0c;我们在这里便不对其进行展开描述&＃xff0c;代码中的注释对于各个变量含义有较为详细的介绍。但是由于之后的程序会调用这些变量&＃xff0c;我们便首先讲解这个类。
class Data{
int vertex_num; //所有点集合n(包括配送中心和客户点&＃xff0c;首尾(0和n)为配送中心)
double E; //配送中心时间窗开始时间
double L; //配送中心时间窗结束时间
int veh_num; //车辆数
double cap; //车辆载荷
int[][] vertexs; //所有点的坐标x,y
int[] demands; //需求量
int[] vehicles; //车辆编号
double[] a; //时间窗开始时间【a[i],b[i]】
double[] b; //时间窗结束时间【a[i],b[i]】
double[] s; //客户点的服务时间
int[][] arcs; //arcs[i][j]表示i到j点的弧
double[][] dist; //距离矩阵&＃xff0c;满足三角关系,暂用距离表示花费 C[i][j]&＃61;dist[i][j]
double gap&＃61; 1e-6; // 一个小数&＃xff0c;表示精读
double big_num &＃61; 100000; // 无穷大
//截断小数3.26434-->3.2
public double double_truncate(double v){
int iv &＃61; (int) v;
if(iv&＃43;1 - v <&＃61; gap)
return iv&＃43;1;
double dv &＃61; (v - iv) * 10;
int idv &＃61; (int) dv;
double rv &＃61; iv &＃43; idv / 10.0;
return rv;
}
public Data() {
super();
}
//函数功能&＃xff1a;从txt文件中读取数据并初始化参数
public void Read_data(String path,Data data,int vertexnum) throws Exception{
String line &＃61; null;
String[] substr &＃61; null;
Scanner cin &＃61; new Scanner(new BufferedReader(new FileReader(path))); //读取文件
for(int i &＃61;0; i <4;i&＃43;&＃43;){
line &＃61; cin.nextLine(); //读取一行
}
line &＃61; cin.nextLine();
line.trim(); //返回调用字符串对象的一个副本&＃xff0c;删除起始和结尾的空格
substr &＃61; line.split(("\\s&＃43;")); //以空格为标志将字符串拆分
//初始化参数
data.vertex_num &＃61; vertexnum;
data.veh_num &＃61; Integer.parseInt(substr[1]);
data.cap &＃61; Integer.parseInt(substr[2]);
data.vertexs &＃61;new int[data.vertex_num][2]; //所有点的坐标x,y
data.demands &＃61; new int[data.vertex_num]; //需求量
data.vehicles &＃61; new int[data.veh_num]; //车辆编号
data.a &＃61; new double[data.vertex_num]; //时间窗开始时间
data.b &＃61; new double[data.vertex_num]; //时间窗结束时间
data.s &＃61; new double[data.vertex_num]; //服务时间
data.arcs &＃61; new int[data.vertex_num][data.vertex_num];
//距离矩阵,满足三角关系,用距离表示cost
data.dist &＃61; new double[data.vertex_num][data.vertex_num];
for(int i &＃61;0; i <4;i&＃43;&＃43;){
line &＃61; cin.nextLine();
}
//读取vetexnum-1行数据
for (int i &＃61; 0; i
line.trim();
substr &＃61; line.split("\\s&＃43;");
data.vertexs[i][0] &＃61; Integer.parseInt(substr[2]);
data.vertexs[i][1] &＃61; Integer.parseInt(substr[3]);
data.demands[i] &＃61; Integer.parseInt(substr[4]);
data.a[i] &＃61; Integer.parseInt(substr[5]);
data.b[i] &＃61; Integer.parseInt(substr[6]);
data.s[i] &＃61; Integer.parseInt(substr[7]);
}
cin.close();//关闭流
//初始化配送中心参数
data.vertexs[data.vertex_num-1] &＃61; data.vertexs[0];
data.demands[data.vertex_num-1] &＃61; 0;
data.a[data.vertex_num-1] &＃61; data.a[0];
data.b[data.vertex_num-1] &＃61; data.b[0];
data.E &＃61; data.a[0];
data.L &＃61; data.b[0];
data.s[data.vertex_num-1] &＃61; 0;
double min1 &＃61; 1e15;
double min2 &＃61; 1e15;
//距离矩阵初始化
for (int i &＃61; 0; i
data.dist[i][j] &＃61; 0;
continue;
}
data.dist[i][j] &＃61;
Math.sqrt((data.vertexs[i][0]-data.vertexs[j][0])
*(data.vertexs[i][0]-data.vertexs[j][0])&＃43;
(data.vertexs[i][1]-data.vertexs[j][1])
*(data.vertexs[i][1]-data.vertexs[j][1]));
data.dist[i][j]&＃61;data.double_truncate(data.dist[i][j]);
}
}
data.dist[0][data.vertex_num-1] &＃61; 0;
data.dist[data.vertex_num-1][0] &＃61; 0;
//距离矩阵满足三角关系
for (int k &＃61; 0; k
data.dist[i][j] &＃61; data.dist[i][k] &＃43; data.dist[k][j];
}
}
}
}
//初始化为完全图
for (int i &＃61; 0; i
data.arcs[i][j] &＃61; 1;
}
else {
data.arcs[i][j] &＃61; 0;
}
}
}
//除去不符合时间窗和容量约束的边
for (int i &＃61; 0; i
continue;
}
if (data.a[i]&＃43;data.s[i]&＃43;data.dist[i][j]>data.b[j] ||
data.demands[i]&＃43;data.demands[j]>data.cap) {
data.arcs[i][j] &＃61; 0;
}
if (data.a[0]&＃43;data.s[i]&＃43;data.dist[0][i]&＃43;data.dist[i][data.vertex_num-1]>
data.b[data.vertex_num-1]) {
System.out.println("the calculating example is false");
}
}
}
for (int i &＃61; 1; i
}
if (data.a[i] &＃43; data.s[i] &＃43; data.dist[i][data.vertex_num-1]
}
}
if (data.E > min1 || data.L
System.exit(0);//终止程序
}
//初始化配送中心0&＃xff0c;n&＃43;1两点的参数
data.arcs[data.vertex_num-1][0] &＃61; 0;
data.arcs[0][data.vertex_num-1] &＃61; 1;
for (int i &＃61; 1; i
}
for (int i &＃61; 1; i
}
}
}
02
Node类
Node类的主要作用是记录分支节点&＃xff0c;下面一段代码是Node类定义的对象
Data data;
int d;
double node_cost; //目标值object
double[][][]lp_x;//记录lp解
int[][][] node_x_map;//node_xij&＃61;1时,node_x_mapijk&＃61;1表示必须访问&＃xff0c;node_x_mapijk&＃61;0表示不能访问
int[][] node_x;//0表示弧可以访问&＃xff0c;1表示必须访问&＃xff0c;-1表示不能访问
ArrayList> node_routes; //定义车辆路径链表
ArrayList> node_servetimes; //定义花费时间链表
Node类的初始化如下&＃xff0c;注意新生成的node_cost 的初始值是无穷大&＃xff0c;因为在没有操作的情况下&＃xff0c;这是一个非法解。
public Node(Data data) {
super();
this.data &＃61; data;
node_cost &＃61; data.big_num;
lp_x &＃61; new double [data.vertex_num][data.vertex_num][data.veh_num];
node_x_map &＃61; new int[data.vertex_num][data.vertex_num][data.veh_num];
node_x &＃61; new int[data.vertex_num][data.vertex_num];
node_routes &＃61; new ArrayList>();
node_servetimes &＃61; new ArrayList>();
}
由于要进行多次的生成节点&＃xff0c;为了方便&＃xff0c;我们设置了一个函数note_copy()来完成这项操作以及两个节点比较大小的函数。
public Node note_copy() {
Node new_node &＃61; new Node(data);
new_node.d &＃61; d;
new_node.node_cost &＃61; node_cost;
for (int i &＃61; 0; i
}
}
for (int i &＃61; 0; i
}
for (int i &＃61; 0; i
}
}
for (int i &＃61; 0; i
} for (int i &＃61; 0; i
} return new_node;
} public int compareTo(Object o){
Node node &＃61; (Node) o; if(node_cost
03
BaB_Vrptw类
这是整个程序中最重要的一个部分&＃xff0c;因此本文将花费大篇幅来讲解这个问题(&＃xff61;&＃xff65;∀&＃xff65;)&＃xff89;&＃xff9e;嗨。看程序先看什么&＃xff1f;答案是-主函数。
public static void main(String[] args) throws Exception {
Data data &＃61; new Data();
int vetexnum &＃61; 102;//所有点个数&＃xff0c;包括0&＃xff0c;n&＃43;1两个配送中心点
//读入不同的文件前要手动修改vetexnum参数&＃xff0c;参数值等于所有点个数,包括配送中心
String path &＃61; "data/c102.txt";//算例地址
data.Read_data(path,data,vetexnum);
System.out.println("input succesfully");
System.out.println("cplex procedure###########################");
BaB_Vrptw lp &＃61; new BaB_Vrptw(data);
double cplex_time1 &＃61; System.nanoTime();
//删除未用的车辆&＃xff0c;缩小解空间
lp&＃61;lp.init(lp);
System.out.println(": "&＃43;lp.data.veh_num);
lp.branch_and_bound(lp);
Check check &＃61; new Check(lp);
check.fesible();
double cplex_time2 &＃61; System.nanoTime();
double cplex_time &＃61; (cplex_time2 - cplex_time1) / 1e9;//求解时间&＃xff0c;单位s
System.out.println("cplex_time " &＃43; cplex_time &＃43; " bestcost " &＃43; lp.cur_best);
for (int i &＃61; 0; i
System.out.println();for (int j &＃61; 0; j
}
}
}
上面的函数就是主函数&＃xff0c;前面的11行都是数据读入的内容&＃xff0c;相信大家都能看懂&＃xff0c;在这里就不做赘述&＃xff0c;遇到的第一个操作init&＃xff0c;这个函数的作用是确定有合法解的最小车辆数量&＃xff0c;由于直接求解&＃xff0c;解空间太大&＃xff0c;且有很多车辆不能使用&＃xff0c;因此&＃xff0c;我们删去无用的车辆&＃xff0c;来缩小解空间(这是一个小优化&＃xff0c;能够加快程序速度)
public BaB_Vrptw init(BaB_Vrptw lp) throws IloException {
lp.build_model();
if (lp.model.solve()) {
lp.get_value();
int aa&＃61;0;
for (int i &＃61; 0; i
aa&＃43;&＃43;;
}
}
System.out.println(aa);
if (aa&＃61;&＃61;0) {
data.veh_num -&＃61;1;
lp.model.clearModel();
lp &＃61; new BaB_Vrptw(data);
return init(lp);
}else {
data.veh_num -&＃61;aa;
lp.model.clearModel();
lp &＃61; new BaB_Vrptw(data);
return init(lp);
}
}else {
data.veh_num &＃43;&＃61;1;
System.out.println("vehicle number: "&＃43;data.veh_num);
lp.model.clearModel();
lp &＃61; new BaB_Vrptw(data);
lp.build_model();
if (lp.model.solve()) {
lp.get_value();
return lp;
}else {
System.out.println("error init");
return null;
}
}
}
如上面的程序所示&＃xff0c;具体的做法就是建立一个松弛了的cplex模型&＃xff0c;并计算使用的车辆数&＃xff0c;如果有aa辆未使用车辆就减少aa辆可用车辆&＃xff0c;否则减少一辆直到没有可行解。当然&＃xff0c;最后我们可使用的车辆是最少的车辆啦~
松弛的模型代码如下&＃xff0c; 这就是之前“干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)”中的模型把x_ijk的整数约束去掉得到的。
private void build_model() throws IloException {
//model
model &＃61; new IloCplex();
model.setOut(null);
// model.setParam(IloCplex.DoubleParam.EpOpt, 1e-9);
// model.setParam(IloCplex.DoubleParam.EpGap, 1e-9);
//variables
x &＃61; new IloNumVar[data.vertex_num][data.vertex_num][data.veh_num];
w &＃61; new IloNumVar[data.vertex_num][data.veh_num]; //车辆访问点的时间
//定义cplex变量x和w的数据类型及取值范围
for (int i &＃61; 0; i
}
for (int j &＃61; 0; j
x[i][j] &＃61; null;
}
else{
//Xijk,公式(10)-(11)
for (int k &＃61; 0; k
}
}
}
}
//加入目标函数
//公式(1)
IloNumExpr obj &＃61; model.numExpr();
for(int i &＃61; 0; i
continue;
}
for(int k &＃61; 0; k
}
}
}
model.addMinimize(obj);
//加入约束
//公式(2)
for(int i&＃61; 1; i
for (int k &＃61; 0; k
expr1 &＃61; model.sum(expr1, x[i][j][k]);
}
}
}
model.addEq(expr1, 1);
}
//公式(3)
for (int k &＃61; 0; k
for (int j &＃61; 1; j
expr2 &＃61; model.sum(expr2, x[0][j][k]);
}
}
model.addEq(expr2, 1);
}
//公式(4)
for (int k &＃61; 0; k
IloNumExpr subExpr1 &＃61; model.numExpr();
IloNumExpr subExpr2 &＃61; model.numExpr();
for (int i &＃61; 0; i
subExpr1 &＃61; model.sum(subExpr1,x[i][j][k]);
}
if (data.arcs[j][i]&＃61;&＃61;1) {
subExpr2 &＃61; model.sum(subExpr2,x[j][i][k]);
}
}
expr3 &＃61; model.sum(subExpr1,model.prod(-1, subExpr2));
model.addEq(expr3, 0);
}
}
//公式(5)
for (int k &＃61; 0; k
for (int i &＃61; 0; i
expr4 &＃61; model.sum(expr4,x[i][data.vertex_num-1][k]);
}
}
model.addEq(expr4, 1);
}
//公式(6)
double M &＃61; 1e5;
for (int k &＃61; 0; k
IloNumExpr expr5 &＃61; model.numExpr();
IloNumExpr expr6 &＃61; model.numExpr();
expr5 &＃61; model.sum(w[i][k], data.s[i]&＃43;data.dist[i][j]);
expr5 &＃61; model.sum(expr5,model.prod(-1, w[j][k]));
expr6 &＃61; model.prod(M,model.sum(1,model.prod(-1, x[i][j][k])));
model.addLe(expr5, expr6);
}
}
}
}
//公式(7)
for (int k &＃61; 0; k
for (int j &＃61; 0; j
expr7 &＃61; model.sum(expr7,x[i][j][k]);
}
}
model.addLe(model.prod(data.a[i], expr7), w[i][k]);
model.addLe(w[i][k], model.prod(data.b[i], expr7));
}
}
//公式(8)
for (int k &＃61; 0; k
model.addLe(data.E, w[data.vertex_num-1][k]);
model.addLe(w[0][k], data.L);
model.addLe(w[data.vertex_num-1][k], data.L);
}
//公式(9)
for (int k &＃61; 0; k
for (int i &＃61; 1; i
for (int j &＃61; 0; j
expr9&＃61;model.sum(expr9,x[i][j][k]);
}
}
expr8 &＃61; model.sum(expr8,model.prod(data.demands[i],expr9));
}
model.addLe(expr8, data.cap);
}
}
之后就是branch and bound过程&＃xff0c;在这里&＃xff0c;就是最重点的环节了&＃xff0c;先说一下我们的定界方法&＃xff0c;把VRPTW的数学模型松弛的成一个线性规划问题可以求解出VRPTW问题的一个下界&＃xff0c;分支的原则就是对于一个选定的x_ijk&＃xff0c;且0
// 找到要分支的弧
public int[] find_arc(double[][][] x) {
int record[] &＃61; new int[3];//记录分支顶点
for (int i &＃61; 0; i for (int j &＃61; 0; j
for (int k &＃61; 0; k //若该弧值为0或1&＃xff0c;则继续
if (is_one_zero(x[i][j][k])) {
continue;
}
// cur_dif &＃61; get_dif(x[i][j][k]);
record[0] &＃61; i;
record[1] &＃61; j;
record[2] &＃61; k;
return record;
}
}
}
}
record[0] &＃61; -1;
record[1] &＃61; -1;
record[2] &＃61; -1;
return record;
}
分支定界的流程是&＃xff1a;
确定一个下界(初始解LB)&＃xff0c;上界定为无穷大UB。
把初始问题构建一个节点加入优先队列(因为是优先队列&＃xff0c;所以使用best first sloution&＃xff0c;也就是每一次最好的目标值最前搜索)。
判断队列是否为空&＃xff0c;如果为空跳转至7&＃xff0c;否则取出并弹出队首元素&＃xff0c;计算该节点的目标值P。
如果P > UB&＃xff0c;返回3。否则判断当前节点是否是合法解(对于任意i,j,k,x_ijk均为整数)&＃xff0c;如果是&＃xff0c;跳转5否则跳转6。
如果P
设置两个子节点L, R。L&＃xff0c;R的建立方式如上&＃xff0c;如果L的目标值L.P <&＃61; UB&＃xff0c;把L加入队列&＃xff0c;如果R的目标值R.P <&＃61; UB&＃xff0c;把R加入队列。返回3.
结束&＃xff0c;返回记录的最优节点BS。如果BS为空则无解。
public void branch_and_bound(BaB_Vrptw lp) throws IloException {
cur_best &＃61; 3000;//设置上界
deep&＃61;0;
record_arc &＃61; new int[3];
node1 &＃61; new Node(data);
best_note &＃61; null;
queue &＃61; new PriorityQueue(); //初始解(非法解) for (int i &＃61; 0; i
System.out.println(); for (int j &＃61; 0; j
}
}
lp.copy_lp_to_node(lp, node1); // node1.node_cost &＃61; lp.cost; // node1.lp_x &＃61; lp.x_map.clone(); // node1.node_routes &＃61;lp.routes; // node1.node_servetimes &＃61; lp.servetimes;
node2 &＃61; node1.note_copy();
deep&＃61;0;
node1.d&＃61;deep;
queue.add(node1); //branch and bound过程 while (!queue.isEmpty()) {
Node node &＃61; queue.poll(); //某支最优解大于当前最好可行解&＃xff0c;删除 if (doubleCompare(node.node_cost, cur_best)>0) { continue;
}else {
record_arc &＃61; lp.find_arc(node.lp_x); //某支的合法解,0,1组合的解,当前分支最好解 if (record_arc[0]&＃61;&＃61;-1) { //比当前最好解好&＃xff0c;更新当前解 if (doubleCompare(node.node_cost, cur_best)&＃61;&＃61;-1) {
lp.cur_best &＃61; node.node_cost;
System.out.println(node.d&＃43;" cur_best:"&＃43;cur_best);
lp.best_note &＃61; node;
} continue;
}else {//可以分支
node1 &＃61; lp.branch_left_arc(lp, node, record_arc);//左支
node2 &＃61; lp.branch_right_arc(lp, node, record_arc);//右支 if (node1!&＃61;null && doubleCompare(node1.node_cost, cur_best)<&＃61;0) {
queue.add(node1);
} if (node2!&＃61;null && doubleCompare(node2.node_cost, cur_best)<&＃61;0) {
queue.add(node2);
}
}
}
}
} //设置左支 public Node branch_left_arc(BaB_Vrptw lp,Node father_node,int[] record) throws IloException { if (record[0] &＃61;&＃61; -1) { return null;
}
Node new_node &＃61; new Node(data);
new_node &＃61; father_node.note_copy();
new_node.node_x[record[0]][record[1]] &＃61; -1; for (int k &＃61; 0; k
} // new_node.node_x_map[record[0]][record[1]][record[2]]&＃61;-1; //设置左支
lp.set_bound(new_node); if (lp.model.solve()) {
lp.get_value();
deep&＃43;&＃43;;
new_node.d&＃61;deep;
lp.copy_lp_to_node(lp, new_node);
System.out.println(new_node.d&＃43;" "&＃43;lp.cost);
}else {
new_node.node_cost &＃61; data.big_num;
} return new_node;
} //设置右支 public Node branch_right_arc(BaB_Vrptw lp,Node father_node,int[] record) throws IloException { if (record[0] &＃61;&＃61; -1) { return null;
}
Node new_node &＃61; new Node(data);
new_node &＃61; father_node.note_copy();
new_node.node_x[record[0]][record[1]] &＃61; 1; // new_node.node_x_map[record[0]][record[1]][record[2]]&＃61;1; for (int k &＃61; 0; k
}else {
new_node.node_x_map[record[0]][record[1]][k]&＃61;0;
}
} //设置右支
lp.set_bound(new_node); if (lp.model.solve()) {
lp.get_value();
deep&＃43;&＃43;;
new_node.d&＃61;deep;
System.out.println(new_node.d&＃43;" right: "&＃43;lp.cost);
lp.copy_lp_to_node(lp, new_node);
}else {
new_node.node_cost &＃61; data.big_num;
} return new_node;
} //找到需要分支的支点位置
这样就完美的利用branch and bound解决了VRPTW。诶&＃xff0c;等等&＃xff0c;完美么&＃xff1f;是不是忘了点什么&＃xff1f;解的合法性有没有检验呢&＃xff1f;
为了检验我们所求的解是不是合法的&＃xff0c;我们利用迟迟没出面的Check类来检查这个问题。
01
Check类
Check类存在的目的&＃xff0c;主要是检验解的可行性&＃xff0c;包括解是否满足车辆数量约束&＃xff0c;是否满足容量约束&＃xff0c;时间窗约束等等。
包括函数
double_compare(v1, v2): 比较两个数大小 v1
fesible()&＃xff1a;判断解的可行性&＃xff0c;包括车辆数量可行性&＃xff0c;车辆载荷可行性&＃xff0c;时间窗、车容量可行性判断。
class Check{
double epsilon &＃61; 0.0001;
Data data &＃61; new Data();
ArrayList> routes &＃61; new ArrayList<>();
ArrayList> servetimes &＃61; new ArrayList<>(); public Check(BaB_Vrptw lp) { super(); this.data &＃61; lp.data; this.routes &＃61; lp.routes; this.servetimes &＃61; lp.servetimes;
} //函数功能&＃xff1a;比较两个数的大小 public int double_compare(double v1,double v2) { if (v1
} return 0;
} //函数功能&＃xff1a;解的可行性判断 public void fesible() throws IloException { //车辆数量可行性判断 if (routes.size() > data.veh_num) {
System.out.println("error: vecnum!!!");
System.exit(0);
} //车辆载荷可行性判断 for (int k &＃61; 0; k
} if (capasity > data.cap) {
System.out.println("error: cap!!!");
System.exit(0);
}
} //时间窗、车容量可行性判断 for (int k &＃61; 0; k
ArrayList servertime &＃61; servetimes.get(k); double capasity &＃61; 0; for (int i &＃61; 0; i
System.out.println("error: servertime!");
System.exit(0);
} if (double_compare(si &＃43; data.dist[origin][destination],data.b[destination]) > 0) {
System.out.println(origin &＃43; ": [" &＃43; data.a[origin]
&＃43; ","&＃43;data.b[origin]&＃43;"]"&＃43; " "&＃43; si);
System.out.println(destination &＃43; ": [" &＃43;
data.a[destination] &＃43; ","&＃43;data.b[destination]&＃43;"]"&＃43; " "&＃43; sj);
System.out.println(data.dist[origin][destination]);
System.out.println(destination &＃43; ":" );
System.out.println("error: forward servertime!");
System.exit(0);
} if (double_compare(sj - data.dist[origin][destination],data.a[origin]) <0) {
System.out.println(origin &＃43; ": [" &＃43; data.a[origin]
&＃43; ","&＃43;data.b[origin]&＃43;"]"&＃43; " "&＃43; si);
System.out.println(destination &＃43; ": [" &＃43; data.a[destination]
&＃43; ","&＃43;data.b[destination]&＃43;"]"&＃43; " "&＃43; sj);
System.out.println(data.dist[origin][destination]);
System.out.println(destination &＃43; ":" );
System.out.println("error: backward servertime!");
System.exit(0);
}
} if (capasity > data.cap) {
System.out.println("error: cap!!!");
System.exit(0);
}
}
}
}
运算结果
以Solomon测试算例为例&＃xff0c;我们对其进行了测试&＃xff0c;输入数据如下&＃xff1a;
输出结果如下&＃xff1a;其中第一列代表顾客编号&＃xff0c;第二列和第三列分别代表顾客的横纵坐标&＃xff0c;第四列代表需求&＃xff0c;第五列第六列代表时间窗&＃xff0c;第七列代表服务时间。车辆数量20&＃xff0c;容量200。
time 25.245537525 bestcost 827.3
0 13 17 18 19 15 16 14 12 101
0 43 42 41 40 44 46 45 48 51 50 52 49 47 101
0 5 3 7 8 10 11 9 6 4 2 1 75 101
0 67 65 63 62 74 72 61 64 68 66 69 101
0 20 24 25 27 29 30 28 26 23 22 21 101
0 32 33 31 35 37 38 39 36 34 101
0 57 55 54 53 56 58 60 59 101
0 81 78 76 71 70 73 77 79 80 101
0 90 87 86 83 82 84 85 88 89 91 101
0 98 96 95 94 92 93 97 100 99 101
第一行是运算时间和最优目标值&＃xff0c;第二行到最后一行分别表示每辆车的运行路线。
终于搞完了&＃xff0c;是不是觉得很舒爽呢&＃xff1f;
欲下载代码请移步留言区。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 