科学技术与工程

P=6	文献模型(RP)		GAP/%
第一组	1 038.1	0.16	1 038.1	0.11
第二组	1 230.5	0.23	1 230.5	0.20
第三组	1 613.4	0.16	1 613.4	0.19
第四组	1 176.5	0.17	1 176.5	0.25
第五组	1 196.5	0.03	1 196.5	0.22

P=6	文献模型(RP)		GAP/%
第一组	1 038.1	0.16	1 038.1	0.11
第二组	1 230.5	0.23	1 230.5	0.20
第三组	1 613.4	0.16	1 613.4	0.19
第四组	1 176.5	0.17	1 176.5	0.25
第五组	1 196.5	0.03	1 196.5	0.22

P=12	文献模型(RP)		GAP/%
第一组	2 319.3	20.67	2 319.3	10.61	0
第二组	2 584.4	80.39	2 585.4	14.49	0.04
第三组	2 419.2	112.77	2 419.2	9.70	0
第四组	2 112.6	20.63	2 112.6	3.14	0
第五组	2 340.2	15.33	2 340.2	5.55	0

P=12	文献模型(RP)		GAP/%
第一组	2 319.3	20.67	2 319.3	10.61	0
第二组	2 584.4	80.39	2 585.4	14.49	0.04
第三组	2 419.2	112.77	2 419.2	9.70	0
第四组	2 112.6	20.63	2 112.6	3.14	0
第五组	2 340.2	15.33	2 340.2	5.55	0

P=15	文献模型(RP)		GAP/%
第一组	3 478	1 911.33	3 478	14.95
第二组	3 611	1 874.69	3 611	146.20
第三组	4 516.9	2 150.02	4 516.9	14.09
第四组	3 874.3	1 129.59	3 874.3	9.17
第五组	3 293.7	1 046.70	3 293.7	110.02

P=15	文献模型(RP)		GAP/%
第一组	3 478	1 911.33	3 478	14.95
第二组	3 611	1 874.69	3 611	146.20
第三组	4 516.9	2 150.02	4 516.9	14.09
第四组	3 874.3	1 129.59	3 874.3	9.17
第五组	3 293.7	1 046.70	3 293.7	110.02

P=20	文献模型(RP)		GAP/%
第一组	4 068.9	10 198.7	4 104.9	956.41	0.88
第二组	3 207.9	3 928.63	3 234.9	6 012.49	0.84
第三组	3 211.4	6 989.42	3 211.4	103.92	0
第四组	4 786.4	5 885.08	4 816.4	1 716.56	0.63
第五组	4 700.7	5 340.11	4 750.7	1 035.55	1.06

P=20	文献模型(RP)		GAP/%
第一组	4 068.9	10 198.7	4 104.9	956.41	0.88
第二组	3 207.9	3 928.63	3 234.9	6 012.49	0.84
第三组	3 211.4	6 989.42	3 211.4	103.92	0
第四组	4 786.4	5 885.08	4 816.4	1 716.56	0.63
第五组	4 700.7	5 340.11	4 750.7	1 035.55	1.06

算例	W=20 h			W=40 h
a1	2 306.3	96.98	2 319.3	4.19	2 319.3	4.63
a2	2 576.4	64.76	2 584.4	54.44	2 589.4	4.55
a3	2 415.2	15.56	2 419.2	3.70	2 419.2	7.59
a4	2 098.6	132.92	2 110.6	6.91	2 112.6	2.72
a5	2 339.2	4.86	2 340.2	3.02	2 340.2	2.91

算例	W=20 h			W=40 h
a1	2 306.3	96.98	2 319.3	4.19	2 319.3	4.63
a2	2 576.4	64.76	2 584.4	54.44	2 589.4	4.55
a3	2 415.2	15.56	2 419.2	3.70	2 419.2	7.59
a4	2 098.6	132.92	2 110.6	6.91	2 112.6	2.72
a5	2 339.2	4.86	2 340.2	3.02	2 340.2	2.91

算例	W=20 h			W=40 h
b1	3 462	464.55	3 478	10.50	3 478	9.30
b2	3 611	102.67	3 611	175.53	3 611	141.06
b3	4 505.9	7155.77	4 516.9	11.83	4 516.9	12.92
b4	3 860.3	257.44	3 874.3	4.48	3 874.3	4.95
b5	3 288.7	411.77	3 295.7	80.34	3 298.7	27.02

算例	W=20 h			W=40 h
b1	3 462	464.55	3 478	10.50	3 478	9.30
b2	3 611	102.67	3 611	175.53	3 611	141.06
b3	4 505.9	7155.77	4 516.9	11.83	4 516.9	12.92
b4	3 860.3	257.44	3 874.3	4.48	3 874.3	4.95
b5	3 288.7	411.77	3 295.7	80.34	3 298.7	27.02

算例	CAP=35 t			CAP=45 t
c1	2 316.3	25.70	2 319.3	3.63	2 319.3	5.00
c2	2 578.4	232.83	2 585.4	9.16	2 585.4	4.52
c3	2 412.2	52.22	2 419.2	4.50	2 419.2	3.84
c4	2 108.6	11.58	2 109.6	3.59	2 112.6	3.11
c5	2 326.2	100.75	2 336.2	5.55	2 340.2	4.20

算例	CAP=35 t			CAP=45 t
c1	2 316.3	25.70	2 319.3	3.63	2 319.3	5.00
c2	2 578.4	232.83	2 585.4	9.16	2 585.4	4.52
c3	2 412.2	52.22	2 419.2	4.50	2 419.2	3.84
c4	2 108.6	11.58	2 109.6	3.59	2 112.6	3.11
c5	2 326.2	100.75	2 336.2	5.55	2 340.2	4.20

算例	CAP=45 t			CAP=55 t
d1	3 476.0	20.63	3 478.0	9.53	3 478.0	11.64
d2	3 605.0	1 004.63	3 610.0	161.83	3 611.0	101.51
d3	4 514.9	89.58	4 516.9	22.27	4 516.9	25.44
d4	3 865.3	257.06	3 867.3	106.56	3 870.3	35.39
d5	3 288.7	473.58	3 290.7	258.89	3 293.7	265.09

算例	CAP=45 t			CAP=55 t
d1	3 476.0	20.63	3 478.0	9.53	3 478.0	11.64
d2	3 605.0	1 004.63	3 610.0	161.83	3 611.0	101.51
d3	4 514.9	89.58	4 516.9	22.27	4 516.9	25.44
d4	3 865.3	257.06	3 867.3	106.56	3 870.3	35.39
d5	3 288.7	473.58	3 290.7	258.89	3 293.7	265.09

航空货运恢复问题的时空网络建模方法

PDF下载

袁媛 , 李欣琪

科学技术与工程 | 论文·航空、航天 2025,25(17): 7398-7404

收起

科学技术与工程 | 论文·航空、航天 2025, 25(17): 7398-7404

航空货运恢复问题的时空网络建模方法

全屏

袁媛, 李欣琪

作者信息

沈阳航空航天大学经济与管理学院, 沈阳 110136

袁媛(1986—),女,汉族,辽宁沈阳人,博士,副教授。研究方向:航空运营管理、生产与物流调度、数学建模与优化。E-mail:yy_sau@163.com。

Spatio-temporal Network Modeling Method for Air Cargo Recovery Problem

Yuan YUAN, Xin-qi LI

Affiliations

College of Economics and Management, Shenyang Aerospace University, Shenyang 110136, China

出版时间: 2025-06-18 doi: 10.12404/j.issn.1671-1815.2406835

文章导航

摘要

收起

随着航空货运量的增加,货运计划频繁因货物需求扰动的影响而中断,因此重新安排航班计划是航空货运恢复的核心问题。在需求临时增加的扰动下,以航空公司的利润最大化为目标,提出了一个基于时空网络方法建立的航空货运恢复模型,重新安排飞机路线、货物路线及航班,并通过增加惩罚因子的方式尽可能地保留初始航班计划。为验证模型有效性,利用CPLEX求解器对模型进行求解,将所提出的基于时空网络的航空货运恢复模型与文献中的模型进行对比,结果表明:所提出的模型在计算效率与寻找最优值方面均有较大优势,且随着算例规模的增大,优势愈加明显。分析了模型的求解结果对时间窗宽度与飞机承载力的敏感性,结果发现:时间窗越窄,求解速度越慢,而随着时间窗宽度的增大,求解速度加快并趋于稳定;随着飞机承载力逐渐增大,模型的求解速度更快并趋于稳定。

关键词

航空运输 / 航空货物 / 需求扰动 / 恢复问题 / 时空网络 / 同时取送货 / 物流配送

Abstract

收起

With the increase of air cargo volume, cargo plans are frequently interrupted due to disruptions in cargo demand, so rescheduling flight schedules is the core issue for air cargo recovery. An air cargo recovery model based on spatio-temporal network method was proposed with the goal of maximizing the profits of airlines under the disturbance of temporary increase in demand. Aircraft routes, cargo routes and flights were reorganized in the model and the initial flight plan was preserved as much as possible by adding penalty factors. In order to verify the effectiveness of the model, the model was solved using CPLEX solver. The proposed spatio-temporal network-based air cargo recovery model was compared with the model in reference. The results show that the proposed model has significant advantages in computational efficiency and finding optimal values, and the advantages become more apparent with the increase of the case size. The sensitivity of the model's solution results to the time window width and aircraft carrying capacity was analyzed. The results show that the narrower the time window, the slower the solution speed, while as the time window width increases, the solution speed accelerates and tends to stabilize. As the carrying capacity of the aircraft gradually increases, the solving speed of the model becomes faster and tends to be stable.

Key words

air transportation / air cargo / demand disruption / recovery problem / spatio-temporal networks / simultaneous pick-up and delivery / logistics delivery

引用本文

袁媛, 李欣琪. 航空货运恢复问题的时空网络建模方法. 科学技术与工程, 2025 , 25 (17) : 7398 -7404 . DOI: 10.12404/j.issn.1671-1815.2406835

Yuan YUAN, Xin-qi LI. Spatio-temporal Network Modeling Method for Air Cargo Recovery Problem[J]. Science Technology and Engineering, 2025 , 25 (17) : 7398 -7404 . DOI: 10.12404/j.issn.1671-1815.2406835

正文

收起

国内航空货运量的持续增加推动了航空运输业的高速发展^[1]。航空货物可以通过专用货机运输,也可以利用在行李装载后客机腹舱的备用容量运输。全货机能够运输客机无法承载的特殊载荷,如超大物品或危险货物。然而,由于货物预订的时间窗口较短,需求扰动通常发生在飞机起飞前几个小时^[2],导致飞行计划中断。因此,在许多航空公司,鉴于需求的不稳定性,航班计划的恢复由接受过规则培训的调度员手动完成^[3],包括调整飞机的航线、改变货物的运输路线,甚至取消或增加航班,以恢复航空公司的正常运营。

虽然针对航空货运恢复问题的研究起步较晚,但对于航空客运恢复问题,已有许多学者进行了大量且深入的研究。Zhang等^[4-5]依次考虑飞机恢复与机组人员调度,之后解决了飞机和乘客时间表综合恢复问题。Liang等^[6]介绍了一种求解飞机恢复问题的启发式方法,重新安排航班和分配机队。杨新湦等^[7]考虑航班不正常一体化恢复,综合考虑飞机、机组与旅客恢复。陆溪等^[8]从空铁联运的角度出发,在航班延误后给旅客提供更灵活的恢复方案。 Evler等^[9]解决了飞机分配、机组人员和飞机调度问题。Yang等^[10]在生成可行路径后分配给飞机以恢复飞行计划。Ding等^[11]制定了一个包含各种恢复决策的框架,并将深度强化学习与可变邻域搜索算法相结合。Lahooti等^[12]提出一种双目标的飞机和机组人员恢复模型,使用改进的禁忌搜索方法求解。Zang^[13]在中断发生之前进行预测,构建主动飞机恢复模型。Peng等^[14]针对航班恢复问题,建立以恢复成本为目标的混合整数规划模型,设计Benders 分解算法确定航班取消、飞机更换以及延误航班的起飞时间,航空客运恢复问题的恢复对象主要包括飞机路径、航班、机组人员及旅客。

相比于客运中的旅客恢复,货运航司在调整预先安排的货运路线时更灵活,成本也更低。在发生飞行中断时,只要在规定的截止日期前运送货物即可^[15]。Delgado等^[16]研究了解决航空货运恢复问题,介绍了航空货运时间表恢复问题,并将其表述为整数线性规划问题。航空公司需要重新安排航班和货物路线,以应对临时的需求扰动。该研究基于航班连接网络进行建模,属于带时间窗的车辆路径问题的变体,并考虑了3种不同的机组人员管理政策,以评估改变原始时间表的成本。Delgado等^[2]进一步研究了航班改期问题,以应对短期内货物需求的变化。为了增加灵活性,考虑了两种不同的货物分配策略,并使用基于列生成与启发式相结合的方法求解该问题。Xiao等^[17]通过考虑直通货物连接和短直通货物连接,生成所有可能的货物路径。Huang等^[15]进一步提出了飞机和货物恢复决策的综合恢复问题,基于航班连接网络制定了两个模型:一个是基于弧的模型,另一个是基于串的模型。基于弧的模型由Cplex商业求解器直接求解。对于串的模型,基于机器学习的行列生成方法来求解。Mousavi等^[18]提供了4种不同的恢复策略,包括重新安排航班、将航班重新分配给机队、提高飞机速度和取消航段,以在满足更多需求的同时最大限度地减少惩罚成本。为提高求解效率,提出了一种启发式算法。除了针对全货机的恢复问题外,Forkink^[19]还为使用全货机和客机的联合航空公司开发了一个机队调度模型,以应对新型冠状病毒肺炎大流行期间出现的全球需求扰动。该模型通过重新安排全货机航班、运输货物的客运航班以及重新安排运输路线,最大限度地提高航空公司的总运营利润。

综上分析,目前航空运输中的恢复问题主要集中在航空客运中,而随着航空货运量的不断增加,需求扰动频繁出现,越来越多的学者开始关注航空货运恢复问题的研究,但解决方案还不完善,所提出的数学模型大多以航班连接网络的方式建立,运用列生成方法求解,还未有学者针对模型的完善进行研究。鉴于此,现考虑需求增加且带有时间窗的情形,使用时空网络方式建立航空货运恢复模型,以航空公司的利润最大为优化目标,在规定时间内尽可能地满足货物订单的运输需求,并最大限度地保留初始的运输计划。运用CPLEX求解器进行求解,旨在重新安排飞机路线、货物路线及航班,恢复航空货运计划,为需求扰动下的航空货运恢复问题提供理论依据和决策支持。

1 问题描述

收起

问题及符号设置均使用了文献[2]的设定,某航空公司运营一支由k架飞机组成的全货机机队K。每架飞机都具有最大承载能力CAP^k以及运输初始货物订单的初始计划FB^k,即初始航班计划。然而在初始航班计划执行前,货物订单量临时增加,此时有一组订单P={1,2,…,$\left|P\right|$}需要运输,每个订单包括一组已知的取货与送货位置,均位于机场,且取货与送货活动带有各自的服务时间窗口,飞机只被允许在时间窗内服务,取货时间窗口的开始表示订单发布时间,送货时间窗口的结束表示交货截止日期。由于航空货运需求的变化通常在计划前几小时内发生,因此需要尽快制订新的运输计划以满足新的订单需求。优先级ϕ_i可用于优先考虑初始订单或某些特定客户。为了减少航空公司经济损失,引入惩罚系数ω,以最大限度地保留初始航班计划。

在基于时空网络的方法建立的航空货运恢复模型中,网络中的每个节点代表一个事件,代表飞机在某机场的起飞或降落及其时间,以及订单的装载和卸载。机场中包含一组订单,它合并了给定飞机将要运输的订单的取货和送货节点。

所研究的问题是带时间窗口的取送货问题(pickup and delivery problem with time windows,PDPTW)的变体。飞机从某一机场出发,经过飞行航段,到达机场进行取送货活动,结束后返回虚拟机场。图1是一个用时空网络构建的航空货运恢复问题的示例。现有4个机场A、B、C、D,共带有6个需求订单,各个订单的初始位置如航段1所对应的列所示,订单1、订单2、订单3位于机场A,订单4、订单5位于机场C,订单6位于机场B。各个订单运输任务完成后的位置如航段4所对应的列所示。所以,飞机K₂的运输计划是在第一个航段到达C机场装载货物4、5,在第二个航段到达D机场卸载货物4,在第三个航段到达B机场卸载货物5并装载货物6,最后在第四个航段到达A机场卸载货物6。

2 模型构建

收起

2.1 模型假设

(1)货物不能在飞机之间转运。

(2)根据行业惯例,承载能力限制以重量表示。

(3)飞机可运输所有货物,不考虑飞机类型与货物类型的匹配。

(4)货物可进行拆分,即在满足时间窗的前提下,一个货物可由多架飞机运输。

(5)初始计划涉及的货物订单部分完成或全部未完成运输,不进行处罚。但优先级ϕ_i可以用于优先考虑初始订单或特定客户。

(6)飞机任务结束均到达虚拟机场。

2.2 参数及变量说明

X_mnkl为决策变量,如果飞机k第l个航段从机场m到达机场n,则等于1,否则为0。

q_ikl为决策变量,表示飞机k第l个航段取/送订单i的重量,q_i⁺kl>0, q_i^-kl<0,重量单位统一为吨(t)。

y_ikl为辅助变量,表示如果飞机k在第l个航段取/送订单i,则等于1,否则为0。

T_kl为飞机k到达第l个航段的时间。

Q_kl为飞机k离开第l个航段时的载货量。

${\mu }_{u,v}^{k}$为辅助变量,如果飞机k的初始航班(u,v)被取消,则等于1,否则为0。

${\omega }_{u,v}^{k}$为飞机k的初始航班(u,v)被取消所施加的惩罚成本。

K为飞机集合,$k\in K$。

P为订单集合,$i\in P$,i⁺表示取货订单,i^-表示送货订单。

L为航段集合,$l\in L$。

S为初始计划涉及的机场集合。

N为取送订单节点集合,$N=\{{i}^{+},{i}^{-}\}$。

NK为所有机场集合,$m,n\in $NK,包括虚拟机场0。

FB^k为飞机k初始计划的飞行弧集合,$(u,v)\in $FB^k,其中$u,v\in S$。

C_m,n为飞机由机场m到机场n的运行成本。

t_m,n为飞机在机场m与机场n之间的飞行时间,时间单位统一为小时(h)。

${\varphi }_{i}$为与订单i相关的优先级,对于${\varphi }_{i}$更大的订单i,优先取送该订单。

r_i为运输订单i的运费。

d_i为订单i的装/卸货时间。

D_i为订单i的总货物需求量。

CAP^k为飞机k的最大承载能力。

e_i为可到达订单节点i的最早时刻。

l_i为可到达订单节点i的最晚时刻。

2.3 航空货运恢复模型

该模型的目标是实现航空公司利润最大化,其目标函数如式(1)所示,由3部分组成,分别为运输订单任务的收入、飞机运行所产生的飞行成本和因初始航班计划取消而产生的惩罚成本。

(1)$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}[\sum _{k\in K}\sum _{i\in P}\sum _{l\in L}{\varphi }_{i}{r}_{i}{q}_{{i}^{+}kl}-\\ 　　\sum _{k\in K}\sum _{m\in \mathrm{N}\mathrm{K}}\sum _{n\in \mathrm{N}\mathrm{K}}\sum _{l\in L}{X}_{mnkl}{C}_{m,n}-\\ 　　\sum _{k\in K}\sum _{(u,v)\in \mathrm{F}{\mathrm{B}}^{k}}{\omega }_{u,v}^{k}{\mu }_{u,v}^{k}]\end{array}$

每当初始计划航班(u,v)被取消或由不同的飞机操作时,约束条件[式(2)]确定航班偏离初始计划,从而在目标函数中施加惩罚。

(2)${\mu }_{u,v}^{k}\ge 1-\sum _{m\in S}\sum _{n\in S}\sum _{l\in L}{X}_{mnkl},\forall (u,v)\in \mathrm{F}{\mathrm{B}}^{k},k\in K$

为了保证飞机飞行计划的有效性,约束条件[式(3)]确保所有有效飞行航段(即$m\ne n\ne 0$时)排在虚拟航段(即m=n=0时)之前,虚拟航段不具有实际意义。

(3)$\begin{array}{l}\sum _{m\in \mathrm{N}\mathrm{K},m\ne 0}\sum _{　n\in \mathrm{N}\mathrm{K}}{X}_{mnk(l-1)}\ge \sum _{m\in \mathrm{N}\mathrm{K},m\ne 0}\sum _{　n\in \mathrm{N}\mathrm{K}}{X}_{mnkl},\\ 　　　　\forall k\in K,l\in L\end{array}$

约束条件[式(4)]和约束条件[式(5)]共同保证了除虚拟航段以外,所有航段均由飞行航段构成,由一个机场飞往另一个不同的机场,并且虚拟节点只能连接虚拟节点,构成虚拟航段。

(4)$\begin{array}{l}\sum _{m\in \mathrm{N}\mathrm{K}}\sum _{　n\in \mathrm{N}\mathrm{K}}{X}_{mnkl}=1,\forall k\in K,l\in L,m\ne n或\\ 　　　　　m=n=0\end{array}$

(5)$\sum _{n\in \mathrm{N}\mathrm{K}}{X}_{0nkl}=0,\forall k\in K,l\in L$

式(6)是飞机执行航段间的衔接平衡约束,确保了飞行可行路线的节点的连续性。

(6)$\begin{array}{l}\sum _{n\in \mathrm{N}\mathrm{K}}{X}_{mnkl}-\sum _{n\in \mathrm{N}\mathrm{K}}{X}_{mnk(l-1)}=0,\\ 　　\forall m\in \mathrm{N}\mathrm{K},k\in K,l\in L\end{array}$

约束条件[式(7)]为每个飞机设置了到达航段的时间,飞机到达航段的时间不小于该飞机到达前一个航段的时间、在前一个航段的装载或卸载货物时间和两航段的飞行时间之和,其中,一个航段由前后两个连接机场组成,到达航段的时间为到达该航段前端机场时间。

(7)$\begin{array}{l}{T}_{kl}\ge {T}_{k(l-1)}+\sum _{m\in \mathrm{N}\mathrm{K}}\sum _{n\in \mathrm{N}\mathrm{K}}{t}_{mn}{X}_{mnk(l-1)}+\sum _{i\in N}{d}_{i}{y}_{ik(l-1)},\\ 　　\forall k\in K,l\in L\end{array}$

约束条件[式(8)、式(9)、式(10)]是对飞机载重量的约束。式(8)确保飞机离开航段时的载重量不小于该飞机离开前一航段时的载重量与飞机在该航段装卸货物重量之和;式(9)约束了每架飞机离开第一个航段时飞机载重不小于飞机在该航段装卸货物重量之和;式(10)保证飞机在虚拟航段载货量为0。其中$M\ge \mathrm{C}\mathrm{A}{\mathrm{P}}^{k}$,M取值接近最小值。

(8)${Q}_{kl}\ge {Q}_{k(l-1)}+\sum _{i\in N}{q}_{ikl},\forall k\in K,l\in L$

(9)${Q}_{k1}\ge \sum _{i\in N}{q}_{ik1},\forall k\in K$

(10)${Q}_{kl}\le M(1-{X}_{00kl}),\forall k\in K,l\in L$

约束条件[式(11)]与飞机k的承载能力有关,飞机实时载重不得超过其最大承载能力。

(11)$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\{0,\sum _{i\in N}{q}_{ikl}\}\le {Q}_{kl}\\ \le \mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{C}\mathrm{A}{\mathrm{P}}^{k},\mathrm{C}\mathrm{A}{\mathrm{P}}^{k}+\sum _{i\in N}{q}_{ikl}\},\\ \forall k\in K,l\in L\end{array}$

约束条件[式(12)和式(13)]对订单i的运输量进行了控制。式(12)所有被使用的飞机对任一订单的装货量总和不得超过该订单所需的总货物运输量;式(13)约束了飞机k对订单i的实际装货量和卸货量相等。

(12)$\sum _{l\in L}\sum _{k\in K}{q}_{ikl}\le {D}_{i},\forall i\in P$

(13)$\sum _{l\in L}{q}_{{i}^{+}kl}+\sum _{l\in L}{q}_{{i}^{-}kl}=0,\forall i\in P,k\in K$

约束条件[式(14)]确保每架被使用的飞机到达任意订单节点至多一次。

(14)$\sum _{l\in L}{y}_{ikl}\le 1,\forall i\in N,k\in K$

飞机执行一个航段,包括飞机到达航段的前端机场、飞机处理前端机场的货物、离开前端机场。约束条件[式(15)和式(16)]共同确保了飞机在机场的停留时间在飞机在该机场取/送订单的时间窗[e_i,l_i]内。式(15)中$M\ge \mathrm{m}\mathrm{a}\mathrm{x}({e}_{i}+{d}_{i})$,式(16)中$M\ge \mathrm{m}\mathrm{a}\mathrm{x}({T}_{kl}-{d}_{i}-{l}_{i})$,M取值为满足条件的最小值。

(15)$\begin{array}{l}{T}_{k(l+1)}-\sum _{m\in \mathrm{N}\mathrm{K}}\sum _{n\in \mathrm{N}\mathrm{K}}{t}_{mn}{X}_{mnkl}\ge {e}_{i}+{d}_{i}-M(1-{y}_{ikl}),\\ 　　\forall i\in N,k\in K,l\in L\end{array}$

(16)$\begin{array}{l}{T}_{kl}-{d}_{i}\le {l}_{i}+M(1-{y}_{ikl}),\\ 　　\forall i\in N,k\in K,l\in L\end{array}$

约束条件[式(17)和式(18)]规定了变量y_ikl与变量q_ikl的关系。其中式(18)中M取值为100。

(17)${D}_{i}{y}_{ikl}\ge \left|{q}_{ikl}\right|,\forall i\in N,k\in K,l\in L$

(18)${y}_{ikl}\le M\left|{q}_{ikl}\right|,\forall i\in N,k\in K,l\in L$

约束条件[式(19)和式(20)]规定了变量y_ikl与变量X_mnkl的关系。

(19)$\begin{array}{l}{y}_{ikl}\le \sum _{n\in \mathrm{N}\mathrm{K}}{X}_{mnkl},\forall k\in K,l\in L,m\in \mathrm{N}\mathrm{K}\mathrm{且}\\ 　　m\ne 0,i\in N\end{array}$

(20)$\begin{array}{l}\sum _{i\in m}{y}_{ikl}\ge \sum _{n\in \mathrm{N}\mathrm{K}}{X}_{mnkl},\\ 　　\forall k\in K,l\in L,m\in \mathrm{N}\mathrm{K}\mathrm{且}m\ne 0\end{array}$

式(21)~式(23)定义了各个变量范围。

(21)$\begin{array}{l}{X}_{mnkl}\in \left\{\mathrm{0,1}\right\},\\ \forall m\in \mathrm{N}\mathrm{K},n\in \mathrm{N}\mathrm{K},k\in K,l\in L\end{array}$

(22)${q}_{ikl}\in R,\forall i\in N,k\in K,l\in L$

(23)${T}_{kl}\in {R}^{+},\forall k\in K,l\in L$

3 仿真验证

收起

3.1 算例数据

对航空货运恢复问题进行算例仿真分析,某航空公司有4架全货机可供使用,每架飞机均无飞行限制,设置订单数P分别为6、12、15、20的4种不同规模情境,每种规模生成五组数据,包含机场数量S、订单节点的位置、飞机数量K及各飞机最大承载能力CAP^k,初始计划FB^k、机场间的运行成本C_m,n及飞行时间t_m,n、飞机初始计划更改时施加的惩罚系数${\omega }_{u,v}^{k}$、订单i的需求量D_i和时间窗[e_i,l_i]等。

实验所使用的计算机硬件环境为1.60 GHz i5-10210U CPU,8 GB RAM以及Windows系统,运用C++编写代码,并采用Visual Studio环境下C++调用CPLEX来求解。

3.2 结果分析

为验证本文模型的有效性,使用上述生成的相同数据并利用CPLEX求解器对本文模型(简称为IM)与文献[2]中的模型(简称为RP)进行求解,4组订单数下所求得的目标函数值(Z)与其对应的求解时间(Time)的对比结果如表1所示。航段L最大值根据式(24)而定,具体数值可根据实际情况变动。GAP计算规则如式(25)所示。

(24)$L=\frac{\sum _{i\in P}{D}_{i}\left|P\right|}{\sum _{k\in K}\mathrm{C}\mathrm{A}{\mathrm{P}}^{k}}+3$

(25)$\mathrm{G}\mathrm{A}\mathrm{P}=\frac{Z\left(\mathrm{I}\mathrm{M}\right)-Z\left(\mathrm{R}\mathrm{P}\right)}{Z\left(\mathrm{R}\mathrm{P}\right)}\times 100\mathrm{\%}$

表1为分布在4个机场的6个订单的算例求解结果,可以发现本文模型(IM)与文献[2]模型(RP)的最优值全部一致,计算速度也基本相同,由于该规模的订单数量较少,两种模型寻找最优解的速度均较快,时间都在1 s以内,无明显差别。

表2为分布在6个机场的12个订单的算例求解结果,除第二组算例外,最优值均一致,在计算速度上,两个模型虽然无明显差别,但5组算例中IM计算速度全部快于RP。对第二组配送结果进行分析发现,两个模型的最优值不一致,IM的最优值更好,利润更高。RP的构建是以取送订单为节点,严格执行同一机场的订单节点时间窗,当飞机在某一机场取送货时,送货时间窗的开始时间在取货时间窗的结束时间之后,货物必须先装后卸,此时由于飞机承载能力的限制导致某些货物无法被运输,但在飞机卸货后离开机场时,飞机却存在剩余空间,显然违背了现实情况。而IM的建立是以机场为节点,不考虑同一机场内订单节点的执行顺序,飞机可在卸货之后装货,更好地利用货舱空间。

表3为分布在6个机场的15个订单的算例求解结果,第一组算例与第四组算例两模型均计算出最优值且最优值一致,但IM的计算最优值的速度明显更快,文献模型的计算时间在本文模型计算时间的100倍以上。对于其他3组算例,在同一计算环境下,RP并未得到最优解,且计算时间较长,而IM均在更短的时间内寻得最优解,证明了该模型在计算效率方面的优势,且该优势随着订单数量的增加愈加明显。

表4为分布在7个机场的20个订单的算例求解结果,RP计算时间较长且并未找到最优解,而IM依然可以在同一计算环境寻得最优解,且计算速度明显快于RP,虽然第二组IM计算时间相比RP更长,但RP并未得到最优解,GAP为0.84%。另外,相比于前三组订单规模,此规模两个模型所求得的目标函数值相差较大,GAP明显增加,证明了该模型对寻找最优值的积极影响。

实验结果表明,随着订单数量的增加,算例规模增大,本文模型在计算速度与寻找最优值方面的优势逐渐扩大,验证了该模型的有效性。

3.3 敏感性分析

3.3.1 时间窗宽度对计算结果的影响

实验发现,订单时间窗对模型的求解速度影响较大,且对RP与IM影响一致。现设置了20 、30 、40 h三组时间窗宽度W,表5和表6分别表示P=12与P=15时, IM在不同时间窗宽度下对应的求解结果。

由以上结果发现,当时间窗宽度最窄,即W=20 h时,各算例的计算速度明显最慢,该时间窗计算的最优值也劣于其他两组时间窗且相差较大。从整体上看,随着时间窗宽度的增加,计算速度随之加快并趋于稳定,W=30 h与W=40 h时的求解结果更接近。实验表明,订单的时间窗宽度对实验结果有影响,时间窗越窄,求解速度越慢,而随着时间窗宽度的增大,求解速度加快并趋于稳定。另外,算例b2的最优值在3组时间窗宽度下相同,计算时间也基本相同,说明该组数据在时间窗宽度为20 h时便已经容易找到最优值并趋于稳定。

3.3.2 飞机承载力对计算结果的影响

IM在P=12与P=15的订单规模下,分别设置了不同的飞机承载力参数,并保证飞机的总承载力少于全部订单总重量,算例中各飞机的最大承载力相等,其计算结果如表7和表8所示。

12个订单规模设置的3组飞机最大承载力分别为35、40、45 t,从整体角度分析,随着飞机承载力的增加,计算速度随之加快并趋于稳定,CAP=40 t与CAP=45 t时的求解结果更接近。15个订单规模设置的三组飞机最大承载力分别为45、50、55 t,当CAP=45 t时,各算例最优值最小,这是因为飞机虽然完成了所有订单需求,但由于飞机载重约束的限制,从而导致飞机运行成本增加,而随着飞机承载力的增加,计算速度随之加快并趋于稳定。

4 结论

收起

针对航空货运恢复问题展开研究,面对货物需求扰动,重新安排货运计划,以恢复航空公司运营。结论如下。

(1)在航空货运需求扰动背景下,以航空公司的利润最大化为目标,基于时空网络方法建立了航空货运恢复模型,以重新安排飞机路线、货物路线及航班,并通过增加惩罚因子的方式尽可能少地偏离初始计划。

(2)使用CPLEX求解器对本文模型(IM)与文献[2]模型(RP)求解,将结果作对比分析,验证了本文模型(IM)的有效性。实验结果表明,随着订单数量的增加,算例规模增大,本文模型在计算速度与寻找最优值方面的优势逐渐扩大。

(3)分析了模型的求解结果对时间窗宽度与飞机承载力的敏感性,发现时间窗越窄,求解速度越慢,而随着时间窗宽度的增大,求解速度加快并趋于稳定;随着飞机承载力逐渐增大,模型的求解速度更快并趋于稳定。

研究丰富了需求扰动下航空货运恢复问题的相关理论研究,针对已有研究的数学模型不足之处进行改进。最后实验表明,改进模型能够较大提升模型求解速度,建立模型的方法实用性更强,帮助航空公司从需求扰动中快速恢复,在尽可能少地改变初始计划的情况下制订新的运输计划。

基金

收起

国家自然科学基金青年项目(71802141)
辽宁省高校基本科研业务费项目(LJ112410143086)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

龙浩南, 黄安迪, 杨升平. 我国航空物流发展现状分析与建议[J]. 中国航务周刊, 2023(38): 48-50.

Long

Haonan

, Huang

Andi

, Yang

Shengping

. Analysis and suggestions on the development status of air logistics in China[J]. China Shipping Gazette, 2023(38): 48-50.

[2]

Delgado

, Mora

. A matheuristic approach to the air-cargo recovery problem under demand disruption[J]. Journal of Air Transport Management, 2021, 90: 101939.

[3]

Abdelghany

, Ekollu

, Narasimhan

, et al. A proactive crew recovery decision support tool for commercial airlines during irregular operations[J]. Annals of Operations Research, 2004, 127(1): 309-331.

[4]

Zhang

, Lau

H Y K H

, Yu

. A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems[J]. Computers & Industrial Engineering, 2015, 87: 436-453.

[5]

Zhang

, Yu

, Desai

, et al. A math-heuristic algorithm for the integrated air service recovery[J]. Transportation Research Part B: Methodological, 2016, 84: 211-236.

[6]

Liang

, Xiao

, Qian

, et al. A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility[J]. Transportation Research Part B, 2018, 113: 70-90.

[7]

杨新湦, 屈琮博, 王梓旭. 巡航速度控制下航空公司受扰航班一体化恢复[J]. 科学技术与工程, 2021, 21(9): 3848-3854.

Yang

Xinsheng

, Qu

Congbo

, Wang

Zixu

. Integrated recovery of airline disrupted flights with cruise speed control[J]. Science Technology and Engineering, 2021, 21(9): 3848-3854.

[8]

陆溪, 邵荃. 基于空铁联运的延误旅客行程恢复方法[J]. 科学技术与工程, 2022, 22(27): 12150-12155.

, Shao

Quan

. Itinerary recovery method for delayed passengers based on air-rail combined transport[J]. Science Technology and Engineering, 2022, 22(27): 12150-12155.

[9]

Evler

, Lindner

, Fricke

, et al. Integration of turnaround and aircraft recovery to mitigate delay propagation in airline networks[J]. Computers & Operations Research, 2022, 138: 105602.

[10]

Yang

, Wang

, Yu

, et al. Aircraft route recovery based on distributed integer programming method[J]. Mathematical Biosciences and Engineering, 2023, 20(7): 12802-12819.

[11]

Ding

, Wandelt

, Wu

, et al. Towards efficient airline disruption recovery with reinforcement learning[J]. Transportation Research Part E: Logistics and Transportation Review, 2023, 179: 103295.

[12]

Lahooti

E M

, Rashidi

K A

, Baradaran

. A bi-objective model for aircraft and crew recovery considering individual flight legs and maintenance requirements[J]. Engineering Optimization, 2023: 1-27.

[13]

Zang

, Zhu

, et al. A proactive aircraft recovery approach based on airport spatiotemporal network supply and demand coordination[J]. Computers & Operations Research, 2024, 165: 106599.

[14]

Peng

, Hu

, Xia

. A study on disrupted flight recovery based on logic-based benders decomposition method[J]. Aerospace, 2024, 11(5): 378.

[15]

Huang

, Xiao

, Zhou

, et al. A machine learning based column-and-row generation approach for integrated air cargo recovery problem[J]. Transportation Research Part B: Methodological, 2023, 178: 102846.

[16]

Delgado

, Sirhan

, Katscher

, et al. Recovering from demand disruptions on an air cargo network[J]. Journal of Air Transport Management, 2020, 85: 101799.

[17]

Xiao

, Guo

, Huang

, et al. Integrated aircraft tail assignment and cargo routing problem with through cargo consideration[J]. Transportation Research Part B: Methodological, 2022, 162: 328-351.

[18]

Mousavi

, Akbarpour

S M

, Mirzapour Al-e-Hashem

. Providing an integrated pramework for an air-cargo network to recover from demand uncertainties and flight disruptions[J]. Social Science Research Network Electronic Journal, 2022, 10: 4310950.

[19]

Forkink

. Developing a fleet scheduling model for a combination carrier using both full-freighters and passenger aircraft under a demand disruption[D]. Delftl: Delft University of Technology, 2021.

2025年第25卷第17期

PDF下载

132

引用本文

BibTeX

文章信息

doi: 10.12404/j.issn.1671-1815.2406835

接收时间：2024-09-11
首发时间：2025-12-15
出版时间：2025-06-18

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-09-11

基金

国家自然科学基金青年项目(71802141)

辽宁省高校基本科研业务费项目(LJ112410143086)

作者信息

沈阳航空航天大学经济与管理学院, 沈阳 110136

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kxjsygc/CN/10.12404/j.issn.1671-1815.2406835

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

P=6	文献模型(RP)		GAP/%
第一组	1 038.1	0.16	1 038.1	0.11
第二组	1 230.5	0.23	1 230.5	0.20
第三组	1 613.4	0.16	1 613.4	0.19
第四组	1 176.5	0.17	1 176.5	0.25
第五组	1 196.5	0.03	1 196.5	0.22

P=6

文献模型(RP)

本文模型(IM)

GAP/%

Time/s

第一组

1 038.1

0.16

1 038.1

0.11

第二组

1 230.5

0.23

1 230.5

0.20

第三组

1 613.4

0.16

1 613.4

0.19

第四组

1 176.5

0.17

1 176.5

0.25

第五组

1 196.5

0.03

1 196.5

0.22

P=12	文献模型(RP)		GAP/%
第一组	2 319.3	20.67	2 319.3	10.61	0
第二组	2 584.4	80.39	2 585.4	14.49	0.04
第三组	2 419.2	112.77	2 419.2	9.70	0
第四组	2 112.6	20.63	2 112.6	3.14	0
第五组	2 340.2	15.33	2 340.2	5.55	0

P=12

文献模型(RP)

本文模型(IM)

GAP/%

Time/s

第一组

2 319.3

20.67

2 319.3

10.61

第二组

2 584.4

80.39

2 585.4

14.49

0.04

第三组

2 419.2

112.77

2 419.2

9.70

第四组

2 112.6

20.63

2 112.6

3.14

第五组

2 340.2

15.33

2 340.2

5.55

P=15	文献模型(RP)		GAP/%
第一组	3 478	1 911.33	3 478	14.95
第二组	3 611	1 874.69	3 611	146.20
第三组	4 516.9	2 150.02	4 516.9	14.09
第四组	3 874.3	1 129.59	3 874.3	9.17
第五组	3 293.7	1 046.70	3 293.7	110.02

P=15

文献模型(RP)

本文模型(IM)

GAP/%

Time/s

第一组

3 478

1 911.33

3 478

14.95

第二组

3 611

1 874.69

3 611

146.20

第三组

4 516.9

2 150.02

4 516.9

14.09

第四组

3 874.3

1 129.59

3 874.3

9.17

第五组

3 293.7

1 046.70

3 293.7

110.02

P=20	文献模型(RP)		GAP/%
第一组	4 068.9	10 198.7	4 104.9	956.41	0.88
第二组	3 207.9	3 928.63	3 234.9	6 012.49	0.84
第三组	3 211.4	6 989.42	3 211.4	103.92	0
第四组	4 786.4	5 885.08	4 816.4	1 716.56	0.63
第五组	4 700.7	5 340.11	4 750.7	1 035.55	1.06

P=20

文献模型(RP)

本文模型(IM)

GAP/%

Time/s

第一组

4 068.9

10 198.7

4 104.9

956.41

0.88

第二组

3 207.9

3 928.63

3 234.9

6 012.49

0.84

第三组

3 211.4

6 989.42

3 211.4

103.92

第四组

4 786.4

5 885.08

4 816.4

1 716.56

0.63

第五组

4 700.7

5 340.11

4 750.7

1 035.55

1.06

算例	W=20 h			W=40 h
a1	2 306.3	96.98	2 319.3	4.19	2 319.3	4.63
a2	2 576.4	64.76	2 584.4	54.44	2 589.4	4.55
a3	2 415.2	15.56	2 419.2	3.70	2 419.2	7.59
a4	2 098.6	132.92	2 110.6	6.91	2 112.6	2.72
a5	2 339.2	4.86	2 340.2	3.02	2 340.2	2.91

算例

W=20 h

W=30 h

W=40 h

Time/s

2 306.3

96.98

2 319.3

4.19

2 319.3

4.63

2 576.4

64.76

2 584.4

54.44

2 589.4

4.55

2 415.2

15.56

2 419.2

3.70

2 419.2

7.59

2 098.6

132.92

2 110.6

6.91

2 112.6

2.72

2 339.2

4.86

2 340.2

3.02

2 340.2

2.91

算例	W=20 h			W=40 h
b1	3 462	464.55	3 478	10.50	3 478	9.30
b2	3 611	102.67	3 611	175.53	3 611	141.06
b3	4 505.9	7155.77	4 516.9	11.83	4 516.9	12.92
b4	3 860.3	257.44	3 874.3	4.48	3 874.3	4.95
b5	3 288.7	411.77	3 295.7	80.34	3 298.7	27.02

算例

W=20 h

W=30 h

W=40 h

Time/s

3 462

464.55

3 478

10.50

3 478

9.30

3 611

102.67

3 611

175.53

3 611

141.06

4 505.9

7155.77

4 516.9

11.83

4 516.9

12.92

3 860.3

257.44

3 874.3

4.48

3 874.3

4.95

3 288.7

411.77

3 295.7

80.34

3 298.7

27.02

算例	CAP=35 t			CAP=45 t
c1	2 316.3	25.70	2 319.3	3.63	2 319.3	5.00
c2	2 578.4	232.83	2 585.4	9.16	2 585.4	4.52
c3	2 412.2	52.22	2 419.2	4.50	2 419.2	3.84
c4	2 108.6	11.58	2 109.6	3.59	2 112.6	3.11
c5	2 326.2	100.75	2 336.2	5.55	2 340.2	4.20

算例

CAP=35 t

CAP=40 t

CAP=45 t

Time/s

2 316.3

25.70

2 319.3

3.63

2 319.3

5.00

2 578.4

232.83

2 585.4

9.16

2 585.4

4.52

2 412.2

52.22

2 419.2

4.50

2 419.2

3.84

2 108.6

11.58

2 109.6

3.59

2 112.6

3.11

2 326.2

100.75

2 336.2

5.55

2 340.2

4.20

算例	CAP=45 t			CAP=55 t
d1	3 476.0	20.63	3 478.0	9.53	3 478.0	11.64
d2	3 605.0	1 004.63	3 610.0	161.83	3 611.0	101.51
d3	4 514.9	89.58	4 516.9	22.27	4 516.9	25.44
d4	3 865.3	257.06	3 867.3	106.56	3 870.3	35.39
d5	3 288.7	473.58	3 290.7	258.89	3 293.7	265.09

算例

CAP=45 t

CAP=50 t

CAP=55 t

Time/s

3 476.0

20.63

3 478.0

9.53

3 478.0

11.64

3 605.0

1 004.63

3 610.0

161.83

3 611.0

101.51

4 514.9

89.58

4 516.9

22.27

4 516.9

25.44

3 865.3

257.06

3 867.3

106.56

3 870.3

35.39

3 288.7

473.58

3 290.7

258.89

3 293.7

265.09