热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

matlab分支定界法linprog_运筹学教学|分支定界法解带时间窗的车辆路径规划问题(附代码及详细注释)...

历尽千辛万苦,外加外援帮助,本辣鸡小编终于搞定了这个大坑-用分支定界法(Branchandbound,B&B)解带时间窗的车辆路径规划问题(VRPTW)

00ce907d6bf32419a405f367cbc92f2a.png

历尽千辛万苦,外加外援帮助,本辣鸡小编终于搞定了这个大坑-用分支定界法(Branch and bound, B&B)解带时间窗的车辆路径规划问题(VRPTW)。

预备知识

前面的推文中有提到过,分支定界法是一种精确解算法,之前推文“运筹学教学|分枝定界求解旅行商问题”中对于分支定界的基本思想进行了详细的阐述,有不记得的小伙伴可以点击上面的链接传送到之前推文。

带时间窗的车辆路径规划问题(下简称:VRPTW)在之前的推文中已经被详细的介绍过了,为了方便读者的阅读,我们在这里给出传送门

干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)

除此之外还要先学习一种数据结构叫做优先队列。优先队列(priority queue)是一种常用的数据结构,在这种数据结构中,队头永远是存储优先级最高的元素,取队头和插入元素的操作的时间复杂度都是O(logn)。在JAVA和C++中都内置了这一种数据结构,因此,亲爱的读者们不要害怕。当然如果有代码实现能力强的读者想要手工实现优先队列,也是可以的,想要学习优先队列以事先学习堆(heap)这种数据结构,可以完美的实现优先队列的功能。

当你仔细的阅读了上面两篇推文并理解了优先队列的原理之后,小编相信聪明的你一定不会对于接下来要讲的内容感到陌生。

代码以及解释

代码共分为4个类包括:

  • BaB_Vrptw :主类,用于建模以及分支定界求解VRPTW。

  • Check : 解的可行性判断

  • Data : 定义参数

  • Node : 定义分支定界的节点

01

Data 类

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&#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 &#61; cin.nextLine();  
           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            for (int j &#61; 0; j                if (i &#61;&#61; j) {  
                   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            for (int i &#61; 0; i                for (int j &#61; 0; j                    if (data.dist[i][j] > data.dist[i][k] &#43; data.dist[k][j]) {  
                       data.dist[i][j] &#61; data.dist[i][k] &#43; data.dist[k][j];  
                   }  
               }  
           }  
       }  
       //初始化为完全图  
       for (int i &#61; 0; i            for (int j &#61; 0; j                if (i !&#61; j) {  
                   data.arcs[i][j] &#61; 1;  
               }  
               else {  
                   data.arcs[i][j] &#61; 0;  
               }  
           }  
       }  
       //除去不符合时间窗和容量约束的边  
       for (int i &#61; 0; i            for (int j &#61; 0; j                if (i &#61;&#61; j) {  
                   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.b[i] - data.dist[0][i]                min1 &#61; data.b[i] - data.dist[0][i];  
           }  
           if (data.a[i] &#43; data.s[i] &#43; data.dist[i][data.vertex_num-1]                min2 &#61; data.a[i] &#43; data.s[i] &#43; data.dist[i][data.vertex_num-1];  
           }  
       }  
       if (data.E > min1 || data.L            System.out.println("Duration false!");  
           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            data.arcs[data.vertex_num-1][i] &#61; 0;  
       }  
       for (int i &#61; 1; i            data.arcs[i][0] &#61; 0;  
       }  
   }  
}  

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 j &#61; 0; j            new_node.lp_x[i][j] &#61; lp_x[i][j].clone();  
       }  
   }  
   for (int i &#61; 0; i        new_node.node_x[i] &#61; node_x[i].clone();  
   }  
   for (int i &#61; 0; i        for (int j &#61; 0; j            new_node.node_x_map[i][j] &#61; node_x_map[i][j].clone();  
       }  
   }  
   for (int i &#61; 0; i        new_node.node_routes.add((ArrayList) node_routes.get(i).clone());  
   }  for (int i &#61; 0; i        new_node.node_servetimes.add((ArrayList) node_servetimes.get(i).clone());  
   }  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            ArrayList r &#61; lp.best_note.node_routes.get(i);
           System.out.println();for (int j &#61; 0; j                System.out.print(r.get(j)&#43;" ");
           }
       }
   }

上面的函数就是主函数&#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                if (lp.routes.get(i).size()&#61;&#61;2) {  
                   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 k &#61; 0; k        w[i][k] &#61; model.numVar(0, 1e15, IloNumVarType.Float, "w" &#43; i &#43; "," &#43; k);  
           }  
           for (int j &#61; 0; j                if (data.arcs[i][j]&#61;&#61;0) {  
                   x[i][j] &#61; null;  
               }  
               else{  
                   //Xijk,公式(10)-(11)  
                   for (int k &#61; 0; k    x[i][j][k] &#61; model.numVar(0, 1, IloNumVarType.Float, "x" &#43; i &#43; "," &#43; j &#43; "," &#43; k);  
                   }  
               }  
           }  
       }  
       //加入目标函数  
       //公式(1)  
       IloNumExpr obj &#61; model.numExpr();  
       for(int i &#61; 0; i            for(int j &#61; 0; j                if (data.arcs[i][j]&#61;&#61;0) {  
                   continue;  
               }  
               for(int k &#61; 0; k                    obj &#61; model.sum(obj, model.prod(data.dist[i][j], x[i][j][k]));  
               }  
           }  
       }  
       model.addMinimize(obj);  
       //加入约束  
       //公式(2)  
       for(int i&#61; 1; i            IloNumExpr expr1 &#61; model.numExpr();  
           for (int k &#61; 0; k                for (int j &#61; 1; j                    if (data.arcs[i][j]&#61;&#61;1) {  
                       expr1 &#61; model.sum(expr1, x[i][j][k]);  
                   }  
               }  
           }  
           model.addEq(expr1, 1);  
       }  
       //公式(3)  
       for (int k &#61; 0; k            IloNumExpr expr2 &#61; model.numExpr();  
           for (int j &#61; 1; j                if (data.arcs[0][j]&#61;&#61;1) {  
                   expr2 &#61; model.sum(expr2, x[0][j][k]);  
               }  
           }  
           model.addEq(expr2, 1);  
       }  
       //公式(4)  
       for (int k &#61; 0; k            for (int j &#61; 1; j                IloNumExpr expr3 &#61; model.numExpr();  
               IloNumExpr subExpr1 &#61; model.numExpr();  
               IloNumExpr subExpr2 &#61; model.numExpr();  
               for (int i &#61; 0; i                    if (data.arcs[i][j]&#61;&#61;1) {  
                       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            IloNumExpr expr4 &#61; model.numExpr();  
           for (int i &#61; 0; i                if (data.arcs[i][data.vertex_num-1]&#61;&#61;1) {  
                   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            for (int i &#61; 0; i                for (int j &#61; 0; j                    if (data.arcs[i][j] &#61;&#61; 1) {  
                       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 i &#61; 1; i                IloNumExpr expr7 &#61; model.numExpr();  
               for (int j &#61; 0; j                    if (data.arcs[i][j] &#61;&#61; 1) {  
                       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[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            IloNumExpr expr8 &#61; model.numExpr();  
           for (int i &#61; 1; i                IloNumExpr expr9 &#61; model.numExpr();  
               for (int j &#61; 0; j                    if (data.arcs[i][j] &#61;&#61; 1) {  
                       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                if (data.arcs[i][j]>0.5) {  
                   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;

  1. 确定一个下界(初始解LB)&#xff0c;上界定为无穷大UB。

  2. 把初始问题构建一个节点加入优先队列(因为是优先队列&#xff0c;所以使用best first sloution&#xff0c;也就是每一次最好的目标值最前搜索)。

  3. 判断队列是否为空&#xff0c;如果为空跳转至7&#xff0c;否则取出并弹出队首元素&#xff0c;计算该节点的目标值P。

  4. 如果P > UB&#xff0c;返回3。否则判断当前节点是否是合法解(对于任意i,j,k,x_ijk均为整数)&#xff0c;如果是&#xff0c;跳转5否则跳转6。

  5. 如果P

  6. 设置两个子节点L, R。L&#xff0c;R的建立方式如上&#xff0c;如果L的目标值L.P <&#61; UB&#xff0c;把L加入队列&#xff0c;如果R的目标值R.P <&#61; UB&#xff0c;把R加入队列。返回3.

  7. 结束&#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            ArrayList r &#61; lp.routes.get(i);  
           System.out.println();  for (int j &#61; 0; j                System.out.print(r.get(j)&#43;" ");  
           }  
       }  
       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]][k]&#61;0;  
       }  //      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                new_node.node_x_map[record[0]][record[1]][k]&#61;1;  
           }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 v2 &#43; eps 返回1&#xff0c; 两数相等返回0。

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        }  if (v1 > v2 &#43; epsilon) {  return 1;  
       }  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            ArrayList route &#61; routes.get(k);  double capasity &#61; 0;  for (int i &#61; 0; i                capasity &#43;&#61; data.demands[route.get(i)];  
           }  if (capasity > data.cap) {  
               System.out.println("error: cap!!!");  
               System.exit(0);  
           }  
       }  //时间窗、车容量可行性判断  for (int k &#61; 0; k            ArrayList route &#61; routes.get(k);  
           ArrayList servertime &#61; servetimes.get(k);  double capasity &#61; 0;  for (int i &#61; 0; i  data.b[origin]) {  
                   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;

27aa446d14487d81be42b646782a314b.png

输出结果如下&#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;

欲下载代码请移步留言区。




推荐阅读
  • 深入解析Java虚拟机(JVM)架构与原理
    本文旨在为读者提供对Java虚拟机(JVM)的全面理解,涵盖其主要组成部分、工作原理及其在不同平台上的实现。通过详细探讨JVM的结构和内部机制,帮助开发者更好地掌握Java编程的核心技术。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本题旨在通过给定的评级信息,利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表,或者是否存在冲突或信息不足的情况。 ... [详细]
  • 本文详细介绍了优化DB2数据库性能的多种方法,涵盖统计信息更新、缓冲池调整、日志缓冲区配置、应用程序堆大小设置、排序堆参数调整、代理程序管理、锁机制优化、活动应用程序限制、页清除程序配置、I/O服务器数量设定以及编入组提交数调整等方面。通过这些技术手段,可以显著提升数据库的运行效率和响应速度。 ... [详细]
  • 本文介绍如何在Java中实现一个罗马数字计算器,重点在于如何通过循环和字符验证确保用户输入合法。我们将探讨创建一个方法来检查字符串中的非法字符,并使用循环不断提示用户输入,直到输入符合要求。 ... [详细]
  • MySQL索引详解与优化
    本文深入探讨了MySQL中的索引机制,包括索引的基本概念、优势与劣势、分类及其实现原理,并详细介绍了索引的使用场景和优化技巧。通过具体示例,帮助读者更好地理解和应用索引以提升数据库性能。 ... [详细]
  • 微软Exchange服务器遭遇2022年版“千年虫”漏洞
    微软Exchange服务器在新年伊始遭遇了一个类似于‘千年虫’的日期处理漏洞,导致邮件传输受阻。该问题主要影响配置了FIP-FS恶意软件引擎的Exchange 2016和2019版本。 ... [详细]
  • 本文深入探讨了POJ2762问题,旨在通过强连通分量缩点和单向连通性的判断方法,解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤,并附带完整的代码示例。 ... [详细]
  • 开发笔记:9.八大排序
    开发笔记:9.八大排序 ... [详细]
  • 本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数,并使用递推算法和大数处理技术来解决这一问题。 ... [详细]
  • 丽江客栈选择问题
    本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]
  • ElasticSearch 集群监控与优化
    本文详细介绍了如何有效地监控 ElasticSearch 集群,涵盖了关键性能指标、集群健康状况、统计信息以及内存和垃圾回收的监控方法。 ... [详细]
  • 由二叉树到贪心算法
    二叉树很重要树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。单就面试而言,在 ... [详细]
  • 并发编程 12—— 任务取消与关闭 之 shutdownNow 的局限性
    Java并发编程实践目录并发编程01——ThreadLocal并发编程02——ConcurrentHashMap并发编程03——阻塞队列和生产者-消费者模式并发编程04——闭锁Co ... [详细]
  • 本文深入探讨了UNIX/Linux系统中的进程间通信(IPC)机制,包括消息传递、同步和共享内存等。详细介绍了管道(Pipe)、有名管道(FIFO)、Posix和System V消息队列、互斥锁与条件变量、读写锁、信号量以及共享内存的使用方法和应用场景。 ... [详细]
author-avatar
大约在冬季1122_867
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有