连续时间动态逆流模型和算法

文摘

研究非常具有挑战性的紧急疏散计划问题是提升的问题,由于大规模的自然或人为灾害。这个过程将疏散人员的最大数量从灾难性的地区安全的目的地尽可能快速高效地。逆流式是一种被广泛接受的模式很好的解决方案的疏散规划问题。它增加了对外公路运输能力扭转的方向道路对安全的目的地。连续动态逆流问题发送的最大数量流流量从源到汇在每一刻的时间单位。我们建议连续动态逆流式问题的数学模型。我们提出有效的算法来解决的最大连续动态逆流和最快的连续逆流问题单源单水槽任意网络和连续最早到达逆流问题在单源单水槽串并联网络未定义的供给和需求。我们还介绍了连续的近似解最早到达两端任意网络反向流动问题。

1。介绍

在正常的理解,转变居民的疏散规划问题是程序从灾难性的区域安全领域尽可能成功最大的可靠性。疏散网络,逆流式是一个被广泛接受的模型,一个好的解决方案,而不是一个最佳实践案例。它增加了出站道路容量通过逆转弧的方向。它是一个具有挑战性的问题找到一个网络重构与理想车道方向满足给定的约束优化给定的目标。,目的是应对不同的大规模的灾害,已研制出许多逆流式撤离计划,寻求消除交通堵塞,使交通系统和光滑。在文献中,我们发现不同的数学模型,启发式优化和仿真技术与交通网络的反向流动,(1,2]。

只有一些文献中分析优化技术处理离散动态逆流式问题。第一个双端最大动态逆流式解析解(MDCF)问题已经提出了2和有效的算法)。多端网络的MDCF问题是np难的强烈即使有两个来源,一个水槽,反之亦然。证明遵循通过减少3-SAT和分区的问题1,2]。作者在2]也解决了最快的逆流式(QCF)问题在多项式二端网络。其解决方案是基于参数搜索算法(3]。他们证明了多端QCF问题比3-SAT和分区。一个最佳的解决方案MDCF(和两端串并联EACF)问题图(TTSP-graph)已获得4]。作者在5]表明,EACF问题一般图形总是存在放松弧逆转能力的次数,一个电弧炉的解决方案要求这个属性。二端网络,一个近似EACF解决方案已经提出了(6]。对于多端网络与给定的供给和需求,按最大动态逆流(LMDCF)问题已经解决在多项式时间复杂度5]。此外,最早到达转运逆流问题在不同的特定的网络已经解决(7]。

在本文中,我们引入一个连续逆流式模型和提出一些有效的算法来解决这个问题。我们主要关注问题的解析解。然而,从实用的角度来看它的重要性也会有趣。

本文的组织如下。节2,我们研究一度连续网络流问题和解释的其余部分中使用的术语。一个多项式时间算法介绍了逆流式配置的最大连续动态逆流问题部分3。相比的最大连续动态逆流,我们解决问题最快的连续逆流,发现最小改变给定的积分值所需的时间流的部分4。通过发送的最大流量从一开始的时候,我们解决连续最早到达逆流问题呈现强烈的多项式时间算法在部分二端串并联网络5.1。部分5.2提出了一种近似解连续最早到达两端任意网络反向流动问题。部分6总结了纸。

2。基本的外延和模型

一个有向图在哪里和,一组节点和一组,代表了疏散场景。我们已经考虑了反向流动问题,因此允许双向网络配置。让和是一组源节点,疏散人员的初始位置,水槽和一组节点,也就是说,分别与足够的容量,疏散人员的安全位置。节点和代表的单一来源和单一的水槽。让在一个实际上是一个上限的流电弧。让的速度流流进入特定的弧/时间单位。它是由电弧弧的容量有限;也就是说,。所需的时间将一个单位的流动从节点来运输时间。这里我们考虑常数运输时间;也就是说,如果我们从节点发送一个单位的流动在时间与流量,那么它将达到节点在时间与流量。我们假设,在那里和为节点。疏散建模为流的组织通过网络。

预定的时间,我们代表了交通网络的所有数据的集合。我们假设一个有限的时间范围这意味着必须在给定的停止时间之前发生的一切。时间可以在离散增量或不断增加。在离散时间的方法,我们出现在网络等一个合适的时间单位和时间相关参数都是整数。但是,在连续的方法,可以取任何值。通过将连续流模型转换为离散的时间可以在实际离散模型。时间单位的选择直接影响问题;如果短时间单位,然后问题是更复杂的。让是时间的领域,可以有效的对离散和连续的方法;也就是说,在离散模型在连续模型。

我们的逆转是。逆流式配置的网络与对称的中转时间,辅助网络包含修改后的电弧能力和交通倍在一条边在如果在。剩下的图结构和数据是不变的。

2.1。离散成连续模型的自然转换

让和在一个流动的量和流率,分别。因此,流的数量吗在离散时间和流输入的数量吗在连续时间。这两个函数在连续和离散模型密切相关,分别为(8]:

离散时间之间的区分方法和持续时间的方法取决于流进入一个在时间已经到达的头节点或仍在电弧在那一刻。在离散方法中,我们假设这样一个流已经在头节点时间。

让是一个可行的离散流进入在时间为并设置连续的流量来为。我们假设弧能力不改变。然后,从这种自然转换,我们获得一个可行的连续流和流值在任何积分区间,,将两个相同和。作者在9)提出了这个自然变换对许多离散动态流基于链可分解的流变换成连续动态流动和证明了其最优性。

假设是一个静态流和它有一个标准链分解成一组与满足所有连锁开始和结束的终端节点和使用相同的弧线方向在离散时间的方法。所有的长度链满足标准链分解。然后,计算获得的一份可行的动态流求和动态流动每个链流引起的。

积分时间范围的自然转换链可分解的流动是可行的。如果不是积分,那么我们有一个离散时间。由于运输时间的积分,所有链流积分长度。这导致链流动使用时间范围也可以使用绑定。链流不受时间的影响开始使用一个弧。但它会降低链流使用弧的时候。因此,一个离散地平线链可分解的流动可以自然地变成一个连续的地平线流和停止发送流沿着每个链流在时间相反的时间。在动态流,链引发相同的流在每个链流。因此如果离散链可分解的流动是可行的,然后连续链可分解的流动也是可行的。

2.2。连续动态流模型

静态流是定义在满足约束的能力和流守恒约束: 如果一个静态流满足流守恒约束在终端,那么它是一个静态循环。剩余的网络一个静态流对能力是相同的网络与重新定义了剩余的能力对电弧和对落后的弧。

一个离散动态流是一个函数代表每个弧流在每一个时间步满足容量约束所有时间的步骤在节点和流守恒约束允许延期:

让是一个连续的动态流量与容量约束流量约束和流守恒约束类似的离散动态流,和随着时间的推移,取而代之的是一个积分如下: 对于一个给定的时间最大持续动态流(MCDF)最大化问题在(7)满足约束(5)和(6): 连续最早到达流(CEAF)最大化问题在(8)满足约束(5)和(6)为所有:

3所示。最大连续动态逆流

在本节中,我们讨论的最大连续动态逆流式(MCDCF)问题。回想一下,最大动态流(MDF)问题解决了10)通过求解最小费用流(MCF)问题在弧弧成本旅行时间。已获得的MDF暂时重复流(基金会)。静态最优流分解为路径的扶轮基金会,MDF屈服。与静态流和一个链分解、作者(10,11)计算了MDF值与给定的时间地平线的扶轮基金会在(9)。右边的总和仅取决于静态流,而不是特定的:

(表达的暂时的重复流9)可以扩展到连续时间。与固定网络弧能力,作者在12)表明,最大持续动态流获得了暂时的重复流的定理1。

定理1(见[12])。MCDF的时间在一个网络是有价值的在哪里是一个最小费用循环流(MCCF)和一个额外的网络吗电弧与成本和无限的能力。

在本节中,我们首次研究单一源和单一的水槽MCDCF问题。我们假设弧逆转在时间为零,没有任何处理成本。这意味着,如果我们选择反向弧形,它仍然是逆转来。我们假定网络是允许不对称对电弧能力。然而,如果两个方向包括弧的网络,然后运输时间这两个弧必须相同。因此,扭转电弧弧的容量只有变化但不改变它的运输时间。

问题2。给定一个动态网络,MCDCF问题是要找到一个最大持续流最大化目标(7)对约束(5)和(6),可以发送来在时间,如果可以扭转弧的方向在时间为零。

回想一下,作者在2)解决了最大在离散时间动态逆流式(MDCF)问题。的哲学MDCF解决方案是每个MDCF在原始网络的解决方案相当于MDF的解决方案在相应的辅助网络。在连续动态逆流模型与弧逆转时间为零,反弧的容量是通过添加双向弧能力但渡越时间不变。因此,弧上的流量增加但不超过逆转的能力。这证明最优MCDF辅助网络上获得与自然的变换(9)类似于一个可行的MCDCF原始网络上在引理3。

引理3。每个MCDCF原始网络相当于MCDF在相应的辅助网络。

先解决MCDCF问题,我们采用离散MDCF算法(2在二端网络。通过逆转弧的方向向下沉,我们计算一个辅助网络。然后,应用连续时间的MCF算法提出了(9),获得MCDF辅助网络。获得的MCDF分解为路径和可拆卸的周期。一个相反当且仅当流大于或者如果有一个负的流。

算法4(最大持续动态逆流(MCDCF))。(1)给定一个网络。
(2)获得辅助网络。
(3)在网络,我们应用MCF算法(9与流量)、容量和运输时间。
(4)执行流分解成链和循环流动的步骤(3)所带来的最大流量和循环流。
(5)相反,当且仅当流吗大于或者如果有一个负的流和由此产生的流与弧MCDF逆转的网络。
(6)获得的最大连续动态逆流式的解决方案。

展示算法的可行性4,只是足以表明,步骤(5)是定义良好的。流分解为路径和周期与积极的步骤(4)中流动。积极的流沿着所有周期取消,没有流沿任何周期。因此,有一个流沿或但从未在弧。这证明不大于流动逆转能力在所有弧时间单位。这证明流是有界的能力在所有反弧时间单位。

定理5。算法4解决了MCDCF两端网络优化问题。

证明。通过在线性时间扭转弧的方向,我们获得辅助网络。在我们运行的连续动态暂时重复流算法9出MCDF解决方案通过使用定理)1。获得的连续流分解成链和周期。周期是删除。在步骤(3)中获得的流不改变算法的步骤(4)和(5)。因此,这在辅助网络流是最优的。此外,任何最优流在辅助网络相当于在原始网络最优逆流(cf引理3)。也就是说,MCDF相当于MCDCF在吗。

推论6。MCDCF解决方案可以获得的,在那里和所需的时间解决流分解和最小费用流问题,分别。

证明。获得的自然转换,MDF解决暂时的重复的最小费用流问题(MCF)10)是一种MCDF。因此,解决MCDF问题的复杂性是相同的离散解因为算法的复杂性4是由步骤(3)和(4)。

4所示。最快的连续逆流

MCDCF问题相比,最快的连续逆流(QCCF)问题转移给积分值流从源下沉在最少的时间通过逆转弧的方向向水槽没有任何处理成本。

问题7。给定一个动态网络,QCCF问题是找到的最小时间满足约束(5)和(6流值)需要发送一个给定积分从来在电弧能力在时刻0逆转。

在离散时间设置,最快的多项式逆流问题已经解决(2二端网络。这个解决方案是参数搜索算法的基础上(3]。首先一个上界取得最快的时间在多项式时间内通过计算从源到汇的道路。然后一个二叉搜索一再被应用来获取MDCF沿着小路,直到所有供应源发送到水槽里。

在连续时间设置,使用的自然转换9),QCCF问题二端网络对于给定积分供应可以解决多项式。首先,我们将考虑到网络到它的辅助网络。在辅助网络,我们解决问题最快的连续流(QCF)使用自然的变换(9)在步骤(3)的算法4。在[9),整体供应和整体运输时间,最快的时间流是一个有理数,分母有界的大小最小割的网络。这一次也可以通过二进制搜索算法(3]在离散的解决方案。由引理3,获得QCF是一个可行的QCCF。

定理8。对于给定的二端网络与整数供应多项式,QCCF问题可以解决。

请注意,辅助网络的建设可以在多项式时间内完成。此外,可以在多项式时间内获得最快的连续流使用的方法9]。从引理3解决方案,获得QCF辅助网络等于QCCF在原始网络的解决方案。QCF解决方案的辅助网络可以在多项式时间内计算,解决QCCF所需的整体复杂性问题是多项式。

5。连续最早到达逆流

我们最早发起连续逆流到来(CEACF)问题在这一节中。它也被称为通用连续逆流式(UCMCF)最大的问题。这是一个扩展的最大连续动态逆流问题额外属性:累积流量到达沉在每一个考虑的时间和所有之前的时间被认为是最大的。这个性质叫做最早到来的财产。

问题9。让二端网络。CEACF问题是要找到一个可行的连续动态流从源下沉最大的时间是哪一个通过最大化目标(8)满足约束(5)和(6)如果可以扭转弧的方向在时间为零。

一般文献中没有有效的解决方案的双端最早到达逆流问题(EACF)任意的供给和需求的终端即使在离散时间的方法。作者在4]研究了两端串并联图表(TTSP-graphs)和问题提出了强烈的多项式时间算法来解决这个问题。他们的算法已经通过修改MDCF算法(2)使用MCCF算法(13]。在串并联网络的主要优点是,每周期残留网络中负的周期长度。这解决了MCCF问题引入11在辅助网络对MDF)问题。暂时的重复流从而获得最优的解决方案EACF两端串并联图问题。

一个单一的与开始串并联终端和结束终端。让和是两个串并联图形终端开始和和终端和,分别。然后,图通过识别作为系列的组合是一个串并联图和作为终端。这个图通过识别作为也作为在并行组合是一个串并联图和作为终端。

此外,作者在6]研究了近似解为EACF两端任意网络未定义的供给和需求。他们还提出了一个完全多项式时间近似算法计算的近似解EACF通过逆转弧的方向在时间为零。这个解决方案是基于MDCF算法(2)和近似电弧炉算法(14]。

在特殊TTSP网络,我们强烈解决CEACF问题在多项式时间(cf部分5.1)。我们也建立一个多项式时间算法,给出了近似解的两端任意CEACF问题网络内的一个因素对于任何(cf部分。5.2)。

5.1。连续最早到达TTSP网络流

首先我们考虑的算法4TTSP网络。它被替换修改步骤(3)与最小费用循环流(MCCF)算法的13]。MCCF算法解决了MCDF在强烈多项式时间最早到达财产问题。我们只使用弧流在TTSP网络。因此,残留网络中每个周期负的周期长度。这解决了MCCF问题引入11)与自然的变换(9辅助网络MCDF问题)。

算法10(连续时间EACF TTSP网络)。(1)在步骤(3)的算法4,我们运行的最小费用循环流算法13)与自然的变换(9)有流量、容量和运输时间。
(2)获得连续的最早到达逆流TTSP网络解决方案。

MCDCF解决方案获得的算法4没有最早到来的财产。它无法找到CEACF具有弧逆转功能的解决方案。因为在给定的网络图1 (b)可能有两个方向和,很难决定哪些是最好的定位在连续时间。但在串并联网络如图1(一),没有任何方向之间的节点和。因此,算法4找不到CEACF解除非串并联网络。CEACF的并发症问题,因为抛的要求等中间弧对时间离散解的4]。

(一)

(b)

算法10由于算法的可行性是可行的吗4。该算法计算MCDCF TTSP网络解决方案。由于最小费用循环流的算法13)与自然的变换(9),获得MCDCF解决方案总是最早到达流的财产。

定理11。算法10解决了CEACF TTSP网络优化。

证明。通过创建辅助网络考虑到网络的,我们应用MCCF算法(13向前,只使用弧发送流但不落后的弧线。MCCF算法给出了暂时的重复流,通过自然的变换(9]的定理1从算法,获得流10在网络辅助MCDF吗最早到达属性。由引理3,MCDF是一个可行的MCDCF原始网络与最早到来的财产。因此,在TTSP-graph CEACF已经解决了。

推论12。TTSP网络CEACF问题可以解决时间复杂度。

证明。算法的复杂性10是由MCCF算法(13]。MCCF算法的复杂性在离散时间。通过自然的变换(9),这可以扩展到连续时间之后的结果。

5.2。近似CEACF

没有任何多项式时间算法解决CEACF两端任意网络问题与未知的供给和需求,我们在本节讨论其近似解。作者在6)提出了一个多项式近似算法,得到一个离散时间流值内的EACF两端任意网络问题与未知的供给和需求。回想一下,算法4不给CEACF解决方案没有任何修改。因此,我们提出一个多项式近似解的CEACF这个网络。

13题。让二端网络。让被给予。然后,问题是要找到一个近似解CEACF从源代码下沉内部的因素,因为在时间如果弧的方向可以逆转时间零没有任何成本。

我们替换步骤(3)的算法4通过完全多项式时间的近似算法14在离散时间与自然的变换(9)连续时间。其他步骤保持。设置初始流,,,,。的算法14)结合容量扩展最短增广路径算法。在他们的动态网络,所有的能力都是均匀整除。起初,他们获得了静态流使用最短增广路径算法,直到流值超过剩余的能力甚至是四舍五入到最近的号码吗。流从每个扩展添加到计算一组链流动这将给最后的动态流。因此,每个连续的阶段使用剩余网络获得前一阶段整除,多个沿着最短路径,增加流到新增加的流量价值超过补充说,增加链流动,最后轮剩余能力所以他们整除。这一过程持续进行直到没有增广路径长度小于或等于。

算法14(近似连续的最早到达逆流)。(1)在步骤(3)的算法4,我们解决CEAF问题使用完全多项式时间的近似算法14)与自然的变换(9]。
(2)获得光纤网络CEACF问题的解决方案。

由于算法的可行性4我们的算法,算法14,也是可行的。现在我们证明算法的正确性。

定理15。算法14计算的近似解CEACF两端任意网络问题有效。

证明。回想一下,我们首先给定网络转化为辅助网络在时刻0没有处理成本。辅助网络,我们解决近似的连续电弧炉的问题。根据(9)的自然转换近似离散电弧炉进行了连续动态流中的价值任何CEAF的间隔。它适用于积分和真正的。因此,获得近似CEAF辅助网络相当于光纤对CEACF原始网络。

推论16。算法14计算光纤的CEACF时间。

证明。作为电弧炉的完全多项式时间近似算法的14)要求时间,算法的复杂性14需要类似的CEACF复杂性计算近似。

6。结论

我们研究了连续动态流和离散动态逆流式问题。然后,我们介绍了连续逆流模型MCDCF, QCCF, CEACF问题自然转换。我们给出了多项式时间算法解决MCDCF和QCCF两端任意网络问题与未定义的供给和需求。特别是网络,TTSP,我们解决了CEACF强烈多项式时间复杂度的问题。此外,在任意的二端网络,我们提出了一个近似解CEACF问题在多项式时间复杂度。

我们解决这些问题有相同的复杂性没有逆流,但根据离散动态逆流式自然转换成连续动态逆流流动值可能翻了一倍。在逆流,我们可以转运给定值两倍没有逆流流动。

我们所知,这些问题我们介绍了首次在连续网络反向流动的方法。此外,我们有兴趣开发连续逆流模型和算法的网络流问题多端网络的灵活性弧随时逆转。此外,我们也很有兴趣在实现连续逆流技术案例研究在我们的未来的工作。

相互竞争的利益

作者宣称没有利益冲突。

确认

短歌Nath Dhamala要感谢亚历山大•冯•洪堡基金会研究支持的疏散计划。

引用

美国金、美国Shekhar和m . Min”逆流式交通网络重新配置为疏散路线规划,“IEEE工程知识和数据,20卷,不。8,1115 - 1129年,2008页。视图:出版商的网站|谷歌学术搜索
s . Rebennack a . Arulselvan l . Elefteriadou, p . m . Pardalos“最大流问题的复杂性分析与弧逆转,”杂志的组合优化,19卷,不。2、200 - 216年,2010页。视图:出版商的网站|谷歌学术搜索|MathSciNet
r·e·Burkard k Dlaska, b . Klinz“最快的流动问题,”Zeitschrift毛皮运筹学,37卷,不。1,31-58,1993页。视图:出版商的网站|谷歌学术搜索|MathSciNet
t . n . Dhamala和美国Pyakurel”,最早到达逆流式串并联图问题,“国际运营研究杂志》上,10卷,不。1,1-13,2013页。视图:谷歌学术搜索|MathSciNet
Pyakurel和t . n . Dhamala”网络上逆流式疏散规划模型和算法问题,“国际运营研究杂志》上,12卷,不。2,36-46,2015页。视图:谷歌学术搜索|MathSciNet
r·c·Dhungana Pyakurel, s . r . Khadka和t . n . Dhamala“普遍最大逆流式疏散计划,”国际运营研究杂志》上4卷,第78 - 67页,2015年。视图:谷歌学术搜索
Pyakurel和t . n . Dhamala“最早到达逆流,疏散计划”工业和管理杂志》上的优化,2015年。视图:谷歌学术搜索
b . Kotnyek一个带注释的动态网络流的概述INRIA Sophia Antipolis,法国,2004年。
l·k·弗莱舍和e .缓慢的“有效的连续时间动态网络流算法,”行动研究快报,23卷,不。3 - 5,71 - 80年,1998页。视图:出版商的网站|谷歌学术搜索|MathSciNet
f·r·福特和d·r·Fulkerson流网络美国新泽西州普林斯顿大学,普林斯顿大学出版社,1962年。
l·r·福特jr .)和d·r·Fulkerson“构造最大动态流从静态流,”运筹学》第六卷,第433 - 419页,1958年。视图:出版商的网站|谷歌学术搜索|MathSciNet
e·j·安德森·纳什和A·b·菲尔波特“一类连续的网络流问题,”运筹学的数学,7卷,不。4、501 - 514年,1982页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
美国Ruzika、h . Sperber和m·施泰纳”最早到达流串并联图”,网络卷,57号2、169 - 173年,2011页。视图:出版商的网站|谷歌学术搜索|MathSciNet
b·e·霍普有效的动态网络流算法[博士。论文),康奈尔大学,1995。

行动研究进展

文摘