Earliest arrival flows in networks with multiple sinks

被引：6

作者：

Schmidt, Melanie ^{[1
]}

Skutella, Martin ^{[2
]}

机构：

[1] Tech Univ Dortmund, Lehrstuhl 2, Fak Informat, Dortmund, Germany

[2] Tech Univ Berlin, Fak 2, Inst Math, Berlin, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2014年 / 164卷

关键词：

Earliest arrival flow; Flow over time; Evacuation problem; MAXIMAL DYNAMIC FLOWS; TIME; ALGORITHMS;

D O I：

10.1016/j.dam.2011.09.023

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Earliest arrival flows model a central aspect of evacuation planning: in a dangerous situation, as many individuals as possible should be rescued at any point in time. Unfortunately, given a network with multiple sinks, flows over time satisfying this condition do not always exist. We analyze the special case of flows over time with zero transit times and characterize which networks always allow for earliest arrival flows. (c) 2011 Elsevier B.V. All rights reserved.

引用

页码：320 / 327

页数：8

共 17 条

[1]

[Anonymous], USE DIRECTED ROUTES

[2] Approximating earliest arrival flows with flow-dependent transit times [J].

Baumann, Nadine ;

Koehler, Ekkehard .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (02) :161-171

[3] Earliest Arrival Flows with Multiple Sources [J].

Baumann, Nadine ;

Skutella, Martin .

MATHEMATICS OF OPERATIONS RESEARCH, 2009, 34 (02) :499-512

[4]

Burkard R. E., 1993, ZOR, Methods and Models of Operations Research, V37, P31, DOI 10.1007/BF01415527

[5] NETWORK MODELS FOR BUILDING EVACUATION [J].

CHALMET, LG ;

FRANCIS, RL ;

SAUNDERS, PB .

MANAGEMENT SCIENCE, 1982, 28 (01) :86-105

[6] Efficient continuous-time dynamic network flow algorithms [J].

Fleischer, L ;

Tardos, É .

OPERATIONS RESEARCH LETTERS, 1998, 23 (3-5) :71-80

[7] Quickest flows over time [J].

Fleischer, Lisa ;

Skutella, Martin .

SIAM JOURNAL ON COMPUTING, 2007, 36 (06) :1600-1630

[8] Faster algorithms for the quickest transshipment problem [J].

Fleischer, LK .

SIAM JOURNAL ON OPTIMIZATION, 2001, 12 (01) :18-35

[9] CONSTRUCTING MAXIMAL DYNAMIC FLOWS FROM STATIC FLOWS [J].

FORD, LR ;

FULKERSON, DR .

OPERATIONS RESEARCH, 1958, 6 (03) :419-433

[10]

Gale D., 1959, Mich. Math. J., V6, P59

← 1 2 →