禁忌搜索在车辆路径问题中的应用

摘 要：本文介绍了禁忌搜索算法的优点及其计算步骤，并用禁忌搜索求解了带时间窗的车辆路径问题(VRPTW)的两个算例，取得了很好的效果。 关键词：禁忌搜索算法；车辆路径问题；组合启发式算法 中图分类号：F502 文献标识码：A The Application of Tabu Search in the Vehicle Routing Problem WANG tao, CAI yan-guang, ZHANG xin-zheng (Guangdong University of Technology automation department, Guangzhou 510090, China) Abstract : This paper introduced the advance of Tabu Search and its computation step, solved two exam- ples of VRPTW by tabu search, has fulfilled successfully and got some meaningful results. Key words : modern logistics ;vehicle routing problem(VRP) ;heuristic algorithm 1 引言 虽然关于禁忌搜索的理论研究还没有得到明确的结论，但很多的计算实例表明，禁忌搜索与其他已有的技术和方法相比已经成为最突出的优化技术。不同领域的研究人员提出了很多种优化方法和技术，并使这些技术在不同的领域内得到应用。所有这些方法和技术都是基于一些相同的思想，同时具有一些独特的特点。在这些优化方法中，迭代技术起着重大的作用，对于绝大多数优化方法来说，没有一个方法能够直接的得到最优解。 禁忌搜索(tabu search)算法是局部搜索算法的推广，是人工智能在组合优化算法中的一个成功应用。Glover[1] 1986年首次提出这一概念，进而形成一套完整算法[2～3]。禁忌搜索算法的特点是使用了禁忌技术。所谓禁忌就是禁止重复前面搜索，为了回避局部邻域搜索陷入局部最优的不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。 2 禁忌搜索 在得到VRP问题的初始解后，利用禁忌搜索来对解进行改进，得到了较好的结果。针对定长禁忌算法搜索呆板的局限性和车辆调度问题的特点，本文提出了自适应的禁忌搜索算法改善了搜索过程。最后，利用改进的自适应禁忌搜索来降低了搜索的计算量和复杂度，并得到满意的解。 由上面的分析可以得到禁忌搜索的算法规则： step5更新禁忌表和特赦条件； step6如果满足中止条件停止搜索否则转到Step2． 禁忌搜索设计的主要内容包括：禁忌对象、候选集合的构成，多初始点的选择，评价函数的构造，禁忌长度，停止策略。 禁忌搜索具有局部搜索方法的优点：计算的复杂度比较低，由于它通过随机初始化和邻域搜索的方法逐步寻优，因此能够克服搜索空间指数增长的问题，适用于NP完全问题的求解。 同时采取禁忌规则，克服了局部搜索算法易于陷于局部最优点的缺陷，是求解组合优化问题的为数不多的有效算法之一。 3 禁忌搜索在VRP问题中的应用 车辆路径问题在工农业生产、交通、物流和资源配置等方面有着广泛的现实意义。该问题同时又是组合优化问题中的一个典型的NP-hard问题，著名的TSP问题是其一个特例。 对于规模较小的VRP问题，现已有一些如指定下界及相关分支定界法、动态规划和列产生算法等精确解法。对于规模较大的问题，启发式的应用较为广泛，如模拟褪火算法、遗传算法和禁忌搜索算法等。 禁忌搜索算法是解决VRP问题为数不多的有效算法之一。目前，TS算法已得到深入研究，并在调度领域、运输问题和神经网络等方面广泛应用。下面详细说明了用禁忌搜索来求解带时间窗的车辆路径问题(VRPTW)。 3．1 单用户插入(SPI)的搜索邻域 搜索邻域是禁忌搜索在动态改进解的过程中的搜索区域。本文中的禁忌搜索是基于路径的，通过路径间相互交换客户来得到邻域的解。将当前解inow中任一条路径的任一客户取出来插入到另 3．2 禁忌对象和禁忌表 禁忌搜索算法中禁忌对象指的是禁忌表中被禁忌的那些变化的元素。当一个客户可以处于某条路径中好几个位置时，它在同一条路径中位置变化对整个解的影响一般小于它从该路径中移出对整个解的影响。因此本算法中将客户在某个路径中作为禁忌对象，如果已将一客户从一条路径中移出，则在一定数目的迭代搜索中不允许将这一客户插回到该路径中，而不是文献[4]中将客户在路径中的位置作为禁忌对象。这样有助于减少算法设计的复杂性，并能同时提高算法的效率。 禁忌表采用一个二维数组TABU表示，它的行和列分别代表客户和路径。如果在第iterl步搜索过程中将客户i从路径j中移出，则此时有 TABU[i][j]：iterl，在此后的TABULENGTH(禁忌步长)步搜索中，将客户i插入到路径j中的操作被禁忌。如在第iter2步搜索过程中，要将客户i插入到路径j中，且此时有TABU[i][j]+TABU-LENGTH>iter2，这说明将客户i插入到路径j中的操作处于禁忌状态，这时不可执行将客户i插入到路径j中的插入操作。在任何时候，如果满足解禁条件，即执行插入操作后得到的解好于当前获得的最优解，不管该插入操作是否处于禁忌状态都执行该插入操作。 3．3 禁忌表长 禁忌表长是禁忌搜索中的一个关键因素，一般根据实际问题的不同而不同。表长过短会导致搜索过程中出现循环，表长过长会导致太多的禁忌，降低搜索的效率。根据实验经验一般当客户数目大于50，时禁忌步长取100，否则，禁忌步长取30。 3．4 r-opt方法 在求解VRPTW问题过程中，有很多种方法可以通过改变路径中客户的顺序来使得一条路径的代价进一步减小，其中最普遍和高效的一种方法是r-opt(r=2，3．．．．．；r指改换的边数)方法。 下面是r-opt的算法步骤： Stepl在该路径中删除r条边，从路径别的部分加上r条新的边，使得路径保持完整。如果这种改变使得路径的代价变小(如长度变短)，则保留改变，否则，通过删除添加不同的边来尝试别的改变。 Step2重复Step1。直到尝试了所有可能的改变，不能再使路径的代价得到改进为止，即陷入了局部最小点。此时退出，所得路径作为结果输出。 该算法中，r越大，功能越强，得到的解从理论上更接近最优解。但另一方面，r越大，尝试的改变次数越多，大大增加了计算时间，而且实际上r过大效果并不是很好，根据经验一般r取2或3，本文方法中取2。 3．5 VRPTW的组合启发式解法 本方法先用插入启发式算法得到VRPTW问题较好的初始解，然后利用禁忌搜索来对初始解进行改进；当通过SPI不能改进解时(此时的解可能是局部最小点)，使用2-opt来对解的每条路径进行优化，并根据优化的结果来判断此时的解是否是真的局部最小点；然后继续使用禁忌搜索算法来改进解，直到满足终止条件。 算法具体步骤如下： Step1用插入启发式算法得到VRPTW问题较好的初始解，并记为当前解和最优解。 Step2当前解路径间交换客户(SPI)得到当前解的领域。并选取最好的邻域解(执行SPI后得到的使目标函数下降最大的解)。 Step3根据禁忌表来评价当前解、最优解和最好的邻域解；根据评价结果更新禁忌表、当前解和最优解。 Step4如果不存在使目标函数下降的SPI，则对任一路径作随机2-opt操作，判断是否保留交换结果，固定尝试次数为y次；否则，执行Step2。 Step5如果在执行2-opt操作后，解没有变化，则终止搜索，输出结果，否则，执行Step2。 Step6 SteD2-Step5重复迭代h步。 3．6算例和计算结果 VRPTW问题有专门用于测试其算法有效性的Benchmark数据。为了检验本文算法的有效性，利用网站http：//w．cba．neu．edu/～msolomon/ problems．htm提供的Benchmark数据中具有代表性的rc201和c103两个算例来测试我们的组合算法。其中rc201有1个车库，100个客户，客户分布比较分散，时间窗没有规律；c103有1个车库，100个客户，客户分布比较集中，大部分客户的时间窗比较宽，少数的比较紧。 在pentium4 1．6G，内存128M环境下，用C语言实现本文中基于禁忌搜索的组合启发式算法，计算上面两个测试数据得到的结果如下表所示： 从表1结果中可以看出，采用本文方法所得的结果与最优解之间的差值很小(小于2)，所用的车辆数相同，同时该算法的计算时间较短，限制在1分钟内，具有较高的效率。 参考文献 [1] Glover F. Future Paths for Integer Programming and Links to Artificial Intelligence[J]. Computers and Operations Research, 1986, (13) :533～549. [2] Glover F. Tabu Search: part. ORSA Journal on Computing [J], 1989, (1) : 190- 206. [3] Glover F. Tabu Search: part. ORSA Journal on Computing [J], 1990, (2) :4-32. [4] William P. Nanry, J. Wesley Barns. Solving the pickup and delivery problem with time windows using reactive tabu search [J]. Transportation Research(part B) ,2000, (34) : 107～121.