自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA)-Toy模板网

这篇具有很好参考价值的文章主要介绍了自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题简介

1、VRP（路径优化问题）

作为运筹学中较为经典的一类问题，一直受到人们的广泛关注。在交通和物流领域，VRP问题则是在已知需求点位置（多为坐标）的情况下，通过计算获得到达这些需求点最短路径或是最小成本的线路。

大量的实际应用表明，在规划和运营层面上，依赖高性能的计算机化方法解决VRP，可以实现在可接受计算时间内找到高质量可行的解决方案，为应用方带来显著的成本节约和更充分的资源利用。近几年出现的实时交通规划应用，更体现计算机在车辆路径规划问题上的经济效益。

VRP问题也有许多的变体，比如CVRP问题（带容量约束的路径优化）、VRPTW问题（带时间窗约束的路径优化）以及MDVRPTW（带时间窗的多车场路径优化）等。但是！！！——万变不离其宗，其核心问题还是VRP问题。本章主要解决的问题是VRPTW问题，下一节将对VRPTW问题做详细介绍。

2、VRPTW（带时间窗的路径优化问题）

上节已经提到，VRPTW问题是带时间窗的路径优化问题。本节，我们通过一个抽象的图来理解VRPTW问题！！
自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA)

图1：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	节点列表ID
Demand	节点需求量
ReadyTime	需求点最早开始服务时间D
ServiceTime	需求点服务时间
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	全局最佳Cost
Local_Value	局部最佳Cost
New_Value	更新后的Cost
Remove_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 < Parameter.NodeNumber; ++i) {
        New_index[i] = i + 2;
    }
    for (int i = 0; i < New_index.length; 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.VehicleNumber;i++) {
        if (Parameter.R[i].N.size() != 0) {
            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 <= Parameter.NodeNumber;i++) {
        int c = New_index[i-1];
        if (Parameter.R[Current_Route].Load + Parameter.N[c].demand > Parameter.Capacity) {     //检查一条线路的容量情况，若容量超出，则更换线路
            Current_Route++;
        }
        for (int j = 0;j < Parameter.R[Current_Route].N.size()-1;j++) {
            if (Parameter.R[Current_Route].N.get(j).ReadyTime <= Parameter.N[c].ReadyTime &&
                    Parameter.N[c].ReadyTime <= Parameter.R[Current_Route].N.get(j+1).ReadyTime) {
                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 < Parameter.Remove_NodeNumber) {
        int b = Calculation.IntRandom(2,Parameter.NodeNumber+2);
        if (useLoop(NodeIDIndex,b) == false) {
            NodeIDIndex[a] = b;
            a++;
        }
    }


    //找到随机编号节点的具体位置
    //int RouteIndex;
    for (int i = 0;i < NodeIDIndex.length;i++) {
        //RouteIndex = Parameter.N[NodeIDIndex[i]].R;
        for (int RouteIndex = 1;RouteIndex <= Parameter.VehicleNumber;RouteIndex++) {
            for (int j = 1; j < R[RouteIndex].N.size(); j++) {
                if (NodeIDIndex[i] == R[RouteIndex].N.get(j).ID) {
                    Calculation.RemoveNode(R, RouteIndex, j, NodeIDIndex[i]);
                    break;
                }
            }
        }
    }
    for (int i = 0;i < NodeIDIndex.length;i++) {
        //Parameter.N[NodeIDIndex[i]].R = 0;      //更新线路
        Parameter.Remove_Node[i] = new Node(Parameter.N[NodeIDIndex[i]]);   //放入移除表中
    }
}

b）Greedy Destroy

贪婪破坏：将线路中的所有节点依次删除-放回，并记录使Cost（目标函数）变化最大（这里应该是变小最多）的节点并记录。依次找到n个节点并删除：

public static void Greedy_Destroy(Route[] R) {          //贪婪破坏1
    double Cost_Old;
    double Cost_New;
    int RouteIndex = 0;
    int PositionIndex = 0;
    int NodeID1 = 0;
    int NodeID2 = 0;

    for (int m = 0;m < Parameter.Remove_NodeNumber;m++) {
        double Value = Parameter.MIN;
        Cost_Old = Parameter.Cost(R);                                    //计算当前Cost
        for (int i = 1; i <= Parameter.VehicleNumber+1; i++) {              //遍历每一条线路
            for (int j = 1; j <= R[i].N.size() - 2; j++) {              //遍历当前路径的每一个节点
                NodeID1 = R[i].N.get(j).ID;                             //记录当前节点的ID
                Calculation.RemoveNode(R, i, j, NodeID1);               //移除当前节点
                Cost_New = Parameter.Cost(R);                           //计算新的Cost

                if ((Cost_Old - Cost_New) > Value) {                   //若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 Destroy

Shaw破坏，也称相关性破坏：指破坏（删除）的下一个节点与删除的前一个节点有着较高的相关性。节点之间的相关性计算方式如下所示：

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 < Parameter.Remove_NodeNumber;m++) {
        double Value = Parameter.MIN;
        int RelatedID = 0;
        for (int i = 2; i <= Parameter.NodeNumber + 1; i++) {
            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 < NodeIDIndex.length;i++) {
        for (int RouteIndex = 1;RouteIndex <= Parameter.VehicleNumber;RouteIndex++) {
            for (int j = 1; j < R[RouteIndex].N.size(); j++) {
                if (NodeIDIndex[i] == R[RouteIndex].N.get(j).ID) {
                    Calculation.RemoveNode(R, RouteIndex, j, NodeIDIndex[i]);
                    break;
                }
            }
        }
    }
    for (int i = 0;i < NodeIDIndex.length;i++) {
        Parameter.Remove_Node[i] = new Node(Parameter.N[NodeIDIndex[i]]);   //放入移除表中
    }
}

6、Repair算子

修复算子也有三种，分别是随机修复、贪婪修复以及后悔修复。

a）Random Repair

随机修复： 将之前破坏算子破坏的n个节点依次按照初始解生成的方式随机插入任意一条线路中。

public static void Random_Repair(Route[] R) {           //随机插入0
    for (int i = 0;i < Parameter.Remove_Node.length;i++) {
        int RandomRouteIndex = Calculation.IntRandom(1,Parameter.VehicleNumber+1);
        for (int PositionIndex = 0;PositionIndex < R[RandomRouteIndex].N.size()-1;PositionIndex++) {
            if (R[RandomRouteIndex].N.get(PositionIndex).ReadyTime <= Parameter.Remove_Node[i].ReadyTime &&
                    Parameter.Remove_Node[i].ReadyTime <= R[RandomRouteIndex].N.get(PositionIndex+1).ReadyTime) {
                Calculation.AddNode(R, RandomRouteIndex, PositionIndex+1, Parameter.Remove_Node[i].ID);
                break;
            }
        }
    }
}

b）Greedy Repair

贪婪修复： 贪婪修复与贪婪破坏较为类似，其方法是依次将需要插入的节点循环放入线路中的所有位置，并记录使Cost（目标函数）变化最好的位置（这里应该是目标函数增加最小）。最后将节点依次插入贪婪插入计算得到“最好”的位置。

public static void Greedy_Repair(Route[] R) {               //贪婪插入1
    double Cost1;
    double Cost2;
    int RouteIndex = 0;
    int PositionIndex = 0;

    for (int m = 0;m < Parameter.Remove_Node.length;m++) {
        double Value = Parameter.MAX;                //设定一个最大值
        Cost1 = Parameter.Cost(R);                   //计算当前Cost
        for (int i = 1; i <= Parameter.VehicleNumber; i++) {      //遍历每一条线路
            for (int j = 1; j < R[i].N.size(); j++) {        //遍历当前线路中的每一个位置
                Calculation.AddNode(R, i, j, Parameter.Remove_Node[m].ID);     //插入节点
                Cost2 = Parameter.Cost(R);                                    //计算当前的Cost
                if ((Cost2 - Cost1) < Value) {                            //若满足更优位置
                    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 < Parameter.Remove_NodeNumber;i++) {
        Parameter.RegretNode[0].N.add(new Node(Parameter.Remove_Node[i]));
    }

    int Number = Parameter.Remove_NodeNumber;
    while (Number > 0) {

        Cost1 = Parameter.Cost(R);          //计算当前的Cost
        for (int m = 0; m < Parameter.RegretNode[0].N.size(); m++) {
            double BestValue = Parameter.MAX;
            for (int i = 1; i <= Parameter.VehicleNumber; i++) {      //遍历每一条线路
                for (int j = 1; j < R[i].N.size(); j++) {        //遍历当前线路中的每一个位置
                    Calculation.AddNode(R, i, j, Parameter.RegretNode[0].N.get(m).ID);     //插入节点
                    Cost2 = Parameter.Cost(R);                                    //计算当前的Cost
                    if ((Cost2 - Cost1) < BestValue) {                            //若满足更优位置
                        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 <= Parameter.VehicleNumber; i++) {             //次佳插入点
                for (int j = 1; j < R[i].N.size(); j++) {
                    Calculation.AddNode(R, i, j, Parameter.RegretNode[0].N.get(m).ID);
                    Cost2 = Parameter.Cost(R);
                    NextValue = Cost2 - Cost1;
                    if ((NextValue - BestValue) < RegretValue && (NextValue - BestValue) != 0) {
                        RegretValue = NextValue - BestValue;
                    }
                    Calculation.RemoveNode(R, i, j, Parameter.RegretNode[0].N.get(m).ID);          //删除节点
                }
            }
            Parameter.RegretNode[0].N.get(m).Regret_Cost = RegretValue;
            Parameter.RegretNode[0].N.get(m).R = RouteIndex;
            Parameter.RegretNode[0].N.get(m).Position = PositionIndex;                              //记录相关指标
        }

        //找到当前后悔值最大的节点
        int RemoveID = 0;
        double Delta = Parameter.MIN;
        for (int i = 0;i < Parameter.RegretNode[0].N.size();i++) {
            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.MaxIteration) {
        System.out.println("------------------");
        System.out.println(Iteration);
        System.out.println("------------------");
        T = 100.0;

        for (int i = 0; i < 3;i++) {
            Parameter.WRepair[i] = 1;
            Parameter.RepairUseTime[i] = 0;
        }
        for (int i = 0; i < 3;i++) {
            Parameter.WDestory[i] = 1;
            Parameter.DestoryUseTime[i] = 0;
        }
        int Count = 0;
        while (T > 5) {
            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 < Parameter.Remove_Node.length; i++) {
                    Parameter.Remove_Node[i] = new Node();
                }
                //采用随机算子
                Destroy.Random_Destroy(Parameter.new_Route);
                Repair.Random_Repair(Parameter.new_Route);
                //直接更新结果
                Calculation.ClearRoute(Parameter.R);
                Calculation.CloneRoute(Parameter.R, Parameter.new_Route);
                //计算更新后的Value
                Parameter.New_Value = Parameter.Cost(Parameter.new_Route);
                Parameter.Local_Value = Parameter.New_Value;
                CountSameNumber = 0;        //完成后更新CountSameNumber
            } else if (CountSameNumber < 30) {      //若相同的次数不足50次
                //将new_Route[]清空
                Calculation.ClearRoute(Parameter.new_Route);
                //将原始线路克隆到new_Route[]中
                Calculation.CloneRoute(Parameter.new_Route, Parameter.R);
                //清空相关列表
                for (int i = 0; i < Parameter.Remove_Node.length; i++) {
                    Parameter.Remove_Node[i] = new Node();
                }
                //通过轮盘赌的方式选择破坏算子和修复算子
                Calculation.selectSol_Roulette();
                //采用选择的算子进行修复和破坏
                Calculation.SelectAlgorithm();
                //更新权重和得分
                Calculation.CalScore();
            }

            T *= Down;
            System.out.println(Parameter.Best_Value);
            System.out.println(Parameter.Local_Value);
        }
        Iteration++;
        Calculation.ClearRoute(Parameter.R);
        Calculation.CloneRoute(Parameter.R, Parameter.Best_Route);
        System.out.println(Parameter.Best_Value);
        System.out.println("------------------------------");
    }
}

四、结果展示

1、Solomn（C101）算例结果

通过ALNS求解SolomnC101算例的结果如下图所示：
自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA)

图2：SolomnC101算例结果

最终的Cost为828，为启发式算法可得最优解

2、求解速度结果

在采用不同破坏算子数量并对C101算例进行多次求解后得到的结果如下图：
自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA)

图3：SolomnC101算例不同破坏节点数量下求解速度 可以发现，对于C101算例来说，该算法求解速度在5s左右，时间可以接受。

五、源码链接

以下附上github中的源代码，希望大家多多fork和star呀ღ( ´･ᴗ･` )！！！！
https://github.com/Empty-City-Wcl/Java-VRPTW-ALNS-文章来源地址https://www.toymoban.com/news/detail-401548.html

到了这里，关于自适应大规模邻域算法(ALNS)解决VRPTW问题(JAVA)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！