干货|遗传算法解决带时间窗的车辆路径规划问题(附java代码及详细注释）

各位读者大家好，今天小编给大家分享如何用遗传算法求解带时间窗的车辆路径规划问题。算法的主要思想来自于论文：A simple and effective evolutionary algorithm for the vehicle routing problem。在实现用遗传算法解VRPTW的过程中，小编一直在被生成了很多不可行解修复很困难而困扰，而这篇论文中所提出的算法恰好就避免了不可行解的处理，那么究竟是如何实现避免讨论不可行解的呢？接着读完这篇推文就能明白了~

1.遗传算法

1

遗传算法简介

遗传算法（Genetic Algorithm，简称GA）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的基于种群的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。遗传算法是现代智能计算中的关键技术之一。

2

遗传算法基本思想

在现实生活中，生物的染色体通过基因控制了生物的性状，而生物的性状决定了生物在环境中的适应度，适应度高的生物，其基因更容易流传下来，随着时间的不断流逝，整个种群的适应度随之提高。

遗传算法和现实非常类似，首先将问题的解通过一定的方法，编码到染色体中，通过适应度函数，得到每个个体的适应度，通过选择，将适应度高的个体保留到下一代中，不断迭代，即可获得满意解。

3

遗传算法流程

对遗传算法的详细介绍见：

• 干货 | 嘿！你和遗传算法的距离也许只差这一文(附C++代码和详细代码注释)
• 遗传算法求解混合流水车间调度问题（附C++代码）

2.带时间窗的车辆路径规划问题介绍

1

车辆路径规划问题介绍

车辆路径规划问题，经过60年来的研究与发展，研究的目标对象，限制条件等均有所变化，已经从最初的简单车辆安排调度问题转变为复杂的系统问题。最初的车辆路径规划问题可以描述为：有一个起点和若干个客户点,已知各点的地理位置和需求,在满足各种约束的条件下,如何规划最优的路径,使其能服务到每个客户点,最后返回起点。通过施加不同的约束条件，改变优化的目标，可以衍生出不同种类的车辆路径规划问题。同时车辆路径规划问题属于典型的NP-hard问题，其精确算法能求解的规模很小，故启发式算法也就成了研究热点。

2

VRPTW简介

VRPTW(Vehicle routing problem with time windows)即带时间窗的车辆路径规划问题，其对于每一需求点加入了时间窗的约束，即对于每一个需求点，设定服务开始的最早时间和最晚时间，要求车辆在时间窗内开始服务顾客。

需求点的时窗限制可以分为两种，一种是硬时间窗(Hard Time Window)，即要求车辆必须在时间窗内开始服务顾客，早到必须等待，迟到就拒收，另一种是软时间窗(Soft Time Window)，不一定要在时间窗内开始服务顾客，但是在时间窗外开始服务必须要惩罚，以惩罚代替等待与拒收是软时间窗和硬时时间窗的最大的区别。

VRPTW的数学模型如下：

（2.2）保证了每个顾客只被访问1次

（2.3）保证了装载的货物不超过容量

（2.4）（2.5）（2.6）确保了每辆车从depot出发最后回到depot

（2.7）（2.8）确保在时间窗内开始服务

在干货 | 十分钟掌握禁忌搜索算法求解带时间窗的车辆路径问题(附C++代码和详细代码注释)中详解介绍了如何用禁忌搜索（Tabu Search）算法求解VRPTW。

3.算法具体实现

1

染色体设计

在论文：A simple and effective evolutionary algorithm for the

vehicle routing problem 中，作者提出了在用GA解决VRP时的几点注意事项，如下图所示：

简单来说染色体的设计可以遵循以下两点：

1. 使用和TSP问题中类似的染色体、编码，没有分隔符

2. 使用split方法将染色体转化为问题的解

在使用GA求解VRPTW的过程中，常见的问题就在于交叉后产生的大量不可行解，这里采用分割的思想，一个染色体所存的解是split函数操作后所产生的最优分割。这样所得到的解都为可行解，大大减少了无效搜索。

在所有分割里，能最小化目标函数的即为最优分割。其实这就是一个编码和解码的过程。

下面我们来具体介绍一下这个split方法:

大家可能会觉得获得最优分割是一个很困难的事情，其实引入图论的思想，利用Bellman-Ford算法，在O(n^2)内就能获得最优分割。

上面两个图展示了如何把原问题转化为一个图论中的问题：

将每个基因位设为一个点，假如将i到j连接，其路径满足容量约束和时间窗约束，则视为从i到j存在一条权值为路径长度的边。则最优分割即为从染色体开头的基因的点到结尾的基因的点的最短路。利用Bellman-Ford算法，可在O(n^2)中求出最优分割。

流程图如下：

2

群体多样性

遗传算法中常见的问题就是早熟，过早收敛。为了避免这种情况的发生，就要保证子代个体中各个个体的不同。

如何判断个体之间是否相同有很多算法，小编这里采用通过适应度的不同来判断的方法：

即两个个体的适应度相差大于一个值，即视为不同的个体。

3

crossover

crossover，即交叉操作，这里使用实数编码中常用的OX（Order Crossover）交叉算子。

OX 交叉算子的过程如图：

1. 随机选择两个点i,j，其中0<=i<=j<=N,N为染色体长度。
2. 将亲代P1从i到j的基因填入子代相同的位置。
3. 将亲代P2的基因不重复地依次填入子代中。

交换p1,p2,即可产生两个子代。

4

mutation

mutation，即突变操作，这里简单地随机交换染色体中的两个基因，过程如下图：

5

selection

选择的方法有很多，这里使用二进制锦标赛选择，每次从亲代中选择两个个体进行比较，将适应度大的个体保留到亲代中即可。

4.代码

代码由小编独立完成，有不周到之处还请多指教！

分为以下几个类：

Chromosome类为染色体类，提供了和Solution类的相互转换，即编码和解码过程，Customer类储存了具体的顾客，Conf类是参数的设定，Solution类储存了解，GA_Stategy中实现了遗传算法用的函数。

这里展示split函数的具体实现：

 Solution toSolution()// 使用分割函数：跑一遍bellman-ford算法获得最优分割，实际上转化为从开始点到结束点的最短路划分问题
    {
        Solution solution = new Solution();
        double [] V = new double[Conf.N+1];//距离数组
        int [] P = new int[Conf.N+1]; // 储存了连接该点的上一点
        int j; // 循环的标识
        int cost;// 当前的花费
        int dist; //
        double time;// 当前的时间
        for(int i = 1;i<=Conf.N;i++)//到达的点的最少花费
            V[i] = INF;
        for(int i = 1;i<=Conf.N;i++) {
            P[i] = this.cur_list.get(i);//最开始所有点都没连上
        }
        for(int i = 1;i<=Conf.N;i++)
        {
            cost  = 0;
            time = 0;
            j = i;
            while(true)
            {
                if(i == j)//行程的开始
                {
                    time += Math.max(Conf.customers[cur_list.get(j)].r_time,Conf.dis_matriax[0][cur_list.get(j)]);
                    time += Conf.customers[cur_list.get(j)].s_time; // 服务时间
                    time += Conf.dis_matriax[cur_list.get(j)][0];
                    cost += Conf.customers[cur_list.get(j)].demand;

                }
                else
                {
                    double next_time = time - Conf.dis_matriax[cur_list.get(j-1)][0] + Conf.dis_matriax[cur_list.get(j)][cur_list.get(j-1)];//到达下一个的时间
                    if(next_time > Conf.customers[cur_list.get(j)].d_time)
                        break;//
                    time = Math.max(next_time,Conf.customers[cur_list.get(j)].r_time);
                    time += Conf.dis_matriax[cur_list.get(j)][0];
                    cost += Conf.customers[cur_list.get(j)].demand;
                }
                if(cost<=Conf.Cap)//假如满足容量约束和时间约束
                {
                    if(V[cur_list.get(j)] > V[cur_list.get(i-1)] + time)
                    {
                        V[cur_list.get(j)] = V[cur_list.get(i-1)] + time;//不断更新当前最短路
                        P[cur_list.get(j)] = this.cur_list.get(i-1);
                    }
                    j++;
                }
                if(j>Conf.N ||time >= Conf.customers[0].d_time || cost>=Conf.Cap )
                    break;

            }


        }
       Route route = new Route();
       int tmp = P[cur_list.get(Conf.N)];
       int i = Conf.N;
       while(i > 0) // 将分割过的重新组成Solution
       {
           if(P[cur_list.get(i)] == tmp)
               route.cus_list.add(cur_list.get(i));
           else
           {
               tmp = P[cur_list.get(i)];
               Collections.reverse(route.cus_list);
               solution.rou_list.add(route);
               route = new Route();
               route.cus_list.add(cur_list.get(i));
           }
           i--;
       }
       if(route.cus_list.size()!= 0) {
           Collections.reverse(route.cus_list);
           solution.rou_list.add(route);
       }

       return solution;
    }

运行结果如图：

欲下载完整的算法代码、测试样例及相关文献，请移步留言区

参考文献：

[1]Anderson E, Phillips C, Sicker D, et al. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 2004, 31(12):1985-2002.

[2]Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 1987, 35(2):254-265.