专栏首页数据魔术师干货|遗传算法解决带时间窗的车辆路径规划问题(附java代码及详细注释)

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

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

1.遗传算法

1

遗传算法简介

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

2

遗传算法基本思想

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

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

3

遗传算法流程

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

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.

本文分享自微信公众号 - 数据魔术师(data-magician),作者:李博骁

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 运筹学教学|修正单纯形法(revised simplex algorithm)代码分享及详细注释

    欢声笑语中,小编学会了单纯形法,心里还有点小傲骄!!准备晚上去PUBG里面潇洒一把~ ? 然而,老板突然来电话说,单纯形法有升级的版本!需要我赶紧准备一份代码。...

    用户1621951
  • 运筹学教学|Berders decomposition (二)应用实例及算法实现(附源代码及详细的代码注释)

    我们在运筹学教学|Benders decomposition(一)技术介绍篇中已经介绍了Benders Decomposition的基本原理,下面为大家提供具体...

    用户1621951
  • 论文拾萃 | 基于树表示法的变邻域搜索算法求解考虑后进先出的取派货旅行商问题(附C++代码和详细代码注释)

    本文参考期刊论文信息如下: "The Tree Representation for the Pickup and Delivery Traveling Sa...

    用户1621951
  • 《Python入门03》对于Python列表和元组你了解多少?

    上一节中,主要介绍了python的变量和python的基本类型。那么本节将首先介绍序列的基本操作,然后具体python的列表和元组。

    ShuYini
  • @程序员,请掌握这些核心生存技能

    以上是一个读者流年似水的提问。我把他的问题置顶了,但一直没想好怎么回答,因为问题太过笼统了。后来,他也可能意识到了这一点,就又给我发了一条微信:

    沉默王二
  • Elasticsearch的Term为什么很快之跳表

    term代表完全匹配,也就是精确查询,搜索前不会再对搜索词进行分词,所以我们的搜索词必须是文档分词集合中的一个,此字段如 "无分词",则完全匹配此字段(如果对于...

    只喝牛奶的杀手
  • 用pandas绘制箱体图(boxplot)

    箱体图是一种用于表示分布的图像,由五个分位数组成。很好用的图,但是excel要生成这个可就得曲线救国了,然而如果用python加上pandas的话就很easy啦...

    钱塘小甲子
  • 证明你是坏程序员的7个迹象

    证明你是坏程序员的7个迹象 1)开始编码之前没有计划 说到这一点,我自己其实也并没有做到,我总是喜欢直接编码。但是慢慢地,我看到了在写代码之前先简单规划一下的好...

    用户1289394
  • AS3关于飘金币的特效

        ②:为了得到贝塞尔曲线的效果,至少需要3个点(你懂得),中间的曲线点是由此类(上)来自动计算的.并且,每个中间点都做了一个随机的偏移.

    用户2398817
  • Renato 说全球:2018 年语言行业前景展望播客

    本期内容采编自 Renato & Michael 的播客节目《全球化说》第41期:“Podcast 041: Forecast 2018: What's Ahe...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动