改进蚁群算法的航空物流运输路径规划仿真

郭 川,山君亮,芮茂雨

(空军勤务学院航空运输与投送保障系,江苏 徐州 221000)

1 引言

航空运输物流因其快速、机动、高效的特点在现代物流运输方式中脱颖而出。随着我国航空运输行业的发展,去往同一个地点的货物有多条航空输送路径可以选择,如何选择最优路径,对企业节省运输成本、缩短货物运输时间有着非常重要的意义。

航空物流运输路径的规划不是单一的数学选择问题,需要借助计算机技术和现代优化方法对其展开求解[1]。例如:邢小虎等人[2]提出利用随机遗传算法对航空物流运输路径求解,获取不同途经点和到达点之间的稳定线路,解决MTSP问题,构建多目标路径规划模型,以此为依据实现航空物流运输路径规划,该方法在路径规划中的危险度高,精准度低。崔叶竹等人[3]提出应用人工鱼群算法对航空物流运输路径求解,根据航空物流运输路径设定约束条件,结合VPR数学模型模拟鱼群觅食过程,对以上模型展开优化,以此为依据实现航空物流运输路径规划,该方法在路径规划中高度代价高,性能低。张洪海等人[4]提出基于改进A*(A-star)算法的航空物流运输路径求解方法。采用栅格法展开环境建模,多方位考虑外在因素,结合曼哈顿距离线性组合设计启发函数构建多约束航空物流运输路径规划模型,以此为依据实现航空物流运输路径规划,该方法路径规划航程长,运输成本高。

为了解决上述方法中存在的问题,提出考虑多因素耦合的航空物流运输路径规划方法。为更精准优化空中运输的路径,首先明确运输影响条件,设计目标函数,获取在多种条件约束下的研究目标,优化蚁群算法,得到航空运输路径的最优解,并通过实验对该方法的实用性完成验证。

2 路径规划

2.1 模型构建

为了解决传统航空物流运输多种路径复杂且多样化的弊端,考虑多因素耦合的航空物流运输路径规划方法,对影响航空物流运输路径的各种因素展开分析。一般情况下,影响航空物流运输路径规划的因素[5]有如下三个:

1)距离因素

最重要的因素就是距离,各航线点中的航线距离是确定的,当航线点之间没有航线时用0表示。由于航线之间的距离值过大,使用此数值会将其它约束条件的影响降低到很小,从而影响到最终结果,所以要统一所有参数,将航线之间的距离值限制在(0,1)之间,表达式如下:

(1)

式中,航线之间距离约束条件为D,两个航线点间确切距离为d,航线点之间最远距离为max。

2)天气因素

由于天气较为复杂,为了将其简单化,对天气影响划分:对运输飞机影响巨大(记成1)、大(记成0.9)、适中(记成0.6)、小(记成0.3)、无影响(记成0)。在求解过程中,随机出现上述情况y,当y=1时,表示天气对航行影响巨大,在路径规划中,需要避开这一航线点,防止因天气影响航空物流运输。

3)飞机密度因素

在一个航空路线上飞机太多也可能造成飞机之间距离太近,进而造成航空事故。在航空运输路径规划时,飞机密度q=c/m也尤为重要。其中,飞机数量为c,航线上承担飞机的最大数量限度为m。当q=1时,表示飞机密度对飞行影响巨大,在路径规划中,需要避开这一航线点,防止航线上飞机过多,导致相撞引发飞行事故。

在路径规划中,依照不同因素影响的程度不同对其加权,当yi≠1并且qi≠1时:

(2)

式中,g(c)为航线点,di/max为加权后的距离约束条件,yi为加权后的天气约束条件,ci/MI为加权后的飞机密度约束条件。权值重新规划,当yi=1或者qi=1时,这一航线点不可以通过。

2.2 约束条件

在路径规划过程中,有很多限制路径规划的约束条件[6]。如下

1)当量航程约束

引入当量航程he(bi,bj)概念,其表达式为:

he(bi,bj)=h(bi,bj)/δij

(3)

式中,bi、bj为任意两个航线点,h(bi,bj)为几何航程,δij为相对燃油里程。当量航程越短,其燃油经济性[7]越高。

2)集结时间窗约束

(4)

式中,当bi∈F,允许最大地面延误时间为Φi,当bi∈T,允许的最大空中等待时间为Φi。

3)拓扑结构约束[8]

航空物流运输路径Y可以抽象理解为Steiner树[9],如图1(a)所示,则Y的拓扑结构为:

图1 航空物流运输路径图

①所有航线点的出入度是1。

②所有脱离点出度小于2、入度是1,集结点相反,入度小于2,出度是1。

4)流量平衡约束[10]

对于所有的航线点,流入和流出节点流量相等,所以同一Steiner点的3条边存在约束,集结点与脱离点的流量平衡约束表达式如下。

(5)

航线衔接点流量平衡约束表达式如下。

wvl=wvl′,vl∈v,vl′∈v

(6)

式中,vl、vl′是相邻的两个衔接点。

5)飞行受限区[11]约束

根据我国《民用航空法》规定,任何航空器非经许可,不得进入禁区、限制区及危险区。飞行受限区即为上述区域。根据图1(b),飞行受限区约束可表示为:

(7)

(8)

式中,地球半径表示为TE。

6)油耗约束

飞机的燃油携带量是经过精准计算其载物时最大起飞重量以及机场航道最大承重获得的,所以要依据飞机燃油量规划其物流运输的距离。

7)任务时间要求约束

有时效性,必须在时效内完成运输任务。

8)途经点约束

在物流运输过程中必须经过的航线点。

9)航线距离约束

根据燃油和时效的影响,飞机的航线距离必须低于同等重量下的最大飞行距离。

3 最优路径计算

3.1 优化蚁群算法

在多种条件约束下,采用实时优化的蚁群算法[12-13],对航空物流运输多路径模型求解,实现对运输路径的优化。

(9)

式中,oml(y)为时刻y连接点的信息浓度,ε为信息素的相对重要性,δ为启发信息的相对重要性。

对蚂蚁移动路径的及时刷新,使得蚁群的移动方式更新为以下:

(10)

蚁群可依据实时释放的不同信息素搜索出路径反常状况,每当路径发生异常,蚁群会迅速完成下一轮最优路径的规划选择与信息迭代[14]。

3.2 步骤设计

1)依据航空物流干扰信息建立多路径规划模型,明确实时优化蚁群的约束条件。

2)设定目标函数。

3)蚁群更新移动起点设定在创建的模型中多条路径的中心点,对多条路径同时移动。

4)蚁群在移动到下一个更新节点的过程中,每一个个体都会释放并自动检索以时间为标准的信息素,完成信息浓度的更新。

5)更新完所有路径节点信息,获得最优路径,完成航空物流运输路径规划。

6)在优化过程中,时间信息素差距影响着蚁群的更新速度,差距越大则更新越快,完成路径优化速度越快。

3.3 最优路径的平滑处理

通常情况下,实时优化蚁群算法求解的最优路径是连续的曲线。由于曲线中有凹凸点,即最优路径本身是连续的但其一阶导数不连续。最优路径的平滑处理[15]就是为了使实时优化蚁群算法求解的曲线和一阶导数均是连续。

由于多种原因约束限制,航空器在从航线点S点行进到航线点N后无法直接沿NV继续行驶,因此,需要在SN和NV之间展开平滑处理,如图2所示。

图2 路径平滑示意图

如果SN和NV之间可以展开平滑(去掉尖角∠SNV),用圆弧连接两个航线点。∠SNV的平分线和NV之间较小边的中垂线相交于P1,P1为圆心SN和NV之间相切的圆,则该圆半径表达式为:

(11)

以同样的方式对NV和NV展开处理,3个直线段和2个圆弧段组成了S→F之间的最优路径,以此完成整个航空物流运输路径的规划。

4 实验分析

为了验证考虑多因素耦合的航空物流运输路径规划方法的整体有效性,需要对其展开相关测试。利用百度地图获取部分地理数据作为实验测试范围。设置起始点为G,终点为H,采用文献[2]提出的MTSP路轨规划模型及其遗传算法、文献[3]提出的人工鱼群算法、文献[4]提出的改进A*(A-star)算法与所提方法对航空物流运输路径展开规划,规划结果如图3所示。

图3 航空物流路径规划结果

由图3可知四种方法均能完成航空物流运输路径规划任务。所提方法在路径规划时途经太原和北京两个重要中转点,而MTSP路轨规划模型及其遗传算法(文献[2]方法)、人工鱼群算法(文献[3]方法)、改进A*(A-star)算法(文献[4]方法)并没有途经此处,表明所提方法在航空物流运输路径规划中可应用性更强。

航空物流运输路径规划优化时间直接影响着路径规划结果,采用不同方法的路径规划结果如图4所示。

图4 不同方法的路径规划时间

分析图4可知,所提方法路径规划时间最短,始终保持在10ms以内,其它三种方法在航空物流运输路径规划中的时间是所提方法的30倍以上,表明所提方法在路径规划中机动性强、路径优化速度快。因为所提方法考虑多耦合因素构建多约束航空物流运输路径规划模型,采用实时优化蚁群算法展开多路径同时优化。大大缩短了路径规划的时间。

将航程(飞行器的实际飞行距离)作为指标,不同路径规划方法的航程如表1所示。

表1 不同路径规划方法的航程

由表1可知。起始点和终点一致的情况下,经过多次实验,所提方法的航空物流平均航程在1194km,远低于其它三种方法的运输航程,表明所提方法在航空物流运输路径规划中效率高,可以有效降低运输成本。

将高度代价作为指标,不同方法的规划路径的高度代价如图5所示。

图5 不同方法的高度代价

由图5可知所提方法在多次实验后的高度代价波动稳定,MTSP路轨规划模型及其遗传算法、人工鱼群算法和改进A*(A-star)算法的高度代价波动很大,并且人工鱼群算法高度代价最高达到600,而所提方法的高度代价仅在190,实验结果表明所提方法在航空物流运输路径规划中性能高。

航空物流运输的路径规划必须在减少全局路径危险程度的基础上完成运输任务,因此在本节实验中,选取危险度作为方法评价指标。危险度指标的计算公式如下:

(12)

式中,λ(pij)表示运输飞机根据飞行点R和障碍物pij处的高度得到的风险位置,rsafe表示安全阈值。n为局部航空环境中邻近的障碍物数量。根据此公式计算不同方法的危险度量化指标如图6所示。

图6 不同方法的危险度

分析图6可知,文献方法的危险度始终在0.6以上,其中文献[2]方法的最高危险度高于0.8。所提方法对航空物流路径规划的危险度最高值在0.3左右,并且随着实验次数的增加逐渐降低,最低值低于0.1。此测试结果表明考虑多因素耦合的航空物流运输路径规划方法精准度高。

5 结束语

航空物流运输中存在同地点多路径,无法快速选择最优路径的问题,为了解决该问题,提出考虑多因素耦合的航空物流运输路径规划方法。通过对航空物流运输路径的干扰因素展开分析,构建多约束航空物流运输路径规划模型,采用实时优化蚁群算法获取模型最优解,实现航空物流运输路径的规划。解决了目前存在的问题,为今后航空物流运输路径研究奠定了基础。