张海军 ，徐廷学 ，逯 程 ，韩 玉

（1.海军航空大学，山东 烟台 264001；2.海军航空大学青岛校区，山东 青岛 266041）

0 引言

配送车辆的路径问题（Vehicle Routing Problem，VRP）是研究物流配送的关键，VRP一直是物流研究领域中的一个具有重要理论意义和现实意义的问题［1-2］。因此，在物流保障过程中，需要制定合理有效的配送路径，选择省时省力的方法，在完成保障任务的前提下，尽最大努力满足客户对配送的需求。

配送车辆的路径问题（Vehicle Routing Problem，VRP）是 Dantzig 和 Ramser［3］在 1959 年提出来的。所谓VRP，一般指的是：调用多辆车辆，从车场出发，对客户组织适当的行车路线，有序地访问所有客户并且只访问一次，在满足所有设定的约束条件下，力争实现所设定的目标。带容量约束的车辆路径问题（CVRP）是车辆路径问题（VRP）中的基本问题之一，广泛应用于资源配置和物流运输等方面。

求解CVRP的算法大致可以分为精确算法和启发式算法两类［4-5］。精确算法（Accurately Arithmetic）在求解规模较小的路径优化问题时能够在可承受的空间与时间消耗下得到精确解。但是配送路径优化问题属于NP问题，实际求解过程中问题的规模较大，使用精确算法所消耗的空间和时间成本都是比较大的。而启发式算法（Heuristics）不管是求解小规模的问题还是大规模的问题，都能够在一定的范围和较短的时间内给出满意解或最优解。因此，目前相关领域的专家以及研究人员对于求解算法的主要研究方向是启发式算法，特别是对现代启发式算法的研究。蚁群算法作为现代启发式算法之一，自从被提出之后就受到了广泛的关注，该算法具有正反馈性、并行性和鲁棒性等优点，在解决任务分配、路径优化等问题时表现出了良好的性能，但同时蚁群算法也存在一定的缺陷，如在解决大规模的问题时，会出现运算时间长、收敛速度慢、容易陷入局部最优解等问题［6］。本文在基本的蚁群算法基础上进行合理改进，提高了算法的性能，使算法的运算结果更加准确。首先，制定转移规则，更加科学地初始化车辆的位置，使得车辆有更大概率地走出最佳的路径；然后，在搜索的过程中与禁忌搜索算法结合，添加新的参数负信息素来记忆已经访问过的客户；同时，使用局部信息素更新和全局信息素更新相结合的信息素更新方式，并且，全局信息素更新添加了动态更新的新模式；最后，使用2-opt搜索［7］对结果进行进一步的探索，扩大搜索的范围，增加了得到最优解的概率。通过仿真实验，用不同的算法对已知案例进行仿真，结果显示本文算法相对于其他算法，无论是结果的准确性还是运算时间的长短都表现出了更好的性能。

1 问题描述及数学建模

CVRP是从同一车场出发的多辆车辆访问多个客户进行运送货物的问题。已知出发车场的位置以及需要访问的客户的位置，客户的数量以及需求数量，车辆的数量以及负载数量，对客户组织适当的行车路线，有序地访问所有客户并且只访问一次，在满足所有设定的约束条件下，力争实现所设定的目标（车辆所走的路径最短或者花费最少）。

将现实问题转化为数学模型，可以将CVRP描述为m辆车从车场0出发访问n位客户进行运送货物的问题。设di为客户i的需求数量，cij为车辆从客户i到客户j的运输花费，bk为车辆k的负载数量，而

求解CVRP是为了使车辆走出的总的路径最短［8-9］，从而令运输的成本J最小，即

且应满足以下约束条件：

式（3）表示所有车辆都从同一个车场出发，完成所担负的任务之后全部返回车场，每一辆车走出的路径都形成一个哈密尔顿巡回；式（4）和式（5）表示车辆要对所有客户进行服务，并且只能服务一次；式（6）表示每辆车服务客户时，自身的负载量不能低于被服务客户的总的需求量。

2 算法设计

2.1 蚁群算法求解CVRP

使用蚁群算法对CVRP进行求解时，蚂蚁会在各路径上产生信息素，信息素ij表示车辆k在对客户i服务完成之后，下一个客户j对车辆k产生的吸引程度。当车辆的负载量能够满足客户的需求时，车辆按照设定好的转移规则来选定客户。在选好所有客户形成回路之后，对各路径上的信息素实行更新策略，进而实现一次迭代。在迭代达到最大次数时，可以获得一个Pareto解集。跟其他的启发式算法相比，蚁群算法具有更高的机能，但在对CVRP的求解过程中还是会有一些不可避免的缺陷。

2.1.1 选取初始客户过程中的局限

在CVRP中，因为车辆都有一定的负载，访问多个客户要满足客户需求，而每辆车在访问客户时都会有货物量限制和访问先后的问题，所以求解CVRP受到选取初始客户的极大影响。运用蚁群算法求解CVRP时，初始化蚂蚁位置的方式有两种：1）全部放置方式。将所有蚂蚁全部放置于每个节点，这样搜索的范围会很大，更容易得到全局最优的解，但同时也将造成大量时间的消耗，在处理较大规模的CVRP时，会令问题更加复杂。2）随机放置方式。将部分蚂蚁随机放置到部分节点，这样做可以节省时间，降低问题的复杂程度，但是也容易造成得到的结果只是局部最优的，令每次迭代得到的Pareto解差距过大。

2.1.2 信息素更新过程的局限性。

随着算法的不断运算，寻找着最优路径，而信息素在路径上不停地累积，当前已寻找到的最优路径上的信息素越来越多，这或许会造成以下的不良后果：1）在当前已寻找到的最优路径上的信息素过多，造成算法的停滞。2）即便寻找到新的最优路径，这条路径上的信息素也远远没有之前得到的最优路径上的信息素多，几次迭代之后，这种现象也可能没有得到缓解。总之，在基本蚁群算法中，原有的信息素更新方式会导致信息素的分布不能很好地体现当前最优路径的变化，这会对算法的求解过程造成很大的影响。

2.2 算法改进

针对在求解CVRP时蚁群算法存在的缺陷，本文改进蚁群算法将提高其求解CVRP的性能。

2.2.1 转移概率的改进

为了降低算法的复杂程度，同时加强算法的精确程度，在算法选择初始客户的过程中，本文将蚁群算法和禁忌搜索进行融合，修正转移概率，以改进蚁群算法。将禁忌搜索融入蚁群算法主要是利用禁忌搜索长久的记忆能力来加强蚁群算法搜索的开拓性［10-12］。本文结合禁忌搜索记忆之前访问过的节点，加入了负信息素的概念：

当蚂蚁k处于节点i的位置时，根据以下规则选择下一节点：

2.2.2 信息素更新方式

针对蚁群算法在信息素更新过程中存在的问题，本文使用局部信息素更新和全局信息素更新相结合的信息素更新方式，并且，全局信息素更新添加了动态更新的新模式。

1）局部更新。在构建最优路径的过程中，蚂蚁每经过边（i，j）都会依照下面的信息素更新公式来更新这条边上的信息素：

其中，ρ1表示局部更新的挥发系数，表示信息素的初始值，是一个较小的正常量，可以设表示节点数，L表示生成的路径长度。引入信息素局部更新的目的，是为了使蚂蚁在经过边（i，j）时，会挥发这条边上一部分的信息素，降低其他的蚂蚁同样选择这条边的几率，可以更多地去探索其他的边，从而令算法的开拓性大大加强。

2）全局动态更新。当迭代一次完成后，按下式对此次迭代得到的最优路径上的信息素实行全局更新：

式（11）和式（12）可以依照每次迭代得到的最优路径的情况，对当前迭代所得的最优路径上的全局信息素进行动态调整。在x次迭代后，得到了一个最优路径，相比x-1次迭代，这条路径要短，L2和L1的差值就为正，说明当前迭代找到的最优路径比之前寻找到的要好，但此时该路径上的信息素浓度并不高，而根据式（12），L2和L1的差值越大，就会越大，在之后的迭代中，信息素浓度的积累就会越快；L2和L1的差值越小就会越小，在之后的迭代中，信息素浓度的积累就会越慢；如果在x次迭代后，得到的最优路径比L2要长，L2和L1的差值就为负，说明当前迭代找到的最优路径不如之前寻找到的好，而根据式（12），L2和L1的差值越大，就会越大，在之后的迭代中，信息素浓度就会加快挥发；L2和L1的差值越小，就会越小，在之后的迭代中，信息素浓度挥发的就会越慢。这种动态调整是为了让算法能够及时修正迭代得到的结果，引导算法可以更快地找到最优的路径。

2.2.3 局部搜索策略

为了能够增加算法的开拓性，本文在所有车辆对路径选择完成之后选用2-opt搜索作为局部搜索的策略，而2-opt搜索只用于一辆车所选择的路径之中。

2.3 算法步骤

根据以上描述的改进策略，改进后的算法步骤如下：

2）初始化车辆的位置。车辆按照式（8）选择客户，将所选择的客户添加到中，并更新的值。

3）路径选择。在满足车辆负载条件的前提下，车辆按照式（9）进行客户的选择；否则车辆返回车场。将所选择的客户或车场添加到中，更的值。

4）信息素的局部更新。每当车辆作出一次选择，便根据式（10）对刚刚走过的路径（i，j）进行信息素的局部更新。

5）2-opt局部搜索。当所有车辆服务客户完成之后，寻找路径完毕时，对每辆车所寻找到的路径进行2-opt搜索，并更新和；否则返回 3）。

3 仿真实例

在车辆路由公共数据集［13］中选择标准算例进行测试，使用Matlab进行编程，并在CPU为Intel（R）Core（TM）i5-4460 CPU@3.20 GHz 3.20 GHz，内存 8G的计算机上运行。实验参数设置为：ρ1=0.1，ρ=0.1，α=1，β=2，γ=1，e=15～30，r0=0.8～0.95，NC=40。

表1 求解各案例结果

表1显示出运用本文算法求解选择出来的这部分算例的结果，求解每个算例都运行10次。这里设B为数据集中目前已知的算例最优解，R为运用本文算法求解该案例得到的最优解，P为运用本文算法求解案例得到的最优解对比数据集中已知最优解B的偏移率。从表1可以看出，运用给本文算法求解从数据集中随机抽选的12个算例中，有7个案例的求解结果和数据集中已知最优解相同，而在剩下5个结果有所偏差的案例中，案例N200K17的偏移率最大，但是偏移率仅为2.67%。以上说明本文算法的性能是值得肯定的。

此外，从数据集中选择5个案例，运用本文算法与其他算法分别对案例进行求解，得出结果进行比较，表2显示了对比的结果。从表2可以看出，本文算法求解案例得到的最优解对比数据集中已知最优解的偏移率平均值为0.88%，与其他3种算法相比，仅高于HGA 0.03%。运用给本文算法求解从数据集中随机抽选的5个算例，有2个案例的求解结果和数据集中已知最优解相同。在求解运算的消耗时间方面，运用本文算法求解N51K5、N76K10所消耗的时间比SA要多一些，而求解另外3个案例的时间都是最短的，而且求解这5个案例所消耗的总时间最短，平均消耗时间也最短。

选择的5个案例，服务的车辆和被服务的客户数量都比较多，问题的规模都很大，在这几个大规模问题中，相对于其他3种算法，本文算法无论是运算结果还是花费的时间都体现出了更佳的性能，而且问题的规模越大，本文算法体现出的性能越好。

表2 各算法对案例求解对比

4 结论

本文首先对VRP问题的理论进行了研究，引出CVRP问题，并且对其进行了数学模型的建立，然后在基本蚁群算法的基础上，改进算法使其能更好地对所建模型进行求解，最后从数据集中抽取案例，运用改进后的算法进行求解，并与其他的算法进行比较，得出本文算法无论是运算结果还是花费的时间都体现出了更佳的性能和结论。