Journal
MATHEMATICS OF OPERATIONS RESEARCH
Volume 25, Issue 1, Pages 36-62Publisher
INST OPERATIONS RESEARCH MANAGEMENT SCIENCES
DOI: 10.1287/moor.25.1.36.15211
Keywords
dynamic network; polynomial-time algorithm
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available