Multiple sink location problems in dynamic path networks
Multiple sink location problems in dynamic path networks
复制标题
DOI：
10.1016/j.tcs.2015.05.053
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Yuya Higashikawa;M. Golin;Naoki Katoh
中科院分区：
文献类型：
--
作者：
Yuya Higashikawa;M. Golin;Naoki Katoh
本文研究了动态路径网络中的k-汇选址问题。动态路径网络由具有正边长度、均匀边容量和正顶点供应的无向路径组成。一条路径可以被认为是一条道路，边的长度是沿路段的距离，顶点是一个位置的人数。所有边缘都有固定的公共容量，这限制了在单位时间内可以进入该边缘的人数。问题是找到路径上k个接收器(出口)的最佳位置，使得每个撤离者被送到k个接收器之一。容量的存在会导致拥堵，这可能会以意想不到的方式减缓疏散速度。设x是表示k汇位置的矢量。X的最优疏散策略是(k−1)维向量d，称为(k−1)除数。D的每个分量对应于将相邻两个水槽之间的所有疏散人员分成两组的边界，即，边界右侧的所有物资都疏散到右侧的水槽，而所有其他的则疏散到左侧的水槽。在这篇文章中，我们考虑了由两个不同的准则定义的最优性，极小极大准则和极小和准则。证明了极大极小问题可在O(K N)时间内求解，极小和问题可在O(n 2⋅{kn+n，2logk logn})时间内求解，其中n是给定网络的顶点数.
This paper considers the k-sink location problem in dynamic path networks. A dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. A path can be considered as a road, edge lengths as the distance along a road segment and vertex supplies as the number of people at a location. The edges all have a fixed common capacity, which limits the number of people that can enter that edge in a unit of time. The problem is to find the optimal location of k sinks (exits) on the path such that each evacuee is sent to one of the k sinks. The existence of capacities causes congestion, which can slow evacuation down in unexpected ways. Let x be a vector denoting the location of the k sinks. The optimal evacuation policy for x is (k− 1)-dimensional vector d, called (k− 1)-divider. Each component of d corresponds to a boundary dividing all evacuees between adjacent two sinks into two groups, ie, all supplies to the right of the boundary evacuate to the right sink and all the others to the left sink. In this paper, we consider optimality defined by two different criteria, the minimax criterion and the minisum one. We prove that the minimax problem can be solved in O (k n) time and the minisum problem in O (n 2⋅ min{k log n+ log n, 2 log k log log n}) time, where n is the number of vertices in the given network.