IEICE TRANSACTIONS on Fundamentals
Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1363-1374
- Publication Date
- 2018/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E101.A.1363
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
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
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
