自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA) |
您所在的位置：网站首页 › 遗传算法求解vrptw › 自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA) |
自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA)
|
文章目录
一、问题简介1、VRP（路径优化问题）2、VRPTW（带时间窗的路径优化问题）
二、算法简介1、优化算法简介2、ALNS简介
三、问题实现1、Node类2、Route类3、Parameter类4、初始解5、Destroy算子a）Random Destroyb）Greedy Destroyc）Shaw Destroy
6、Repair算子a）Random Repairb）Greedy Repairc）Regret Repair
7、ALNS主程序
四、结果展示1、Solomn（C101）算例结果2、求解速度结果
五、源码链接
一、问题简介
1、VRP（路径优化问题）
作为运筹学中较为经典的一类问题，一直受到人们的广泛关注。在交通和物流领域，VRP问题则是在已知需求点位置（多为坐标）的情况下，通过计算获得到达这些需求点最短路径或是最小成本的线路。 大量的实际应用表明，在规划和运营层面上，依赖高性能的计算机化方法解决VRP，可以实现在可接受计算时间内找到高质量可行的解决方案，为应用方带来显著的成本节约和更充分的资源利用。近几年出现的实时交通规划应用，更体现计算机在车辆路径规划问题上的经济效益。 VRP问题也有许多的变体，比如CVRP问题（带容量约束的路径优化）、VRPTW问题（带时间窗约束的路径优化）以及MDVRPTW（带时间窗的多车场路径优化）等。但是！！！——万变不离其宗，其核心问题还是VRP问题。本章主要解决的问题是VRPTW问题，下一节将对VRPTW问题做详细介绍。 2、VRPTW（带时间窗的路径优化问题） 上节已经提到，VRPTW问题是带时间窗的路径优化问题。本节，我们通过一个抽象的图来理解VRPTW问题！！ 图的左侧，有一个Depot（仓库、车场）节点和部分需求节点。其中： Depot： 仓库（车场）、中心节点 n（Vehicle）：车辆数 C（Capacity）：车辆容量 需求点1： （45,68）：需求点经纬度位置 [912,967]：需求点时间窗（最早到达时间、最晚到达时间） S（90）：需求点服务时间 D（10）：需求点需求量 问题描述： VRPTW问题是需要在depot发出n辆车，车辆容量不得超出C（Capacity）的限制，在满足每一个需求点时间窗需求的前提下，找到最佳的运输车辆数以及最佳的运输路线（通常以距离最短作为目标，当然也有时间最短），如右侧图所示。因此，我们可以得到相对应的目标函数和约束函数（公式无趣，这里就不放了） 二、算法简介 1、优化算法简介我们常见的求解优化算法的方法有三类： a）精确解算法 b）启发式算法 c）优化算法求解器 精确解算法： 指可求出最优解的算法。已提出的精确算法种类较多，有分支定界法、割平面法、整数规划算法和动态规划算法等。精确解可以求得优化算法的最优解，但是相对应其时间成本较大，当算例的规模较大时求解速率极低。 启发式算法： 通过某些特定的原理在一个解集空间中去搜寻相对最优的解，常见的启发式算法有遗传算法、粒子群算法等等。本文采用的自适应大规模邻域搜索算法也是启发式算法中的一种。 优化算法求解器： 优化求解器产品是求解优化问题的专业设计软件，常见的求解器有Gurobi、CPLEX等。 2、ALNS简介自适应大邻域搜索算法（Adaptive Large Neighborhood Search），简称 （ALNS） ，是由Ropke与Pisinger在2006年提出的一种启发式方法，其在邻域搜索的基础上增加了对算子的作用效果的衡量，使算法能够自动选择好的算子对解进行破坏与修复，从而有一定几率得到更好的解。 具体了解ALNS算法详见论文（Stefan Ropke, David Pisinger, (2006) An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science 40(4):455-472. https://doi.org/10.1287/trsc.1050.0135） 三、问题实现 1、Node类该部分定义了节点类部分指标： 参数名称ID节点列表IDDemand节点需求量ReadyTime需求点最早开始服务时间DServiceTime需求点服务时间Duetime需求点最晚开始服务时间x需求点x坐标y需求点y坐标R需求点所属线路Position需求点所在线路中的位置Regret_Cost节点的后悔值 2、Route类该部分定义了Route类部分指标： 参数名称Node N由节点N所组成的线路集合SubT违反时间窗量Load车辆载重量Dis某条线路的距离 3、Parameter类该部分定义了参数类部分指标： 参数名称MAX定义一个极大值MIN定义一个极小值NodeNumber需求节点的数量VehicleNumber车辆数量Capacity车辆载重量MaxIteration算法迭代次数Remove_NodeNumber移除节点的数量Alpha，Beta违反时间窗、载重量的惩罚系数Best_Value全局最佳CostLocal_Value局部最佳CostNew_Value更新后的CostRemove_Node移除节点集合R当前解集new_Route更新后的解集DisMatrix距离矩阵RelatedMatrix节点相关性矩阵WDestory破坏算子权重表WRepair修复算子权重表DestoryUseTime破坏算子使用次数RepairUseTime修复算子使用次数 4、初始解在满足绝对容量要求的前提下，生成 初始线路 解集： public static void ExtracRoutes() { //分割线路 //生成初始解(2-101)随机打乱 int[] New_index = new int[Parameter.NodeNumber]; for (int i = 0; i //生成一个随机索引 int randomIndex = Calculation.IntRandom(0,New_index.length); //拿着随机索引指向的元素 跟 i 指向的元素进行交换 int temp = New_index[i]; New_index[i] = New_index[randomIndex]; New_index[randomIndex] = temp; } for (int i = 1;i Parameter.R[i].N.clear(); } Parameter.R[i].N.add(new Node(Parameter.N[1])); Parameter.R[i].N.add(new Node(Parameter.N[1])); Parameter.R[i].N.get(0).Duetime = Parameter.N[1].ReadyTime; Parameter.R[i].N.get(1).ReadyTime = Parameter.N[1].Duetime; Parameter.R[i].Load = 0; } int Current_Route = 1; for (int i = 1;i //检查一条线路的容量情况，若容量超出，则更换线路 Current_Route++; } for (int j = 0;j Parameter.N[c].R = Current_Route; Parameter.R[Current_Route].N.add(j+1,new Node(Parameter.N[c])); Parameter.R[Current_Route].Load = Parameter.R[Current_Route].Load + Parameter.N[c].demand; break; } } Route.UPDis(Parameter.R[Current_Route]); //更新路径的长度 Route.UPSubT(Parameter.R[Current_Route]); //更新路径中时间窗的总量 } } 5、Destroy算子破坏节点的算子共有三种，分别为随机破坏、贪婪破坏以及Shaw相关性破坏。 a）Random Destroy随机破坏算子，顾名思义，随机选取n个节点进行破坏（将选中的节点从线路中删除）： public static void Random_Destroy(Route[] R) { //随机破坏0 int[] NodeIDIndex = new int[Parameter.Remove_NodeNumber]; int a = 0; //t b = 0; while ( a NodeIDIndex[a] = b; a++; } } //找到随机编号节点的具体位置 //int RouteIndex; for (int i = 0;i for (int j = 1; j Calculation.RemoveNode(R, RouteIndex, j, NodeIDIndex[i]); break; } } } } for (int i = 0;i //贪婪破坏1 double Cost_Old; double Cost_New; int RouteIndex = 0; int PositionIndex = 0; int NodeID1 = 0; int NodeID2 = 0; for (int m = 0;m //遍历每一条线路 for (int j = 1; j //若SuBT减少的更多 Value = Cost_Old - Cost_New; //则更新Value RouteIndex = i; PositionIndex = j; NodeID2 = NodeID1; //并记更优节点相关信息 } Calculation.AddNode(R, i, j, NodeID1); //将节点插回 } } Parameter.N[NodeID2].R = 0; //移除所属线路 Parameter.Remove_Node[m] = new Node(Parameter.N[NodeID2]); //将最优去除节点加入破坏节点表中 Calculation.RemoveNode(R, RouteIndex, PositionIndex, NodeID2); //在线路中移除选定节点 } } c）Shaw DestroyShaw破坏，也称相关性破坏：指破坏（删除）的下一个节点与删除的前一个节点有着较高的相关性。节点之间的相关性计算方式如下所示： public static double NodeRelated(Node n1, Node n2) { double a = 0.0; a = 1 * (Parameter.DisMatrix[n1.ID][n2.ID]) + 0.2 * (abs(n1.ReadyTime - n2.ReadyTime) + abs(n1.Duetime - n2.Duetime)) + 1 * (abs(n1.demand - n2.demand)); return a; }Shaw破坏中的第一个破坏节点为随机节点，后续破坏节点为与上一个节点关联性最强的节点，共破坏（删除）n个节点。 public static void Shaw_Destroy(Route[] R) { //相关性破坏2 int[] NodeIDIndex = new int[Parameter.Remove_NodeNumber]; int a = Calculation.IntRandom(2,Parameter.NodeNumber+2); //先随机产生一个节点ID编号 NodeIDIndex[0] = a; //将随机节点ID放入IndexID中 for (int m = 1;m if (Parameter.RelatedMatrix[NodeIDIndex[m-1]][i] > Value) { //若找到更大的Related值，则记录节点id Value = Parameter.RelatedMatrix[NodeIDIndex[m-1]][i]; RelatedID = i; } } NodeIDIndex[m] = RelatedID; } //找到随机编号节点的具体位置 for (int i = 0;i for (int j = 1; j Calculation.RemoveNode(R, RouteIndex, j, NodeIDIndex[i]); break; } } } } for (int i = 0;i //随机插入0 for (int i = 0;i if (R[RandomRouteIndex].N.get(PositionIndex).ReadyTime //贪婪插入1 double Cost1; double Cost2; int RouteIndex = 0; int PositionIndex = 0; for (int m = 0;m //遍历每一条线路 for (int j = 1; j //若满足更优位置 Value = Cost2 - Cost1; RouteIndex = i; PositionIndex = j; //记录位置 } Calculation.RemoveNode(R, i, j, Parameter.Remove_Node[m].ID); //删除节点 } } Calculation.AddNode(R, RouteIndex, PositionIndex, Parameter.Remove_Node[m].ID);//将节点插入最优的线路位置 } } c）Regret Repair后悔插入： 后悔插入需要首先理解一个概念——后悔值（ 即某一节点插入最佳插入位置后计算得到的Cost和次佳插入位置后计算得到的Cost的差值）。当一个节点的后悔值越大，则表明这个节点若在当前不插入该最佳位置，之后再将其插入其他位置的效益将会大大降低。 在理解了后悔值的前提下，我们简要说明后悔插入方法。依次循环计算得到n个需要插入节点的后悔值，找到当前n个节点中后悔值最大的节点，将其插入线路，更新Cost。再次重新循环计算得到n-1个需要插入节点的后悔值，找到n-1个需要插入节点中后悔值最大的节点并插入。重复上述步骤，直到所有删除节点均被修复为止。 public static void Regret_Repair(Route[] R) { //后悔插入2 double Cost1; double Cost2; double Cost3; int RouteIndex = 0; int PositionIndex = 0; //将RegretNode列表清空 if (Parameter.RegretNode[0].N.size() != 0) { Parameter.RegretNode[0].N.clear(); } //将RemoveNode中的点输入到RegretNode中 for (int i = 0;i Cost1 = Parameter.Cost(R); //计算当前的Cost for (int m = 0; m //遍历每一条线路 for (int j = 1; j //若满足更优位置 BestValue = Cost2 - Cost1; RouteIndex = i; PositionIndex = j; //记录位置 } Calculation.RemoveNode(R, i, j, Parameter.RegretNode[0].N.get(m).ID); //删除节点 } } double NextValue; double RegretValue = Parameter.MAX; for (int i = 1; i Calculation.AddNode(R, i, j, Parameter.RegretNode[0].N.get(m).ID); Cost2 = Parameter.Cost(R); NextValue = Cost2 - Cost1; if ((NextValue - BestValue) if (Parameter.RegretNode[0].N.get(i).Regret_Cost > Delta) { Delta = Parameter.RegretNode[0].N.get(i).Regret_Cost; RemoveID = i; //记录当前最大后悔值的节点并移除 } } //将找到的当前后悔值最大的节点加入 Calculation.AddNode(R, Parameter.RegretNode[0].N.get(RemoveID).R, Parameter.RegretNode[0].N.get(RemoveID).Position, Parameter.RegretNode[0].N.get(RemoveID).ID); //将移除的节点在RegretNode中移除 Parameter.RegretNode[0].N.remove(RemoveID); Number--; } } 7、ALNS主程序以下是ALNS算法的主程序，为了方便跳出最优解，还在其中加入了退火模拟和强制跳出当前解的操作（个人感觉退火模拟的作用不大） public static void ALNS() { Parameter.Best_Value = Parameter.MAX; int Iteration = 1; double T; double Down = 0.99; int CountSameNumber = 0; //计算线路相同的次数 while (Iteration Parameter.WRepair[i] = 1; Parameter.RepairUseTime[i] = 0; } for (int i = 0; i Count++; System.out.println("------------------"); System.out.println(Iteration + "-"+ Count); //记录破坏-修复前线路的Cost if (Iteration >=20) { if (Calculation.CompareRoute(Parameter.R, Parameter.new_Route) == true && Parameter.Local_Value == Parameter.New_Value) { //若解集相同，则相同计数+1 CountSameNumber++; } } Parameter.Local_Value = Parameter.Cost(Parameter.R); if (CountSameNumber == 30) { //若解40次没有发生变化，则进行强制跳出（采用随机破坏和随机插入算子并直接接受） //将new_Route[]清空 Calculation.ClearRoute(Parameter.new_Route); //将原始线路克隆到new_Route[]中 Calculation.CloneRoute(Parameter.new_Route, Parameter.R); //清空相关列表 for (int i = 0; i //若相同的次数不足50次 //将new_Route[]清空 Calculation.ClearRoute(Parameter.new_Route); //将原始线路克隆到new_Route[]中 Calculation.CloneRoute(Parameter.new_Route, Parameter.R); //清空相关列表 for (int i = 0; i |
【本文地址】
今日新闻 |
推荐新闻 |