×

Balanced-flow algorithm for path network planning in hierarchical spaces. (English) Zbl 1442.90027

Summary: Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm.

MSC:

90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Evans, James, Optimization Algorithms for Networks and Graphs (1992), Marcel Dekker: Marcel Dekker New York
[2] Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz, Shortest paths algorithms: theory and experimental evaluation, Math. Program., 73, 2, 129-174 (1996) · Zbl 0853.90111
[3] Jalali, S. E.; Noroozi, M., Determination of the optimal escape routes of underground mine networks in emergency cases, Saf. Sci., 47, 1077-1082 (2009)
[4] de Queirós Vieira Martins, Ernesto; Queir, Ernesto; Esteves dos Santos, José Luis; Martins, Vieira; Margarida, Marta; Margarida Braz Pascoal, Marta, A new algorithm for ranking loopless paths (1997), Univ. de Coimbra, Technical Report · Zbl 1319.68163
[5] Eppstein, David, Finding the k shortest paths, SIAM J. Comput., 28, 2, 652-673 (1998) · Zbl 0912.05057
[6] Jin, Wen; Chen, Shuiping; Jiang, Hai, Finding the K shortest paths in a time-schedule network with constraints on arcs, Comput. Oper. Res., 40, 2975-2982 (2013) · Zbl 1348.90156
[7] Sever, Derya; Dellaert, Nico; Van Woensel Ton De Kok, Tom, Dynamic shortest path problems: hybrid routing policies considering network disruptions, Comput. Oper. Res., 40, 2852-2863 (2013) · Zbl 1348.90189
[8] Nazarahari, Milad; Khanmirza, Esmaeel; Doostie, Samira, Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm, Expert Syst. Appl., 115, 106-120 (2019)
[9] Klein, Morton, A primal method for minimal cost flows with applications to the assignment and transportation problems, Manag. Sci., 14, 205-220 (1967) · Zbl 0178.22902
[10] Goldberg, Andrew V.; Tarjan, Robert E., Finding minimum-cost circulations by canceling negative cycles, J. ACM, 36, 4, 873-886 (1989) · Zbl 0697.68063
[11] Edmonds, Jack; Karp, Richard M., Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 2, 248-264 (1972) · Zbl 0318.90024
[12] Orlin, James B., A polynomial time primal network simplex algorithm for minimum cost flows, Math. Program., 78, 109-129 (1997) · Zbl 0888.90058
[13] Kuban Altınel, I.; Aras, Necati; Şuvak, Zeynep; Caner Taşkın, Z., Minimum cost noncrossing flow problem on layered networks, Discrete Appl. Math. (2018) · Zbl 1418.90047
[14] Dhamala, Tanka Nath, A survey on models and algorithms for discrete evacuation planning network problems, J. Ind. Manag. Optim., 11, 1, 265-289 (2015) · Zbl 1304.90052
[15] Choi, Wonjoon; Hamacher, Horst W.; Tufekci, Suleyman, Modeling of building evacuation problems by network flows with side constraints, Eur. J. Oper. Res., 35, 1, 98-110 (1988) · Zbl 0636.90029
[16] Liu, Yue; Chang, Gang-Len; Liu, Ying; Lai, Xiaorong, Corridor-based emergency evacuation system for Washington, DC: system development and case study, Transp. Res. Rec., 2041, 58-67 (2008)
[17] Hong, Yi; Li, Deying; Wu, Qiang; Xu, Hua, Dynamic route network planning problem for emergency evacuation in restricted space scenarios, J. Adv. Transp., 2018, Article 4295419 pp. (2018), 13 pages
[18] Hong, Yi; Li, Deying; Wu, Qiang; Xu, Hua, Priority-oriented route network planning for evacuation in constrained space scenarios, J. Optim. Theory Appl., 181, 279-297 (2019) · Zbl 1414.90090
[19] Han, Jihee, An efficient approach to 3D path planning, Inf. Sci., 478, 318-330 (2019) · Zbl 1443.68165
[20] Graf Plessen, Mogens M., Partial field coverage based on two path planning patterns, Biosyst. Eng., 171, 16-29 (2018)
[21] Hong, Yi; Liu, Jiandong; Luo, Chuanwen; Li, Deying, Min-max-flow based algorithm for evacuation network planning in restricted spaces, (COCOA 2018. COCOA 2018, LNCS, vol. 11346 (2018)), 233-245 · Zbl 1523.90068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.