摘  要： 将蚁群优化和变邻域下降搜索VND相结合，形成一种混合启发式算法ACS_VND，应用于客运公司的汽车调度，求解车辆需求数和最佳路径。该算法充分利用了2种不同算法的优点。实验结果表明，算法ACS_VND能在较短时间内获得比单个算法更好的车辆调度路径。
关键词： 蚁群系统； 变邻域下降搜索； 车辆路径； 混合启发式算法

　　车站车辆路径问题是直接关系到客运汽车公司的效率与效益、服务质量和企业形象的关键问题，一直是运筹学、管理学、计算机科学等领域的研究热点问题，在生活中有着广泛的应用价值,如物流陪送、邮政投递、汽车、火车和飞机的调度等。对该类问题的研究主要集中在能否找到在较短的时间内给出较优解的算法。自1959年Dantzig^[1]提出这一问题以后，几十年来已取得了大量的成果。Dethloff[2]提出了带有参数的插入法，Crispim^[3]提出了基于禁忌的混合启发算法，但求解质量还有较大的改进空间。
蚁群优化ACO(Ant Colony Optimization)是一种基于群体的元启发算法，最初的灵感来源于真实的蚂蚁搜寻食物的行为^[4]，以信息素作为媒介，间接进行信息交换。变领域搜索VNS(Variable Neighborhood Search)最早由Hansen和Mladenovie^[5]提出，其核心思想是：领域对应搜索空间的拓扑特性，不同的领域结构对应搜索空间的不同区域。一般地，问题解空间中某个区域的特性不同于其他区域，因此，动态使用不同的领域结构能够增加解的多样性。变领域下降VND(Variable Neighborhood Descent)是VNS的一种变形，它通过一种确定的方式来改变领域结构的使用。蚁群优化属于群体基于群体的算法，而变领域下降搜索则是属于轨迹法。基于群体的元启发式算法的优势是善于发现搜索空间中可能存在最优解的区域，而轨迹法的优势在于善于探索搜索空间中较好的区域^[6]。因此，将二者结合可以充分利用各自的优势，提高算法的搜索性能和效率。本研究就是将二者进行结合，应用于客运公司汽车的调度。
1 车辆路径的描述
　　本研究利用有向带权图G描述车辆调度路径问题。假设G=(V，A，C)，其中，V={i|i=0,1,…,n}是顶点集(其中0表示车站调度中心，其他表示站点)；A={(i,j)|i, j∈V}是连接各顶点的弧集；C={c_ij|(i,j)∈A}是权重矩阵，c_ij表示从站点i到站点j的距离。任意站点i(i=1,2,…,n)都有一定的上车d_i与下车需求p_i。安排车辆为所有客户服务，要求满足以下条件并使得总行程长度最短：
(1)每辆车都从仓库出发，并最终返回仓库。
(2)每个客户都只被1辆车服务，且仅被服务1次。
(3)任1车辆在行程过程中，载重始终不能超过Q。
设s={r_i|i={1,2,…,k}}是问题的一个解，其中,r_i对应1条车辆路径。由上面问题描述要求可以知道，s作为问题的1个可行解的重要条件是：对任意r_i都满足以下条件：
(1)r_i上所有站点的总上车需求D(x)不超过Q。
(2)r_i上所有站点的总下车需求P(x)不超过Q。
(3)车辆承载ri上的任何客户之后人员都不超过Q。
若都满足条件(1)、(2)、(3)，则称s满足强可行条件，是强可行解；若都满足条件(1)、(2)，但不满足条件(3)，则称s满足弱可行性条件，是弱可行解。由Mosheiov^[7]已经证明，如果D(x)和P(x)都不超过车辆容量限制，则ri一定可以通过某种方式转化成可行路径。因此，若s是弱可行解，则一定可以通过某种方式转化为强可行解。
2 混合启发式算法ACS_VND
2.1 初始化信息素
　　首先使用最近邻启发式构造一个强可行解s0，并且根据τ₀=1/n·f(s0)设定信息素的初值,其中n是站点数量。则最近邻启发式算法构造解的步骤如下：
(1)从尚未访问的节点中选择距离调度中心最小的站点，开始一条新的车辆路径r。
(2)若V₀不为空，则从中选择距离r上最后1个站点最近的站点，作为下一个访问的节点；否则，转步骤(1)，直到所有站点都已经被访问。这里，将V₀定义为尚未被访问，且加入r后，使得r仍能约束强可行性条件的所有站点节点的集合。
2.2 构建可行解
由于弱可行性条件检查比较简单，因此在算法ACS_VND的构建阶段，首先产生一组弱可行解，然后转化成强可行解。在ACS_VND中应使用一种基于插入的启发式方法构造弱可行解。首先，从调度中心0出发，随机选择1个站点，开始1条新的路径r；然后，根据如下伪随机比例规则：

　　不断地从V1中选择站点，直到V₁为空，结束当前路径r的构造。若所有站点都已在当前解中，算法结束；否则，重新开始1条新的r并重复上述构造过程。为取得利用历史信息和随机选择之间的平衡，算法ACS_VND中动态调整q₀的大小，使其取值为q_max或q_min。
ACS_VND算法将弱可行解转化为强可行解的过程如下：从头到尾逐个扫描每1条路径r上的站点，若访问当前站点后r不能满足强可行性条件，则跳过当前站点扫描下一个；否则，继续扫描下一个；最后，按照逆序将在第1次扫描中被跳过的站点逐个重新加入r，即可得到1个强可行解。
在求解过程中，根据，利用构造的每一个解s进行局部信息素更新，其中，0＜ρ₁＜1是信息素的挥发系数，τ₀是信息素的初值。
2.3 变邻域下降搜索
变邻域下降搜索的基本步骤是：从初始解出发，选择一种邻域结构进行局部搜索，直到找到局部最优解。以当前局部最优解为初始解，使用另一种邻域结构继续进行局部搜索。当使用任何一种邻域结构都不能继续改进当前解时，结束VND过程。
在使用变邻域下降搜索之前，需要定义一组邻域结构。算法ACS_VND中分别使用3种求解VRP问题时常用的邻域结构：插入(insert)、交换(swap)和2-opt。
(1)插入(insert)
　

　　(2)交换(swap)
将解s中的站点i和j的位置互换(i和j可属于同一路径，也可属于不同路径)，产生新解。例如，解s=0-3-5-7-0-1-2-4-6-0，交换同一路径上的站点3与7，产生新解s′=0-7-5-3-0-1-2-4-6-0；解s=0-3-5-7-0-1-2-4-6-0，交换不同路径上的站点3与2，产生新解s′′=0-2-5-7-0-1-3-4-6-0。
(3)2-opt
解s同一路径上的2个站点i和j，在解s中的位置分别为p_i与p_j(p_i

_j）。2-opt是指将pi+1位置上的站点与j交换，并将p_i+1和站点j(不包括p_i+1位置上的站点和站点j）之间的节点按逆序访问。例如：解s=0-1-9-5-7-4-0-2-6-3-8-10-11-0，对2条路径分别通过2-opt优化后，得到新解s′=0-1-4-7-5-9-0-2-10-8-3-6-11-0。
2.4 搜索策略

3 实验结果与分析比较
以某长途汽车客运公司为实验对象，该运输公司有17个站点(包括14个途经站点和3个终点站)，车辆都是德国产欧洲之星，已知各站点上下车客户需求服务总量为k。为了验证混合启发式算法ACS_VND的性能，将它与单独使用ACS或 VND算法进行了比较。除了算法不同之外，其他实验样本和设置均相同，以保证实验不失一般性。实验结果如表1所示。其中，L表示最优解得到的车辆路径总长度；n表示所需车辆的台数。

　　本实验结合多种元启发方法的优点和策略，设计了更有效的混合启发式算法。结合蚁群系统ACS和变邻域下降搜索VDN，提出一种混合启发式算法ACS_VND。该混合算法充分利用了蚂群搜索的多样性和变邻域下降搜索有较强的局部寻优能力，提高了解的质量，加速了算法的收敛。

参考文献
[1]  DANTZIG G B, RAMSER J H. The truck dispatching problem. Manegement secience, 1959,6(1):80-91.
[2]  DETHLOFF J. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum,2001,23(1):79-96.
[3]  CRISPIM J, BRANDAO J. Metaheuristics applied to mixed  and simultaneous extensions of vehicle routing problems with backhauls. Journal of the Operational Research Society,2005,56(11):1296-1302.
[4]  DORIGO M, STUTZLE T. Ant colony optimization. Cambridge, Massachusetts, London, England： The MIT
Press, 2004.
[5]  HANSEN P, MLADENOVIE N. An introduction to variable   neighborhood search. Metaheuristic: Advanced and Trends in Loal Search Paradigms for Optimization. Boston: Kluwer  Academic Publishers, 1999: 433-458.
[6]  HANSEN P, MLADENOVIE N. Variable neighborhood search: principles and applications. European Journal of
 Operational Research, 2001,130(3):449-467.