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

本文参考期刊论文信息如下:

"The Tree Representation for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading", Yongquan Li, Andrew Lim, Wee-Chong Oon, Hu Qin*, Dejian Tu, European Journal of Operational Research, Volume 212, Issue 3, 1 August 2011, Pages 482-496.

欲下载本文的C++源代码，请移步留言区。

一

什么是考虑后进先出的取派货旅行商问题？（the Pickup and Delivery Traveling Salesman Problem with LIFO Loading）

考虑后进先出的取派货旅行商问题是旅行商问题的一个变种，它可以描述为：假设车辆从起点（depot）出发去完成所有任务，每个任务分别对应着一个位于不同地理位置的取货点和派货点,需要制定一条路线来保证总费用最小。其中，从起点出发提供服务的车辆只有一辆；车辆必须先到达取货点获得货物才能去派货点；车辆装卸货时必须服从后进先出原则。要处理现实情况中的问题，首先要将其转化为对应的数学模型，然后研究模型，对所建立的模型进行求解。

给出的完全无向连通图G=(V,E,d)中，点的集合表示为V=P∪D∪{0+,0-},边的集合表示为E={(x,y):x≠y∈V}，d(x,y)表示点x和点y之间的距离。其中点0+和点0-表示起点，P={1+,...,n+}表示取货点集合，D={1-,...,n-}表示送货点集合。车辆的速度为单位速度（即从点x到点y的时间在数值上与其欧式距离dij相等）。车辆必须从位置0+开始并回到位置0-。车辆装卸货时必须服从后进先出原则。

关于基础旅行商问题的上述相关内容在之前的推文中已有详细的介绍，分别从旅行商问题的发展由来、对应算法和详细的实验结论三个角度给大家一一做了讲解，使大家对旅行商问题有全方位的理解。下面给出两篇旅行商问题推文的链接：干货|十分钟教你用动态规划算法解Travelling Salesman Problem（TSP）问题，附代码……、运筹学教学|分枝定界求解旅行商问题

二

变邻域搜索算法（VNS）

① 什么是变邻域搜索算法？

变邻域搜索是由Mladenović Hansen于1997年提出的，它是一个用来求解组合优化以及全局优化问题的元启发式（meta-heuristic）搜索算法。变邻域搜索主要是利用多个邻域结构对当前解进行搜索，让特定的目标函数值逐步优化。它分为两个阶段，即变领域下降阶段（variable neighborhood descent）和扰动阶段（shaking phase）,这两个阶段都会改变搜索的邻域。

迄今为止，变邻域搜索在解决整数规划问题、混合整数规划问题和非线性规划等问题中取得了很大的成功。变邻域搜索能应用到许多领域，并且正在迅速增多，例如选址问题、调度问题、车辆路径优化问题、网络通信设计、聚类分析、人工智能、可靠性、几何问题、统筹问题等等。

② 变邻域搜索算法

在介绍变邻域搜索算法之前，有必要先给大家简单介绍一下局部搜索算法，使大家充分地了解变邻域搜索算法的发展历程。

局部搜索算法

局部搜索算法是通过选择一个初始解x，每次从x的邻域N（x）中选择一个比当前解优且是最好的邻居作为下一次迭代的当前解，直到找到问题的局部最优解。如果没有比当前解好的邻居，则搜索停止；否则，继续迭代。上述规则如下图所示，我们假定初始解x，输出为用x表示的局部最优解。

观察到邻域N（x）定义为所有x∈X，即在每次迭代中需要搜索x的完整邻域N（x）。对于大的算例来说这个过程过于耗费时间，另一种方法是直接选取搜索过程中第一个出现有改进的解。上述规则如下图所示，我们假定初始解x，输出为用x表示的第一个改进解。

变邻域搜索算法

变邻域搜索是一种元启发式算法，在解下降到局部最优和跳出局部最优过程中不断改变邻域。变邻域搜索是建立在以下定理之上：

1.一个邻域中的局部最小值不一定是另一个邻域中的局部最小值；

2.全局最优值即为所有可能存在的邻域中的局部最小值；

3. 对于许多问题，不同邻域中的局部极小值比较接近。

变邻域搜索算法结合了邻域的确定性和随机变化。具体步骤于如上图所示。在步骤4中，为了避免循环情况发生，采用随机的方法来产生解x。

在步骤5中，通常采用取第一个改进解策略的局部搜索算法[function FirstImprovement(x)],取搜索到的第一个改进解更新当前解，解对应的解空间也随之改变。然而，也可以用取最好改进解策略的局部搜索算法[Function BestImprovement(x)]来代替它。

在步骤6中，改动邻域函数[Function NeighborhoodChange(x,x',k)]的具体步骤如下图所示。将从第k代邻域中得到的新目标函数值f(x')与原值f(x)进行比较，如果有改进，则将x更新为x'并初始化邻域；否则更新邻域。

当变邻域搜索找不到很好的解时，在搜索过程中调整以下几个部分可以起到帮助作用，如在局部搜索中比较采取改进最多解和第一个改进解的策略、缩减邻域、加剧抖动和试验参数设置。

与许多其他的启发式相比，变邻域搜索对于基本格式的要求很少，而且有时不需要设置参数。因此，变邻域搜索除了能提供很好的解之外，往往比其他方法更简单有效。

欲了解更多变邻域搜索算法的技术细节，请参考下面的文献:

1. Hansen, P.; Mladenovic, N.; Perez, J.A.M. (2010). "Variable neighbourhood search: methods and applications". Annals of Operations Research. 175: 367–407.

2. Nenad Mladenovi´c, Pierre Hansen (1997). "Variable neighborhood search". Computers and Operations Research. 24 (11): 1097–1100.

3. Gendreau, M.; Potvin, J-Y. (2010). "Handbook of Metaheuristics". Springer.

4. Glover, F.; Kochenberger, G.A. (2003). "Handbook of Metaheuristics". Kluwer Academic Publishers.

三

使用树表示法的变邻域搜索算法求解考虑后进先出的取派货旅行商问题

旅行商问题中解的编码方式一般采用自然数编码并使用数组进行存储，如下图所示。此种存储结构的优点是清晰易懂且解码过程简单，但在进行移动或遍历等操作时具有时间复杂度高的缺点（即操作耗时多）。

本文采用树结构来存储解，如下图（a）所示。此种存储结构虽然看起来有些繁琐难懂，但是便于进行移动和遍历操作。解码过程如下图（b）所示，即从顶点0处对树中叶子节点进行遍历和递归。将树转换为可行解及其逆过程的算法复杂度仅为O(n),其中n是节点的个数（即线性时间）。

与数组存储方式相比，树表示法主要有以下优点：

节点序列表示的解与树表示的解释呈一一对应的关系，树形结构可以自动保证解的可行性，而节点序列表示的解不一定是可行解；基于树形表示方式，在用算子进行操作时不需要检验新生成解的可行性，节省计算时间；如果用节点序列来表示解，一旦采用交换节点的邻域搜索算子，生成的新解极有可能违反先进后出的约束；基于树形表示方式的算子实现过程简单且更直接，大量与树相关的算子可以被使用。

TSP问题是经典的NP完全问题。精确的解决TSP问题的算法复杂度为O(2n), 其中n是节点的个数。而TSPPDL在基础的TSP问题上加了约束，其复杂度远远高于原问题。

四

伪码

本文参照文献编写代码，伪码如下图所示：

算法大体框架采用变邻域搜索和遗传算法结合。关于遗传算法的相关内容已在之前的推文中出现，给出链接：干货 | 嘿！你和遗传算法的距离也许只差这一文(附C++代码和详细代码注释)

算法的主要步骤为：步骤1，设置最大迭代次数max_iter、最大无改进迭代次数max_nonimproving、种群大小pop_size等参数；步骤2，新建大小为pop_size的种群population（即新建大小为pop_size的数组）；步骤3，初始化当前最好解S_best；步骤6-8，初始化种群population（即将个体S_best执行pop_size次扰动操作）；步骤10-18，对种群population的每个个体使用局部搜索算子、ATSP算子、交叉算子crossover进行搜索（具体算子描述见下文）；函数local_search()使用了5种邻域搜索算子，就是前文提到的Variable neighborhood Descent阶段；步骤19-24，更新当前解S_current和全局最好解S_best；步骤25-27，对种群population使用扰动算子perturbation进行一定的扰动（具体算子描述见下文）。

其中，函数local_search()共采用5种搜索算子：

1.子树移位算子：随机删除原树中的一棵子树，遍历插入到树中的任意节点下，邻域为所有子树移位可能得到的解的集合。如下图所示，图（a）、（b）分别为初始解和经过子树移位后的解。

2.子树交换算子：随机选择原树中的两棵子树并交换他们的位置。邻域为子树交换算子完全遍历能得到的解的集合。如下图所示，图（a）、（b）分别为初始解和经过子树交换后的解。

3.节点移位算子：随机删除原树中的一个节点，遍历插入到树中的任意节点下。邻域为节点移位算子完全遍历能得到的解的集合。如下图所示，图（a）为初始解，删除节点x后将其作为节点0的子节点可以有4种情况，即如图(c),(d),(e)和(f)。

4.节点交换算子：随机选择原树中的两个节点并交换它们的位置。如下图所示，图（a）、（b）分别为初始解和经过节点交换后的解。

5.混合移位算子：随机删除原树中的若节点，随机插入到树中的任意位置。

ATSP算子：随机选择原树中的一个节点，如果此节点的子节点数目小于8，则使用穷举法优化子节点服务顺序；否则使用RAI算法进行搜索（即从此节点的子节点集合中随机踢出若干节点，再使用贪婪算法进行插入）。下图（a）、（b）和（c）给出如何将调整子节点顺序的问题转化为一个非对称的TSP问题（Asymmetric TSP，简称ATSP）。

交叉算子crossover：随机删除原树T1中的一棵子树Ts，然后根据树T2中的父子关系将删除子树Ts中的节点以贪婪的规则插回到原树T1中。如下图所示，图（a）、（b）、（c）、（d）、（e）和（f）分别为原树T1、树T2、删除子树Ts之后的T1和Ts中节点以贪婪的规则逐步插回而生成的新解。

扰动算子perturbation：随机删除原树T1中的一棵子树，然后利用贪婪算法将删除子树中的节点插回到原树T1中。