后勤。介绍 只是复杂

我们所有人都喜欢梦想，尤其是在游览新地方或返回自己喜欢的地方时。没有什么比预想中的活动更能激发人们的灵感，而仅由于组织问题（尤其是机票的选择和购买）的存在而无所作为。出于某种原因，在内部，我们总是推迟发布此问题或将其转移给旅行社，元搜索引擎或其他聚合器。在实践中，有时会在屏幕上显示一条消息：“很遗憾，您的请求找不到任何内容。可能还有其他日子的航班。”

经常发生的情况是，并非总是响应路线搜索请求，而给出了飞行所需的结果，该结果立即转到结帐处。我们开始从一个站点转移到另一个站点以获得满意的答案。

类似情况的发生与缺乏直接沟通或缺乏预先计划的组合（转机）航线有关，或者提出了带有中转的航线，其中包括下一次航班等待时间超过5-6小时，甚至整天。

在各种各样的航空公司中，我们如何得到远远不能总是满足我们的答案？总的来说，如何通过算法构造寻找路线选择的算法？在这方面，应用数学可以通过算法和评估标准为我们提供帮助。


世界机场地图

我长期以来一直在处理后勤问题，当我面临着构建一个搜索引擎来搜索最佳路线的任务时，在我看来，这很琐碎。根据经验，我可以事先说，可以通过相当简单的方法并在较短的时间内解决它。但是，如果一切都这么简单，那么这篇文章就不会出现了。因此，加入该作品后，不久后我意识到它并不那么琐碎。

出行的起点（通常是旅行时发生的），正是我想到的这种方法，是决定以图形形式构建运输网络。运输网络最初包括有关机场，航空公司，其航班时刻表和转机时间指标的数据。

以此为基础，将机场视为图表的顶部，并且它们之间的飞行是边缘。结果，我们得到了一个骨架，就像骨架一样，在此基础上，我开始制定了一个时间表，该时间表具有自己的特征：出发和到达时间。此外，始终只能在特定时间沿边缘移动，这具有解决问题的特定选项：

• 最短旅行时间；
• 最少（或用通俗易懂的语言）移植数量；
• 选择复杂航线时从一个航班转换为另一航班的时间间隔。

困难在于，在任何情况下我们都不会仅使用一种特定情况，查询总是包含相关的搜索条件，包括一个或两个或多个优化条件。因此，标准的应用在所需路线选项的计算上施加了某些条件。除了上面列出的三个之外，该计算还包括使用服务类别的类别（第一，商务，经济），成本，乘客人数及其类别，以及影响结果的许多其他服务的可用性。因此，这完全开始适合我通过多准则优化（多用途优化）解决问题的概念，即通过多个准则找到最短路径（MOSP-多目标最短路径）。

但是，众所周知，为了检验一个假设，必须引用许多其他假设。作为解决该问题的另一种选择，考虑使用非线性编程。

假定图的弧线由矢量加权，则问题的解决方案可以简化为二次（非线性）编程。而且，如果矢量不是仅具有两个特征，即长度和在坐标轴上的投影，这一切都是完美的，这意味着在目标函数中存在不超过两个的变量。但是，在我的情况下，向量的组成部分彼此“冲突”，这与非线性（二次）编程是矛盾的。例如：“冲突”可能是由于每个航班都有特定的飞机容量，因此不可能出售更多座位。由于存在“冲突”，必须放弃通过非线性编程来解决问题的选项，而应采用相同的多准则编程。

在分析了解决问题的选项之后，我使用了分解的经典版本，包括以下部分：

1. 根据从出发点到到达点的所有“最短”路线的时间表进行搜索；
2. 根据条件在最“最优”的“最短”路径中搜索。

同时，在分解之后，这个问题在逻辑上随之而来，但是在哪种方法的基础上构建运输路线网络更好？哪个可用图形更适合解决此问题？

根据该流派的经典，没有找到一个，而是我开始考虑的几种模型。

时间延长模型

时间扩展图是有向图。该图的弧线是飞行的出发点和到达点的方向，并且峰值是飞行的时隙（起飞和着陆时间）。时间扩展模型的使用是用机场的高峰和弧线扩展原始图，通过根据航班时刻表将机场相互组合来反映航线的关系：



弧线表示为$$$e_{BC,3}$。例如，一条弧线连接了机场$$$B$ 与机场 $$$$C$$并由 $$$B$至 $$$C$由逗号索引指定 $$$3$表明这不是唯一的航班，而是连续第三次。而且，可以容易地对每个电弧进行加权，例如，电弧的重量$$$e_{BC,3}$ 可以计算为 $$$w_{BC,3} = t_{C,9}-t_{B,6}$。可以根据每个航班的时间指示器轻松地排列单个机场内的顶点，而且，根据机场内部的连接时间，可以通过弧线连接航班，这些弧线对应于从一个航班到另一个航班的可用转移时间。

时间扩展图的优点是可以在最短的时间内找到最快的到达路径，例如使用Dijkstra算法。使用此方法的缺点是顶点和边的多次增加，但是，这不会影响图形的稀疏性，因为边数的增加与顶点数的增加成比例。

时间相关模型

时间相关图是有向图，在原始图上没有其他转换。每个弧线对应于一条机场之间连接的航线，而弧线则具有一个特殊的数据集，其中包括有关沿该路线飞行的出发和到达时间的参数。从此数据集中检索的值取决于访问此弧发生的确切时间，因此名称为“时间相关”。



时间相关图的优点是它允许您查找传输次数最少的路径，缺点是每个弧的数据负担过重。

多图

多重图是一个有向图，它具有时间增强和时间依赖模型固有的特征集。



机场之间的弧线与扩展模型中的弧线一样多，但是这些弧线由起飞和到达时间“加权”，并且每个机场之间的航班之间的转机时间必须不断重复计算。另一方面，在多图表示中，与飞行有关的信息与在与时间有关的模型中一样多，但是所有这些信息都分配给许多弧。找到传输次数最少的路径就像在依赖时间的模型中一样简单，但是沿着一条弧线传递不会考虑其他弧线的信息，因此在找到传输次数最少的路径后，您将不得不重复此路径计算有关其他航班（弧）的信息。

以多重图的形式表示运输路线网络是时间延长和时间依赖模型的原始状态。到达时间最短的路径的搜索将通过时间扩展模型的相同转换特性执行，而传递次数最少的路径的搜索将通过时间相关的模型执行。并且需要增加网络计算时间。但是，这里存在一个细微差别，因为在一般情况下，根据两个标准搜索“最短”路径已经属于NP类困难任务，并且Dijkstra算法的修改会执行带有顶点标记的相当复杂的操作。

可以通过最简单的修改方法-Dijkstra算法（仅搜索帕累托最优路径）来考虑使用具有机场和航班的路线集合模型的多图来表示问题的计算复杂性。单个帕累托最优路径的标准总数不能比同时所有所有准则的其他帕累托最优路径差或更好。例如，具有两个标准{（30，10），（20，20），（10，30）}的总和如下的一组路径将是帕累托最优的。

作为一个更具说明性的示例，我们考虑算法在小图上的操作，该小图的弧线由二维向量加权：



修改后的Dijkstra算法在此类图上的操作以及在规则图上的常规算法将由具有连续触顶的迭代组成，不同之处在于每个顶点可能没有一个Pareto最优值，而是多个。另外，还必须保存有关每个和的计算值的来源的信息。

考虑到该问题考虑的是具有机场连接航班的航线，因此非常恰当的假设两个顶点之间可能有很多弧，并且每个顶点至少可以由三个分量矢量加权。但是随着向量分量的增加，帕累托最优路径也可能发生。此外，两个顶点之间的几乎所有弧都可以是帕累托最优的。在这种情况下，路径总和将包含更多的帕累托最优路径。这可以在一个由二维向量加权的小多重图形上看到：



允许在这种模型中使用经过修改的Dijkstra算法，因为它可以在多重图形上使用，但是算法的处理速度取决于顶点的数量。$$$n$，以及弧数 $$$m$。对于稀疏的简单图和常用算法，复杂度约为$$$O(n\log n+m\log n)$。但是，很难说出生成的多图是否将是“稀疏的”，因为在通常情况下，多图的边缘密度可能比完整图的边缘密度高得多。如果考虑到完整图的边数$$$E$ 由其顶点数确定 $$$V$根据公式：

$$$E={\frac {V(V-1)}{2}}$

边缘密度定义为：

$$$D={\frac {2E}{V\,(V-1)}}$

对于完整的图形 $$$max(D) = 1$，但是对于多图，边缘密度的值通常是无限的。

因此，我得出的结论是，可以使用Dijkstra算法找到最短路径，而使用Yen算法可以找到所有其他最短路径。假设在此阶段我们使用非加权弧进行操作，并且可以立即丢弃路径（例如进行四次传输），那么将确保在不超过20分钟的时间内搜索一条最短路径$$$O(n^{2})$。



考虑到本文没有涵盖实现的直接结果，我可以预先假设在考虑最佳时间间隔的情况下，对多图模型进行改进的Dijkstra算法是行不通的。

因此，我将继续讨论第一个子问题的立即解决方案，即与多准则优化有关的问题的解决方案，该问题是我通过条件优化方法选择的。该方法包括以下事实：尽管准则不一致，但始终存在最高优先级，而所有其他优先级都具有有效值。结果，整个任务的优化归结为最高优先级的优化。

任务的一个特点是，计算不仅包括直接飞行，这总是大大简化了任务，相反，包括转机或转机。因此，时变图模型非常适合解决该问题，因为路线中的转移次数通常不超过3-4个段。首先，与时间相关的图以航班的形式携带有机场之间连接的可用路线的全部信息。然后，考虑到通常的未加权图，计算出对接的出发和到达时间的估计值。在此阶段需要做的所有事情就是找到机场“ A”和“ B”之间具有预定数量（例如三趟）的所有有效路线。



考虑到在此阶段图形未加权，可以使用常规的广度优先搜索找到最短路径，并使用Yen算法找到所有其他最短路径。由于广度优先搜索是在线性时间中执行的，因此可以说，对于具有相同3次传输的所有路径，搜索时间将是线性的。

在评估算法的使用以查找最佳路线以及时间表更新频率上的数据可用性时，我们可以说在方向上具有所有``最短''路径的预先计算矩阵的想法是合理的。当然，在创建矩阵的初始阶段，这样的解决方案将变得很费力，但是在将来，它将允许您几乎立即找到“最短”路径，并迅速对矩阵本身进行调整。

但是，问题仍然存在，哪条具有连接和转移的“最短”路线是最“最短”的路线？否则，我们将拥有一系列数据，无法做出决定。在这种情况下，通常将一组标准降低为最佳标准：

• 最短旅行时间；
• 最小转账数。

这两个标准都可以具有自定义的间隔或时间值，因此仅需合并路线并即时检查允许值的对应关系：



考虑到最大转机次数的值在3-4之间变化，某些航班组合将立即被排除在外，这使我们找到了以下子问题的解决方案-在路线中确定该品种最“最佳”的标准。

标准系统是路线发布形式中的主要问题，因为“最优”的概念将取决于特定乘客的偏好，并且他通常只有在收到请求答案后才能通过设置不同的过滤器集来管理接收到的路线。即使您根据“最短”路径为他提供了有序的路线，结果也将是一系列数据，这些数据将使乘客无法做出决定，并将导致无休止的搜索选择。因此，考虑到过滤器应用程序的各种组合（集体和单独）的路由选项数组的形成是影响整个任务的极其重要的参数。

然后需要考虑什么？如何考虑？创建排名过滤器是一项非常耗时的任务，因为一组过滤器，它们的数量和相互影响的程度可以通过优化搜索算法而显着改变搜索最佳路径的结果。那它包括什么呢？我们都知道关键的航班参数-航空公司信息，出发/到达时间，出发/到达机场的日期，时区偏移，转机和中转的信息，但我们常常忘记了这样的数据，即到达机场或如果随后的出发地是从该地点的另一点出发，则在机场之间建立联系的旅行时间。而且我们不应该忘记我们的乘客的类别，以及其数量，以便根据关税政策，不仅及时提供最佳路线，而且还提供价格。

无论这听起来有多矛盾，一系列的提议都应该使每个旅行者都充满一定的信心。基于数学原理的信心，其中包括提供最少的建议书，并提供考虑了偏好并减少不可抗力风险的路线选项。在这种情况下，不可抗力不仅是航班延误或起飞/到达的时间和机场发生变化的可能性，而且还是诸如自然，技术和流行病学情况之类的指标，要求完全或部分取消航班。

现实中管理数据的能力每次都会带来许多问题：是否考虑了所有因素，还可以添加其他内容。并且在建立交通运输路线网络的这种愿望中，出现了一个与以下事实有关的悖论，即算法应该同时是最优的和简单的。但是您常常不得不牺牲一些东西，从这里开始，将初始标准最小化到我认为最可接受的最小数量。

如果我们沿着选择标准的道路前进，然后省略次要标准，则我们可以区分这样的选择，这些选择不仅考虑到整个行程的时间，成本和舒适度，转机次数及其转送时间，而且还考虑了有关机场拥堵的信息以及机场之间的通信数据在将一个机场改为另一个机场时。这是有道理的，在建立连接时，要考虑到一个城市中多个与外部机场通信不同的机场的存在，不仅会计算空中交通流量，还会在计算时间和航线形成时计算出现这种情况时的移动时间。他们有一个地方...

在我们有一组影响偏好的标准集的情况下，选择“最优”路线的决策系统只是我最初没有想到的绊脚石。即使将它们引导到某种系统化状态，它们之间的应用也存在很多差异，因此我们将分别考虑它们。

舒适

每个人对“舒适”概念的含义都有不同的理解，但航空公司接受以下级别的信息：

• 一年级;
• 商务课程;
• 经济舱。

在我的方法中，我承认可以测量``舒适度''参数并将其值从1转换为10，并形成以下条件：特定航班的此指标越低，排名系统中的舒适度就越低。在这种情况下，立即出现与这样的量的非可加性有关的问题，即。两次飞行的舒适度指标之和不会反映其总体舒适度。例如，有两种路线组合：

• 第一条路线分为两部分，第一条袭击的舒适度为10，第二条袭击的舒适度为1；
• 第二条路线分为两部分，第一条路线的舒适度为6，第二条路线的舒适度为5。

结果，每条路径的“舒适”参数的总和和算术平均值将是相同的，但它们不会反映事务的真实状态。但是，由于需要考虑两条路线的总舒适度，因此在这种情况下最可取的是将它们的平均值与标准偏差一起使用，这将使我们能够估算舒适度的``分布''。也就是说，在最初考虑时，我们关注平均舒适度，然后，通过标准偏差的大小，我们考虑这些舒适度彼此之间的巨大差异。因此，该标准分为两个非常“接近”的标准。尽管另一方面，即使没有经过艰苦的检查，很显然，这种“可衡量的”舒适度的假设与现实相距甚远，因为我们有众所周知的班级。其次，显而易见的是，整个旅程的舒适性在某种程度上取决于其他标准的功能，例如，飞行时间，中转次数及其持续时间，航空公司及其机队的等级。关注这个标准是否有意义是一个问题。毕竟，该方法是基于对“最佳”方式的整体进行会计处理的系统。因此，将来我们将以两个指标的形式使用舒适度表示形式：航班舒适度指标的算术平均值及其标准偏差。转移次数及其持续时间，航空公司及其机队的等级。关注这个标准是否有意义是一个问题。毕竟，该方法是基于对“最佳”方式的整体进行会计处理的系统。因此，将来我们将以两个指标的形式使用舒适度表示形式：飞行舒适度指标的算术平均值及其标准偏差。转移次数及其持续时间，航空公司及其机队的等级。关注这个标准是否有意义是一个问题。毕竟，该方法是基于对“最佳”方式的整体进行会计处理的系统。因此，将来我们将以两个指标的形式使用舒适度表示形式：飞行舒适度指标的算术平均值及其标准偏差。

转移的持续时间

路线协调有两种类型：

• 转移（航空公司之间事先商定）；
• 对接。

此列表中有趣的是“连接”的概念，它是在相同航线上将两家或两家以上航空公司按约定的时间段组合而成的结果，基于所需的最短连接时间，但并不总是足以从一个航班转换为另一航班。因此，为了在这样的路线上组合航班，必须计算完成连接所需的足够时间。

在这里，我们感到不和谐，因为通常可以将此类航班排除在要约的选项之外，但是由于存在这样的标准，因此在某些情况下，对我们的乘客而言，临时等待超过一天的时间是“最佳”的。因此，有意义的是不要放弃移植时间过长的路径，因为尽管很少，但仍然可能需要它们。

机场

拥堵在计算“最佳”航线时，可以估算出机场拥挤指标，并在考虑机票参与度的情况下评估售票时的填充程度。显然，在这种假设下，最短的接驳时间将对机场的拥挤有一定的功能依赖性。

转移次数

移植的数量本身是矛盾的。实际上，通常可以通过这种方式降低整个路线的成本。另一方面，存在一类乘客，即使发生一次变化也会造成许多问题。不要忘记以下情况：中转路线是最“最佳”的，这是因为昂贵的商务舱机票仍留在所需的路线上，或者说，有些机票的票价没有兑换/退款的可能性，这导致拒绝的可能性建议的选项。

但是，在转机数量上，还规定了另一个子标准-这是从一个机场转移到另一个机场的可能性。因此，连接的建立通常是一项艰巨的任务，因为在计算路线时，有必要安排机场之间的往返时间，这就需要订购机票以在城市内运输以分段进行。

“旅行时间”和“成本”标准绝对是可加数量，因此它们依赖于具有排名系统的直接指标。如果不需要将总旅行时间包括在到达机场或从机场出发到目的地的时间的计算中，以及在考虑到机场之间往返的额外费用的需要时，一切都会很好。在这一阶段，让我忽略这一澄清。

全球目标的层次结构

假设“最优性”的定义应始终被理解为最佳，并且不仅对于乘客，而且对于航空公司，机场以及可能的其他旅行服务提供商也应如此。

在这种情况下，将单个非常复杂的目标划分为子目标是唯一的出路。这种细分可能看起来像这样：



很明显，为了满足所有感兴趣的领域，人们将必须实现较少的“全球”目标，但在某种程度上是相互矛盾的目标。如何实现呢？也许这是另一篇文章的重要话题。但是展望未来，我们可以说将复杂的目标划分为更简单的子目标也与优化和图论相关联，即寻求最佳的层次结构。

决策系统与拉普拉斯（Laplace），沃尔德（Wald），萨维奇（Savage）和赫维兹（Hurwitz）的标准之类的方法紧密相关，因此，拥有一系列“最短”路线，我不禁要知道其中哪些路线是最“最佳”的。

解决多用途优化问题的最通用方法之一是Pareto和Slater寻找最佳解决方案。如果我们根据Slater的最优性标准评估“最短”路线的阵列，则最优路径将同时被所有标准视为最佳路径。如果某条参数中的所有其他路径均优于某条路径，而另一条参数（如一个人不能通过至少一个标准来改善一条道路，而不能通过其他标准来恶化它。

对于最小化问题，所有的Pareto和Slater最优解都可以通过两个标准轻松地以图形方式展示：



带有Pareto最优标准的参数的点集用绿色表示，而Slater最优解的点用黄色表示。Slater最佳点集还包含Paretto最佳点集。在所考虑的问题的框架内，所有这些点将是向量的末端，起始于七维空间的原点。

总之，我可以说这只是冰山一角，它使您可以初步了解搜索引擎在形成最佳路线时会遇到的情况。