Discrete Newton methods for the evacuation problem

A dynamic network is a directed graph in which arcs have capacities and transit times. In this paper, we consider the evacuation problem in dynamic networks. In this problem, we are given a dynamic network with a single sink vertex in which each vertex except the sink vertex has a supply. Then the goal of this problem is to find the minimum time limit T such that we can send all the supplies to the sink vertex by T. In this paper, we propose a discrete Newton method for the evacuation problem. First, we prove that the number of iterations of this method is at most the number of vertices of the input dynamic network. Then we propose theoretical and practical implementation of this method. The theoretical implementation is based on submodular function minimization, and the practical implementation is based on maximum flow computations in time-expanded networks. Finally, we compare the proposed practical implementation with an algorithm using a binary search in time-expanded networks in computational experiments.