Academic Journal of Computing & Information Science, 2022, 5(7); doi: 10.25236/AJCIS.2022.050704.

Research on emergency distribution problem based on graph theory algorithm

Author(s)

Mengting Liu1, Yangjie Li2, Jiahui Li3, Xiaoqi Tan2

Corresponding Author:
Mengting Liu
Affiliation(s)

1Faculty of Accounting, Guangzhou Southern College, Guangzhou, Guangdong, 510000, China

2Faculty of Electrical Engineering, Guangzhou Southern College, Guangzhou, Guangdong, 510000, China

3Faculty of Public Administration, Guangzhou Southern College, Guangzhou, Guangdong, 510000, China

Abstract

When unexpected events such as road block, closure and damage caused by some major events occur, they will have an impact on people's daily life. With the gradual popularization of 5g network, the application of UAV is becoming more and more extensive. This paper mainly studies the "emergency material distribution problem in 5g network environment". It analyzes the two cases of separate distribution of distribution vehicles and the combined distribution of "distribution vehicles + UAVs" respectively. In order to complete the material distribution task as soon as possible, it puts forward the best distribution scheme respectively. First, the optimal time is simplified, that is, the optimal time is converted into the shortest path, and the graph theory model is used for modeling. The path graph is highlighted by MATLAB, and the minimum spanning tree method is used to visualize all paths. After that, the shortest path from the ninth point to any point and the sequence of several traveling paths are obtained. The sequence of several traveling paths is classified into three schemes, and the total kilometers of the three schemes are calculated respectively. The best scheme is the one with the smallest total number of paths. For the best scheme, the path map of the best scheme is obtained by drawing. Secondly, the combined distribution mode of "distribution vehicle + UAV" is adopted for material transportation. Nowadays, 5g network is becoming more and more popular, and UAVs are more and more widely used. In order to complete the material distribution task as soon as possible, it is assumed that UAVs are used to transport materials to the greatest extent to reduce the transportation time and improve the efficiency. Visualize the path of "distribution vehicle + UAV" for subsequent problem solving. The aircraft route is divided into "three consecutive sections" and "two consecutive sections". After a large amount of data processing, the classification scheme is obtained. Combined with the vehicle optimal path, the best scheme of "distribution vehicle + UAV" combination to complete a complete distribution is obtained. Finally, the maximum load capacity of the delivery vehicle is 500 kg, and the other conditions are the same as above. Based on the obtained optimal scheme, the second question is solved by MATLAB for the constraints given in the question, and two feasible schemes are obtained. The frequency of UAV use in both schemes is greater than that of distribution vehicles. Disassemble and analyze scheme 1 and scheme 2 respectively.

Keywords

Minimum spanning tree; Heuristic algorithm; Path visualization; combined distribution

Cite This Paper

Mengting Liu, Yangjie Li, Jiahui Li, Xiaoqi Tan. Research on emergency distribution problem based on graph theory algorithm. Academic Journal of Computing & Information Science (2022), Vol. 5, Issue 7: 20-26. https://doi.org/10.25236/AJCIS.2022.050704.

References

[1] Vidal T, Crainic T G, Gendreau M, et al. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems[J].Operations Research,2012,60(3):611-624.

[2] REN Xinhui, YUE Yidi, YIN Xiaoli, ZHAO Lingfei. Discussion on logistics distribution path planning of UAV vehicle combination [J/OL]. Flight Mechanics:1-6[2020-03-23].

[3] WANG Lingxiao, CEN Zhongdi. Application research of drones in rural e-commerce logistics "last-kilometer" distribution m. China market, 2019(06):1762-163

[4] Liang Yiwei." Research on emergency material distribution route in vehicle-drone series mode [D].Chang'an University, 2021.DOI:10.26976/d.cnki.gchau.2021.00000839.

[5] Wang X, Poikonen S, Golden B. The vehicle routing problem with drones: Several worst-case results [J]. Optimization Letters, 2017, 11(4): 679-697.

[6] Ray S, Soeanu A, Berger J, et al. The multi-depot split-delivery vehicle routing problem: Model and solution algorithm [J]. Knowledge-Based Systems, 2014.71(1):238-265.