多车型混载低油耗车辆路径问题的混合算法.doc

1、 多车型混载低油耗车辆路径问题的混合算法蔡芸程志文I,张利平2(1.武汉科技大学冶金装备及其控制教育部重点实验室，式汉430081：2.式汉科技大学机械传动与制造工程湖北省重点实验室.式汉430081)摘要：为了实现低磯运输和扩展多车型车辆路径问题求解方法，针对单车场有固定车辆数的多车型低油耗车 辆路径问題，建立了以最小化车辆油耗为目标的优化模型，在模型中考虑了与油耗密切相关的车辆实我量以 及混載问题：混合算法将具有整数编码的优势的遗传算法与具有觅伶操作的人工鱼群算法相结合，利用觅食 操作更好地优化车辆对集货点的访问顺序。遗传算法负责车辆和集货点配对的全局搜索，而人工鱼群算法负 责访问顺序的局

2、部搜索。算例实鞭结果表明：利用该模型求得的最低油耗较最短路径对应的油耗节省30%以 上；在全局搜索能力上，混合算法依次比自适应遗传算法、人工鱼群算法.蚁群算法强：当问題规模变大时， 其性能明显优于人工鱼群算法、蚁群算法；但加入的人工鱼群操作彩响了迢合算法的时效，算法混合策略还 有待改进。关键词：计算机应用；混合算法：车辆路径；车辆调度：低碳 中图分类号：F224： TP301.6 文献标识码：A文章编号：A hybrid algorithm for vehicle routing problem withmulti-vehicle mixed-loading and Minimum fuel

3、consumptionCAI Yun12, CHENG Zhiwen1, ZHANG Liping2(1 Key Laboratory of Metallurgical Equipment and Control Technology, Wuhan University ofScience and Technology, Wuhan 430081, China；2. Hubei Key Laboratoiy of Mechanical Transmission and Manufactunng Enineenn, WuhanUniversity of Science and Technolog

4、y, Wuhan 430081, China)Abstract: To realize low-carbon transport and explore the optimization method of the multi-type vehicle routing problem a minimum fuel consumption model is established for heterogeneous fixed fleet routing problem in a single-depot. The hybrid algorithm combined a genetic algo

5、rithm, which is good at handling integer coding* with an artificial fish swarm algorithm whose prey operation is helpful to optimize vehicle arrival sequence of collection nodes Genetic algorithm was responsible for the overall search of matching vehicles with collection notes, while artificial fish

6、 swarm algorithm was responsible for local search of vehicle arrival sequence For a test case, computational experimental results show that: the minimum fuel consumption in the above model is 30% less than that in a model of the shortest path problem. The global searching ability of the hybrid algor

7、ithm is stronger than adaptive genetic algorithm, artificial fish swarm algorithm and ant colony algorithm successively. Its performance is superior than artificial fish swarm algorithm and ant colony algorithm when the scale of the problem becomes larger, but the added operation of artificial fish

8、swarm algorithm increases the time consumption of the hybrid algorithnb hybrid strategies of algorithms need to be improvedKey words: computer applications; hybrid algorithm: vehicle routing; vehicle scheduling; low carbono引言中国政府承诺到2030年，单位国内生产总值的二氧化碳排放量比2005年下降60% 65%o而对不断变化的气候和环境，实施低碳运输是减少碳排放的必然趋势

9、，低碳车辆基金项目：国家自然科学基金(51305311 )作者简介：蔡芸(1970-),女.副教授，研究方向为物流系统的仿真和优化，E-mail: HYPERLINK mailto:caiyun caiyun 路径问题也备受学者关注。目前单车型低碳车辆路径问题模型的相关研究较为完善，模 型中除了考虑汕耗、碳排放等必要因素外，还会考虑综合成本工。由于单车型车辆路径问 题研究的日趋完善，多车型车辆路径问题渐受关注，该类问题模型常以运营成本最小为 优化目标叫此外，涉及到的因素有逍路网络地貌、车场数疑、顾客需求的随机性或时 间窗约束、车辆装载情况制、运营成本外的优化目标圧。少数学者X”开展了多车型低

10、碳路径问题研究，有的以车辆总的碳排放量最小为优化目标，有的将碳排放量与运营成 本波10-巴甚至顾客满意度一起进行了优化川。多车型车辆路径问题属于组合优化问题，也是NP-hard问题，常见的求解算法有整数 规划、构造算法、下界生成算法、禁忌搜索算法、遗传算法、进化算法、列生成算法等匕：。 为了提髙求解能力，研究者常会对现有算法进行改进，或采用混合算法求解，以提高问 题的求解效率和解的质量，如文献6用多起点策略改进禁忌搜索算法的多样化搜索能力, 文献12为了提髙算法效率，将量子进化算法和遗传算法结合。但是，目前还没有学者进 行多车型车辆路径问题的混合人工鱼群算法研究，只有单车型问题的应用研究，如文

11、献 13将人工鱼群算法与遗传算法以串行混合的方式用于求解物流配送的一般车辆路径问 题，获得了优于自适应蚁群算法，近似于蚁群遗传混合算法的最优解。人工鱼群算法早期收敛快，使用其求解组合优化问题时，曾获得较好的优化效果山： 加之，遗传算法及其混合算法在求解车辆路径问题时二工，不但表现良好而且其应用研究 较为成熟，因此，本文确左研究嵌入式混合鱼群遗传算法，以文献12中算例来验证混合 算法的有效性和可行性，并与自适应遗传算法、人工鱼群算法、蚁群算法进行算法性能比 较。另外，为了研究油耗il崔方法对路径优化结果的影响，没有采用文献12中通过实载 率计算油耗，而是采用了实载量计算。同时模型考虑了满载和非满

12、载的混合问题，由于 一部分客户需求或供应的货物数量大于或等于车辆的载重量，而另一部分客户需求或供 应的货物数量小于车辆的装载戢，造成一些配送车辆需要满载运行，而另一些车辆则经 常处于不满载状态。综上所述，本文研究的问题是对以往多车型低碳路径问题的理论模 型和求解方法的扩展，具有一定的理论和实践研究意义。1问题描述多车型车辆路径问题总体上分为车辆数固左和车辆数无限制的两类多车型问题。根 拯配送业务的不同，一般多采用多种车型混合（车型表现为不同的车辆形式、吨位、体 积）。本文研究的车辆数目固左的多车型车辆集货问题可描述为：已知有”个l,2,n） 集货点，第f个集货点的货运量为q. （/=lX-.n

13、）,需将所有货物运往一个车场，由车场 派出车型为加（匸1,2,M）、载重量为0 （/n=l,2,.,M,且假设Q Q2 .Qm）的 货车来承运，求满足货运需求的最低油耗行车线路。为了便于简化汁算，问题假设条件为：（1）每个货物点必须被访问且只能被访问一次; （2）车型以载重量分类且数目已知，车辆由一个车场空车发车，其配送路径上的总载量不 允许超过其载重呈:，完成载货后，回车场卸货：（3）假设车辆没有最大行驶距离限制：（4） 车辆汕耗量与车辆类型、载重和运输距离相关，且可由经验公式求得。2问题的数学模型2.1模型中的符号定义首先左义模型中符号含义如下：有向图G = V,E为配送网络，其中V=0,

14、l,2,n有n+1顶点,其中0顶点表示车场，其余顶点组成集货点集合V=V0； E =eV,i h j表示弧集;D丿为第i个集货点到第/个集货点的距离：G为集货点i货运量，沱0：川为车型编号，”疋1,2,.21为车型的总数：R为车辆编号,gl,2,-,K, K为车辆总数;0耕为第m类车型的空重：0“为第加类车型的运载能力，Q v 0 vv Q,:aMm为第加类车型的油耗计算系数;的为离开集货点F后前往集货点j的车辆已装货物总量；”为第加类车型的限制数量;_J1.牛辆从集货点F行驶到集货点j：”叫其他=集货点凍货由千辆R完成：九0其他2.2目标函数和约束条件建立上述问题的数学模型如下：M K n

15、ii TOC o 1-5 h z Obj： minZ=工工工工qX於心 +) + 】(1)fw=k=k=0 7=0S.t偷 Qmxijk, Vi J. m. k(2)土张 ijkZjQVWk(4)1=0戶0n kn kE E x0 jk =工 Z xiOk=U=Ir=l Xr=lxijk + xjik I.V/JgVW jyk(7)方一工甸=g ,巧W(8)；eV/eVzj=I=lMK = Xnm(10);?j=1承 NiwVNjwVNk(11)xijk =0或和=0或12讥(12) 式(1)表示目标函数为最小化车辆总油耗：式(2)表示车的载重不大于它的载重能力：式(3) 表示每个客户都会被服

16、务到：式(4)和式(5)表示集货点有且仅被一辆车服务；式(6)表示离开 配送中心的车辆和返回配送中心的车辆数量是一致的：式(7)表示两个集货点间的线路数不能 超过h式(8)满足集货点的取货需求，同时消除子回路：式(9)保证返回车场的所有车辆取货 总和等于所有集货点的取货需求总和：式(10)保证总车辆数等于各类车辆数总和：式(11) 保证离开集货点后车辆的载重不小于该点的货运量：式(12)用变量的取值，表示车辆与集货 点间关系。该模型放宽了文献9中刚从车场出发的车不会取货和返回车场的车辆不再服务的约束， 允许车辆在车场卸货后，再次被使用。车辆碳排放疑与车型、距离和路况、车速、载重量、驾驶状况等因

17、素有关，二氧化碳排 放量的计算由精确度要求和所采集的数据种类和精确度不同而不同，碳排放量与油耗成正比 例关系，油耗与行驶距离成正比例关系，与装载量成正线性相关凹。因此，最小化车辆油耗 与最小化碳排放一致。为了使用文献12中算例校验算法可行性，本文选择了只考虑车辆载 重0、运输距离Q (km)的车辆油耗F (L)计算方法9,即F=D(aQ+b)(13)其中“、b分别为与车型对应的燃油消耗参数。3求解问题的混合算法3.1算法总体设计混合算法求解的基本思路是：为顺序排列的集货点随机生成为其服务的编号车辆，归 纳每个编号车辆需要服务的集货点集合，车辆按英集货点从小到大的顺序号服务，产生 可行路径，即将

18、一个多车型路径问题分解为多个单车型路径问题解决。由于遗传算法擅长全局搜索但收敛速度慢，人工鱼群算法前期收敛快速、擅长微调但 常会陷入局部最优。本文混合算法采用将局部搜索方法插入到遗传算法主循环中的混合 形式。遗传算法负责进行种群中的全局搜索，而人工鱼群算法负责局部搜索，进行染色 体间的局部搜索。混合时将人工鱼群算法作为遗传算法基本循环的插件，让其与变异算 子、交叉算子和选择交算子一同工作，以执行快速的局部搜寻，从而在对后代进行评价 之前对其进行改进。令G是当前世代t时的车辆和集货点的对应编码,F(t)是当前世代t的各车辆对集货 点的访问序列，S是当前世代t的解集(S由G和F构成)。整个算法过程

19、归结如下： 整个算法过程归结如下：begint0；染色体初始化G(t)：人工鱼群编码初始化F(t)；S(t) -G(t)+ F(t):应用适应值函数评价S(t)：while终止条件不满足dobegin对G进行变异操作：对G进行交叉操作：对F执行人工鱼群操作；S(t) -G(t)+ F(t):用适应值函数评价S(t)；对G进行选择操作：t=t+l：endend3.2算法关键技术3.2.1编码和解码本模型的求解涉及两个方面的决策，第一个方而是每个集货点车辆类型的指派，第二个 方面是集货点访问顺序的决策。由于遗传算法在整数编码较为便捷，故将每个集货点车辆类 型的指派用遗传算法完成；又由于集货点访问顺

20、序存在大量的组合，人工鱼群算法含有多次 尝试觅食的算子，有利于顺序寻优，因而将集货点访问顺序决策交与人工鱼群算法执行。算法染色体采用长度为”的双层编码结构。第一层编码为集货点的节点排序，采用自然 数编码到“（”为集货点数量），第二层编码为对应上层集货点的服务车辆型号，采用自然数 编码到M （M为车型总数），K辆服务车辆构成这M类车型的车辆集合。以n=6, M=3时为例，图1显示一个染色体编码的意义，第一行为集货点编号，第二行为 遗传算法操作的染色体，即服务车辆类型的排序，其意义为1型车为集货点2服务，2型车为集 货点1、3和6服务，3型车为集货点4和5服务，每类车访问集货点的顺序交给人工鱼群算

21、法确 定。集货点编号：214356服务车编号：123032图1遗传算法染色体示意图Fig. 1 A Sample Chromosome in GA人工鱼群算法编码长度仍然为“（为集货点数量），采用精确到小数点后两位的实数编 码。图2所示的第一行是由1至“的集货点编号，第二行是人工鱼群算法的人工鱼，人工鱼码 值是由软件随机生成的0,1区间实数，根据人工鱼编码值进行扩展升序排序后，产生“个集 货点被服务的新序列及英服务车辆类型（如图3所示）。图3隐含了各类车辆对集货点的访问序 列，其可解析为1类车访问顺序为020,2类车访问顺序为03亠60 3类车访问顺序为0540集货点編号：123456人工鱼編

22、码值：0.820.660.200.460.130.91图2各集货点对应的人工鱼编码值Fig. 2 Artificial Fish Coded Values of Corresponding Collection Nodes534216030.200.460.660.820.91集货点访问顺用号: 人工鱼褊码值：图3以上集货点的访问序列Fig. 3 The Arrival Sequence of Above Collection Nodes3.2.2遗传算子的设计遗传算法对染色体种群G处理时，不改变染色体第一层的集货点序列，只针对染色体 第二层的车辆型号。交叉算子分别对染色体的两层编码进行交叉，

23、同时都采用两点交叉。变 异算子分别对染色体的两层编码进行变异，对第一层编码采用两点互易的变异策略，而对第二 层编码采用单点变异的策略。选择算子采用轮盘赌选择。3.2.3人工鱼群算子的设计人工鱼群算法模拟鱼群觅食的行为，每个备选解被称为一条“人工鱼”，初始化为一群人 工鱼（随机解），通过觅食、聚群及追尾等行为迭代搜寻最优解，在人工鱼群算法内部的每次 迭代过程中，通过更新人工鱼自己，从而实现寻优14。该部分算子设讣使用文献14的经典 人工鱼群算法动作，不再赘述。算法适应度值用目标函数公式（1）计算获得。另外，算法中 视距采用线性递减策略（参见公式（14），使得算法前期视距大，有利于快速收敛，后期视

24、距 小，有利于提髙收敛精度。1（14）其中为当前迭代次数为第M弋鱼的视距，/为最大迭代次数Vnwc为最大视距，Vnun为 最小视距。3.2.4目标函数的求解求解过程如下：1）首先通过遗传算法获取M类车俩服务的集货点的对应关系，得到集合G，G2,Gw,（如图1 G = 2, G2=1,3,6, G=4.5）：然后，通过人工鱼群算法的随机赋 值方法（如图2）,获得人工鱼编码值，然后使用扩展升序的方法，获得各类车对集货点访 问的新序列 F/，F2，F”，（如图 3 的 F/ = 2 , =3,1,6, Fj=5,4）。2）根据巧，兄，F”，分割岀M种类型K辆车的车辆调度路径，即获取路径卩，Sk，步骤

25、为:a）根据人工鱼群算法得到的某类车辆服务的集货点的访问顺序，从集货节点集合的第 一个点开始：b）达到一个节点后，判断车辆是否可以装载该点的全部货物量，如果可以,那么装载之, 淸空节点货物量，转d）,如果不能装完，转c）：c）去车场卸货，更新节点的货物量，再返回未装节点，转b）：d）判断是否全部访问完毕，如果未访问完毕，驶往下一个廿点，转b）,否则转e）：e）输出访问路径和车辆装载情况；3）根据2）得到的M类车辆集合内的各车辆的装载情况及访问路径，通过各车型耗汕公式, 计算岀它们的总油耗，即目标函数值。325适应度函数由于求油耗最小化问题，故适应度函数设左为目标函数的倒数，作为评价染色体好坏的

26、标准，即完成集货任务的所有车辆汕耗越小，染色体越优。具体的左义如下1（15）英中/为第i个染色体的适应度，乙为第，个染色体采用（1）式计算得到的目标函数值。4混合算法实验4.1最小化油耗与最短路径油耗的比较实验在Matlab软件平台下，混合算法在Intel奔腾i5-2450M CPU 2.50GHZ , 4G运行内存的 计算机上运行，采用文献12中表3、表4数据，以最小化油耗为优化目标，计算获得油耗是 1789.539L；文献12以最短路径为目标,获取的计算路径结果为文献12中表5,依据此求 得的最低油耗在2563.5L以上，可见若以最低油耗规划车辆路径，可节省约30%的汕。但是， 量子遗传算

27、法IB在求优时平均搜索迭代次数15.42,而混合人工鱼群算法平均搜索迭代次数 需要30次左右，混合算法收敛较慢。4.2算法性能比较实验为了分析混合人工鱼群算法（HAFSA）对于求解以最低油耗（LFC）为目标的多车型车辆调 度问题的性能，本文采用经典的人工鱼群算法（AFSA）、自适应遗传算法（AGA）和蚁群算 法（ACO）进行了算法实验对比。车型及油耗参数选择如下:5t车型，a=0.72.b=15； 10t车型， a=O.52,b=18： 15t车型，a=O.313,b=22集货点信息如表1所示。表1集货点信息Tab. 1 Information of Collection Nodes编号坐标/

28、km集货fit编号坐标/km集货助1|41O.22O|2.518430.1280162卩 4&1178|319I465.890J183320.1003J420(375903211352,1050265|5OO.31O|2.5221700.78096|190704231800.11901871320.400424938.145078|55O.35O|925I646J590J391239.436626R67.326I810(1309,346|72711222.10352411I500.4S0)728|118&1230|5121600.530)1229|929J 28OJ1

29、113620,580)1030978.16301514|650.69()|1331|105& 16701815|690.1020|143211200.1780)20161760.11501933|13(X).193O1017525.131018在算法参数实验方面，实验结果表明：混合算法中的人工鱼群算法参数设巻为种群数250, 迭代次数50,尝试次数10,人工鱼的最大视距3,人工鱼最小视距1,拥挤度因子0.618,最大 移动步长2,变异概率0.3,交叉概率0.6,通常会获得较优的计算结果：人工鱼群算法参数取 混合算法中相应参数时，计算结果也较优：自适应遗传算法的部分参数采用经典设置，当取 变异槪

30、率0.15,交叉概率0.6时，可以得到较优的讣算结果。在算法寻优效果方而，由表2可知，四种算:法求解的最低油耗值从小到大依次为混合人 工鱼群算法、自适应遗传算法、人工鱼群算法、蚁群算法，反映岀混合人工鱼群算法的全局 搜索能力最强，自适应算法次之，蚁群算法最弱。在算法收敛性能方而，由表2和图4可知，单纯使用人工鱼群算法时，其前期收敛快，但 后期易陷于局部最优，收敛速度慢，计算时间长，求解的最低油耗平均值为1860.4L,平均收 敛次数为106次，相比自适应遗传算法，其求解结果和收敛性能都较差。蚁群算法前期收敛也 较快，相比人工鱼群算法，更易摆脱局部最优。当使用人工鱼群算法和自适应遗传算法结合而成

31、的混合算法时，由于自适应遗传算法的 加入，混合算法表现出了较强全局搜索能力及良好的鲁棒性，这是由于遗传算法通过自适应 处理后，当种群趋于收敛时，交叉概率会降低，变异槪率会提高，从而可以保持种群的多样 性，避免“早熟“现象。此外，当种群个体发散时，交叉槪率会提高，变异概率会降低，使得 种群趋于收敛，也提高了算法的收敛速度。此外，混合算法中的人工鱼群算法也发挥了其前 期收敛快的优势，增强了混合鱼群算法寻优能力。综上原因，由表2分析可知，混合算法相比 自适应遗传算法不仅可以取得很好的计算结果，而且苴计算效率也比经典人工鱼群算法有了 很大的提高，计算结果也很稳左。实验结果表明：混合算法比自适应遗传算法

32、可以平均节省 约233.8L的燃油消耗,从而更好地达到节能环保的目的。表2仿頁结果分析Tab. 2 Analysis of Simulation Results以法名称tfi/Ltll/L平均值/L计算时平均收敛次数/limesHAFS13471789.51568.3240.332AFSA1805.41915.31860.42362.7106AGA1786.91817.21802109.947ACO1932213620346759图4四种算法的迭代图Fig. 4 Iterative Graph of Four Algorithms当车辆类型规模m取不同值时，由表3统汁的试验结果表明：对于小规模

33、的车辆调度问 题，四种算法均能计算岀比较好的解，但是随着规模的增大，人工鱼群算法和蚁群算法的稳 立性就开始下降了，而混合算法却依然能够取得较好的结果，这得益于该算法是人工鱼群算 法和自适应遗传算法同步演化，每一代的染色体和鱼群位置都是变化的，提高了人工鱼群算 法收敛速度、精度和全局搜索能力。表3不同算法在m取不同值时的LFC值Tab. 3 The Value of LFC of Different Algorithms in mmHAFSAAFSAAGAACO51680.21805.218722006.6101843.52147.31874.72020.8151897.22128.818442

34、089201897.32245.21836.32085251885.32264.71836.32136301863.62291.91868.5218291873.82205.9401909.923181983.92259.65结论本文在国家实施的一系列宏观调控中，强力降低碳排放的背景下，提岀了一种由人工鱼 群算法和自适应遗传算法组成的混合算法，并运用到求解车辆汕耗受多车型、集货点位宜、 货物量、车辆混载等多边因素影响的车辆调度问题，这是该种混合算法在以最低油耗为目标 的多车型混载车辆调度的首次应用。算法实验结果证明了该混合算法性能明显优于单一的人 工鱼群算法和蚁群算法

35、，同时也证明了混合算法求该问题的有效性。但与自适应遗传算法的 时效相比，该混合算法还有不足，还需要在人工鱼群算法的算法行为、参数，以及与自适应 遗传算法的结合方式上，做出进一步的改进。【参考文献(References)fl|许茂增，余国印.周翔等综合成本最小的低碳乍辆调度问题及算法J|讣算机集成制造系 统.2015,21(7):1906-1914.XU M Z.YU G Y, ZHOU X.et al. Low-carbon vehicle scheduling problem and algorithm with minimum-comprehensive-costlJ. Computer

36、Integrated Manufacturing Systems.2015.21(7) J906-19I4. (in Chinese)21罗平.多牟型辆路径问题研尤与应用D成都：西南交通大学,2014.LUO P. Research and application of fleet size and mix vehicle routing problem|D.Chengdu : Southwest Jiaotong University. 2014. (in Chinese)3| Bae H. Moon I. Multi-depot vehicle routing problem with l

37、ime windows considering delivery and installation vehicles. Applied Mathematical Modelling. 2016.40(14):36-49.Wang Z. Li Y. Hu X. A heurislic approach and a tabu search for the heterogeneous multi-type fleet vehiclerouling problem with time windows and an incompatible loading conslraintJl. Computers

38、& Industrial Engineering. 2015.89(5):162-176.Qu Y. Bard J F. The heterogeneous pickup and delivery problem with configurable vehicle capacity! J|.Transportation Research Emerging Technologies. 2013,32(3):1-20.Molina J C. Eguia I. Racero J, et al. Multi-objective Vehicle Routing Problem with Cost and

39、 Emission Functions)J. Procedia Social and Behavioral Sciences. 2014,160(6):254-263.7|李进，傅培华.具有固定车辆数的多车型低碳路径问题及算法卩计算机集成制造系,2013,24(6)： 1351-1362.LI J. FU P H. Heterogeneous fixed fleet low-carbon routing problem and algorithm|J|. Computer Integrated Manufacturing Systems. 2013 24(6)： 290 1351-1362.

40、(in Chinese)8李淑琴杨斌赵磊，等.需求帯时间窗的环保女吃型组合配送路径优化卩广西大学学报(自然科学版). 201333(02)： 388-394.LI S Q. YANG B. ZHAO L, et al. Environmental multi-model combination distribution routing optimization for demand with time windows|J. Journal of Guangxi University(Nat Sci Ed). 2013,13(02)： 388-394. (in Chinese)9|赵燕伟，李文，张景玲，等.多车型同时取送货问题的低碳路径研尤|J浙江工业大学学