混合启发式算法在汽车调度中的运用

　　车站车辆路径问题是直接关系到客运汽车公司的效率与效益、服务质量和企业形象的关键问题，一直是运筹学、管理学、计算机科学等领域的研究热点问题，在生活中有着广泛的应用价值，对该类问题的研究主要集中在能否找到在较短的时间内给出较优解的算法。Dethloff提出了带有参数的插入法，Crispim提出了基于禁忌的混合启发算法，但求解质量还有较大的改进空间。

　　蚁群算法蚁群算法（ant colony optimization, ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

　　1 车辆路径的描述

　　本研究利用有向带权图G描述车辆调度路径问题。假设G=（V，A，C），其中，V={i|i=0,1,…，n}是顶点集；A={（i,j）|i, j∈V}是连接各顶点的弧集；C={cij|（i,j）∈A}是权重矩阵，cij表示从站点i到站点j的距离。任意站点i（i=1,2,…，n）都有一定的上车di与下车需求pi。满足以下条件并使得总行程长度短：

　　（1）每辆车都从仓库出发，并终返回仓库。

　　（2）每个客户都只被1辆车服务，且仅被服务1次。

　　（3）任1车辆在行程过程中，载重始终不能超过Q。

　　设s={ri|i={1,2,…，k}}是问题的一个解，其中，ri对应1条车辆路径。由上面问题描述要求可以知道，s作为问题的1个可行解的重要条件是：对任意ri都满足以下条件：

　　（1）ri上所有站点的总上车需求D（x）不超过Q。

　　（2）ri上所有站点的总下车需求P（x）不超过Q。

　　（3）车辆承载ri上的任何客户之后人员都不超过Q。

　　若都满足条件（1）、（2）、（3），则称s满足强可行条件，是强可行解；若都满足条件（1）、（2），但不满足条件（3），则称s满足弱可行性条件，是弱可行解。由Mosheiov[7]已经证明，如果D（x）和P（x）都不超过车辆容量限制，则ri一定可以通过某种方式转化成可行路径。

　　2 混合启发式算法ACS_VND

　　2.1 初始化信息素

　　首先使用近邻启发式构造一个强可行解s0，并且根据τ0=1/n·f（s0）设定信息素的初值，其中n是站点数量。则近邻启发式算法构造解的步骤如下：

　　（1）从尚未访问的节点中选择距离调度中心的站点，开始一条新的车辆路径r。

　　（2）若V0不为空，则从中选择距离r上1个站点近的站点，作为下一个访问的节点；否则，转步骤（1），直到所有站点都已经被访问。这里，将V0定义为尚未被访问，且加入r后，使得r仍能约束强可行性条件的所有站点节点的集合。

　　2.2 构建可行解

　　由于弱可行性条件检查比较简单，因此在算法ACS_VND的构建阶段，首先产生一组弱可行解，然后转化成强可行解。在ACS_VND中应使用一种基于插入的启发式方法构造弱可行解。首先，从调度中心0出发，随机选择1个站点，开始1条新的路径r；然后，根据如下伪随机比例规则：

　　不断地从V1中选择站点，直到V1为空，结束当前路径r的构造。若所有站点都已在当前解中，算法结束；否则，重新开始1条新的r并重复上述构造过程。为取得利用历史信息和随机选择之间的平衡，算法ACS_VND中动态调整q0的大小，使其取值为qmax或qmin。

　　ACS_VND算法将弱可行解转化为强可行解的过程如下：从头到尾逐个扫描每1条路径r上的站点，若访问当前站点后r不能满足强可行性条件，则跳过当前站点扫描下一个；否则，继续扫描下一个；，按照逆序将在第1次扫描中被跳过的站点逐个重新加入r。

　　在求解过程中，根据，利用构造的每一个解s进行局部信息素更新，其中，0＜ρ1＜1是信息素的挥发系数，τ0是信息素的初值。

　　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中的位置分别为pi与pj（pij）。2-opt是指将pi+1位置上的站点与j交换，并将pi+1和站点j（不包括pi+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。该混合算法充分利用了蚂群搜索的多样性和变邻域下降搜索有较强的局部寻优能力，提高了解的质量，加速了算法的收敛。