车辆路径问题(vehicle routing problem，VRP)是对车辆的运行线路进行合理规划与优化，在满足各种约束条件的情况下，使车辆以最小的费用通过所有装货点或卸货点^[1]。获取VRP问题的最优解具有重要的实用价值，能有效降低物流运输的成本。因此，VRP问题一直是运筹学、GIS网络分析研究中的热点问题之一。VRP是一个经典的NP(non-deterministic polynomial)问题，无法在多项式时间内获取精确解，且随着客户点数的增加，可选车辆路径方案数量和求解时间均呈几何级数式增长^[2]。随着实际应用中VRP规模的不断扩大，传统的串行算法已无法满足大规模地理网络VRP问题的求解需要。

而并行技术能够充分利用多核、多CPU、GPU、PC集群、大规模并行计算机等提供的高性能计算能力，大幅提高地理运算的效率^{[3, 4, 5, 6]}。国内外学者应用不同的并行策略对VRP算法进行了深入的研究。文献^{[7, 8]}基于迭代局部搜索框架和禁忌搜索算法，设计了并行VRP算法；文献^[9]应用客户点集分割的策略，发展了一种结合局部搜索与整数规划的并行算法；文献^[10]将多种不同的邻域结构融入禁忌搜索过程，提出多邻域协作并行VRP算法；文献^[11]设计了自适应大邻域局部搜索算法；文献^[12]提出了基于双禁忌对象的并行禁忌搜索算法。但上述并行VRP算法多以大规模并行服务器(计算节点数>128)为基础，针对基于PC集群的并行VRP算法研究较少。PC集群成本低廉，易于搭建与维护，是应用最为广泛的并行算法运行平台。但与大规模并行硬件环境相比，PC集群存在着计算节点内存小、通信速度慢等问题。为此，本文拟以PC集群环境为基础，设计分布式数据存储结构，以降低算法对内存的需求量，并采用邻域分解策略实现VRP算法的并行化，通过精简通信数据结构降低计算节点间的通信开销，进而提高PC集群环境中求解大规模地理网络VRP问题的效率。

2 并行地理网络VRP算法

2.1 地理网络VRP算法流程

求解VRP时，需要反复用到网络节点(包括客户点和车场点)中任意两点间的距离。图论中，网络节点间的距离多采用欧氏距离^[13],见图 1(a)，计算简单快捷，无须设计相应的矩阵进行存储。而地理网络中，网络节点间距离多采用节点间最短路径的距离值，见图 1(b)。由于最短路径求解用时远多于欧氏距离的计算耗时，因此，地理网络VRP求解过程中需建立网络节点间的距离矩阵，即origin-destination(OD)矩阵。随着地理网络规模的扩大，OD矩阵所需存储空间将呈指数形式增长，从而导致PC集群各计算节点出现内存不足的问题。因此，需采用分布式存储结构，以减少OD矩阵对内存的占用量。在获取OD矩阵的基础上，应用随机法产生初始解，采用邻域分解策略对VRP迭代优化过程进行并行化，以获取客户点序号编码，即VRP问题的解。最后，为了获取实际的运输路径，需将客户点序号编码转换为车辆的实际运送路径。地理网络VRP问题的求解流程如图 2所示。

图 1 VRP中的距离值 Fig. 1 Distance in VRP

图选项

图 2 地理网络VRP求解流程 Fig. 2 Procedure of solving VRP in geographical network

图选项

OD矩阵包括距离矩阵D和前趋矩阵P两部分：前者记录了任意两节点间的最短距离；后者记录了任意两节点间的最短路径。它们均是地理网络VRP求解的基础。假设c为客户点数，w为车场数，n为网络节点数，则矩阵D的大小为(c+w)×(c+w)，矩阵P的大小为(c+w)×n。通常网络节点数n远大于c，因此P远大于D。以网络节点数n=200 000，客户点数c=3000，车场数w=1的VRP问题为例，假设每个矩阵元素占4 Byte，OD矩阵将占用大约2.4 GB的内存空间。若不对OD矩阵的存储方式进行优化处理，很容易出现各计算节点内存不足的问题。此外，OD矩阵的计算也是VRP求解过程中耗时最多的环节。笔者利用ArcGIS提供的VRP分析工具，使用试验数据(网络节点数为100 703个，边数为124 164条，车场个数为1，客户点数为1000个，车辆数为10辆)测试了OD矩阵计算用时占算法整体时间的比重。结果表明：OD矩阵计算耗时占VRP算法总用时的65%，是VRP算法中耗时最多的环节之一。因此，降低OD矩阵的存储开销、减少OD矩阵的计算用时对保证VRP算法的稳健性和高效性具有重要意义。

为了降低OD矩阵的内存开销，本文采用了分布式存储的策略。矩阵D占用内存空间较小，且为后续禁忌搜索过程的基础，因此各进程均存储完整的D；而矩阵P十分庞大，且仅用于后续的路径转换过程，因而将其分布式存储于各进程中。通过这种策略，单进程内存开销近似减少为原来的1/p(p为进程数)。同时，为了提高OD矩阵的计算效率，引入并行Johnson算法来获取各客户点及车场点间的最短路径。具体实现过程如下：首先，将c+w个源点(包括客户点和车场点)平均分配至p个进程，每个进程分别计算(c+w)/p个源点的最短路径，得到部分D和P；然后，应用讯息传递接口(message passing interface，MPI)中的Allgather函数对D进行同步操作，使得各进程均获得完整的矩阵D，如图 3所示(以4进程为例)。通过分布式存储策略和并行Johnson算法，OD矩阵计算过程的时间复杂度降低为O(cn logn/p)，空间复杂度降低为O(cn/p)。由此可以看出，随着进程数的增加，该算法能够处理更大规模的OD矩阵，具有很强的扩展性。

图 3 DM矩阵的同步方法 Fig. 3 Synchronizing of distance matrix

图选项

VRP问题无法在多项式时间内获得精确解，因此多采用启发式算法来求解^[14]。禁忌搜索算法是一种常用的启发式算法，是解决组合优化问题行之有效的方法^[15]。该算法采用一定的藐视准则使搜索过程跳出局部最优解，从而提高了获得全局最优解的可能性^[16]。国内外大量研究成果表明，禁忌搜索算法是解决VRP问题的有效途径，具有求解效率高、解质量稳定等优点^{[17, 18, 19, 20, 21, 22, 23]}。因此，本文拟对串行禁忌搜索算法进行并行化，来完成VRP问题的求解。

禁忌搜索算法的实现流程如图 4所示。首先，采用随机法(辅以最低成本增加法)构建若干初始解，选取目标函数值最小的解作为当前解S和最优解S^*。然后利用迭代邻域搜索对最优解进行优化，具体过程如下：①利用随机交换法和插入法得到S的邻域；②从邻域中搜索目标函数值最小的解S′，判断其是否满足特赦准则,若满足则用该解更新最优解S^*，否则判断其禁忌属性,若未被禁忌则用该解更新当前解S,否则继续搜索邻域中其他解；③更新禁忌表，判断是否满足终止条件。当该迭代过程达到终止条件后，即得到最终解S^*。从禁忌搜索算法的实现过程可以看出，由于禁忌准则的使用，各次迭代间具有内在的关联性。若采用任务划分的方式进行并行化，会破坏禁忌搜索机制，从而影响最终的求解质量。因此，本文采用细粒度的并行方式，对邻域搜索过程进行并行化。具体实现过程如下：首先，将待搜索邻域中的N个邻解平均分配至p个进程，各进程分别搜索N/p个邻域解得到局部最优解；然后，由主进程回收各进程的局部最优解，比较得到全局最优解后再广播给各进程；最后，各进程根据邻域搜索获得的最优解更新当前解、最优解和禁忌表。在解的迭代优化过程中，邻域搜索过程耗时最多，通过对该过程的并行化可以有效提高禁忌搜索的效率。

图 4 禁忌搜索算法流程 Fig. 4 Flow chart of tabu search

图选项

在并行邻域搜索过程中，各进程需要频繁地进行数据交换。若采用发送解编码的方式进行同步，一次迭代中的通信量将达到2s个整型值(s为解编码长度，约等于客户点数)，会产生大量的通信开销。为此，本文引入一种新的通信模式。为了减少通信量，采用发送解编码变换规则的方式，无须发送完整的解编码。与解编码相比，编码变换规则的长度仅为8个整型，大幅降低了通信量，提高了进程间的通信效率。具体实现步骤如下：①各从进程发送局部最优解的目标函数值至主进程(通信量为1个整型)；②主进程进行比较后得到全局最优值，并将该值对应的解所在进程编号广播给各进程(通信量为1个整型)；③由包含最优解的进程向其他各进程广播最优解的编码变换规则(通信量为8个整型)。由此过程可以看出，每次邻域搜索的通信量为10个整型数据。解编码变换规则可用向量T(含8个整型)表示

为了验证算法的有效性和正确性，本文利用模拟的路网数据进行了相关试验。试验环境为两台双核计算机(CPU为Intel Core i3-530，内存为3.24 GB)和一台四核计算机(CPU为Intel Core i5-2400，内存为3.24 GB)组成的Windows PC集群，最多可运行8个进程。消息传递接口采用MPICH2。试验数据为6个人工生成的测试数据集，如表 1所示。试验均将车辆数(等价于距离约束)和每辆车的容量设为约束条件，以配送路径长度总和为目标函数值。客户点和车场点均从网络节点中随机选取。

为了验证VRP并行策略的可行性，分别统计了串行VRP算法中各计算环节的耗时情况。由于禁忌搜索算法是启发式算法，每次的运行结果略有不同，取10次运行结果的平均值作为最终结果。测试结果如表 2和图 5所示。其中，OD项表示OD矩阵计算时间；TS项表示禁忌搜索时间；其他项表示数据读取、预处理等过程所消耗的时间。

图 5 串行VRP算法各部分耗时比重 Fig. 5 Time consumption of each procedure in serial VRP algorithm

图选项

表 2中，采用单进程进行VRP求解时，由于计算过程均放在一个计算节点内执行，未进行数据的分布式存储，导致测试数据集6出现内存不足的问题，无法求出最终结果。其他测试结果表明，OD计算耗时占算法总用时的比重在14.1%~60.0%之间，TS计算过程用时占算法总用时的比重在30.2%~85.4%之间；OD矩阵计算和TS过程用时总和占算法总用时的比重在90.2%~99.5%之间。因此，对VRP算法中的OD矩阵计算和TS搜索过程进行并行化，能有效提高VRP算法的整体性能。

为了进一步分析分布式存储策略对内存使用的影响，以测试数据6为例，分别测试了采用不同进程数时OD矩阵计算过程的内存消耗情况。采用单进程时，由于无法发挥分布式存储策略的作用，VRP求解过程中出现了内存不足的现象。因此，本文仅测试采用2～8个进程时，OD矩阵计算的内存使用情况，如图 6所示。结果表明：采用两个进程时，每个进程的内存开销约为1.2 GB；随着进程数的增加，单进程的内存消耗量逐步降低；采用8个进程时，每个进程的内存开销减少为约0.35 GB。尽管采用8个进程时的总内存消耗量与单进程时基本一致，但是分布式的存储机制充分利用了PC集群中各节点的内存资源，从而有效避免了单节点内存消耗过大的问题。

图 6 OD矩阵计算的内存开销情况 Fig. 6 Per-process memory consumption of OD matrix computing

图选项

为了测试并行OD矩阵计算过程的效率，应用测试数据进行了相关试验，结果如表 3所示。由表 3可知：随着参与运算的进程数的增加，OD矩阵计算用时在各测试数据中均出现了明显的加速效果。采用两个进程时，算法在各测试数据中的加速比(算法单进程运行时间与多进程运行时间的比值)均在1.81 以上；采用8个进程时，算法加速比均在4.63以上。为了更直观地表示算法时间与进程之间的关系，依据所用进程数和算法运行时间绘制了二者的关系曲线，如图 7所示。由图可见，随着进程数的增加，算法耗时呈下降趋势，加速效果明显。

图 7 并行OD矩阵计算的运行时间 Fig. 7 Running time of parallel OD matrix computing

图选项

禁忌搜索中的邻域大小直接影响求解的质量和效率。经大量试验得出：邻域大小为(c+w)²/200(c+w为客户点数和车场数之和)时效果最佳；此时，VRP算法能够兼顾计算效率和解质量。并行禁忌搜索过程的运行时间如表 4所示。表 4表明：随着进程数的增加，并行禁忌搜索耗时总体呈下降趋势。在禁忌搜索过程中，新解的生成采用了一些随机方法，以保证解的多样性。这使得生成新解的时间不稳定，导致整个邻域搜索过程的时间出现波动。因此，表 4中测试数据1、2、3、5在多进程计算时，出现了超加速比的情况(表中用黑体表示)；在进程数为7和8时产生了耗时波动情况。根据禁忌搜索耗时和进程数的关系绘制它们之间的关系曲线，如图 8所示。由图可见，测试数据1和4、2和5、3和6的曲线基本重合。该结果表明：在不同规模的测试数据中，禁忌搜索的时间主要取决于客户点的数量，与网络规模无关。

图 8 并行禁忌搜索的运行时间 Fig. 8 Running time of parallel VRP algorithm

图选项

为了对算法的整体效率进行评价，对算法的总用时情况进行统计，结果如表 5和图 9所示。随着进程数的增加，算法的运行时间均呈明显的下降趋势。在测试数据3中的运行时间由单进程时的603.6 s减少为8进程时的95.42 s；采用7～8个进程时，在各测试数据中的算法加速比均在4.46～6.32之间。由此可见，采用并行技术能有效提高算法的运算效率。某些试验结果出现了超加速比的现象(表中用黑体表示)，其原因在3.4节中已阐述。

图 9 并行VRP算法的运行时间 Fig. 9 Running time of parallel VRP algorithm

图选项

为了验证计算结果的正确性，本文将算法的运行结果与ArcGIS进行了对比。首先，将测试数据导入ArcGIS中，用ArcGIS的VRP分析工具求出运输路径的目标函数值。结果如表 6所示，测试数据1—6的目标函数值见栏目“ArcGIS结果”。然后，将本文算法的计算结果与上述结果进行比较，用偏差率表示其差异性

针对图论VRP问题的并行算法已有较多研究成果，但是在地理网络VRP中的实际应用以及针对特定并行环境的算法中，还有很多问题需要解决。本文提出的基于PC集群环境的并行VRP算法，通过分布式存储结构充分利用集群的内存资源，有效避免了求解地理网络VRP时单节点内存不足的问题；同时，采用精简的通信策略以及基于邻域分解的并行禁忌搜索算法，大幅提升了计算效率。基于模拟路网数据的相关试验表明：本文算法能够在保证计算精度的前提下(平均偏差率在2.11%～2.87%之间)高效地求解大规模地理网络VRP问题，且具有良好的扩展性；同时能够在PC集群环境中获得良好的加速性能，采用8个进程时的算法加速比在4.46～6.32之间。此外，本文研究着重于PC集群环境下的并行化方法，核心的求解算法仅采用了基本的禁忌搜索。因此，在求解质量方面本文算法还有很大的提升空间。下一步研究工作将引入更高级的策略对禁忌搜索过程进行优化，进一步提升求解质量。