分⽀定界法matlab_cplex教学分⽀定界法
（branchandbound）解带时间窗。。。
历尽千⾟万苦，外加外援帮助，本辣鸡⼩编终于搞定了这个⼤坑-⽤分⽀定界法(Branch and bound, B&B)解带时间窗的车辆路径规划问题(VRPTW)。
预备知识
前⾯的推⽂中有提到过，分⽀定界法是⼀种精确解算法，之前推⽂“运筹学教学|分枝定界求解旅⾏商问题
”中对于分⽀定界的基本思想进⾏了详细的阐述，有不记得的⼩伙伴可以点击上⾯的链接传送到之前推⽂。
班主任节带时间窗的车辆路径规划问题(下简称：VRPTW)在之前的推⽂中已经被详细的介绍过了，为了⽅便读者的阅读，我们在这⾥给出传送门
⼲货|⼗分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)
除此之外还要先学习⼀种数据结构叫做优先队列。优先队列(priority queue)是⼀种常⽤的数据结构，在这种数据结构中，队头永远是存储优先级最⾼的元素，取队头和插⼊元素的操作的时间复杂度都是O(logn)。在JAVA和C++中都内置了这⼀种数据结构，因此，亲爱的读者们不要害怕。当然如果有代码实现能⼒强的读者想要⼿⼯实现优先队列，也是可以的，想要学习优先队列以事先学习堆(heap)这种数据结构，可以完美的实现优先队列的功能。
当你仔细的阅读了上⾯两篇推⽂并理解了优先队列的原理之后，⼩编相信聪明的你⼀定不会对于接下来要讲的内容感到陌⽣。
代码以及解释
代码共分为4个类包括：
BaB_Vrptw ：主类，⽤于建模以及分⽀定界求解VRPTW。
Check ：解的可⾏性判断
Data ：定义参数
QQ扫码Node ：定义分⽀定界的节点
01
Data 类
Data类的作⽤就是读⼊数据以及数据预处理，在这⾥我们便不做过多的解释，为了⽅便后⾯的阅读以及篇幅限制，我们在这⾥便不对其进⾏展开描述，代码中的注释对于各个变量含义有较为详细的介绍。但是由于之后的程序会调⽤这些变量，我们便⾸先讲解这个类。
class Data{
class Data{
int vertex_num; //所有点集合n(包括配送中⼼和客户点，⾸尾(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; //距离矩阵，满⾜三⾓关系，暂⽤距离表⽰花费 C[i][j]=dist[i][j]
double gap= 1e-6; // ⼀个⼩数，表⽰精读
double big_num = 100000; // ⽆穷⼤
//截断⼩数3.26434-->3.2
public double double_truncate(double v){
int iv = (int) v;
if(iv+1 - v <= gap)
return iv+1;
double dv = (v - iv) * 10;
int idv = (int) dv;
double rv = iv + idv / 10.0;
return rv;
}
public Data() {
super();
}
//函数功能：从txt⽂件中读取数据并初始化参数
public void Read_data(String path,Data data,int vertexnum) throws Exception{
String line = null;
String[] substr = null;
Scanner cin = new Scanner(new BufferedReader(new FileReader(path))); //读取⽂件 for(int i =0; i < 4;i++){
line = Line(); //读取⼀⾏
}
line = Line();
空气炸锅做美食
我的周末英语作文substr = line.split(("\\s+")); //以空格为标志将字符串拆分
//初始化参数
data.vertex_num = vertexnum;
data.veh_num = Integer.parInt(substr[1]);
data.cap = Integer.parInt(substr[2]);
data.vertexs =new int[data.vertex_num][2]; //所有点的坐标x,y data.demands = new int[data.vertex_num]; //需求量
data.vehicles = new int[data.veh_num]; //车辆编号
data.a = new double[data.vertex_num]; //时间窗开始时间 data.b = new double[data.vertex_num]; //时间窗结束时间 data.s = new double[data.vertex_num]; //服务时间
data.arcs = new int[data.vertex_num][data.vertex_num];
//距离矩阵，满⾜三⾓关系,⽤距离表⽰cost
data.dist = new double[data.vertex_num][data.vertex_num];
for(int i =0; i < 4;i++){
line = Line();
}
//读取vetexnum-1⾏数据
for (int i = 0; i < data.vertex_num - 1; i++) {
line = Line();
substr = line.split("\\s+");
data.vertexs[i][0] = Integer.parInt(substr[2]);
data.vertexs[i][1] = Integer.parInt(substr[3]);
data.demands[i] = Integer.parInt(substr[4]);
data.a[i] = Integer.parInt(substr[5]);
data.b[i] = Integer.parInt(substr[6]);
data.s[i] = Integer.parInt(substr[7]);
}
cin.clo();//关闭流
//初始化配送中⼼参数
data.vertexs[data.vertex_num-1] = data.vertexs[0];
data.demands[data.vertex_num-1] = 0;
data.a[data.vertex_num-1] = data.a[0];
data.b[data.vertex_num-1] = data.b[0];
data.E = data.a[0];
data.L = data.b[0];
data.s[data.vertex_num-1] = 0;
double min1 = 1e15;
double min2 = 1e15;
//距离矩阵初始化
for (int i = 0; i < data.vertex_num; i++) {
for (int j = 0; j < data.vertex_num; j++) {
if (i == j) {
data.dist[i][j] = 0;
别生气continue;
}
data.dist[i][j] =
Math.sqrt((data.vertexs[i][0]-data.vertexs[j][0]) *(data.vertexs[i][0]-data.vertexs[j][0])+
(data.vertexs[i][1]-data.vertexs[j][1])
*(data.vertexs[i][1]-data.vertexs[j][1]));
data.dist[i][j]=data.double_truncate(data.dist[i][j]); }
}
data.dist[0][data.vertex_num-1] = 0;
data.dist[data.vertex_num-1][0] = 0;
//距离矩阵满⾜三⾓关系
for (int k = 0; k < data.vertex_num; k++) {
for (int i = 0; i < data.vertex_num; i++) {
for (int j = 0; j < data.vertex_num; j++) {
if (data.dist[i][j] > data.dist[i][k] + data.dist[k][j]) { data.dist[i][j] = data.dist[i][k] + data.dist[k][j]; }
}
}
}
//初始化为完全图
for (int i = 0; i < data.vertex_num; i++) {
for (int j = 0; j < data.vertex_num; j++) {
if (i != j) {
data.arcs[i][j] = 1;
}
el {
data.arcs[i][j] = 0;
data.arcs[i][j] = 0;
}
}
}
/
/除去不符合时间窗和容量约束的边
for (int i = 0; i < data.vertex_num; i++) {
for (int j = 0; j < data.vertex_num; j++) {
if (i == j) {
continue;
}
if (data.a[i]+data.s[i]+data.dist[i][j]>data.b[j] ||
data.demands[i]+data.demands[j]>data.cap) {
data.arcs[i][j] = 0;
}
if (data.a[0]+data.s[i]+data.dist[0][i]+data.dist[i][data.vertex_num-1]> data.b[data.vertex_num-1]) {
System.out.println("the calculating example is fal");
}
}
}
for (int i = 1; i < data.vertex_num-1; i++) {
if (data.b[i] - data.dist[0][i] < min1) {
min1 = data.b[i] - data.dist[0][i];
}
远行的诗句
if (data.a[i] + data.s[i] + data.dist[i][data.vertex_num-1] < min2) {
min2 = data.a[i] + data.s[i] + data.dist[i][data.vertex_num-1];
}
}
if (data.E > min1 || data.L < min2) {
System.out.println("Duration fal!");
}
//初始化配送中⼼0，n+1两点的参数
data.arcs[data.vertex_num-1][0] = 0;
data.arcs[0][data.vertex_num-1] = 1;
于晓晞for (int i = 1; i < data.vertex_num-1; i++) {
data.arcs[data.vertex_num-1][i] = 0;
}
