后勤。第1部分。优化方向和时间表的空中交通

当然，每个人都必须坐半空飞机或转乘飞机，也许您考虑过这种飞机的成本效益和效率。航空公司会损失多少潜在利润？确实，航班是无利可图的，有时甚至是无利可图的。是否可以根据航空承运人的最佳行为来解释此类决定？例如，在当前由于COVID-19而导致航班取消的情况下：机队如何在其他方向上分配，从而提供本地收益率？让我们尝试建立一个动态模型，以响应外部变化并努力达到平衡状态。在本文中，我们仅采用少量参数，尝试预测需求，发送容量较低的飞机，减少无利可图的航班频率。



乍一看，该任务与“背包问题”非常相似。其实有$$$n$ 机场 $$$a_{1}, a_{2}, .., a_{i}, .., a_{n}$，每个机场都可容纳 $$$b_{1}, b_{2}, .., b_{i}, .., b_{n}$飞机。飞机本身是不同类型的$$$f_{1}, f_{2}, .., f_{j} .., f_{m}$。飞机维修费用$$$j$输入 $$$i$机场费用 $$$z_{ij}$和利润 $$$p_{j}$。找到这样的$$$x_{ij}$ （$$$x_{ij} \geqslant 0, x_{ij} \in \mathbb{Z}$），使总利润最大化 $$$P$：

$$

$$max(P) = \sum_{j = 1}^{m} p_{j}x_{j}\; ; \;\;\; x_{j} = \sum_{i = 1}^{n} x_{ij}$$

和总费用 $$$Z$ 用于飞机维修的飞机被最小化：

$$

$$min(Z) = \sum_{i = 1}^{n} \sum_{j = 1}^{m}z_{ij}x_{ij}$$

有每个机场的容量限制：

$$

$$\sum_{j = 1}^{m} x_{ij} \leqslant b_{i}$$

现在考虑到机场是由航空公司互连的 $$$r_{1}, r_{2}, .., r_{k}, .., r_{l}$。然后，不仅要考虑飞机的类型，还要考虑飞机的飞行方向，即飞机的布置。最初寻求$$$x_{ij}$ 现在变成 $$$x_{ijk}$。而且，这些方向本身可以组合成飞机发生运动的任意路线。

型号说明

显然，总损益的价值取决于一些相当复杂的航空公司战略：选定的飞机类型，拟定的航线以及每架飞机的时间表。但是，要更详细地讨论策略，您需要做很多澄清。

航空旅行需求

形成最佳战略的最重要参数之一是各个城市之间对航空旅行的需求，但收集的数据并没有可靠的思路。但是，即使在这种不确定的情况下，随着新信息的到来，也应该采取一些旨在增加利润和减少损失的行动。

关于特定目的地需求的一些间接结论可以基于通过该目的地运输的乘客数量的数据得出。例如，如果一架飞机在某个方向进行了5次飞行，并且平均满载率超过90％，那么我们可以得出结论，该方向的需求量很大，因此决定增加该方向的交通量。另一方面，如果在第六次的这五次飞行之后，乘客人数急剧减少，那么从长远来看，该因素会影响“平均”入住率，这可能是进行调整的一个很好的理由。

根据此类随机数据做出决策的最简单方法是使用移动平均值。但是，问题在于航空公司无法承受实验来检验其关于需求的假设，也就是说，如果在飞行之后飞机上的载客量急剧下降，那么这已经被视为采取行动的信号。例如，在这种情况下，您可以减少在该方向上的飞行频率，并在始终保持较高的占用率的情况下将其增加。另一方面，对前10个航班的平均占用率的了解只能使我们或多或少准确地判断飞机在该方向上的占用率有多稳定。如果平均入住率的值开始稳定下降，那么这可以作为采取更严格措施的信号，例如，用容量较小的飞机替换飞机，改变飞机路线的戏剧性，或者同时更换飞机并更改其路线。

为了创建模型，假设每个方向上的真实需求值是一个随机变量 $$$q_{ijt} = \xi(t)$ 并可以从间隔中获取值 $$$[0, q_{ij, max}]$具有相同的可能性。现在假设最大容量的飞机沿该方向运行$$$d_{j,max}$显然，如果 $$$q_{ijt}$ 比...多得多 $$$d_{j,max}$，那么飞机很可能快满了。为了使建模过程成为可能，请假设该值$$$q_{ij, max}$例如，可以通过与该方向相连的城市规模来粗略估计每个方向上的距离。我们还假设要研究模型的行为，可以更改此值，但无法预测。

计算每架飞机的损益

每架飞机的维护成本可以通过以下比率确定：

$$

$$z_{ij}(t) = c_{ij}\Delta t + c_{0ij}$$

该比率表明维护飞机类型的成本 $$$f_{j}$ 在机场 $$$a_{i}$取决于他在这个机场的停留时间。有一些固定费用$$$c_{0ij}$可能需要收取起降费用。将来，此固定费用与系数成比例增加$$$c_{ij}$。该比率不允许在某些机场“冻结”个别飞机，即 反映了现实的一个非常重要的特征：“ 无为而为=损失 ”。

由于我们在谈论单个平面，为了唯一地标识每个平面，我们引入了另一个索引$$$x = \overline{0, g}$ 哪里 $$$g = \sum x_{ijk}$。然后，可以通过以下公式计算每架飞机的利润：

$$

$$p_{ijkx} = d_{ijkx}s_{jk} - \beta_{j} \Delta t_{jk}$$

值 $$$d_{ijkx}$ 确定索引为$ x $的飞机在自然约束下的满度 $$$d_{ijkx} \leqslant d_{j,max}$，这表明飞机的充满度不能超过其最大容量。方向的一张车票的成本$$$r_{k}$ 坐飞机去的 $$$f_{j}$ 由设置 $$$s_{jk}$。此外，此公式还考虑到飞行费用还取决于飞机的类型以及完成飞行所需的时间：$$$\beta_{j}$ 是确定飞机类型航班每单位时间成本的系数 $$$f_{j}$和 $$$\Delta t_{jk}$ -这是这类飞机需要克服方向的时候 $$$r_{k}$。

如果您将飞机的航线标记为$$$R_{x} = (r_{1},r_{2},..r_{k})$，则其中包含的所有排期的总利润和费用记录为

$$

$$P_{R_{x}} = \sum_{k}(d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk}) \; ; \;\;\;\;\;\;\; Z_{R_{x}} = \sum_{k}(c_{ij} \Delta t_{ijkx} + c_{0ij})$$

哪里 $$$k$ 遍历路线中所有方向的索引，并且 $$$\Delta t_{ijkx}$-这是飞机在每个机场航线上的延迟时间。然后，可以通过以下公式计算所有飞机的总利润和成本：

$$

$$P = \sum_{x}\sum_{k}(d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk}) \; ; \;\;\;\;\;\;\; Z = \sum_{x}\sum_{k}(c_{ij} \Delta t_{ijkx} + c_{0ij})$$

另一方面，如果可以获得所有飞机路线的所有信息，则可以通过以下公式计算总利润和成本：

$$

$$P = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk})\; ; \;\;\;\;\;Z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (w_{ij} \Delta t_{ijkx} + w_{0ij})$$

管理费用

用于计算利润和成本的表达式可能已经适合于建模，但是它们没有考虑到重要的事实，即在执行某些控制操作后，整个系统的功能会发生变化，并且整个系统的重组不能立即进行。此外，应该理解，控制动作本身本质上不能是“魔术”的，也就是说，我们无法传送飞机，使它们连续飞行数天等等。要使一架飞机的时间表与其他飞机的时间表同步，您可以延迟或延迟其起飞。如果应用控制动作的那一刻飞机被困在空中，那么我们仍然必须等待它降落。



在采取控制措施的时刻，飞机在其中一个机场遇难，就会出现另一种限制-无法迫使飞机在着陆后立即起飞。对于每种类型的飞机，必须在机场花费一些最少的时间$$$\Delta t_{ij,min}$飞机的强制维护（加油，清洁机舱等）所需

$$

$$\Delta t_{ijkx} \geqslant \Delta t_{ij,min}$$

这意味着施加控制动作的时刻仍必须与着陆时刻相关联。



施加控制动作后，飞机会按照明确的定期时间表再次飞行，即 飞机在机场花费的时间（可通过该时间来调整时间表）可能不同于所有随后的相等时间间隔。这意味着与控制措施相关的成本也可能与所有后续成本不同，因此需要单独计算。由于控制动作始终与飞机着陆的时刻相关，因此我们可以将此时间间隔指定为$$$\Delta t_{0, ijkx}$ 并使用熟悉的公式确定与此相关的成本

$$

$$z_{ij}(t) = c_{ij}\Delta t_{0, ijkx} + c_{0ij}$$

用于计算所有飞机总成本的公式也没有太大变化。

$$

$$Z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (w_{ij} \Delta t_{0, ijkx} + w_{0ij})$$

飞机路线

飞机路线提出了一个非常重要的要求-周期性。这个要求似乎不合理，因为将飞机紧紧地绑在这样的路线上可能是不利的。但是，此要求并不强制飞机绕过整个周期。同样，此要求不会改变以下事实：系统状态仍分为两个阶段-控制操作的应用“之前”和“之后”。这意味着，如果系统中发生了任何变化，例如，需求在一个方向上发生了变化，其中一个平面已被延迟或完全损坏（消失），则仅执行一个控制动作，即所有飞机仅在完成后才开始周期性地执行其路线。原则上，如果在每次控制操作之后路线更改非常频繁地发生，这样飞机的航线就不会有周期性。但是，另一方面，如果经过一些优化后，不再遵循路线变化的控制动作，那么这将意味着系统本身将保持其最佳和静止状态。

所有路线都是周期性的要求也可以由以下事实证明是合理的：将来没有任何信息需要更改路线，也就是说，事实证明飞机将沿着某个路线飞行任意时间而无需一次调整。如果这条路线不是一个循环，那么在一次迭代中它将停止移动。这意味着在每次迭代中，有必要跟踪每架飞机的停靠点并对其进一步的移动做出一些决定。

除了上述所有以外，还有其他重要的路线和时间表要求-每个机场的最大同时飞机停留时间不应超过其容量。因此，在草拟航线之后，有必要草拟一份时间表，以确保在任何时间任何机场，飞机数量都不会超过他的能力。如果飞机的航线很长而不是周期，那么您将不得不计算该航线每个机场的飞机数量，这些计算将与其他飞机的航线和时间表有关。另一方面，如果飞机绕开了一段已知的周期，然后知道了每个机场的进出频率，则可以很轻松地制定时间表，这不会导致容量限制过大。

由于对路由的严格要求是循环，因此很明显，所有路由必须由对网络建模的有向图的简单循环组成。为了说明这一点，我们将描述四个相互连接的机场，如下所示：



该图由六个简单周期组成：$$$(a_{1},a_{2})$， $$$(a_{2},a_{3})$， $$$(a_{3},a_{4})$， $$$(a_{2},a_{4})$， $$$(a_{2},a_{3},a_{4})$， $$$(a_{2},a_{4},a_{3})$。通过其顶点的循环位移获得的循环被认为是等效的，例如，循环将是等效的：$$$(a_{2},a_{4},a_{3})$， $$$(a_{4},a_{3},a_{2})$ 和 $$$(a_{3},a_{2},a_{4})$。

但是，如果已知某架飞机位于特定的机场，则其路线中峰的顺序就变得很重要。通过组合基本周期（包括其他周期中的某些周期），或者如果路线中已经包含内部周期，则将基本周期组合起来，即可完成对位于机场的特定飞机的航线安排。

考虑一个简单的例子，假设某架飞机位于机场$$$a_{3}$那么它可以在两个简单周期之一中飞行： $$$(a_{3},a_{2})$ 和 $$$(a_{3},a_{2},a_{4})$。周期$$$(a_{3},a_{2})$ 可以结合一个周期 $$$(a_{1},a_{2})$，结果是一个循环 $$$(a_{3},a_{2},a_{1},a_{2})$。同一周期$$$(a_{1},a_{2})$ 可以包含在循环中 $$$(a_{3},a_{2},a_{4})$ 导致 $$$(a_{3},a_{2},a_{1},a_{2},a_{4})$。

现在假设飞机在机场$$$a_{3}$将在路线中循环 $$$R_{1}=(a_{3},a_{2},a_{1},a_{2},a_{4})$，但在这种情况下，无法满足指示的要求 $$$(a_{4},a_{2})$， $$$(a_{3},a_{4})$ 和 $$$(a_{2},a_{3})$ 这意味着您可以在现有飞机的航线上添加另一个简单的周期 $$$(a_{3},a_{4},a_{2})$ 并得到 $$$(a_{3},a_{2},a_{1},a_{2},a_{4},a_{3},a_{4},a_{2})$ 或添加将在路线中循环的另一架飞机 $$$R_{2} = (a_{3},a_{4},a_{2})$。

在此有必要对路线的“更改”和“替换”的概念进行一些澄清。更改路线涉及通过增加或减少其内部基本循环数来对其进行修改。替换路线涉及替换基本循环本身。
显然，飞机路线可以相互重叠，并且最好在需求特别高的网络部分重叠。

可以使用Johnson算法找到所有简单的图循环，其复杂度等于$$$O((n+e)(c+1))$哪里 $$$n$ -顶点数 $$$e$ -肋骨的数量，以及 $$$c$-基本链的数量。将来，您应该检查飞机边缘的并集，以更改飞机的航线。其中包括$$$R_{x}$与整个图形的边缘集重合 $$$E$，即 如果飞机总数是$$$g$，则应满足相等性：

$$

$$\bigcup_{x = 1}^{g} R_{x} = E$$

符合机场容量限制

除了已编制的时间表会影响每个方向的吞吐量这一事实之外，它还会影响同时可以在机场飞行的飞机数量。为了方便起见，假设某个机场一次只能容纳两架飞机，但是该机场包含在三架飞机的航线中。显然，必须有一些严格的条件才能符合限制。

首先，我们将尝试确定一种通用方法，该方法要考虑以下事实：飞机在给定的周期内周期性地执行其航线，并且只有通过与更改飞机的起飞时间相关的一种控制动作，才能进行时间​​表调整。



红色虚线表示系统达到最佳静止状态的时刻。到此行为止的所有内容都可以视为执行控制操作的时间间隔。在这种情况下，显示了如何更改时间间隔$$$t_{0,1}$ 和 $$$t_{0,2}$您可以控制两架飞机访问同一机场的时间。该图显示飞机在机场花费的时间不同，但同时这些时间间隔不会重叠。仅当它们的周期相等或这些周期的最小公倍数等于其中一个周期时，才有可能。

例如，如果乘坐两架飞机前往机场的时间为200和600小时，则可以选择它们相对于彼此的偏移，以使它们永远不会同时访问机场。但是，如果它们的时间分别为300和700小时，那么无论它们相对于彼此如何移位，迟早它们都将同时到达机场。

但是，很明显，控制动作可以满足该条件，但是间隔仍然可以相交，这意味着满足以下条件（字母 $$$a$ 在索引中表示飞机已飞往机场； $$$d$ -飞出机场）：

$$

$$\left\{\begin{matrix} t_{1,a} \leqslant t_{2,d} \\ t_{1,d} \geqslant t_{2,a} \end{matrix}\right.$$

如果机场可容纳2架飞机，但已包含在3架飞机的航线中，则同时对所有3架飞机成对满足这些条件意味着将超出限制。

另一方面，如果两个平面的周期不导致它们同时停留在机场，则第三平面可能具有任意周期。但是在这种情况下，必须满足他在机场的时间必须严格小于前两架飞机不在机场的时间间隔的要求。

这导致遵循两个简单的规则来遵守机场容量限制：

1. 如果机场容量是 $$$n$那么飞机的停留时间应该分为 $$$n$ . .
2. $$$n$ .

仅在一种情况下才可以证明严格满足这些条件是合理的，即可以肯定知道将来不会期望采取任何控制措施。但是由于没有这样的保证，这些条件可能会有所减弱。而且，严格地满足这些条件可能需要飞机的很大的延误，这对于换班周期是必需的。证明非常昂贵。因此，可以调整这些条件，以便仅在某个可接受的时间段之后才超过容量限制，然后可以进行下一个计划调整。但是，不能保证这样的分阶段调整总是会导致调整成本的降低。所有这些表明，这些规则可以作为更复杂规则的基础，例如，您可以根据航线保持不变的飞机的时间表来调整航线已更改的飞机的时间表，或者计算各种顺序调整的组合成本并选择最佳的。

建模过程和最佳决策

假设在初始时间，这些平面以某种随机或预定顺序排列。因为在最初的时刻，没有关于所载乘客数量的信息，所以在初始阶段，存在“情况调查”。在这一阶段，在开始模拟过程之前，必须为每架飞机分配一定的路线。显然，所有这些路线都应覆盖整个机场网络，并有助于确保就装载而言最佳地进行机场之间的所有移动。

一旦在其路线的所有方向上知道了载荷值，就可以开始某些飞机的优化过程。只有在这一刻，才有可能计算出这架飞机在这条航线上的利润和成本值，并将其用于优化过程。如果有可能改变路线和时间表，从而增加已知利润并降低成本，则它们将取代以前的利润。

在知道每个方向上的所有工作量值之前，无法替换飞机路线，因为这无法让我们判断总利润和成本。只有知道每个方向上的所有工作量值之后，您才可以开始更改单个飞机的路线和时间表，还可以更改总体运输计划。

我们为每个方向分配一个数组。$$$W_{ij}$ 输入每架飞机的乘客占用率的特定长度（例如5） $$$w_{ijt}$朝这个方向飞行的人 该数组将是此类值的堆栈。该数组中的最后一个值-前一次飞行的负载，将使我们能够得出有关需要采取小型战术行动的结论，而整个数组中的平均值将作为需要进行重大战略调整的指标。

如果数组的最后一个值$$$W_{ij}$ 超过一定间隔 $$$w_{ij, min} \leqslant w_{ijt} \leqslant w_{ij, max}$确定更改的适当性，然后采取适当的措施来减少或增加该方向的飞行频率。同时，如果在减少或增加此方向的飞行频率后，该值$$$\overline{W}_{ij}$如果它继续下降或增长，则可能表明需要进行更根本的改变，例如，在几架飞机的航线中包含给定方向，或者在所有飞机的航线中均不包含该方向。

例如，假设飞机沿循环路线飞行$$$(a_{1},a_{2},a_{3},a_{2})$。假设下一次从机场出发$$$a_{1}$飞机上的乘客人数急剧下降。在这种情况下，到达机场后$$$a_{2}$ 可能会决定更改路线 $$$(a_{1},a_{2},a_{3},a_{2})$ 在 $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2})$。这样的替换很有用，因为如果方向上的需求下降$$$(a_{1},a_{2})$不是偶然的，而是稳定的趋势，那么至少在这个方向上飞行的频率将会减少。如果在下一次访问此目的地时，携带的乘客人数很少甚至更少，那么该路线$$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2})$ 可以更改为再次路由 $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2},a_{3},a_{2})$，从而减少了访问路线的频率 $$$(a_{1},a_{2})$更强大。如果方向$$$(a_{1},a_{2})$ 持续下降，您通常可以替换路线 $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2},a_{3},a_{2})$ 在 $$$(a_{3},a_{2})$ 或任何其他不包含路线的路线 $$$(a_{1},a_{2})$。

所有这些都可以使用以下方案进行演示，该方案显示了前往目的地的频率如何变化，从而大大降低了其获利能力：


减少目的地航班频率的指标$$$(a_{1},a_{2})$ 具有意义 $$$w_{1,2}$，每当它小于50时，就决定以较少的频率访问该方向。值之后$$$\overline{W}_{ij}$当飞行器的飞行方向变得低于允许间隔的最小值时，该方向通常不包括在飞机的航线上。

此外，对于每种飞机，您都可以确定阵列元素平均值的允许间隔$$$W_{ij}$。如果此值包含在特定类型飞机的可接受间隔中，但不包含在已经沿其飞行的飞机的可接受间隔中，则将进行连续的路线更改，从而用更合适的飞机类型替换飞机类型。

似乎随着时间的流逝，一旦每个方向上的乘客人数的所有平均值达到平衡，所有飞机将只会集中在一条最有利可图的路线上。如果每个机场的容量都是无限的，这确实是正确的。但是由于每个机场都有能力$$$b_{i}$一些飞机将不得不在利润较低的航线上飞行。显然，只有在更改后才执行优化一架或多架飞机的措施才有意义$$$w_{ijt}$ 或有什么价值 $$$\overline{W}_{ij}$将从一个间隔移到另一个间隔。所有这些都可以如下图所示：



该图显示了如何更改四种不同类型（容量不同）的五架飞机的航线。最初，某些飞机的飞行利润不高，但是随着出现有关所载乘客的更多信息，其航线也会发生变化，因此它们会尽可能地匹配其容量。最终，达到一个平衡状态，其中每个平面都带来最大的利润，即 以最高的频率在其路线上运行。还考虑了机场的容量，这不允许航线完全重叠。

出现了一个非常重要的问题-如何找到最佳的行动系统？这个问题与全局优化直接相关，即 您需要选择飞机路线，类型和时间表的此类组合，在这些组合中，总利润最大，而成本最小。如果我们仅谈论飞机及其路线，那么即使如此，解决方案的搜索区域也将非常庞大，因为该区域的大小取决于机场网络中简单循环的数量，并且取决于飞机的数量。鉴于路径可以具有不同的长度并包含不同数量的内部循环，因此对解决方案空间大小的最乐观估计将如下所示：$$$(n!)^m$哪里 $$$n$ 是简单循环的数量，并且 $$$m$-飞机数量。随着飞机类型及其时间表的组合的增加，决策空间将得到更大的扩展。

自然地，只有借助元启发式算法才能搜索最佳动作，并且这种搜索将在单个飞机的空座位数量发生任何重大变化之后进行，这种变化可能经常发生。而且，优化过程分为两个阶段：首先，执行针对每种类型飞机的最佳航线搜索，然后优化其计划。同时，日程安排优化可以是绝对确定的过程，并且由于了解在单独的简单循环中运送的乘客数量，因此可以比简单地整理出更快的路线来更改或替换为最佳路线。但您还应该记住可能的局部最大值和最小值，例如，具有最高负载度的路线，即最有利可图的项目可能需要在机场延误很长时间的时间表，即大大增加了其维护成本。

出现以下问题：“我应该选择哪种元启发法：蚂蚁，模拟退火或进化？”蚂蚁算法擅长于寻找有利可图的路线，但是在建模的某个阶段，这种搜索的需求就消失了，并且又出现了另一个问题-更改和替换路线，而不一定要承受最大的乘客负担。
进化算法不能保证达到全局最大值，同时由于变异和穿越路线的过程规则而非常复杂。
路线的某些有利部分可能会在下一次迭代中被突变破坏，或者无法与总体其他成员的有利部分交叉。但是，问题的范围并不太大，以至于很难将其实际预测为事实并预测该算法的行为将非常困难。

寻找最佳动作的最简单，最有前途的方法是退火模拟算法，实现和配置参数非常简单。该算法还允许您应用各种经验策略来生成更多最优路线，例如，最有利可图的简单路线周期的降温速度要快于收益较低的路线。进行较小的更改，这将有助于最快的收敛。

结论

当然，所考虑的问题只是冰山一角，创建的模型仅是在本系列文章的后续部分中进行进一步研究的基础。例如，您需要考虑民用航空运输市场中有很多航空公司，即他们必须互相竞争。在模型中，需求由绝对随机变量表示，但实际上，它应该对航空公司的定价政策有某种依赖性。还必须考虑到机场的运营要复杂得多，因为机场中的飞机形成了类似排队的东西。此外，还有许多不同的限制，这些限制受各种协议和法律的约束。

将来，准确的模型可以成为必不可少的集中工具，以方便对民用航空运输市场进行分析和预测，并使做出最佳决策成为可能。