基于优化蚁群算法的多配送中心车辆路径研究

黄玉文

摘要：为了提高多配送中心车辆调度效率，该文提出了一种基于优化蚁群算法的的多配送中心车辆路径调度算法。优化算法通过对信息素挥发因子、启发式因子，信息素强度初始值的够造，消除参数选择对蚁群算法性能的影响，使其具有较强的全局搜索能力。实验表明，该文提出的基于优化蚁群算法的多配送中心车辆路径算法比其余算法有更好的实验效果。

关键词：蚁群算法，遗传算法；多配送中心；车辆路径优化

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）15-0190-02

Abstract：In order to improve the the efficiency of the multiple depots vehicle routing， a new method of the improved genetic algorithm for the multiple depots vehicle routing isproposed. The improved algorithm eliminates the influence of the selected parameter by optimizingthe heuristic factor， evaporation factor， initial pheromone distribute， and have the strong globalsearching ability. The experiments demonstrate that the solving results of the improved algorithm is more excellent than the other algorithm

Key words： ant colony algorithm； genetic algorithm； multiple depots； vehicle routingoptimization

当前，随着电子商务的快速兴起，物流业在市场经济中占有越来越重要的地位，引起国家的高度重视和越来越多的企业的关注，物流服务业在国民经济中的地位越来越重要，党的十八大明确提出要转变经济结构，鼓励电子商务和现代物

流行业的快速发展[1]。物流业和信息产业、运输产业、信贷业务等产业密切相关，涉及就业人员较广，对生产力的影响较大，在现代市场经济和增强国民经济竞争力中发挥重要作用。目前对单配送物流企业的车辆配送路径的优化问题研究的较多，在实际应用中单配送中心的路径比较成熟，但对多配送中心车辆路径优化的研究还比较少，与我国高速发展的物流配送业不相适应。从我国现有物流配送企业的发展看，多配送中心的车辆路径优化问题比单配送中心的物流调度求解更难，计算复杂度更高度，也更具有现实意义，逐渐成为物流调度中的一个研究热点问题[2-3]。

1 多配送中心车辆优化的数学模型

在多配送中心车辆优化的数学模型中，所有车场、货物配送点、客户等是配送网络的结点多配送中心车辆路径的数学模型如下。

约束（2）保证起点和终点是相同的，而约束条件（3）和（4）保证所有路径平行及其不超过客户数量。约束条件（5）假定多配送中心没有分配任务。约束条件（6）确保车辆不超过负载的需求。约束（7）和（8）是路线长度和客户数量限制，约束（9）是时间限制。约束（10），（11）和（12）是软时间窗，和约束（13）是硬时间窗，c和d是惩罚系数。

2 基于优化蚁群算法的多配送中心车辆路径算法

为了提高收敛效果和全局的搜索能力，本文提出了一种蚁群算法与遗传算法相融合的混合算法。遗传算法优化蚁群算法的交叉算子和变异算子，每个进化储备最佳解决方案，加快收敛速度，提高算法的全局的能力。整个算法分两个阶段进行，第一阶段引入遗传算法，利用遗传算法收敛速度快、全局性等优点调整蚁群算法中初始参数的分布。第二阶段利用第一阶段得到的值对蚁群算法进行初始化，执行蚁群算法，并在蚁群算法中加入交叉和变异，对多配送中心的车辆路径进行求解，具体算法步骤执行如下：

2.1 编码方式

本文对对染色体采用[G1，G2，...，GL]的编码方式，染色体包括起点车场号、车辆编号、顺序编号和终点车场号四部分。例如：染色体[SA13BB13AA11BA12BB12AB11A]表示编号为1和编号为2的车辆的行驶路线，其中编号为1的车辆以A为起始车站，以B为终止车站，行驶路线为[A→3→4→1→B]。编号为2的车辆以B为起始站点，以A为终止站点，编号为2的行驶路线为[B→6→5→2→A]。

2.2 基于优化蚁群算法的多配送中心车辆路径算法

步骤1： 利用遗传算法对蚁群算法参数[ρ，α，β，Q]进行优化。首先对染色体[ρ，α，β，Q]编码，[0.1≤ρ≤0.99]，[0≤α≤5]，[0.1≤β≤5]，[10≤ρ≤10000]，首先进行初始化种群，然后对适应度函数进行计算，为了充分考虑蚁群算法求解特性，从求解问题的目标函数、蚁群算法探索能力和开发能力 3 个方面来构建适应度函数。然后进行交叉和变异运算，采用正比选择策略，即每个个体被选中进行遗传运算的概率为该个体的适应值和群体中所有个体适应值总和的比例。查看是否达到最大迭代次数，如果没有达到，继续利用遗传算法对蚁群算法参数进行优化。

步骤2：初始化各个参数，将m只蚂蚁放置在[M+H]个顶点上，如果顶点为车场，则置该车场为该路径的永久车场，并将除该车场除外的其它车场加入禁忌表；否则将该顶点放置在此蚂蚁禁忌表里。当前路径tour、当前最优路径best_tour、当前路径的长度tour_length，当前最优路径长度best_length；visited[i] 表示节点i是否被访问过，qual表示车辆目前已载货物重量，随机选择一个车场，以变量start_depot表示当前车场编号，赋值变量i=start_depot；

步骤3：选择下一个节点 j，若没找到可用节点，将边（i，start_depot）加入当前路径，若对所有的节点i（i=1，2， ，N）都有 visited[i]=1，此时蚂蚁完成一条完成路径的搜索，对各边信息素进行局部更新， k=k+1 ，若所求路径小于当前路径 ， 则设置所求路径为最优路径，

步骤4：将边（i，j）加入当前路径，修改车辆目前已载货物重量，设置结点j被访问过。

步骤5：更新信息素，若满足结束条件，转向step 7，计算最优路径和次优路径值。

步骤6：选出本次循环中的最优路径和次优路径，并保留最优路径，转向步骤3。

步骤 7：算法结束。

3 算法验证

用VC + +6.0来设计程序，并选择标准测试集Cordeau算例中的数据做为测试数据进行实验，以取得最佳参数，从而使本文提出的基于优化蚁群算法的多配送中心车辆路径算法（GAACVNS）取得更好的实验效果。本文GAACVNS算法和TS算法[4]，VNS算法[5]，CNVNS算法[6]的车辆配送路径的最优解比较结果如表1所示。

从表1可以看出，本文提出的基于优化蚁群算法的多配送中心车辆路径算法比其余算法有更好的实验效果。

4 结论

本文给出了多配送中心车辆调度模型及染色体蚂蚁的编码方法。融合算法消除了所选参数的影响，融合算法通过对信息素挥发因子、启发式因子，信息素强度初始值的够造，消除参数选择对蚁群算法性能的影响，使其具有较强的全局搜索能力。引入遗传操中的交叉算子和变异算子，对蚁群算法在每次解过程中的最优解和次优解进行运算，并对优秀解进行保留，对优秀解公共解集的保留加快了算法收敛速度，引入交叉和变异扩大了解的搜索空间，提高了解的全局性。

参考文献：

[1] 张欣钰. 半开放式多配送中心车辆路径优化问题研究[D]. 大连： 大连海事大学， 2014.

[2] 李保伟. 多配送中心的城市物流配送车辆路径问题研究[D]. 合肥： 合肥工业大学， 2013.

[3] 孙丽君. 基于畅通可靠性分析的城市物流配送网络优化研究[D]. 长沙： 长沙理工大学， 2010.

[4] Cordeau J F， Laporte G， Mercier A. An improved Tabu search algorithm for the handling of route du-ration constraints in vehicle routing problems with Time windows[J]. Journal of the Operational Re-search Society， 2004， 55（5）： 542-546.

[5] Polacek M， Hartl R F， Doemer K. A variable neighborhood seareh for the multi-depot vehicle routing problem with time windows[J]. Journal of heuristics， 2004， 10（6）： 613-627.

[6] Polacek M， Benkner S， Doerner K， et al. A cooperative and adaptive variable neighborhood search for the multi-depot vehicle routing problem with timewindows[J]. Business Research Journal， 2008， 1（2）： 207-218.