葛金辉,沈晓奎,班允龙

(1.通化师范学院 数学系,吉林 通化134002;2.桂林理工大学)

1 问题提出

物流配送是物流业中一个重要的直接与消费者相连的环节，而车辆路径问题(Vehicle Routing Poblem， VRP)是物流系统优化的关键步骤，最早由Dantzig和Ramsen于1959年首次提出[1]，将其模型命名为“货车运输分派问题”，后来称为“车辆路径问题”，成为运筹学与组合优化领域的前沿与研究热点.基本车辆路径问题又称为闭合式车辆路径问题，简称车辆路径问题(VRP)，一般描述为：对一系列给定的客户(送货点或取货点)，确定适当的车辆行驶路线，使其从中心点出发，有序的完成任务，最后返回中心点，并在满足一定的约束条件下(如车辆容积、客户需求量、取送货限制等)使总运输成本(车辆数、行驶路程)达到最小.近十多年来，国内外专家学者对该问题及其求解方法进行了大量的理论研究和实验分析，取得很大进展，获得了一些富有成效的成果[2-5]，并将其广泛用于汽车运输、海上运输、航空运输、管道运输及通讯、电力、工业管理、计算机应用等领域.

本文针对车辆路径问题，设计动态禁忌结构，改进了禁忌搜索算法，仿真实验证明了算法的可行性和有效性.

2 禁忌搜索算法原理

禁忌搜索[6](Tabu search，简称TS)算法是一种扩展邻域、全局性逐步寻优的搜索算法，它模拟人类具有记忆功能的最优特征.1986年Glover最先提出禁忌搜索思想，是一种确定性的迭代优化算法，由于其搜索速度快，局部“爬山”能力强等优势，其主要步骤为：

(1)给定算法参数，随机产生初始解x，将禁忌表置空;

(2)判断终止条件是否满足?如满足，结束算法并输出最优结果;否则:

(3)利用当前解x的邻域函数产生其邻域解，从中确定候选解y;

(4)判断y是否满足藐视规则?满足则用此候选解y替代x成为当前解，并将y进禁忌表，同时替换“best so far”状态，转步骤(2)；否则:

(5)判断候选解的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时将其相应的禁忌对象进禁忌表;

(6)转步骤(2).

3 应用禁忌算法求解车辆路径问题

应用禁忌算法求解车辆路径问题主要包括算法中解的表示、初始解的形成、邻域结构、禁忌对象、禁忌长度、候选集合、终止准则及藐视准则等，本文在原有算法的基础上，以客户平均分配的方式形成初始解，双层操作构造邻域，设计了动态禁忌表等工作来提高整体寻优能力.

3.1 解的表示方法

对于一个有L个客户的车辆路径问题,这种解的表示法是直接产生L个1～L间的互不重复的自然数的排列，表示客户顺序，假设有N个客户，则产生2N个点，1～N则表示各个客户即实点，N+1～2N表示虚拟的配送中心即虚点，把它们都认为是配送中心，这2N个点的一个排列就是一个解，对于我们的解要求第一个数字必须大于N，也就是说第一个点必须是虚拟的配送中心，因为车辆要从配送中心出发.如5个客户的车辆路径问题，初始解可表达为7→4→5→6→10→2→8→9→3→1→11，该初始解表示为三条路径：配送中心→客户4→客户5→配送中心；配送中心→客户2→配送中心；配送中心→客户3→客户1→配送中心.并满足一定的限制，如车辆的容量限制等，这样，根据得到的解是否满足这些约束的要求可以把这些解分成两类，满足的就是可行解，不满足的就是不可行解，然后对于可行解计算路程，找出路程最短的配送方式.下面给出根据解的结构判断是否是可行解以及路程计算的具体方法.

(1)车辆数约束.按照最坏的情况打算就是为每一个客户配备一辆车，所以增加N个虚拟点，这样就产生了插入的虚拟点的上限，这是在没有车辆数约束的情况，如果限制了车辆数，例如有N个客户，有M辆车的时候，插入M个虚拟点，这样最多产生M条路径，有多少条路径，就是需要用多少辆车，这样需要车辆数不会大于现有车辆数，这就产生了插入的虚拟点的下限，插入的虚拟点的个数越接近上限就越有可能出现车辆不够用的情况，越接近下限，由于约束的过紧就越难产生初始解，这就需要根据具体情况酌情而定.

(2)载重能力约束.经过上一步，就可以计算出哪些客户是在一辆车上的，然后根据客户的需求量表计算总和，看是否超过了车辆的载重能力，如果超过了，说明这个解是不可行解.

(3)路程计算.针对提出的解的结构，相邻两个点之间的距离可以分为四类.

虚点→实点：在问题中能找到数据，标志着一条路径的开始.

虚点→虚点：规定距离为0.

实点→实点：在问题中能找到数据.

实点→虚点：在问题中能找到数据，标志着一条路径的结束.

根据上述规则可以算出一个解中任意两点的距离，再求和就是整个运输计划的距离了.

3.2 初始解的形成

一个好的初始解可以决定禁忌搜索空间，同时也可以加快搜索速度，但载重能力的约束是硬性的，就说明会有一部分不可行解产生，而且车辆数越少可行解就越少.因为后续的工作都依赖于这个可行的初始解，所以构造初始解的时候要尽量使其可行，本文采用把客户平均分配到每一辆车的方法构造初始解，若按此方法构造出的解不符合容量约束可人为稍加调整.

3.3 邻域结构

禁忌搜索算法是一种基于邻域搜索技术的算法，确定邻域操作方法是构造该算法的一个重要步骤，根据需要，设计了双层操作的方法，如图1.内层，依规律交换初始解中的两个点，遍历所有可能，收集一些比较好的可行解作为下一次邻域操作的候选集并禁忌本次的最优解.这里主要采用2-opt交换两个点.外层是在内层操作中得到的候选集中随机挑选一个解作为下一次邻域操作的初始解进行内层操作.内层操作中交换的这两个点有可能在同一条路径上，也有可能在不同的路径上，因而实现了路径间和路径内同时优化的策略.由于遍历所有可能，就可以使解尽量收敛.外层操作由于是在一些较好的解中随机挑选一个解进入下一次循环，这就使解可以发散，避免陷入局部最优解.双层操作既不会过于发散而使解不稳定，又不会过于收敛而陷入局部最优，统筹兼顾.

图1 双层结构

3.4 禁忌对象的确定

禁忌表是局部最优解的集合，禁忌表主要目的之一是阻止搜索过程中出现循环和避免陷入局部最优，之二是通过调整其大小使搜索发散或收敛.禁忌表是禁忌搜索算法的核心，其大小在很大程度上影响着搜索速度和解的质量.禁忌对象是指禁忌表中的元素，本文将每次迭代得到的最好解作为禁忌对象放入禁忌表中.

3.5 禁忌长度的确定

禁忌长度是指在搜索过程中禁忌对象在禁忌表中滞留的次数，为更好的联系实际、优化禁忌表的结构以及更好的控制解的收敛与发散程度，本文使用动态禁忌表，使每个禁忌对象在进入禁忌表时根据所处的阶段不同其禁忌长度也发生变化.其大小表示为：L=Lmin+[Lmax-In].

Lmin、Lmax表示禁忌长度的最小值、最大值，I表示解迭代次数，n为任意整数，意在调节禁忌长度改变的幅度，例如n=10时表示若最优解保持不变，每收索10次禁忌表长度缩小一次.

3.6 候选集合的确定

每次迭代后得到的较好的解的集合作为下次迭代的候选集，随机选取一个进行下次迭代.这里需要对“较好”做一下说明，把得到的解由好到次进行排列，可以取前几名的作为较好解，取的越多解越发散，取的越少解越收敛，具体取多少可根据数据的规模酌情而定.

3.7 终止准则的确定

当总迭代次数达到一个给定的值，或在一个给定的连续迭代步数内当前的最好解没有改变时，则算法终止.本文给定的步数为Lmax.

3.8 藐视准则

在禁忌搜索中，可能会出现候选解全部被禁忌的情况.藐视准则可使某状态解禁，以实现更高效的优化性能.本文采用的是基于适配值的藐视准则，如某个候选解被禁忌，但它的目标值优于“best so far”,则解禁此候选解并更新“best so far”.

4 实验计算和结果分析

为了进行比较采用文献[4]的数据进行实验，算法参数设定为Lmin=3，Lmax=50，n=10，并用MATHEMATICA编程求解.求得最小值为69，对应的路径分别为0→8→4→7→2→0和0→6→5→3→1→0.将改进禁忌算法与文献[4]中的有关算法如标准GA、双种群GA及改进PSO比较，如表1.表中结果可以看出，本文改进的禁忌搜索算法已经很接近混合PSO算法，并且优于双种群遗传算法、单亲遗传算法及改进交叉算子算法，得到了令人满意的结果.

表1 优化结果比较

用本文设计的禁忌搜索算法求解车辆路径问题，不仅可以得到质量较高的解，而且算法的收敛速度较快、计算效率较高，计算结果也较稳定，显示了良好的寻优性能，说明算法的有效性和可行性，若能设计更加合理的动态结构，将进一步改进解的质量对求解类似的组合优化问题有一定的理论意义和应用价值．

参考文献：

[1]Dantzig G B, Ramser K B. The truck dispatch problem[J].Operation Research,1959,12(1):80-91.

[2]Marius M.Solomon. Algorithms for the vehicle routing and scheduling Problems with time Window Constraints [J].Operations Research.1987.

[3]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用,2000,9 (3):235-239.

[4]赵燕伟,吴斌,蒋丽,等.车辆路径问题的双种群遗传算法求解方法[J].计算机集成制造系统,2004, 10(3):303-3061.

[5]李显生,赵鲁华,李文裴,等.城市配送车辆调度模型及算法设计[J].吉林大学学报:工学版,2006,36(4):618-621.

[6]郭科,陈聆,魏友华.最优化方法及其应用[M].北京:高等教育出版社,2007.

[7]张晓红,张建勋.数学软件与数学实验[M].北京:清华大学出版社,2004.

[8]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999.