  We address the facility location problems on dynamic flow path networks. A
dynamic flow path network consists of an undirected path with positive edge
lengths, positive edge capacities, and positive vertex weights. A path can be
considered as a road, an edge length as the distance along the road and a
vertex weight as the number of people at the site. An edge capacity limits the
number of people that can enter the edge per unit time. In the dynamic flow
network, given particular points on edges or vertices, called sinks, all the
people evacuate from the vertices to the sinks as quickly as possible. The
problem is to find the location of sinks on a dynamic flow path network in such
a way that the aggregate evacuation time (i.e., the sum of evacuation times for
all the people) to sinks is minimized. We consider two models of the problem:
the confluent flow model and the non-confluent flow model. In the former model,
the way of evacuation is restricted so that all the people at a vertex have to
evacuate to the same sink, and in the latter model, there is no such
restriction. In this paper, for both the models, we develop algorithms which
run in almost linear time regardless of the number of sinks. It should be
stressed that for the confluent flow model, our algorithm improves upon the
previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and
one for the non-confluent flow model is the first polynomial time algorithm.
