The Quickest Transshipment Problem

DOI Web Site 被引用文献21件

書誌事項

公開日
2000-02
DOI
  • 10.1287/moor.25.1.36.15211
公開者
Institute for Operations Research and the Management Sciences (INFORMS)

この論文をさがす

説明

<jats:p> A dynamic network consists of a graph with capacities and transit times on its edges. The quickest transshipment problem is defined by a dynamic network with several sources and sinks; each source has a specified supply and each sink has a specified demand. The problem is to send exactly the right amount of flow out of each source and into each sink in the minimum overall time. </jats:p><jats:p> Variations of the quickest transshipment problem have been studied extensively; the special case of the problem with a single sink is commonly used to model building evacuation. Similar dynamic network flow problems have numerous other applications; in some of these, the capacities are small integers and it is important to find integral flows. There are no polynomial-time algorithms known for most of these problems. </jats:p><jats:p> In this paper we give the first polynomial-time algorithm for the quickest transshipment problem. Our algorithm provides an integral optimum flow. Previously, the quickest transshipment problem could only be solved efficiently in the special case of a single source and single sink. </jats:p>

収録刊行物

被引用文献 (21)*注記

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ