The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -