基于智能混合算法的车辆配送路径优化

基于智能混合算法的车辆配送路径优化

汪岚

( 黎明职业大学 机电工程与自动化学院，福建 泉州 362000 )

摘要：为提高车辆配送效率，节约配送成本，建立了以配送路径和成本综合最优为目标的车辆配送路径问题数学模型.设计并实现了一种智能混合算法，首先利用具有自适应交叉率和变异率的改进遗传算法生成全局较优解，再将较优解转换为初始信息素进行蚁群算法，并结合2-opt算法对解进一步迭代优化，最终获得了车辆最优配送路径.实验结果表明，该算法优化后的目标值比蚁群算法减少了15.0%，比遗传算法减少了10.4%，验证了该算法的有效性和优越性.

关键词：车辆配送路径问题； 智能混合算法； 遗传算法； 蚁群算法； 2-opt算法

收稿日期：2015-07-23

基金项目：泉州市科技局社会发展计划项目(2012Z132);黎明职业大学校科研团队项目(LMTDD2014108)

文章编号：1004-4353(2015)03-0261-06

中图分类号：TP391.9

Research on optimizing vehicle routing based on intelligent hybrid algorithm

WANGLan

(DepartmentofMechanicalandElectricalEngineering,LimingVocationalUniversity,Quanzhou362000,China)

Abstract：In order to improve the efficiency and reduce the cost of vehicle delivery,a VRF mathematic model on optimizing vehicle routing and cost was established. An intelligent hybrid algorithm was proposed. Hybrid genetic algorithm which combined with self-adaptive crossover rate and mutation rate was used in the algorithm to conduct the global better solution. Then the better solution was taken as the initial solution of the ant colony algorithm and the stage solution was optimized by 2-opt algorithm to obtain the best vehicle routing. The experimental result showed that the objective value based on hybrid algorithm was 15.0% less than ant colony algorithm and 10.4% less than genetic algorithm，so the efficiency and superiority of the intelligent hybrid algorithm were proved.

Key words： vehicle routing problem; intelligent hybrid algorithm; ant colony algorithm; genetic algorithm; 2-opt algorithm

随着现代物流业的飞速发展，物流配送规模和数量急剧猛增，从而导致配送成本在整个物流成本中占有过半的比例[1].配送路径优化设计，能够节约配送成本，提高配送效率，提高企业竞争力，因此，寻求合理、有效的车辆配送优化路径具有重要的实际意义.目前，对于车辆路径配送问题(vehicle routing problem,VRP)常用的智能算法有遗传算法[2]、模拟退火算法[3]、禁忌搜索算法[4]和蚁群算法[5]等，但随着配送过程中需考虑的约束条件日益复杂，单一的智能算法已无法很好地解决VRP问题，逐渐被混合优化算法[6]所取代.针对车辆配送路径优化问题，本文构造了由改进遗传算法、蚁群算法和2-opt算法相融合的智能混合算法，并与基本遗传算法、蚁群算法进行比较，最后在车辆配送实例中验证了混合算法的有效性和优越性.

1车辆配送路径优化数学模型

车辆配送路径优化思路为：在配送车辆的最大承载量、最大行驶距离、客户(节点)需求量和位置固定等条件下，配送中心派遣多辆车对客户进行商品配送.基于实际配送原则，通过合理的车辆配送路径规划，在满足所有约束条件的情况下，使配送成本和配送路径综合最优.

假设某一物流配送中心，拥有m辆同规格配送车，每辆车的最大承载量为Q，最大行驶距离为D.对n个节点进行配送，节点号为i(i=1,…,n，其中i=1为配送中心)，每个客户对应的商品需求量为qi，客户接受配送服务的有效时间区间为[ai，bi]，车辆实际到达客户的时间为ti.dij为结点i到结点j的路径长度，cij为结点i到结点j的配送成本.结点i到结点j的关系如下：

(1)

(2)

其中：i=1,…,n,j=1,…,n; k=1,…,m.车辆配送路径优化数学模型为：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

式(3)中w1、w2为配送路径和成本目标函数对应的权重，式(4)为车辆承载量约束，式(5)为车辆行驶距离约束，式(6)限制每个节点配送任务有且只有一辆车负责，式(7)和式(8)则限制到达和离开某一节点的车辆有且只有一辆，式(9)为时间窗约束，l和u为配送早到和晚到的惩罚因子.

2智能混合算法设计

遗传算法具有全局高效寻优和鲁棒性强的优点，但存在着早熟和反馈信息利用率低的缺点；蚁群算法具有反馈信息利用率高且能收敛到最优解的优点，但因初期信息素匮乏，存在求解速度慢的缺点.本文提出的智能混合算法的思路是：将遗传算法与蚂蚁算法相结合，先对基本遗传算法进行改进，实现变异率和交叉率的自适应调整，生成若干全局较优解，然后将其处理转换为蚁群算法的初始信息素再进行求解，并在解生成阶段采用2-opt算法[7]进一步优化，最终获得最优配送路径方案.

2.1　改进遗传算法

1) 编码与初始种群生成.采用实数编码，生成长度为n+m+1的染色体，其中n为包括配送中心和客户在内的所有节点数，m为车辆数.如某一配送中心有2辆车为8位客户配送商品，应生成长度为11位的染色体.将节点1默认为配送中心，则染色体12345167891表示，车辆1负责为位于节点2、3、4、5的客户配送商品，车辆2负责为位于节点6、7、8、9的客户配送商品，以此类推.初始种群采用随机方式产生.

2) 适应度函数.在遗传算法中，适应值函数与目标函数相映射，即当VRP优化目标数值Z越小时，对应的个体适应函数值应越大，其对应解性能就越好.适应值函数设置为

(10)

4) 自适应交叉、变异操作.采用固定值的交叉率和变异率不合理，会影响新个体产生的快慢，容易导致算法陷入局部最优解，难以保证种群多样性.因此，本文对二者进行改进设计，使其能够根据每代具体情况进行自适应调整[8]，其公式如下：

(11)

2.2　蚁群算法

1) 信息素初始值.蚁群算法的初始信息素计算公式为

τij(t0)=F(sij)，

(12)

其中F(sij)是遗传算法获得的较优解对应的适应值.这种方法可有效避免初期因信息素匮乏而造成路径的盲目搜索，可有效提高寻径的针对性和效率.

2) 移动规则.t时刻，蚂蚁k将根据路径上的信息素强弱从客户i移动到下一个客户j，其移动概率为

(13)

式中τij(t)表示t时刻客户i和客户j之间路径上的初始信息素，ηij=1/dij为客户i和客户j之间路径的能见度，allowed为蚂蚁k下一步可选择的节点，α为信息启发式因子，β为期望启发式因子.

3) 信息素更新.蚂蚁移动至新的一个节点时，其对应路径的信息素将发生更新，计算公式为

(14)

式中ρ为信息素挥发系数(0<ρ<1)，Δτij=Q/dij为客户i和客户j之间路径的信息素增量，Q为常数，dij为客户i和客户j之间的路径长度.

4) 2-opt优化.当车辆配送路径存在交叉情况时，配送距离会增大.因此，在蚁群算法的最后阶段引入2-opt算法，即在承载量不变的情况下对当前最优路径进行局部优化，消除交叉现象，以缩短距离.2-opt算法的优化步骤为：

Step1在一条节点数为n的路径中随机产生正整数i和m(m=1,…,n)，m=1.

Step2令i为1~n的任一随机整数，对当前最优路径进行交叉判别，当di,i+1+di+m,i+m+1>di,i+m+di+1,i+m+1时，转Step3；否则，转Step4.

Step3判断存在路径交叉现象，删除边(i,i+1)和边(i+m,i+m+1)，增加边(i,i+m)和边(i+1,i+m+1).令m=m+1，转Step5.

Step4判断不存在路径交叉现象.令m=m+1，转Step5.

Step5判断m=n，若等式不成立，转Step2；等式成立，算法结束.

2-opt算法优化路径的效果如图1所示.

(a)路径交叉　　　　　　　　(b)路径无交叉 图1　2-opt算法优化路径效果图

2.3　智能混合算法的具体步骤

1)改进遗传算法基本参数初始化，如种群规模，交叉率Pc1、Pc2，变异率Pm1、Pm2，最大进化代数Genmax，配送早到和晚到的惩罚因子l、u等.

2)实数编码，随机生成初始种群P0，根据式(10)计算每个个体的适应值.

3)进行选择操作，按照式(11)计算自适应交叉率Pc和自适应变异率Pm后，进行交叉变异操作，生成新一代种群Pi(t).

4)计算新种群每个个体的适应值.

5)判断Genmax是否达到，若未达到，则迭代次数加1，跳转到3)；若达到,则输出对应的若干个较优解，转到6)继续执行；

6)蚁群算法基本参数初始化，如α，β，ρ，Q和最大循环次数NCmax等.

7)将混合遗传算法获得的较优解，按照式(12)转换处理成蚁群算法各路径上的信息素初始值τij(t0)，令车辆数等于蚂蚁数，将蚂蚁放置配送中心.

9)判断蚂蚁k是否周游过所有节点，若未完成，则跳转到8)；若完成，令k←k+1，转到10)继续执行.

10)判断是否所有蚂蚁都完成了周游遍所有节点，若未完成，则跳转到8)；否则，转到11)继续执行.

11)路径构建完成，对当前路径进行2-opt优化，并根据式(14)进行当前最佳路径信息素全局更新.

12)判断是否达到最大循环次数，若未达到，循环次数加1，跳转到8)；否则，算法结束，获得全局最优配送路径R.

3实验结果及分析

以某物流配送点为例：拥有配送中心1个，坐标为(0,0)对应节点号为1；同规格配送车辆9辆，车辆最大载重量8t，客户17个.遗传算法的参数设置为：种群规模为80，交叉率Pc1=0.3,Pc2=0.7，变异率Pm1=0.001,Pm2=0.01，最大进化代数Genmax=150，配送早到和晚到的惩罚因子l=1，u=2；蚁群算法的参数设置为：α=1，β=1，ρ=0.15，Q=15，最大循环次数NCmax=150.分别采用蚁群、遗传和混合3种算法进行配送路径优化仿真，各自进行10次测试取平均值，3种算法的优化目标与迭代次数的关系曲线以及收敛过程如图2和图3所示.

图2　优化目标与迭代次数的关系曲线

图3　不同算法下的配送路径仿真图

由图2可看出，智能混合算法的收敛速度和目标值的优化效果比其他两种优化算法具有明显的优势，由此证明了该算法的有效性和优越性.由图3可看出,最佳配送路线为：1→11→1→4→16→15→1→6→14→1→2→1→3→1→13→7→5→1→12→17→1→10→18→1→9→8→1，配送最短行驶里程为124.6517km.表1为3种算法优化后的性能指标.由表1中3种不同算法对配送路径优化后的性能指标可知:对于综合目标值，混合算法比蚁群算法减少了15.0%，比遗传算法减少了10.4%；对于运算耗时，混合算法耗时比蚁群算法缩短了2.20%，比遗传算法缩短了2.18%.由此可知，采用混合算法获得的配送路径比蚁群算法和遗传算法能够节省配送成本，缩短配送路径，可有效地提高配送效率.

表1　不同算法优化对应的性能指标

4结束语

本文构建了以配送路径和配送成本为优化目标且带有时间窗约束的车辆配送路径优化数学模型,针对模型特点，提出一种智能混合算法，将遗传算法、蚁群算法和2-opt算法融合起来，发挥各自算法的优点，提高了算法全局寻优能力和局部搜索的科学性.仿真实验结果表明，采用智能混合算法求解，比遗传算法和蚁群算法获得的结果更优，具有较好的实际意义.本文所建的模型有一定的局限性，且对时间窗的研究还较为不足，今后将对此做进一步地研究，使之更加贴近实际情况.

参考文献：

[1]张晓龙.电子商务下现代物流企业配送系统优化研究[J].物流技术,2011,30(6):135-138.

[2]柳林,朱建荣.基于遗传算法的物流配送路径优化问题的研究[J].计算机工程与应用,2005(27):227-229.

[3]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法[J].中国公路学报,2006,19(4):123-126.

[4]王雪莲,汪波,钟石泉.一类半开放式车辆路径问题及其晋江算法研究[J].机系统仿真学报,2008,20(8):1969-1972.

[5]杨从平.基于蚁群算法的快递物流配送路径优化[J].物流工程与管理,2014,36(4):27,65-67.

[6]蒋国清,潘勇,胡飞跃.两阶段式的物流配送路径优化方法[J].计算机工程与应用,2015,51(2)：255-258.

[7]任璐.基于遗传算法的建立与求职岗位匹配研究[D].广州：暨南大学，2009:22.

[8]宋娟,崔艳.基于改进遗传算法的同城快递配送模型[J].电子技术应用,2014,40(12):136-139.