Lexicographically optimal earliest arrival flows

Journal Article

Abstract A dynamic network introduced by Ford and Fulkerson is a directed graph in which each arc has a capacity and a transit time. The evacuation problem is one of the fundamental problems in a dynamic network. The goal of this problem is to find the minimum time limit Θ such that we can send all the supplies to the sinks within time Θ. An earliest arrival flow is an optimal flow for the evacuation problem such that the amount of supplies which have reached the sinks is maximized at every time step. It is known that in a dynamic network with multiple sinks, if the sinks have capacities, then an earliest arrival flow does not necessarily exist. In this paper, to cope with this issue, we first introduce a lexicographically optimal earliest arrival flow in a dynamic network with multiple sinks. Then we propose a pseudo‐polynomial‐time algorithm for finding a lexicographically optimal earliest arrival flow. Furthermore, we prove that if the transit time of every arc is zero, then we can find a lexicographically optimal earliest arrival flow in polynomial time.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.