大规模邻域搜索（LNS）求解带时间窗的车辆路径问题（VRPTW）（附MATLAB代码）

2023-12-01 08:40:10

本文引用

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过程

用符号表示当前解，表示将要被移走的客户，表示被移走的客户组成的集合，表示移走的客户数目，表示从中移走个客户后剩余的部分解。则Remove过程如下：

首先，从中随机移走一个客户到中，作为集合的第一个元素。剩下的个元素按照如下方法来选定：每次从集合中随机选一个客户，将中剩余的客户按照与的相关性由小到大的顺序排列。从中选出与的相关性最大的客户，从中移走，并把它加入到中去。重复该过程次，直到剩下的个元素都选好。相关性的定义为：

其中表示将标准化后的值，在[0,1]之间，表示与之间的欧式距离。

表示与是否在同一条路径上，即是否由同一辆车服务。如何在同一条路径上时为0，否则为1。

也就是说地理位置相距很近的两个客户的相关性比相距很远的要大；在同一条路径上的两个客户的相关性比不在同一条路径上的要大。

实际情况中，不存在完美的相关性函数，如果过度依赖相关性函数选择被移出的客户可能会出现“鼠目寸光”的情况。为避免这种情况的出现，Shaw在算法中加入了随机元素，即

，它的结果是相关性大小序列中的一个客户，即假设

然后将中剩余的客户按照与的相关性由大到小的顺序排列，得到排序后的序列为lst，因此上述过程的结果为lst[index]。可以看出当D为1时，被移出的客户是完全随机选择的；当D等于正无穷时，即接近选择相关性最大的客户。也就是说D的值越大，越有利于相关性大的客户。

Remove过程的伪代码如下所示：

1.2 Re-inserting过程

Re-inserting过程是将移走的客户集重新插回部分解，以产生更好的解。首先计算中每一个客户的最佳插入位置，将中的客户插回部分解，在多个插入位置中，找出使目标值增加最少的那个位置即为最佳插入位置（该插入位置即为cheapest insertion point），并记下对应的目标值。那么如何从选择客户插回到中，以产生更好的解呢？

计算中每一个客户插入到各自的最佳插入位置后所带来的目标值增量，选择目标值增量最大的客户作为第一个插回客户,该方法被称farthest insertion heuristic。将此方法重复执行直到中的所有客户都被重新插回部分解。

Shaw 在Re-inserting过程中还使用了有限偏差搜索(Limited Discrepancy Search，LDS)以提高搜索效率。但说句实在话，小编没有看明白如何用LDS提高搜索效率。

此处可以省略不看

不过在这里还是有必要介绍一下LDS：它是建立在“手头上已经有求解某个问题的一种较好的启发式算法”的基础上的，其基本思想是：假设按照事先设计的启发式算法不能找到目标，则很有可能是算法在几个关键点上“出差错了”—— 本该朝东走的，却在朝西走了。如果允许算法在这些关键点上“犯错误”——背离算法在这些点的走向，转向其他方向，然后继续按照算法搜索下去，则极有可能找到目标。运用到VRPTW，D=0表示全部的客户都插入到最佳位置，记为，其中表示第i个插回客户的插入位置，0表示插入到最佳位置，可以看出满足；D=1表示中只有一个客户插入到其第二好的位置，其余的都插入到最佳位置，即满足的位置，如（1,0,......,0）;D=2表示中一个客户插入到其第三好的位置，或者中两个客户插入到其第二好的位置，即满足的位置，如（2,0,......,0）,(1,1,......,0)，其余依此类推，其中D的上限d为一事先给定的值。