期刊
MATHEMATICS OF OPERATIONS RESEARCH
卷 25, 期 1, 页码 36-62出版社
INST OPERATIONS RESEARCH MANAGEMENT SCIENCES
DOI: 10.1287/moor.25.1.36.15211
关键词
dynamic network; polynomial-time algorithm
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 our of each source and into each sink in the minimum overall time. 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 Row problems have numerous other applications: in some of these, the capacities are small integers and it is important to rind integral Rows. There are no polynomial-time algorithms known for most of these problems. 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据