考虑缓冲时间的受扰航班恢复问题建模与求解

李杰; 李昆鹏; 田倩南

doi:10.14188/j.1671-8836.2022.0155

武汉大学学报（理学版） ›› 2023, Vol. 69 ›› Issue (6) : 749 -756. DOI: 10.14188/j.1671-8836.2022.0155

算法与应用

考虑缓冲时间的受扰航班恢复问题建模与求解

李杰 ¹ ,
李昆鹏 ¹ ,
田倩南 ²^,³

作者信息 +

Modeling and Solution for Disturbed Flights Recovery Problem with Buffer Time

Jie LI ¹ ,
Kunpeng LI ¹ ,
Qiannan TIAN ²^,³

Author information +

文章历史 +

PDF (604K)

摘要

在制定受扰航班恢复计划时，为航班设置缓冲时间，可有效减少航班实际执行时的延误传播。研究考虑缓冲时间的受扰航班恢复问题，以恢复成本最小化为目标建立混合整数规划模型和集合划分模型。采用改进分支定价算法求解，并应用两种加速策略加快算法的求解。小规模算例的求解与CPLEX优化软件进行对比，验证了模型和算法的有效性，大规模算例实验表明了改进分支定价算法的高效性。使用加速策略使得算法的平均求解时间由937.63 s降到185.22 s，平均效率提高80.25%。

Abstract

Setting a buffer time can effectively reduce the delay propagation when making a recovery plan for disturbed flights. This paper studies the disturbed flight recovery problem with buffer time. To achieve the objective of minimizing the total recovery cost, this paper introduces a mixed integer programming model, and a set-partitioning model is proposed. The problem is tackled using an enhanced branch-and-price algorithm incorporating two acceleration strategies to improve efficiency and solution quality. The CPLEX is used to compare with the algorithm in small-scale experiments to verify the model's and the algorithm's effectiveness. The large-scale experiments show the efficiency of the algorithm. The comparison experiment of the acceleration strategy shows a remarkable effect: the average solution time is reduced from 937.63 s to 185.22 s, and the average efficiency is increased by 80.25%.

Graphical abstract

关键词

航班恢复 / 航班延误 / 鲁棒 / 分支定价算法

Key words

flight recovery / flight delay / robust / branch-and-price algorithm

引用本文

引用格式 ▾

李杰,李昆鹏,田倩南. 考虑缓冲时间的受扰航班恢复问题建模与求解[J]. 武汉大学学报（理学版）, 2023, 69(6): 749-756 DOI:10.14188/j.1671-8836.2022.0155

登录浏览全文

4963

注册一个新账户忘记密码

0　引言

航空客运极易受到恶劣天气（大规模台风和雨雪雾等）、航空公司（机组人员空勤等）、空管（流量控制等）等因素影响而产生延误，突发公共卫生事件也会导致部分航班取消，并影响后续航班计划。航班计划是航空运营生产中的一个重要环节，如果受扰航班的波及范围不断扩大会引起多方面的问题，对航空公司和旅客关系以及航空公司经营造成严重损害。

受扰航班恢复问题属于复杂的NP-hard问题^[1]，已引起许多学者关注^[2，3]，但现有文献中尚未有研究考虑缓冲时间的受扰航班恢复问题。大多数研究基于已经发生的干扰事件解决航班恢复问题^[4],没有考虑潜在干扰因素对航班计划的影响。航班恢复和乘客恢复、机组恢复在实际中往往被依次解决，一些研究将简化的航班恢复问题分别和乘客恢复、机组恢复进行集成研究，忽略了潜在干扰因素^[5~13]。

在考虑潜在干扰因素的文献中，Lee等^[14]预测枢纽机场系统性延误，Vink等^[15]通过预先计算延误成本矩阵来模拟乘客的延误成本，均没有将缓冲时间作为一种恢复策略来应对潜在干扰。

在受扰航班恢复过程中，在航班计划出发时间前设置缓冲时间，可减少潜在干扰对航班计划的影响^[16]，避免航班计划的二次恢复。因此，本文研究考虑缓冲时间的受扰航班鲁棒恢复问题，以最小化航班取消成本、延误成本、交换成本、飞机数目不平衡的惩罚成本和缓冲时间不足的惩罚成本为目标函数，建立混合整数规划模型。为求解大规模算例，提出集合划分模型，使用分支定价算法对问题进行求解，并使用加速策略加快求解速度。最后通过对比实验，验证本文模型的正确性及算法和加速策略的有效性。

1　问题描述与数学模型

1.1　问题描述

受扰航班恢复问题的数学描述如下：在一个有向图

G = F, E

中，

F = 1,2, ⋯, F

表示图中所有点，即航班和维护集合；

E = i, j, i, j ∈ F, i ≠ j

表示边集合，边

i, j

连通需要满足时间和机场不冲突，且不违背最小地面中转时间要求。对于边

i, j

，航班

j

的实际缓冲时间为

i

到达且满足最小中转时间要求后，到

j

出发之前的空闲时间。给定的缓冲时间不能被满足时，会产生惩罚成本。设置缓冲时间可以有效避免实际执行时，潜在干扰对航班计划的影响。图1(a)表示没有缓冲时间的情况，当出现临时性突发事件时，航班

f 1

延误，但是由于延误后的航班

f 1

和

f 2

之间不能满足航班间中转时间约束，导致后面的航班（

f 2

、

f 3

）被取消；图1(b)表示有缓冲时间的情况，航班

f 1

延误后与

f 2

之间仍然满足中转时间要求，因此后续航班可以正常执行。本文综合决策各飞机执行哪些航班、取消哪些航班、执行航班和维护的顺序及延误时间、各航班的缓冲时间，最小化总恢复成本，并得到鲁棒恢复计划。

在制定航班鲁棒恢复计划时，需满足如下约束：1）飞机在任意时间只能执行一个航班或维护；2）飞机执行的航班或维护应与飞机当前所在机场一致；3）当飞机依次执行两个任务（航班或维护）时，应满足时间和机场不产生冲突；4）飞机执行航班或维护应满足飞机的可用时间窗；5）飞机执行连续两个航班时，飞机的地面时间应满足最小地面中转时间要求；6）航班的实际到达延误不能超过最大允许到达延误时间；7）应满足指定机场在航班恢复后的飞机数量与原计划结束时飞机数量一致。

1.2　混合整数规划模型

模型中使用的符号及定义如下：

P

：飞机集合；

A

：机场集合；

A'

：要求恢复计划结束后与原计划结束后飞机数量一致的指定机场集合；

I n d e x

：飞机执行航班次序集合；

e h a

：原计划中初始时机场的飞机数目，

a ∈ A

；

h a

：表示原计划结束时机场

a

的飞机数目，

a ∈ A

；

s p a

：飞机

p

初始所在机场为

a

时等于1，否则为0，

p ∈ P

，

a ∈ A

；

s t p, e t p

：飞机可用时间窗，

p ∈ P

；

c f

：取消航班

f

的成本，

f ∈ F

；

g f

：航班

f

单位时间延误成本，

f ∈ F

；

d t f

：航班原计划出发时刻，当

f

为维护时表示原计划维护开始时刻，

f ∈ F

；

a t f

：航班原计划到达时刻，当

f

为维护时表示原计划维护结束时刻，

f ∈ F

；

i s m f

：当

f

代表维护时等于1，否则为0，

f ∈ F

；

f a f

：原计划中执行航班

f

的飞机，

f ∈ F

；

b t f

：航班

f

要求的缓冲时间，

f ∈ F

；

B C f

：航班

f

缓冲不足的单位时间惩罚成本，

f ∈ F

；

T f u p

：航班

f

允许的最大到达延误时间，

f ∈ F

；

d a f a

：航班

f

出发机场为

a

时等于1，否则为0，

f ∈ F, a ∈ A

；

a a f a

：航班

f

到达机场为

a

时等于1，否则为0，

f ∈ F

，

a ∈ A

；

S C p f

：飞机

p

执行计划外航班

f

的成本（即交换成本），当

f

为飞机

p

原计划执行航班时为0，

p ∈ P

，

f ∈ F

；

g t p

：飞机

p

依次执行两架航班之间的最小地面周转时间，

p ∈ P

；

W

：恢复结束时机场飞机数目与原计划结束时不一致的惩罚成本，本文中该惩罚成本的值为一个大数，表示强制要求飞机数目一致；

M

：一个大数。

决策变量：

z p f i

表示当航班

f

是飞机

p

执行的第

i

个航班时等于1，否则等于0，

p ∈ P

，

f ∈ F

，

i ∈ I n d e x

；

x p f 1 f 2

等于1时表示航班

f 1

和

f 2

由飞机

p

依次执行，否则等于0，

p ∈ P

，

f 1 ∈ F

，

f 2 ∈ F

；

d f

表示航班

f

的出发延误时间，

f ∈ F

；

b f

表示航班

f

的实际缓冲时间，

f ∈ F

；

P C f

表示航班

f

缓冲不足惩罚成本，

f ∈ F

；

Q A a

为机场

a

恢复计划结束后与原计划结束后飞机数量的差值，即飞机不平衡数，

a ∈ A'

；

Q A L L

表示全部机场的飞机不平衡数。

根据以上变量，建立混合整数规划模型如下：

M i n ∑ f ∈ F c l f 1 - ∑ p ∈ P ∑ i ∈ I n d e x z p f i + ∑ f ∈ F g f d f ∑ p ∈ P ∑ i ∈ I n d e x z p f i + ∑ p ∈ P ∑ f ∈ F S C p f ∑ i ∈ I n d e x z p f i + W ⋅ Q A L L + ∑ f ∈ F P C f

(1)

s.t.

d t f 2 + d f 2 - a t f 1 + d f 1 + g t p ≥ M x p f 1 f 2 - 1,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2

(2)

b f 2 = ∑ p ∈ P ∑ f 1 ∈ F x p f 1 f 2 d t f 2 + d f 2 - a t f 1 + d f 1 + g t p,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2

(3)

x p f 1 f 2 = ∑ i ∈ I n d e x, i < F z p f 1 i z p f 2 i + 1,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2

(4)

P C f = B C f m a x b t f ∑ p ∈ P ∑ i ∈ I n d e x z p f i - ∑ p ∈ P z p f 1 - b f, 0, ∀ f ∈ F

(5)

∑ f ∈ F d a f a z p f i = s p a ∑ f ∈ F z p f i, ∀ p ∈ P, a ∈ A, i = 1

(6)

∑ p ∈ P ∑ f ∈ F a a f a ∑ i ∈ I n d e x z p f i - ∑ p ∈ P ∑ f ∈ F d a f a ∑ i ∈ I n d e x z p f i - h a - e h a = Q A a, ∀ a ∈ A'

(7)

Q A L L = ∑ a ∈ A' Q A a

(8)

z p f 1 i + z p f 2 i + 1 ≤ 1,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2, i ∈ I n d e x, i < F,

a a f 1 a ≠ d a f 2 a

，

a ∈ A

(9)

d f ≤ T f u p, ∀ f ∈ F

(10)

d f ≥ 0, ∀ f ∈ F

(11)

d f ≤ M ∑ p ∈ P ∑ i ∈ I n d e x z p f i, ∀ f ∈ F

(12)

s t p ∑ i ∈ I n d e x z p f i ≤ d t f + d f, ∀ p ∈ P, f ∈ F

(13)

d f + a t f ≤ e t p ∑ i ∈ I n d e x z p f i + M 1 - ∑ i ∈ I n d e x z p f i,

∀ p ∈ P, f ∈ F

(14)

∑ i ∈ I n d e x z p f i = 1, ∀ p ∈ P, f ∈ F, i s m f = 1, p = f a f

(15)

∑ f ∈ F z p f i ≤ 1, ∀ p ∈ P, i ∈ I n d e x

(16)

∑ f ∈ F z p f j ≤ ∑ f ∈ F z p f i,

∀ p ∈ P, i ∈ I n d e x, j ∈ I n d e x, i < j

(17)

∑ p ∈ P ∑ i ∈ I n d e x z p f i ≤ 1, ∀ f ∈ F

(18)

z p f i ∈ 0,1, ∀ p ∈ P, f ∈ F, i ∈ I n d e x

(19)

x p f 1 f 2 ∈ 0,1, ∀ p ∈ P, f 1 ∈ F, f 2 ∈ F

(20)

（1）式为最小化航班取消成本、延误成本、飞机临时执行计划外航班的成本（交换成本）、飞机数目不平衡的惩罚成本和航班缓冲时间不足的惩罚成本之和。（2）式表示由同一架飞机依次执行的两个航班应满足最小地面中转时间要求。（3）式表示航班的实际缓冲时间为该航班实际出发时刻与前一个航班到达且满足地面中转要求后的时刻的差值，其中飞机执行的首个航班不设置缓冲时间。（4）式表示由同一架飞机依次执行的两个航班，其被执行的次序相邻。（5）式表示航班的缓冲惩罚成本为单位时间缓冲惩罚成本与缺少的缓冲时间的乘积，如果实际缓冲时间满足计划缓冲要求则惩罚成本为0；另外，飞机执行的第一个航班不设置缓冲时间。（6）式表示飞机执行第一个航班时出发机场为飞机所在机场。（7）式表示每个指定机场飞机数目不平衡的个数。（8）式表示所有指定机场飞机数目不平衡个数。（9）式表示飞机执行连续航班时，前一航班到达机场应为后一航班的出发机场。（10）式表示航班的实际到达延误时间不能超过最大允许延误时间。（11）式表示实际到达延误为非负数。（12）式表示航班取消时，延误时间为0。（13）和（14）式表示飞机可用时间窗约束。（15）式表示维护不能取消，必须执行。（16）式表示每架飞机同一时刻只能执行一个航班。（17）式表示飞机执行航班顺序的取值要求。（18）式表示每个航班最多被执行一次。（19）和（20）式分别表示

z p f i

和

x p f 1 f 2

为零一变量。

分别将（3）、（4）、（5）和（8）式线性化，将非线性规划模型转化为可使用优化软件CPLEX求解的二次规划模型^[17]。

（3）式线性化:令

w p f 1 f 2 = x p f 1 f 2 d t f 2 + d f 2 - a t f 1 + d f 1 + g t p

,则

b f 2 = ∑ p ∈ P ∑ f 1 ∈ F w p f 1 f 2, ∀ f 2 ∈ F, f 1 ≠ f 2

(21)

w p f 1 f 2 ≥ M x p f 1 f 2 - 1 + d t f 2 + d f 2 - a t f 1 + d f 1 + g t p,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2

(22)

w p f 1 f 2 ≤ M 1 - x p f 1 f 2 + d t f 2 + d f 2 - a t f 1 + d f 1 + g t p,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2

(23)

w p f 1 f 2 ≤ M x p f 1 f 2, ∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2

(24)

（4）式线性化:令

v p f 1 f 2 i = z p f 1 i z p f 2 i + 1

，则

x p f 1 f 2 = ∑ i ∈ I n d e x, i < F v p f 1 f 2 i,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2

(25)

v p f 1 f 2 i ≥ z p f 1 i + z p f 2 i + 1 - 1,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2, i ∈ I n d e x, i < F

(26)

v p f 1 f 2 i ≤ z p f 1 i,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2, i ∈ I n d e x, i < F

(27)

v p f 1 f 2 i ≤ z p f 2 i + 1,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2, i ∈ I n d e x, i < F

(28)

v p f 1 f 2 i ≥ 0,

∀ p ∈ P, f 1 ∈ F, f 2 ∈ F, f 1 ≠ f 2, i ∈ I n d e x, i < F

(29)

（5）式线性化:引入变量

u f 1

，

u f 2

，则

P C f ≥ B C f b t f ∑ p ∈ P ∑ i ∈ I n d e x z p f i - ∑ p ∈ P z p f 1 - b f, ∀ f ∈ F

(30)

P C f ≤ B C f b t f ∑ p ∈ P ∑ i ∈ I n d e x z p f i - ∑ p ∈ P z p f 1 - b f + M 1 - u f 1, ∀ f ∈ F

(31)

P C f ≤ M 1 - u f 2, ∀ f ∈ F

(32)

u f 1 + u f 2 ≥ 1, ∀ f ∈ F

(33)

P C f ≥ 0, ∀ f ∈ F

(34)

u f 1, u f 2 ∈ 0,1, ∀ f ∈ F

(35)

（8）式线性化:引入变量

Q A a'

，则

Q A L L = ∑ a ∈ A' Q A a'

(36)

Q A a ≤ Q A a', ∀ a ∈ A'

(37)

- Q A a ≤ Q A a', ∀ a ∈ A'

(38)

1.3　集合划分模型

初步实验发现CPLEX只能求解较小规模的算例。为了求解更大规模算例，重新建立了集合划分模型，将混合整数规划模型分解为主问题（master problem, MP）和子问题。

1.3.1　主问题模型

建立集合划分模型所需符号与变量如下。

R

表示由飞机依次执行的航班和维护组成的序列，

r ∈ R

；

α p f r

表示当航班

f

包含于飞机

p

的序列

r

时等于1，否则等于0，

p ∈ P

，

f ∈ F

，

r ∈ R

；

β p a r

表示当飞机

p

执行序列

r

后的终点机场为

a

时等于1，否则等于0，

p ∈ P

，

a ∈ A

，

r ∈ R

；

c p r

表示飞机

p

执行序列

r

的成本，

p ∈ P

，

r ∈ R

。决策变量

x p r

表示当飞机

p

执行序列

r

时等于1，否则等于0，

p ∈ P

，

r ∈ R

；决策变量

y f

表示当航班

f

被取消时等于1，否则等于0，

f ∈ F

。

建立的集合划分模型如下：

M i n ∑ p ∈ P ∑ r ∈ R c p r x p r + ∑ f ∈ F c l f y f

(39)

s.t.

∑ p ∈ P ∑ r ∈ R α p f r x p r + y f = 1, ∀ f ∈ F

(40)

∑ p ∈ P ∑ r ∈ R β p a r x p r = h a, ∀ a ∈ A'

(41)

∑ r ∈ R x p r ≤ 1, ∀ p ∈ P

(42)

x p r ∈ {0,1}, ∀ p ∈ P, ∀ r ∈ R

(43)

y f ∈ {0,1}, ∀ f ∈ F

(44)

（39）式表示最小化所有被执行序列的成本和航班取消成本之和。（40）式表示每个航班要么被执行，要么被取消。（41）式表示航班恢复期结束时，指定机场的飞机数目应与原计划结束后保持一致。（42）式表示每个序列只能被执行一次。（43）和（44）式为变量取值约束。

为求解集合划分模型，将整数约束松弛，得到线性松弛主问题，并使用列生成算法迭代求解，每次需求解一个限制线性主问题（restricted linear master problem，RLMP）和若干个定价子问题^[18]。

1.3.2　定价子问题

分别用

π f 1

、

π a 2

和

π p 3

表示约束（40）~（42）式中的对偶变量，对于飞机

p

的序列

r

，简约成本（Reduced Cost）

c ¯ p r

计算方法如下：

c ¯ p r = ∑ f ∈ F S C p f + g f d f + P C f - π f 1 α p f r - ∑ a ∈ A' π a 2 β p a r - π p 3

(45)

2　分支定价算法

分支定价算法由分支定界算法和列生成算法构成，分支定界算法在每个节点运行列生成算法，通过迭代求解RLMP和定价子问题获得线性松弛主问题的最优解。首先，使用数学求解器对RLMP的初始解进行求解，并将对偶变量传递给定价子问题。其次，求解定价子问题获得满足简约成本为负的序列并添加到RLMP的序列池中。然后再次求解RLMP并重复以上过程，当无法获得负简约成本的序列时停止，此时获得线性松弛主问题的最优解。

2.1　初始解

首先，使用预处理程序筛选掉由于机场关闭导致只能取消的航班，同时更新受机场关闭影响的航班的允许延误时间。其次，采用构造算法生成初始解。根据出发时间先后顺序对航班进行排序，假设所有航班都不可延误，基于贪心思想，在可行的前提下按顺序将它们分配给飞机。在分配过程中，维护具有高优先级。然后，依次为每架飞机分配一个不执行任何航班的空序列。最后，计算每个序列的终点机场和总成本。

2.2　标签算法求解子问题

使用

L = i, r t, e, N v, D e, B, c ¯

表示节点

i

的一个标签，

r t

表示飞机最早可用时间，

e

表示当前所在机场，

N v

表示经过的节点集合，

D e

和

B

表示经过的各节点的延误时间集合和缓冲时间集合，

D e k

和

B k

表示经过的各节点

k

的延误时间和缓冲时间，

c ¯

表示简约成本。

2.2.1　标签扩展

标签

L

通过弧

i, j

扩展存在两种情况，下面给出新标签

L' = j, r t', e', N v', D e', B', c ¯'

的参数计算方法。

i）

r t + b t j ≤ d t j

，飞机最早可用时间和缓冲时间之和不大于航班

j

的出发时间，且当前序列中各航班均满足缓冲时间要求。新标签

L'

的计算方法如下：1）

r t' = a t j + g t p

；2）

e' = a, ∀ a ∈ A, a a j a = 1

；3）

N v' = N v ⋃ j

；4）

D e j' = 0, D e' = D e ⋃ D e j'

；5）

B j' = b z j, B' = B ⋃ B j'

；6）

c ¯' = c ¯ + S C p j - π j 1

。

ii）

r t + b z j > d t j

，飞机最早可用时间和缓冲时间之和大于航班

j

的出发时间，或

r t + b t j ≤ d t j

但当前序列中存在航班不满足缓冲时间要求。

e'

和

N v'

仍以i）中的方式更新，其他参数需要求解一个线性规划来确定取值。首先引入两个0-1参数，

n f k

等于1时表示航班

k

不是由飞机执行的第一个航班，否则为0，

k ∈ N v ⋃ j

；

a d j k l

等于1时表示飞机依次执行航班

k

和

l

，否则为0，

k ∈ N v ⋃ j

，

l ∈ N v ⋃ j

。

u k 1, u k 2

为0-1变量，

k ∈ N v ⋃ j

。

M i n ∑ k ∈ N v ⋃ j g k D e k + ∑ k ∈ N v ⋃ j P C k

(46)

s.t.

d t l + D e l - a t k - D e k ≥ g t p,

∀ k ∈ N v ⋃ j, l ∈ N v ⋃ j, k < l

(47)

D e k ≤ T k u p, ∀ k ∈ N v ⋃ j

(48)

d t k + D e k ≥ s t p, ∀ k ∈ N v ⋃ j

(49)

a t k + D e k ≤ e t p, ∀ k ∈ N v ⋃ j

(50)

D e k ≥ 0, ∀ k ∈ N v ⋃ j

(51)

b l = d t l + d l - a t k + d k + g t p,

∀ k ∈ N v ⋃ j, l ∈ N v ⋃ j, a d j k l = 1

(52)

P C k ≥ B C k n f k b t k - b k, ∀ k ∈ N v ⋃ j

(53)

P C k ≤ B C k n f k b t k - b k + M 1 - u k 1,

∀ k ∈ N v ⋃ j

(54)

P C k ≤ M 1 - u k 2, ∀ k ∈ N v ⋃ j

(55)

u k 1 + u k 2 ≥ 1, ∀ k ∈ N v ⋃ j

(56)

P C k ≥ 0, ∀ k ∈ N v ⋃ j

(57)

u k 1, u k 2 ∈ 0,1, ∀ k ∈ N v ⋃ j

(58)

（46）式表示最小化航班延误成本和缓冲时间不足的惩罚成本。（47）式表示执行的相邻航班应满足最小地面中转时间要求。（48）式表示航班的实际到达延误时间不能超过最大允许延误时间。（49）和（50）式表示飞机的时间窗约束。（51）式表示航班的实际延误时间为非负数。（52）式表示航班的缓冲时间。（53）~（58）式由（30）~（35）式演化而来，其中（53）~（56）式表示缓冲时间不足的惩罚成本与缓冲时间的关系；（57）式表示缓冲时间不足的惩罚成本应为非负数；（58）式表示0-1变量。

求解上述线性规划可得

D e k'

，

B k'

以及新标签的成本

c'

。因此，新标签的计算方法如下：

1）

r t' = a t j + g t p + D e j'

；

2）

e' = a, ∀ a ∈ A, a a j a = 1

；

3）

N v' = N v ⋃ j

；

4）

D e' = D e k', k ∈ N v ⋃ j

；

5）

B' = B k',

k ∈ N v ⋃ j

；

6）

c ¯' = c' + ∑ k ∈ N v ⋃ j S C p k - ∑ k ∈ N v ⋃ j π k 1

。

2.2.2　占优准则

在推导出新标签后，利用占优准则舍弃不能获得更好解决方案的标签，可以加快求解速度。

标签

L' = j, r t', e', N v', D e', B', c ¯'

占优于

L = i, r t, e, N v, D e, B, c ¯

需要满足：

1）标签所属节点：

j = i

；

2）标签的简约成本：

c ¯' < c ¯

；3）飞机最早可用时间：

r t' ≤ r t

。

2.3　加速策略

策略1：添加多个负简约成本的序列。添加多个负简约成本列是提高列生成求解效率的常用策略。每次解决子问题时，保留多个负简约成本序列，并选择简约成本最小的三个序列添加到RLMP。

策略2：定价子问题并行求解。定价子问题彼此独立，可以并行求解。设

P

为飞机总数，当使用线程数为

T

且

T ≤ P

时，可同时求解

T

个定价子问题。

2.4　分支策略

如果列生成算法得到的最优解为非整数解，执行分支策略。使用最佳优先遍历策略，每次选择目标函数最优的解作为父节点进行分支；对飞机与航班的执行关系进行分支，选取

∑ r ∈ R α p f r x p r

最接近0.5的飞机

p

和航班

f

，生成两个子节点，分别对应

∑ r ∈ R α p f r x p r = 1

和

∑ r ∈ R α p f r x p r = 0

，前者表示飞机

p

必须执行航班

f

，后者表示飞机

p

禁止执行航班

f

。相应的，子节点RLMP中包含禁止执行航班的序列被删除。

3　算例测试及结果分析

实验使用的计算机CPU为2.4 GHz Intel i5-9300H，内存8 GB，操作系统为Windows 10。基于计算机硬件，并行运算使用8个线程。应用CPLEX 12.10求解混合整数规划模型和RLMP，使用C++编码实现分支定价算法。实验算例基于国内某航空咨询公司提供的实际数据生成。航班恢复周期为1天，参数取值如下：

c l f = 90 000

；

g f = 100

；

B C f = 120; b t f = 20 m i n; T f u p = 180 m i n; S C p f = 1 000

；

g t p

=30 min。

3.1　小规模算例实验

通过小规模实验对模型的正确性和算法的有效性进行验证。使用CPLEX求解小规模算例的混合整数规划模型，与分支定价算法对比，结果如表1，“Gap”表示分支定价算法的最优解与CPLEX的差值百分比。“下界”表示分支定价算法根节点的解，可以看出所有小规模算例均在根节点获得最优解。由表1可知，求解小规模算例时，CPLEX与分支定价算法求得结果一致，模型正确性和算法有效性得到验证。分支定价算法的求解时间远远小于CPLEX，体现了分支定价算法求解的高效性，可以充分满足航班恢复计划实时性的要求。

3.2　较大规模算例实验及加速策略效果分析

为探究本文算法求解效果，使用较大规模算例进行实验，并分别在不使用加速策略、仅使用添加多个负简约成本序列策略（策略1）、仅使用定价子问题并行求解策略（策略2），以及同时使用两种加速策略场景下进行实验。测试结果如表2所示，由测试结果可知，分支定价算法可求得全部算例的最优解，且均在根节点求得最优整数解。每一种加速策略都能有效降低求解时间，而同时采用两种加速策略的效果最为显著，平均求解时间由937.63 s减少到185.22 s，平均效率提高80.25%。

4　结语

提高航班恢复计划的鲁棒性可以有效减少航班实际执行时的延误传播，提高乘客体验，而为航班设置合理的缓冲时间可以提高航班恢复计划的鲁棒性。本文以制定航班鲁棒恢复计划为目标，研究考虑缓冲时间的受扰航班恢复问题。建立了航班鲁棒恢复的混合整数规划模型和集合划分模型，并使用改进的分支定价算法进行求解。多组不同规模算例的实验验证了模型的正确性和算法的有效性，针对加速策略的对比实验显示了加速策略的显著效果。针对航班设置缓冲时间，在保障航班恢复计划具有一定鲁棒性的同时，对提高民航业的服务水平和旅客的满意度以及运行效率具有重要意义，也为研究相关航空调度问题提供了理论借鉴。未来可进一步将航班恢复与乘客恢复、机组恢复问题相结合，研究综合恢复问题；当前算法求解时间上仍有提升空间，未来可研究求解速度更快的优化算法。

参考文献

原文顺序 | 出版日期 | 本文引用

[1]	HU Y Z， XU B G， BARD J F， et al. Optimization of multi-fleet aircraft routing considering passenger transiting under airline disruption［J］. Computers & Industrial Engineering， 2015， 80： 132-144. DOI： 10.1016/j.cie.2014.11.026 .

[2]	HASSAN L K， SANTOS B F， VINK J. Airline disruption management： A literature review and practical challenges［J］. Computers & Operations Research， 2021， 127： 105137. DOI： 10.1016/j.cor.2020.105137 .

[3]	EGGENBERG N， SALANI M， BIERLAIRE M. Constraint-specific recovery network for solving airline recovery problems［J］. Computers & Operations Research， 2010， 37（6）： 1014-1026. DOI： 10.1016/j.cor.2009.08.006 .

[4]	LIU T K， CHEN C H， CHOU J H. Optimization of short-haul aircraft schedule recovery problems using a hybrid multiobjective genetic algorithm［J］. Expert Systems with Applications， 2010， 37（3）： 2307-2315. DOI： 10.1016/j.eswa.2009.07.068 .

[5]	JOZEFOWIEZ N， MANCEL C， MORA-CAMINO F. A heuristic approach based on shortest path problems for integrated flight， aircraft， and passenger rescheduling under disruptions［J］. Journal of the Operational Research Society， 2013， 64（3）： 384-395. DOI： 10.1057/jors.2012.20 .

[6]	ZHANG D， HENRY-LAU H Y K， YU C H. A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems［J］. Computers & Industrial Engineering， 2015， 87： 436-453. DOI： 10.1016/j.cie.2015.05.033 .

[7]	MAHER S J. Solving the integrated airline recovery problem using column-and-row generation［J］. Transportation Science， 2016， 50（1）： 216-239. DOI： 10.1287/trsc.2014.0552 .

[8]	AKTÜRK M S， ATAMTÜRK A， GÜREL S. Aircraft rescheduling with cruise speed control［J］. Operations Research， 2014， 62（4）： 829-845. DOI: 10.1287/opre.2014.1279 .

[9]	HU Y Z， LIAO H， ZHANG S， et al. Multiple objective solution approaches for aircraft rerouting under the disruption of multi-aircraft［J］. Expert Systems with Applications， 2017， 83： 283-299. DOI： 10.1016/j.eswa.2017.04.031 .

[10]	LIANG Z， XIAO F， QIAN X W， et al. A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility［J］. Transportation Research Part B： Methodological， 2018， 113： 70-90. DOI： 10.1016/j.trb.2018.05.007 .

[11]	HUANG Z C， LUO X D， JIN X F， et al. An iterative cost-driven copy generation approach for aircraft recovery problem［J］. European Journal of Operational Research， 2022， 301（1）： 334-348. DOI： 10.1016/j.ejor.2021.10.055 .

[12]	田倩南，李昆鹏，李文莉，等. 受扰航班恢复问题的优化方案研究［J］. 管理学报， 2018， 15（10）： 1081-1088. DOI： 10.3969/j.issn.1672-884x.2018.10.017 .

[13]	TIAN Q N， LI K P， LI W L， et al. The research on optimization of disrupted flights recovery problem［J］. Chinese Journal of Management， 2018， 15（10）： 1081-1088. DOI： 10.3969/j.issn.1672-884x.2018.10.017（Ch ）.

[14]	田倩南，李昆鹏，李文莉，等. 基于改进列生成算法的受扰航班优化调度［J］. 系统工程理论与实践， 2019， 39（11）： 2815-2827. DOI： 10.12011/1000-6788-2018-0472-13 .

[15]	TIAN Q N， LI K P， LI W L， et al. Optimization operation of disrupted flights by improving column generation algorithm［J］. Systems Engineering —Theory & Practice， 2019， 39（11）： 2815-2827. DOI： 10.12011/1000-6788-2018-0472-13（Ch ）.

[16]	LEE J， MARLA L， JACQUILLAT A. Dynamic disruption management in airline networks under airport operating uncertainty［J］. Transportation Science， 2020， 54（4）： 973-997. DOI： 10.1287/trsc.2020.0983 .

[17]	VINK J， SANTOS B F， VERHAGEN W J C， et al. Dynamic aircraft recovery problem — An operational decision support framework［J］. Computers & Operations Research， 2020， 117： 104892. DOI： 10.1016/j.cor.2020.104892 .

[18]	BRUECKNER J K， CZERNY A I， GAGGERO A A. Airline mitigation of propagated delays via schedule buffers： Theory and empirics［J］. Transportation Research Part E： Logistics and Transportation Review， 2021， 150： 102333. DOI： 10.1016/j.tre.2021.102333 .

[19]	Bliek C， Bonami P， Lodi A. Solving Mixed-integer Quadratic Programming Problems with IBM-CPLEX： A Progress Report［DB/OL］.［2022-03-10］.

[20]	COSTA L， CONTARDO C， DESAULNIERS G. Exact branch-price-and-cut algorithms for vehicle routing［J］. Transportation Science， 2019， 53（4）： 946-985. DOI： 10.1287/trsc.2018.0878 .

基金资助

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

国家社会科学基金青年项目(21CGL019)

湖北省高等学校优秀中青年科技创新项目(T2022024)

湖北省教育厅哲学社会科学研究项目(20Q120)

AI Summary AI Mindmap

PDF (591KB)

访问

被引

详细

导航

Received	Published
2022-07-24	2023-12-24
Issue Date
2026-07-23

摘要

Abstract

Graphical abstract

关键词

Key words

引用本文

0 引 言

1 问题描述与数学模型

1.1 问题描述

1.2 混合整数规划模型

1.3 集合划分模型

1.3.1 主问题模型

1.3.2 定价子问题

2 分支定价算法

2.1 初始解

2.2 标签算法求解子问题

2.2.1 标签扩展

2.2.2 占优准则

2.3 加速策略

2.4 分支策略

3 算例测试及结果分析

3.1 小规模算例实验

3.2 较大规模算例实验及加速策略效果分析

4 结 语

参考文献

基金资助

AI思维导图

0　引言

1　问题描述与数学模型

1.1　问题描述

1.2　混合整数规划模型

1.3　集合划分模型

1.3.1　主问题模型

1.3.2　定价子问题

2　分支定价算法

2.1　初始解

2.2　标签算法求解子问题

2.2.1　标签扩展

2.2.2　占优准则

2.3　加速策略

2.4　分支策略

3　算例测试及结果分析

3.1　小规模算例实验

3.2　较大规模算例实验及加速策略效果分析

4　结语