Multiple sink location problem in path networks with a combinational objective
- PDF / 1,152,369 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 64 Downloads / 166 Views
Multiple sink location problem in path networks with a combinational objective Taibo Luo1 · Hongmei Li2 · Shaofeng Ru2 · Weitian Tong3 · Yinfeng Xu4 Received: 30 November 2019 / Accepted: 13 May 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we consider the k-sink location problem in a path network with the goal of optimizing a combinational function of the maximum completion time and the total completion time. Let P = (V , E) be an undirected path network with n vertices. Each vertex has a positive weight, indicating the initial amount of supplies, and each edge has a positive length and a uniform capacity, which is the maximum amount of supplies that can enter the edge per unit time. Our goal is to identify k sink locations on the path P so that all supplies will be successfully evacuated and the given objective function is optimized. This paper presents two efficient polynomial time algorithms, which achieve O (n) for k = 1 and O n 6 for general k, respectively. Keywords Sink location · Path network · Combinational objective · Polynomial time algorithm
B
Hongmei Li [email protected] Taibo Luo [email protected] Shaofeng Ru [email protected] Weitian Tong [email protected] Yinfeng Xu [email protected]
1
School of Economics and Management, Xidian University, Xi’an 710126, China
2
School of Economics and Management, Northwest University, Xi’an 710127, China
3
Department of Computer Science, Eastern Michigan University, Ypsilanti, MI 48165, USA
4
Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, China
123
T. Luo et al.
1 Introduction Currently, the world faces dangerous threats from various natural and man-made disasters. When facing these disasters, people will suffer from serious damage, or even lose their lives, if the evacuation is not efficient. Therefore, developing effective evacuation planning systems for large-scale disasters is urgent and of great significance. The sink location problem was first proposed by Cheng et al. [7] in the context of the Tohuku-Pacific Ocean earthquake, which occurred in Japan on March 11, 2011 and caused enormous damage to the local area. To represent the dynamic flows of people in evacuation as the movement of people on a graph, they adopt the dynamic flow network [8], whose underlying graph is usually undirected and connected. In a dynamic flow network G = (V , E, W , L, C), with |V | = n and |E| = m, each vertex vi ∈ V is a source if its initial weight wi ∈ W is positive and each edge e j ∈ E is associated with a length l j ∈ L and a capacity c j ∈ C. With a given travelling speed, the length decides the time need to traverse the edge. The capacity is the maximum amount of weight (or number of people) that can enter the edge e j per unit time. In other words, the edge capacity restricts the speed of entry. The underlying graph (V , E) can be line, tree, cycle or any general graph. By associating the vertices with major areas (or cities), edges with paths (or roads), weight (and flow
Data Loading...
