基于自适应蚁群算法的车辆路径问题研究

(同济大学 上海 200092)

基于自适应蚁群算法的车辆路径问题研究

胡萌萌

(同济大学上海200092)

车辆路径的选择本质上是一个非确定性多项式问题，当其规模相对较小时可以利用多种传统方法求得最优解；但是随着问题规模的逐渐增大，方法的适用性也越来越差。本文首先论述了蚁群算法在解决该类问题中的适用性以及应用过程中的优势和劣势，最后提出在不同搜索阶段对其参数进行相应调整的改进措施，最大程度上提升其收敛速度，满足问题解决的需要。

车辆路径问题；蚁群算法；自适应策略

一、问题描述

随着电子商务的快速发展，物流配送过程中常见的问题是物流车辆对区域内用户配送过程中的最佳路径：假设该配送中心共有n辆车，每一辆快递车的最大运送量为G；配送范围内共有m个客户，每个客户的货物重量都各不相同，用qi表示(i=1,2……m)；快递车辆的节点用p表示，其中p0代表快递中心，pi代表客户点(i=1,2……m)；快递运送过程中的成本用ci表示，其成本包括时间、人力和运输过程中的各种费用。则这一问题的变量可通过以下的公式定义：

数学模型可以概化为：

s.t.

二、算法概述

昆虫学家在对蚂蚁生活研究过程中发现，其从野外觅食点到蚁巢之间的路径选择过程中依靠的是蚂蚁之间的相互沟通，其中最为重要的媒介是蚂蚁的分泌物—信息素。其中的任何一只蚂蚁都会在根据路径上信息素的浓度来选择其下一步的路径，而随着最优路径上信息素浓度的不断累计，后续的蚂蚁都会选择该路径完成食物的搬运。

蚁群算法简称做ACO，最早由Dorigo等人在上世纪九十年代提出；在该算法提出之前学术界内针对组合优化问题采用的较为成熟的算法有模拟退火算法、遗传算法、人工神经网络等。截止目前该算法已经经过了众多学者的研究和使用，已经基本趋于成熟。

M.Dorigo等人在TSP问题中对该算法进行了成功的应用，之后由根据其特点将其应用范围拓展至不均衡的TSP、QAP和job-shop调度问题，并且效果良好[1]。鉴于该算法应用过程中会出现收敛停滞的现象，Stützle,T.等人对传统的蚁群算法做了进一步的完善，提出了MAX-MIN蚁群算法(简称做MMAS)其中最重要一处改进是将不同路径内的信息浓度都进行了限制，为其设定了最大和最小值，同时规定某次循环结束之后只将最短路径的信息素添加进去；这样就能够有效限制过早收敛非全局最优解的出现；吴庆洪在其研究成果中将变异机制引入到蚁群算法中，将算法的收敛变得更加简洁和高效[2]；姚宝珍则是在基本算法中加入了自适应的机制，能够根据算法搜索阶段的不同对其中的部分参数进行调整[3]；陈陵也提出了新的基于自适应机制的蚁群算法，其依靠的是解的分布均匀度，根据其变化来选取最佳的概率确定和信息量更新方法[4]。

三、自适应蚁群算法

(一)自适应转移规则

基本蚁群算法计算过程中通常会将“信息素”浓度不同作为路径选择的依据。考虑到最优解位置的未知性，搜索过程中需要保证搜索过程中的随机性；但是算法的应用有要求能够高效的解决具体的问题，所以必须有一定的确定性；两方面综合作用下就要求算法的转移规则能够最大程度上满足这两方面的需求，从而保证算法执行的效率。

一般情况下，如果源问题确定之后，算法执行过程中信息素强度和期望度也不会出现大的变化，所以精确找到两个启发式因子(α和β)成为算法中的重要环节。通常来讲，会利用仿真来获得这两个参数，并且选择固定值贯穿于算法应用过程中；但这样一来就忽略了蚁群计划过程中这两个参数的地位的变化。例如算法运行初期，信息素还没在系统中形成，期望信息能够在很大程度上决定蚁群的运动；但是随着算法的不断运行，信息素基本成型，这时信息素强度将成为决定蚁群运动的重要参数。

鉴于此，本次在基本蚁群算法的基础上引入了自适应的机制，以第i点的第k只蚂蚁作为论述对象，其在下一个阶段向j点运动的概率为：

式中：τij代表(i,j)边信息素的浓度；ηij则代表其能见度；α和β是算法中相应的启发因子，其中前者能够代表搜索过程的随机性，而后者能够代表搜索过程的确定性；tabuk代表问题中的禁忌点组合；t是进化代数，其取值范围为1～T，取整数。

(二)自适应信息素更新策略

算法运行过程中不同的蚂蚁都能够感知信息素的浓度，从而完成相互之间的信息沟通；过程中蚂蚁会根据预先设定好的转移规则进行运动，其最终运动曲线则构成了某个具体问题的优化解决方案。并且各次循环结束之后，每条边上的信息素浓度都会发生相应的变化；其变化的最终依据就是确定好的更新策略。

式中，ρ代表了信息素残留系数，本次算法优化中取值0.8；τ是蚂蚁k在本次循环过程中在(i,j)边处信息素的变化量；p代表蚁群中蚂蚁的数量。通常来说，运动路径越短，其边上的信息素浓度也会越大；对于具体的问题来说，如果某一个路径越与最优方案的相似程度越高，其信息素农业也会越大，越能够在下一个循环过程中吸引更多的蚂蚁。

四、结论

车辆路径选择和优化问题是物流分配过程中的重要环节，研究过程中要充分考虑每个车辆的最大载重等因素，在保证客户需求的同时又要尽可能的降低物流运送过程中的成本；其本质上是一个非确定性多项式问题，当其规模相对较小时可以利用多种传统方法求得最优解；但是随着问题规模的逐渐增大，方法的适用性也越来越差。本文在基本蚁群算法的基础上在更新策略中加入了自适应的机制，既能够提高算法的收敛速度，同时还能够有效降低局部最优解的出现几率。

[1]Dorigo,M,Maniezzo,V,Colorni,A,(1996);The Ant System:Optimization by a Colony of Cooperating Agents,IEEE Transactions onSystems,Mans,and Cybernetics 1(26):29-41

[2]吴庆洪,张纪会,徐心和:具有变异特征的蚁群算法[J].计算机研究与发展，36(10):1240-1245(1999).

[3]姚宝珍:自适应并行蚁群算法[J].模式识别与人工智能.2015,20(4):458-461

[4]陈陵,沈洁,秦玲等:基于分布均匀度的自适应蚁群算法[J].软件学,2013.14(08):1379-1387

胡萌萌(1992.2-)，女，汉，河北邯郸，同济大学，学生，硕士，研究方向车辆路径规划。