The quickest transshipment problem is a problem defined in a dynamic network with multiple sources and multiple sinks. The goal of this problem is to send all the supplies from sources to sinks as quickly as possible. It is known that this problem can be solved in polynomial time. In particular, Schlöter, Skutella, and Tran proposed a strongly polynomial-time discrete Newton method for this problem. In this paper, we propose a simple polynomial-time discrete Newton method for the quickest transshipment problem.
The mixed evacuation problem is a variant of the dynamic transshipment problem where there exist two modes of transportation and we allocate supplies to each mode of transportation in such a way that we can send all the supplies from sources to sinks within a given time limit. It is known that this problem can be solved in polynomial time when the number of sources and sinks is small. In this paper, we prove that the mixed evacuation problem can be solved in polynomial time with the ellipsoid method.