大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 祝大家元宵节快乐
本文引用
Shaw P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[M]// Principles and Practice of Constraint Programming — CP98. 1998.
刘小兰, 郝志峰, 汪国强, et al. 有时间窗的车辆路径问题的近似算法研究[J]. 计算机集成制造系统, 2004, 10(7):825-831.
Shaw P的这篇论文首次提出大规模邻域搜索算法(后文统一称为LNS),之前小编写的推文感觉有点简单,这次再一次精度了这篇经典论文后,决定用MATLAB编写文中的提出的LNS求解带时间窗的车辆路径问题(后文统一称为VRPTW问题)的代码。
小编会带大家详细梳理LNS的基本流程,其实说白了LNS只包括两个步骤:Remove和Re-inserting,先别急后文会详细介绍针对VRPTW问题,如何Remove和如何Re-inserting;然后用MATLAB编写LNS代码求解VRPTW问题。
1.LNS流程
Remove过程是如何选择出移走的客户,Re-inserting过程是如何快速地将客户插到能产生更好解地位置。
1.1 Remove过程
用符号
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示当前解,
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示将要被移走的客户,
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示被移走的客户组成的集合,
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示移走的客户数目,
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示从
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中移走
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 个客户后剩余的部分解。则Remove过程如下:
首先,从
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中随机移走一个客户到
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中,作为集合
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 的第一个元素。剩下的
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 个元素按照如下方法来选定:每次从集合
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中随机选一个客户
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ,将
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中剩余的客户按照与
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 的相关性由小到大的顺序排列。从
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中选出与
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 的相关性最大的客户
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ,从
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中移走
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ,并把它加入到
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中去。重复该过程
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 次,直到剩下的
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 个元素都选好。相关性的定义为:
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 其中
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示将
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 标准化后的值,在[0,1]之间,
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 与
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 之间的欧式距离。
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 与
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 是否在同一条路径上,即是否由同一辆车服务。如何在同一条路径上时为0,否则为1。
也就是说地理位置相距很近的两个客户的相关性比相距很远的要大;在同一条路径上的两个客户的相关性比不在同一条路径上的要大。
实际情况中,不存在完美的相关性函数,如果过度依赖相关性函数选择被移出的客户可能会出现“鼠目寸光”的情况。为避免这种情况的出现,Shaw在算法中加入了随机元素,即
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ,它的结果是相关性大小序列中的一个客户,即假设
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 然后将
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中剩余的客户按照与
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 的相关性由大到小的顺序排列,得到排序后的序列为lst,因此上述过程的结果为lst[index]。可以看出当D为1时,被移出的客户是完全随机选择的;当D等于正无穷时,即接近选择相关性最大的客户。也就是说D的值越大,越有利于相关性大的客户。
Remove过程的伪代码如下所示:
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 1.2 Re-inserting过程
Re-inserting过程是将移走的客户集
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 重新插回部分解
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ,以产生更好的解。首先计算
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中每一个客户的最佳插入位置,将
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中的客户
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 插回部分解
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ,在多个插入位置中,找出使目标值增加最少的那个位置即为最佳插入位置(该插入位置即为cheapest insertion point),并记下对应的目标值。那么如何从
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 选择客户
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 插回到
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中,以产生更好的解呢?
计算
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中每一个客户插入到各自的最佳插入位置后所带来的目标值增量,选择目标值增量最大的客户作为第一个插回客户,该方法被称farthest insertion heuristic。将此方法重复执行直到
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中的所有客户都被重新插回部分解
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 。
Shaw 在Re-inserting过程中还使用了有限偏差搜索(Limited Discrepancy Search,LDS)以提高搜索效率。但说句实在话,小编没有看明白如何用LDS提高搜索效率。
此处可以省略不看
不过在这里还是有必要介绍一下LDS:它是建立在“手头上已经有求解某个问题的 一种较好的启发式算法”的基础上的,其基本思想是:假设按照事先设计的启发式算法不能找到目标,则很有可能是算法在几个关键点上“出差错了”—— 本该朝东走的,却在朝西走了。如果允许算法在这些关键点上“犯错误”——背离算法在这些点的走向,转向其他方向,然后继续按照算法搜索下去,则极有可能找到目标。运用到VRPTW,D=0表示全部的客户都插入到最佳位置,记为
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ,其中
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 表示第i个插回客户的插入位置,0表示插入到最佳位置,可以看出满足
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) ;D=1表示
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中只有一个客户插入到其第二好的位置,其余的都插入到最佳位置,即满足
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 的位置,如(1,0,......,0);D=2表示
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中一个客户插入到其第三好的位置,或者
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 中两个客户插入到其第二好的位置,即满足
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 的位置,如(2,0,......,0),(1,1,......,0),其余依此类推,其中D的上限d为一事先给定的值。
2.MATLAB代码(后台回复“LNS”提取代码)
代码说明:直接运行LNS.m即可(小编是按照自己的理解编写代码的,可能与论文中讲的不太一致,在这里还是希望大家多和小编交流,大家共同进步)
链接:https://pan.baidu.com/s/1w1kvuNx3ESi_d2uNSrKZ6A
提取码:x10h
用CW法构造VRPTW初始解(数据集采用solomon中的c101),共需要12辆车,总距离是916.8716;
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码) 用LNS优化初始解后,共需要11辆车,总距离是884.1077(这里各位小伙伴运行的解可能与我的不一样,没关系,因为我在编程序的时候,设定只要优化后的总距离一旦小于初始总距离就立马跳出循环)
大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码)