下载掌阅APP，畅读海量书库
立即打开
作为启发式算法的一类，禁忌搜索算法（Tabu Search）由Glover（1986）最早提出，它采取了邻域选优的搜索算法，且在一定的情况下接受劣解。为避免陷入局部循环，算法使用禁忌列表，持续将最近接受的一些移动放在表中，在后面的迭代中禁止使用。如果禁忌列表中某些移动产生的解比历史最优解更好，则打破禁忌，允许使用该移动，称此为渴望原则。本章设计了一种改进的禁忌搜索算法，称为颗粒禁忌搜索算法（GTS），其最早被Toth和Vigo（2003）提出来解决车辆路径问题。Toth和Vigo（2003）在传统的禁忌搜索算法的基础上提出了“颗粒邻域”（Granular Neighborhoods）的概念，在采用禁忌搜索算法生成邻域解时，只允许考虑接受可能带来较好的解的移动。相比传统的禁忌搜索算法，GTS仅仅搜索小部分的邻域空间，在不降低解的质量的情况下大大加快了整个算法的搜索速度。GTS的详细流程如图4-1所示，本章设计的GTS由四个部分组成：
（1）构造初始可行解：分别采用贪婪算法与随机算法；
（2）颗粒邻域生成邻域解：简介颗粒邻域结构，并提出四种产生邻域解的移动方式及一种简单的计算邻域解目标值的算法；
（3）局部搜索算法优化邻域解：采取了一种优化车辆路径的局部搜索算法；
（4）禁忌搜索算法准则：设计禁忌列表、集中搜索与分散搜索。
图4-1 GTS流程
该问题的初始解由一系列车辆路径构成，每条车辆路径中包含不同的客户点，每个客户点的订单在仓库的可得时间不同，因此每辆车的出发时间与行驶时间均不同。禁忌搜索算法从构造初始解开始，分别采取贪婪算法、节约算法和随机算法来生成多个解，计算每个解的目标值，从中挑选出最好一个解作为GTS的初始解。
1）贪婪算法
客户根据订单可得时间的非升序排列，从序列中的第一个客户开始，将其插入到每条路径的末尾，计算各条路径的完成时间（车辆可得时间与车辆行驶时间之和），选择造成最短完成时间的路径插入。在此过程中，需检验路径的可行性。若当一个客户插入到某条路径，而该条路径超出其容积限制，则令该路径的完成时间为一个极大值，从而避免选择该路径插入。贪婪算法的详细步骤见算法4-1：
算法4-1：贪婪算法
（1）设置客户集合 C =｛1，2，……， n ｝，路径集合 R =｛1，2，……， K ｝
（2）将集合 C 中的客户根据订单可得时间的非升序排列
（3）While（ C =！Ø）do
（4）选择集合 C 中的第一个客户 f
（5）计算客户 f 与每条路径 r∈R 中最后一个客户之间的行驶距离 tf_last
（6）If（路径 r 中的总订单大小＞车辆容积Q）
（7）令行驶距离 tf_last 为一个极大值M
（8）选择具有小的 tf_last 值的一条路径
（9）将客户 f 插入该路径的末尾
（10）将客户 f 从客户集合 C 中删除
（11）End while
（12）Return车辆行驶路径
2）节约算法
Clarke和Wright（1964）提出了用节约算法来解决有容积限制的车辆路径问题。该算法首先给每个客户安排一辆车，即每条路径只访问一个客户；然后计算任意两条路径中的点合并后的节约值， s ij = c i0 + c 0j -c ij ，其中， i 与 j 分别表示两条不同路径中的两个客户，0表示仓库即车辆出发点， c ij 表示两点之间的行驶成本， s ij 表示客户 i 与 j 在同一条路径中比在不同的路径中节约出来的行驶成本；再根据任意两点的节约值安排路径的访问顺序。在本问题中，用 t ij 取代 c ij ，即计算路径行驶时间的节约量。节约算法的具体流程见算法4-2。
算法4-2：节约算法
（1）设置变量 k =1，可用车辆数目为 K ；客户点集合 C =｛1，2，……， n ｝， S =｛ s ij ：i，j∈C ｝
（2）分别将 n 个客户安排到 n 条空路径中
（3）计算任意两个客户合并到一条路径后的节约值 s ij
（4）将所有的节约值 s ij 在集合 S 中按照降序排列；清空所有路径
（5）While（ S =！Ø）do
（6）从集合 S 中选择最大节约值 s ij
（7）If（车辆 k 装载客户 i 与 j 后的载量≤车容积Q）
（8）将客户点 i 与 j 加入路径X的末尾
（9）将包含点 i 或 j 的节约值 s ij 从集合 S 中删除
（10）Else
（11） X=X +1
（12）If（ X＞K ）
（13）Break；//终止while循环
（14）End while
（15）For（客户集合 C 中的每个客户点 c ）
（16）If（客户点 c 不在任何一条路径中）
（17）将客户点 c 加入具有最大剩余容积的路径中
（18）Return车辆行驶路径
3）随机算法
客户随机排列，从序列中的第一个客户开始，将其插入到每条路径的末尾，计算各条路径的完成时间（车辆可得时间与车辆行驶时间之和），选择造成最短完成时间的路径插入。在此过程中，需检验路径的可行性。若当一个客户插入到某条路径，而该条路径超出其容积限制，则令该路径的完成时间为一个极大值，从而避免选择该路径插入。
邻域解是指按照一定的规则对当前解进行一些改变得到的一系列解，改变包括点和边的移动等，每一种改变方式被称为一种邻域结构。Toth和Vigo（2003）提出为了缩减邻域解搜索的时间，一个邻域结构仅考虑那些可能带来较优解的移动，而摒弃那些可能带来不好的解的移动，例如某个移动中含有较长的边是被禁止的。这样的邻域结构被称为颗粒邻域结构（Granular Neighborhoods）。首先，在原问题的基础上考虑一个缩减的完全无向图 G ′ ，该图中只包含成本低于一定数值 v 的边。 v 的计算公式为 v=β×zn+K，z 表示初始解的值， n 表示客户数目， K 表示车辆数目。 β 是一个1.0～2.0之间的正数，其初始值设为1，若算法迭代到一定次数以后最优解没有得到更新，则可以增加 β 的值，拓展邻域结构。
本小节设计的四种邻域结构包括点的移动和边的交换，分别为1-0-exchange，1-1-exchange，1-1-arc-exchange与Piece-exchange，如图4-2所示。每一种移动方式都会产生新的边，图4-2中的虚线表示基于各种移动方式产生的新的边。在本问题中，当一种移动方式作用于当前解，若产生的新的边中至少有一条边是属于缩减图 G ′ 的，则接受该移动并生成相应的邻域解；若产生的新的边全部都是长边，即不属于缩减图 G ′ ，则不执行该移动且不产生邻域解。
图4-2 邻域结构
以下是对四种邻域结构的简单介绍：
1-0-exchange：从当前解的一条路径中随机选取一点插入剩余路径的任意位置。
1-1-exchange：从当前解的两条路径中各随机选取一点并交换位置。
1-1-arc-exchange：从当前解的两条路径中各随机选取一条边并交换位置。
Piece-exchange：从当前解的两条路径中各随机选取一个点作为切点，交换各切点到各自路径末尾的片段。
当生成新的邻域解后，需要检查其可行性。若该邻域解中有任意一条路径超出容积限制，则说明该邻域解非可行，并令该邻域解的目标值为一个极大值。否则，说明该邻域解为可行解，采取一种简单的策略来计算该邻域解的目标值，该策略仅计算当前解中发生变化的那个部分的成本。在本问题中，生成邻域解时，当前解有两个部分会发生改变，一部分是边的改变，即车辆行驶时间的改变，另一部分是车辆可得时间的改变。
令 f 表示邻域解目标值与当前解目标值之间的变化值， f 1 和 f 2 分别表示车辆行驶时间的变化量与车辆可得时间的变化量。 R k 表示当前解中车辆 k 的可得时间， R N k 表示新生成的邻域解中车辆 k 的可得时间。下面以按邻域结构1-0-exchange生成的一个邻域解为例来说明邻域解的计算方法。从图4-2（a）可以看出，客户点 i 从当前解中的路径 R 1 中移出并插入到另外一条路径 R 2 中的客户点 j 的后面，生成了一个相邻解，其计算公式为
该邻域解的计算方法只需计算发生改变的边与发生改变的车辆可得时间的变化值，再与当前解的目标值相减即可得到邻域解的目标值，传统的计算则需要计算所有的边与所有的车辆可得时间的值。显然，该策略相比传统的重新计算解的值节省了时间。
每一个邻域解都由一系列路径构成，每一条路径可以看作为一个旅行商问题（Traveling Salesman Problem，TSP），可采用局部搜索算法来优化车辆行驶路径，减少每辆车的路径行驶时间。在本章中，一种局部搜索算法“US算法”被用来优化车辆路径，为节省计算时间，该算法只对每一次迭代产生的最优邻域解进行优化。US算法最早被Gendreau et al.（1992）提出来优化TSP问题，通过预先规定的准则来重新排列单条路径中客户点的顺序，从而得到改进的解。其对初始解中已经形成的每条路径环路，将其中一个客户点（包括出发点）从路径中移除后按一定的规则重新连接路径中的客户点；再从新路径中与被移除的客户点较近的点中选择两个点，将该移除点插入到两点之间，再按一定的规则重新连接路径。Li et al.（2014）修改了标准的US算法，并将修改后的US算法用于解决库存—路径问题，本章采用该修改后的US算法来优化每一条车辆路径。修改后的US算法在本书中被称为“MUS算法”，其具体流程见算法4-3，与标准的US算法的不同在于：
（1）标准的US算法使用了两种类型的点的删除与插入方法，本书则仅使用其中的第一种，如图4-3和图4-4所示。
（2）标准的US算法中，插入点的两个相邻点是从该插入点的P个邻域点中随机选择的；本研究的算法中，插入点的两个相邻点则是直接选择与该插入点最近的两个点。
（3）当一条路径中的客户点的数目不超过7时，本书用全排列的算法来枚举，选择最好的排列；当超过7时，则采用MUS算法来优化。
图4-3 点的移除方式
图4-4 点的插入方式
算法4-3：MUS算法
（1）设置变量 t =1；路径中点的数目为 Nt
（2）While（ t≤m ）do
（3） i =0
（4）While（i＜ Nt ）do
（5） v i+1 是 v i 直接后点，找出点 v i+1 的 p 个相邻点，并从中随机选择一个点作为 v j
（6） v i-1 是 v i 直接前点，找出点 v i-1 的 p 个相邻点，并从中随机选择一个点作为 v k
（7）如图4-3所示，从当前路线中删除点 v i
（8）在新生成的路径中，找出与点 v i 最近的两个点 v m 和 v n
（9） v n+1 表示 v n 的直接后点，找出 v n+1 的 p 个相邻点，并随机选择一个点记为点 v p
（10）如图4-4所示，把点 v i 重新插入到当前线路中
（11） i=i +1
（12）End while
（13） t=t +1
（14）End while
禁忌列表是GTS算法的一个重要组成部分，里面存储了两类元素。一类元素是当前解中用于生成邻域解的两条路径的编号；另一类元素是该两条路径中被选中的插入点或交换点或切点。当生成一个邻域解时，需要检查该邻域解是否被禁忌。首先检查当前解中用于产生该邻域解的两条路径，若该两条路径在禁忌列表中，则再检查该两条路径中用于产生邻域解的交换点，若所有的点被禁忌，则该邻域解被禁忌；否则该邻域解没有被禁忌。
集中搜索与分散搜索也是GTS算法的两个重要准则。通过集中搜索，搜索过程可以集中在产生较好的解的区域；通过分散搜索，搜索过程可以跳出当前区域，到达另外的区域搜索。若当前解连续多次未能优于最优解时，意味着算法陷入了局部循环，此时需要采用分散搜索，通过随机生成新的当前解来跳出到另外一个搜索区域；其余情况下则采取集中搜索，每一次迭代中使用上一次产生的邻域解作为当前解，继续产生新的邻域解。
算法4-4详细介绍了颗粒禁忌算法流程，各个符号的含义定义为：Cur表示当前解；Best代表最优解；Non-Improvement表示最优解连续未更新的次数；Div表示执行分散操作的次数；Is-Better是一个判断条件。
算法4-4：GTS算法
（1）构造初始可行解 s
（2）初始化禁忌列表
（3）设置 Cur=s，Best=s，Div =0， Non-Improvement =0， Is-Better=false
（4）While（ Div ≤50） do
（5）以当前解 Cur 为基础生成一系列的邻域解
（6）选择最优的邻域解
（7）采取MUS算法优化该邻域解
（8）While（ Is-Better =false）do
（9）If（该邻域解没被禁忌）then
（10）If（该邻域解优于最优解）then
（11） Non-Improvement =0， Cur =该邻域解， Best =该邻域解， Is-Better =true
（12）清空禁忌列表（集中搜索）
（13）If（该邻域解劣于最优解）then
（14） Cur =该邻域解， Is-Better =true
（15）更新禁忌列表
（16） Non-Improvement=Non-Improvement +1
（17）If（Non-Improvement＞25）then
（18） Div=Div +1， Non-Improvement =0
（19）清空禁忌列表并随机生成新的解 s 1 （分散化）
（20） Cur=s 1
（21）If（该邻域解被禁忌）then
（22）If（该邻域解优于最优解）then
（23） Non-Improvement =0， Cur =该邻域解， Best =该邻域解， Is-Better =true
（24）清空禁忌列表（渴望准则）
（25）If（该邻域解劣于最优解）then
（26）寻找次优的邻域解作为选中的邻域解， Is-Better =false
（27）End while
（28）End while
（29）Return 最优解 Best