干货|自适应大邻域搜索(ALNS)算法求解带时间窗的车辆路径规划问题(附JAVA代码)

转眼距离开学又过去一个多月了,不知道大家在家里学习的怎么样?这段时间小编在家里也没闲着,时隔多日,再次为大家带来干货内容

邻域搜索类启发式算法有很多种,比如禁忌搜索啦,模拟退火啦,变邻域搜索啦等等。这次带来的自适应大邻域搜索代码,相对上述几种会更复杂,内容相对全面。

小编在编写代码时,主要采用git-hub上一位作者de.markusziller的代码,参考他的ALNS框架下写出了解决带时间窗的车辆路径规划问题的代码,今天文章的主要内容将围绕代码实现展开。下面就开始今天的内容吧!

算法介绍

有关ALNS概念的介绍,公众号内已经有相关内容了,这里稍提一下,有疑惑的同学可以参考往期内容:

干货|自适应大邻域搜索(AdaptiveLargeNeighborhoodSearch)入门到精通超详细解析-概念篇

干货|自适应大规模邻域搜索算法求解带时间窗的车辆路径规划问题(上)

简单的讲,ALNS主要有两个特点:1.先用destroy方法破坏当前解,再用repair方法组合成新解。2.设计一组destroy,repair方法,动态评估每种方法的效果,在搜索中选用效果较好的方法。

ALNS算法是脱胎于大邻域搜索算法(LargeNeighborhoodSerach,LNS)的,第一个特点就是LNS的关键。通过带有随机性的destroy、repair方法构造新解,从而对解空间进行启发式搜索。

第二个特点是ALNS的自适应部分。类似于蚁群算法中的信息素,或禁忌搜索算法重点的禁忌表,由于ALNS算法的解空间是有destroy和repair方法定义的,因此这里记忆的主要是算子的使用情况

下面针对这次的VRPTW代码进行一些讲解。当然,这里只是挑选部分重点内容进行讲解,代码总量有2000多行,想要认真研究还需要下载代码亲自查阅哦!

初始解:Greedy方法

初始解的构造一般采用简单的greedy方法,这里小编编写了一个简单的greedy算法在满足时间窗约束和容量约束的情况下,往路径中不断加入距离最后一个客户距离最近的客户,若不满足约束,则使用下一辆车。

Greedy构造初始解(by.zll):solution=空集;newroute=空集;adddepottonewroute;whileunservedcustomers>0:c=findtheclosestcustomer();ifsatisfyloadconstraintandtimewindowsconstraint:addctonewroute;else:addnewroutetosolution;newroute=空集;endwhilereturnsolution

不过在实际测试中,小编也发现这种方法的一些缺陷。车辆数量约束较小、客户较少的Solomon算例,这种算法没有太大问题,而且构成的解效果不错;但对车辆约束较大、客户较多的Homberger算例,初始解可能无法在车辆约束内装满客户。因此构造方法还是视算例情况而定。

一种解决策略是放宽车辆上限,在后续优化中减少到约束条件内。对这次小编编写的代码,还可以采取另一种方式:构造违背约束条件的不可行解。因为在后续ALNS优化部分,我们允许不可行解的存在,因此可以将多余的客户随机插入greedy后的路径中,保证被服务到。

框架:ALNSProgress

先给出ALNS框架的伪代码:

ALNSProgress(by.zll):global_solution=initial_solution;local_solution=global_solution;fori=0toMaxIteration://产生新解current_solution=local_solution;destroy_opt=Chose_destroy();destroy_solution=Destroy(destroy_opt,current_solution);repair_opt=Chose_repair();new_solution=Repair(repair_opt,destroy_solution);//更新满意解ifnew_solutionbetterthanglobal_solution:Update_global_solution(new_solution,local_solution,destroy_opt,repair_opt);elseifnew_solutionbetterthanlocal_solution:Update_local_solution(local_solution,destroy_opt,repair_opt);elseUpdate_worse_solution(local_solution,destroy_opt,repair_opt);//更新算子选择策略Update_OptChose_strategies();endwhilereturnglobal_solution

框架主要将解区分为global_solution(以下简称s_g)、local_solution(以下简称s_c)和current_solution(以下简称s_t)。s_c与s_g的区别在于,算法中设计了模拟退火的接受worsesolution策略,概率更新s_c,避免陷入局部最优解中。

每个算子都有一定的选择概率,通过轮盘赌的方式随机选择本次迭代使用的算子。

每当一组算子被选择后,根据算子更新的s_g的优劣,动态更新算子的参数,在一定步长后更新算子被选择的概率。

算子:destroy&repair

相对于ALNSProgress框架,算子和所解决的问题相关度更大。前文的框架适用于任何问题,而算子部分则需要针对解决的问题进行重写。有关VRPTW的destroy、repair算子,公众号内有一篇推文进行过详细介绍:

干货|自适应大规模邻域搜索算法求解带时间窗的车辆路径规划问题(上)

这里简单讲一下小编所采用的算子。小编的算子主要参考了原先的代码,由于解决的问题不同,小编进行了修改调整,有一定原创性,童鞋们如果觉得效果不好可以自行修改、增删。

destroy算子

小编编写了三个destroy算子:randomdestroy、shawdestroy、worstcostdestroy。

randomdestroy随机remove一定量客户,没啥好讲的。

shawdestroy定义了关联结点,每次选择与上一个移除的结点关联度较高的结点进行移除。关联度的计算公式如下:

intl=(lastRoute.getId()==s.routes.get(j).getId())?-1:1;doublefitness=l*2+3*distance[lastRemove.getId()][relatedNode.getId()]+2*Math.abs(lastRemove.getTimeWindow()[0]-relatedNode.getTimeWindow()[0])+2*Math.abs(lastRemove.getDemand()-relatedNode.getDemand());

worstcostdestroy顾名思义就是选择所有结点中对cost影响最大的。计算公式如下:

doublefitness=(route.getCost().getTimeViolation()+route.getCost().getLoadViolation()+customer.getDemand())*(distance[customer.getId()][route.getRoute().get(0).getId()]+distance[route.getRoute().get(0).getId()][customer.getId()]);

变量名应该写的比较清楚,如果还有疑问,可以查看具体代码。

repair算子

repair也写了三个算子,分别是:randomrepair,greedyrepair和regretrepair。

randomrepair就不讲啦。

greedyrepair也比较好理解,按照greedy策略评估每个结点的最优插入位置,进行插入操作。

greedyrepair的不足之处在于,总是将那些困难(能使目标函数值提高很多)的顾客放到后面插入。这使得可插入的点变得很少。regretrepair对比了两个较优插入位置,计算deltacost,最大化把顾客插入到最好的中和第2好的位置中目标函数的差异。

代码查阅

下载代码后在Main函数中修改算例参数,代码文件夹内包括部分Solomon算例和Homberger算例。

如果需要修改ALNS部分相关参数,可以在ALNSConfiguration内修改,重要参数做了注释(其实不需要管太多啦)。

运行结果展示

各个算子的使用情况:

结果显示:

对结果进行验证:

后记

关于ALNS,小编还会专门做一期测试对比,展示一下ALNS的效果。同时,这段代码里面还有一部分可视化的内容,可以实时查看算子的使用情况和解的收敛情况,也会更新相关内容,敬请期待!

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...