The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
본 논문에서는 그래프로 표시된 대상 지역을 여러 지역으로 분할하여 각 지역이 정확히 하나의 대피소를 포함하도록 하는 대피 계획 문제라고 불리는 그래프 분할 문제의 변형을 연구합니다. 피난로의 교차점을 줄이기 위해 각 지역은 볼록해야 하며, 재난 발생 시 주민이 신속하게 대피할 수 있도록 각 지점에서 대피소까지의 거리를 제한해야 하며, 각 대피소에 배정된 주민의 수가 대피소 수용 인원을 초과하지 않도록 해야 합니다. . 본 논문에서는 연결된 구성 요소의 볼록성을 다음과 같이 공식화합니다. 최단 경로 숲을 관통하는 일반 그래프에 대해 이 다목적 최적화 문제를 해결하기 위한 새로운 알고리즘을 제안합니다. 알고리즘은 단일 분할을 구하는 것뿐만 아니라 기존 알고리즘으로는 처리하기 어려운 위의 복잡한 제약 조건을 만족하는 모든 분할을 동시에 열거합니다. 제로 억제 이진 결정 다이어그램 (ZDD)를 압축된 표현으로 사용합니다. 제안된 알고리즘의 효율성은 실제 지도 데이터를 이용한 실험을 통해 확인되었다. 실험 결과, 제안한 알고리즘은 수백 개의 간선을 갖는 입력 그래프의 모든 제약 조건을 만족하는 수억 개의 파티션을 몇 분 안에 얻을 수 있음을 보여주었다.
Yu NAKAHATA
Nara Institute of Science and Technology
Jun KAWAHARA
Nara Institute of Science and Technology
Takashi HORIYAMA
Saitama University
Shoji KASAHARA
Nara Institute of Science and Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Yu NAKAHATA, Jun KAWAHARA, Takashi HORIYAMA, Shoji KASAHARA, "Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1363-1374, September 2018, doi: 10.1587/transfun.E101.A.1363.
Abstract: This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1363/_p
부
@ARTICLE{e101-a_9_1363,
author={Yu NAKAHATA, Jun KAWAHARA, Takashi HORIYAMA, Shoji KASAHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints},
year={2018},
volume={E101-A},
number={9},
pages={1363-1374},
abstract={This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.},
keywords={},
doi={10.1587/transfun.E101.A.1363},
ISSN={1745-1337},
month={September},}
부
TY - JOUR
TI - Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1363
EP - 1374
AU - Yu NAKAHATA
AU - Jun KAWAHARA
AU - Takashi HORIYAMA
AU - Shoji KASAHARA
PY - 2018
DO - 10.1587/transfun.E101.A.1363
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2018
AB - This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.
ER -