How could drones help us solve humanitarian crises?

How could drones help us solve humanitarian crises?

Is this FinTech related? Not really, but despite not being FinTech related we think it is super cool! Not all of our News will be FinTech centric!

The United States territory, Puerto Rico, was the hardest hit by hurricanes, causing more than 2,900 deaths and causing serious damage in 2017.

Roads and wires have been cut. Buildings and houses have been demolished. The network and telephone lines have been destroyed. All of this is due to the hurricane, especially the eastern and southeastern coasts of Puerto Rico, where widespread flooding has isolated Puerto Rico from the outside world. As a result, the Government is not in a position to assess the damage caused by Puerto Rico and to provide effective support, including medical supplies, life-saving equipment, etc., which are also faced by NGOs, and therefore require new ideas to address these issues. Between medical assistants and supply needs. Medical NGOs and governments can provide. 

1.2 Restatement of Problem 

In order to provide and detect as much information as possible from NGOs, NGO HELP, Inc. A mobile disaster response system called “DroneGo ” is designed to improve responsiveness. Use drones to supply supplies and detect information. 

1.2.1 Part 1 

Our team uses the conditions provided by the questions to meet the requirements below. 

• Design the configuration of the ISO container. 

• Fix the location the ISO should set. 

• Offer the configurations of medical drone’s packing, drone’s time table and delivery routes. 

• Design a flight plan for searching drones. 

1.2.2 Part 2 

Provide a memo to the CEO of HELP in order to share with her Board of Directors.

Team # 1917823 Page 3 of 20 

1.3 Problem analysis 

The goal of this question is to build a DroneGo UAV system in Puerto Rico. In order to achieve this goal, this paper divides the problem into three steps, namely, regional fixed point, route planning, and three-dimensional packing. Through the analysis and in-depth study of the problem, there is some support work to be completed, namely the performance evaluation of the drone, the loading capacity of the container and the aircraft, the solution of the three-dimensional packing problem and the alternative drone packing scheme. In this paper, the method of solving problems with two lines is used. The open line is the solution of the three progressive problems, the dark line is the solution to the support problem, and finally the better solution is obtained. 

model support 

 Map  

_processing Drone  

Previous work Step 1 

Step 2 

Step 3 

2 Assumption 

_evaluation Container  

evaluation 

Location  

 planing 

 3D packing  

optimization 

 Route  

planing 

Drone packing options 

Drone 

packing 

conclusion memo 

Figure 1: route map 

• Drones that deliver medical kits and road probes may not fly back 

• The aircraft itself can communicate directly with the outside world without resorting to the Puerto Rico communication network. 

• The maneuverability of the drone is not affected by factors such as climb angle, climb height, and turning angle. 

• The flight time of the drone includes the time taken by the aircraft to take off and land.

Team # 1917823 Page 4 of 20 3 Symbols and Notations 

The specific description is as follows 

Symbol or Notation Specification 

w_i Weight corresponding to the i-th point 

x_i, y_i The coordinates of the i-th demand point 

x_s, y_s Service facility coordinates 

n nsum of demands 

v_i ith drone’s volume 

V volume of container 

Z(K) k-th iteration 

4 Previous work 

4.1 Map processing 

Since there is no data in the map of Puerto Rico as the basis of calculation, in order to obtain the basic data, based on OSM (OpenStreetMap), this paper obtains open source data including road route map of Puerto Rico, latitude and longitude coordinates of node nodes, and node spacing. 

• Step1. Using the API(graph_from_bbox) from OSMNX package download the data from the web site: https://www.openstreetmap.org/, whose bottom structures include this triple types namely “nodes”, ”ways”, ”relations” but there are also several top structures defined by the bottom structure, such as “walking”, “bicycle”, “driving” and other roads. With the greatest help in mind, we should use our limited power to detect the main roads. For this reason, the top structure does not meet our requirements, so the OSMNX package needs some improvements. 

• Step2. According to the given requirement, we pick the type of road “motorway”, “truck”, “secondary road” by using OSMNX package which we improve by adding some code. 

• Step3. Mark the node as the intersection of the roads. Finally get the following map.

Team # 1917823 Page 5 of 20 Figure 2: route map 

By comparing with the key routes in the map of Puerto Rico in attachment 1, the visual Terrain route map is obtained by means of the visualization tool matplotlib. (The red line in figure3 is the overlap between the open source data and the brown route in the figure) 

Figure 3: Terrain route map 

In this paper, we use matplotlib and the above figure to get the rough calibration point, and then search the map data to get the precise latitude and longitude coordinates. According to the fixed point coordinates and the database, we then establish the distance matrix between the points and the adjacent point matrix. The precise open source data used in this paper. Therefore, the distance matrix error between points is within 0.1km, and an undirected connection diagram for route planning is established in combination with the line network,such as Figure 4.

Team # 1917823 Page 6 of 20

Figure 4: line network 

Note: In order to highlight the importance of certain population gatherings in the process of discussing route detection, we will adopt a method of marking multiple points, such as San Juan, selecting 16-19, connecting between 4 points. Replace the road network in the area. 

4.2 Drone evaluation 

4.2.1 Analytic hierarchy process 

positive reciprocal matrix and Characteristic root There are 5 different capabilities of the drone. The drone A is a standard drone. The score of all the abilities is 1. The standard ability is the video capability. The score is also 1. By using the data of the attachment 2, the data will be a positive reciprocal matrix of the data. As shown in Table 1.[4] 

Table 1: positive reciprocal matrix 

volume load ability cargo bay range video capable 

volume ¹3 

load ability ¹9 

cargo bay ¹6 

range ²3 

video capable 3 1 6³₂1 

The drone H was unable to perform the delivery or reconnaissance mission, so we did not consider the drone. Then according to function Aw = λw, we can get the Characteristic root 6, 2, 3, 12, 18The average value is a volumetric weight of 6, a load capacity of 2, a cargo type weight of 3, a detection distance of 12, and a video capability weight of 18. 

Normalize capability matrix According to D1’s over-bad performance and D8’ no performance, We decided that D1 and S8 will not participate in the assessment. fWe consider drone A and video functionality as 1. Then we normalize the video functionality. Finally we get a positive reciprocal matrix, as shown in Table 2.

Team # 1917823 Page 7 of 20 

Table 2: positive reciprocal matrix 

1 1 1 1 1 

0.22 1.75 2 0.71 1 

1.58 1.375 1 0.34 1 

1.46 1.875 2 0.29 1 

0.5 2.75 2 0.61 0 

1.13 2.5 2 0.33 1 

All kinds of drone’s score The feature magnitudes of the dot product of the positive reciprocal matrix of Table 2 are used. Then we get the score for each drone. The details of this table are shown in Table 3 below. 

Table 3: positive reciprocal matrix 

D2 41 

D5 39.99 

D7 39.74 

D3 37.34 

D4 37.31 

D6 21.82 

Di means a kind of drone. 

Finally we got the ranking of the drone:D2>D5>D7>D3>D4>D6. 

4.2.2 Packing initial test 

Based on the volume of the container and the average length and width of the six alternative drones, a rough estimate of a container-loadable drone can be obtained, and a container can be loaded with approximately 42 drones. 

4.3 Container evaluation 

We used the simulation packing software load expert to make a preliminary evaluation of the loading capacity of the container, and randomly selected two or three types of drones to fill the container. Got the following results

Team # 1917823 Page 8 of 20 

Table 4: Container initial test 

D2 38 44 21 20 8 8 D3 9 

D4 

D5 20 D6 5 D7 24 D8 

total load 66 Space utilization 96.23% 94.74% 94.61% 93.86% 93.69% 92.86% 92.49% 92.92% 

5 Location planning 

According to the title, there are three containers that can be used. After preliminary analysis and calculation, the service capability of the DroneGo system will be limited. According to the factors such as population density distribution, road network density and natural terrain, the map is divided into three. Areas are three, as shown on the left According to the undirected connected graph, a simplified map of the three regions can 

Figure 5: Area map 

be obtained, as shown in the right figure of Figure5. 

5.1 Precise center of gravity method 

For the most efficient delivery and reconnaissance, we must find the smallest total distance from the nearest neighbor city. We apply a position model called the Exact Gravity model to determine the location of the container settings. Our analogy is the way to find the center of gravity. We regard distance as weight. Then we get the objective function: 

_{Z = min}Xⁿ i=1 

w_i[(x_i − x_s)² + (y_i − y_s)²]^1/2(1) 

Among that,w_iWeight corresponding to the i-th point,x_i, The coordinates of the i-th demand point,x_s, y_sService facility coordinates,nsum of demands. 

5.2 Model solving 

We use an iterative method to solve the model. Solve by the known point and find the new point and repeat the solution process until a qualified solution is obtained.

Team # 1917823 Page 9 of 20 

5.3 Weight determination 

In order to determine the weight of the fixed point of each region, this paper studies the surrounding road network of each fixed point. The results are as follows: 

• 1. In area 1, the road network is much denser than the other fixed points, and the situation between the other fixed points is roughly similar. 

• 2. In Area 2, the road network is much denser than the other fixed points. Since San Juan takes more points, the nearby fixed point is considered to be roughly similar to the other fixed points. 

• 3. In the three regions, the road network is much denser than other fixed points, and the situation between the other fixed points is roughly similar. 

According to the output of the algorithm, considering the operating conditions (topography, external connection, meteorology, personnel concentration, etc.) in the actual scene, select the red dot (-66.7072, 18.2681), (-66.2256, 18.2188) respectively. (-66.0424, 18.2427), that is, the three points of 7, 15 and 24 in the non-directional connectivity diagram are used as container placement points. 

5.4 Solution algorithm 

• STEP1. Determine initial value. Arbitrarily, select a point as the initial point. • STEP2. Using the formula (1) and initial point find a new point. • STEP3. regard the new point as the initial point and repeat STEP2. 

• STEP4. according to the formular (2)if two iterations less than set value , terminate the procedure. Output result. 

∆Z(K) = |Z(K) − Z(K − 1)| ≤ ∆Z_limit (2) 

Z(K) is the k-th iteration. 

5.5 Solution 

In view of the maximum flight distance of the Drones, this paper uses the precise center of gravity algorithm to obtain the regional center of gravity as the main reference for the determination of the container placement point. The position of the center of gravity is marked with green dots on the map.

Team # 1917823 Page 10 of 20

Figure 6: Exact Gravity 

6 Route planning 

Based on the depth-first search algorithm [2], this paper proposes an optimization algorithm to give the solution space for the flight path problem of a fixed flight distance UAV. 

6.1 New depth-first search algorithm 

• Point depth concept. Using the search starting point as a vertex, defining the depth of the vertex to be 0, the depth of the adjacent point directly connected thereto is 1, and the depth of the adjacent point of the point having a depth of 1 (not including the point determining the depth of 0 or 1) is 2, And so on. 

• Depth first concept. In the traversal process of the traditional depth-first search algorithm, first dive to the point with the highest depth in any depth direction, then go to the deep dive behavior at the sub-deep level until the sub-deep traversal is completed, and so on. As shown below 

Figure 7: traditional depth-first search algorithm 

This algorithm follows this idea, but allows the same depth points to enter the iteration space during the retrieval process. As shown in fig 8. 

• Iterative termination condition. Set the record variable L_max(i) = L_max(i−1) + s(i), where s is the distance of the point from the previous node each time a new node is passed. According to the principle of Lmax, the iteration can be set by setting the threshold interrupt to the variable L_max, that is, when Lmax >= threshold, the

Team # 1917823 Page 11 of 20

Figure 8: New depth-first search algorithm 

iteration is terminated, and the new node is recorded as the end point of a certain route. In this question, the threshold is 52km, which is the ultimate flight distance of the Drone2 . 

• Path optimization (ideas) When a certain path appears in multiple routes, only the shortest one of the total length of the route is selected, but because the algorithm is immature, it cannot be realized. In this paper, the flight path of the drone is given by testing the finite solution space. 

6.2 model solution 

• step1 Depth the division of each area, as shown below 

Figure 9: Area 1,2 

Figure 10: area 3 

In the figure, the depth of the blue area is 1, the depth of the green area is 2, and the depth of the red area is 3. 

• step2 The region 1 is optimized by using the optimized depth-first exploration model to obtain the solution space, and the solution space is tested to obtain the following figure. The black path in the figure indicates the region that cannot be explored. And the drone exploration path, as shown following .

Team # 1917823 Page 12 of 20

Figure 11: area uncharted 

Table 5: route 

• step3 Repeat the above process to get the following figure, where the black path indicates the area that could not be explored. 

6.3 model result 

Through the model solving, we got the complete flight plan of the drone formation to explore the drone flight plan as shown below.

Team # 1917823 Page 13 of 20 

Table 6: area 1 

Table 7: area 2 

And got the flight plan of the medical support drone, and its flight plan is also related to other drones carried by the container. The specific results are shown in the figure below. After the test,we got the conclusion below: The first container is responsible for the exploration of the first area.After the flight route is planned, the undetected route accounts for 13% of the total route. The second container is responsible for the exploration of the second area.After the flight route is planned, the undetected route accounts for 5% of the total route. The third container is responsible for the exploration of the third area.After the flight route is planned, the undetected route accounts for 2% of the total route. And the total undetected route accounts for 7% of the whole route network.

Team # 1917823 Page 14 of 20 

Table 8: area 3 

₁₉21 D2 41 -11 18 20 D2 65 13 

19 D2 24 -28 

18 D2 23 -29 17 

22 D2 53 1 

16 19 D2 30 -22 20 D2 44 -8 

24 

22 D2 75 23 21 

27 D2 53 1 21 D2 74 22 27 21 D2 62 10 22 

23 D2 62 10 

22 D2 73 21 23 

26 D2 70 18 

26 23 D2 67 15 

Table 9: medical support plan 

hospital starting depth1 depth2 type time load D1 load D2 load D3 Max day Arecibo 7 9 D2 every day 1 0 0 480 first day 11 0 0 

Bayamón 15 16 D6 San Juan 15 17 18 D6 

⁴⁴ second day 0 11 0 first day 11 0 0 

₄₄ second day 0 11 0 third day 0 0 7 

San Pablo 24 every day 2 0 1 70 Jajardo 24 22 27 D2 every day 1 0 1 70

Team # 1917823 Page 15 of 20 

7 Drone packing 

7.1 3D packing optimization 

7.1.1 Multivariate optimization model 

Our goal is to get the highest fill rate in addition to the drone without spilling over the container, and use as little buffer material as possible in the container. The objective 

function of the problem is 

F(v) = max 

^Pv_i 

_V(3) 

among that, v_iis with drone’s volume,and V is volume of container. 

7.1.2 Multivariate optimization algorithm 

We choose a multivariate optimization algorithm to optimize our objective function. The main idea of the algorithm is the optimization principle.[3]. 

7.1.3 optimization principle 

regardless of past states and decisions, to the state of the present decision-making, the remaining states should be the most strategic. That is, to solve an optimization problem, n times decisions need to be madeD₁, · · · , D_i, · · · , D_n, if this decision series is the most optimal strategy, For any one i, 1 < i < n,Regardless of the previous decisions, the optimal decision after decision depends only on the presenti state determined by all previous decision, the subsequent decision D_i+1, D_i+2, · · · ; D_nis also the most optimal decision[3]. 

7.1.4 Model algorithm 

(1) Random placement: randomly selected drone type and the mode of placement; 

(2) adjustment: According to the objective function, we use the optimization principle to adjust the drone in the container; 

(3) approximation: By recurrence, using random placement and adjustment press the objective function on the optimum solution. 

7.1.5 Algorithm steps 

• Step1. Use the random placement mode to load the drone into a random free space in the container. If the drone cannot be placed in space, randomly select a mode until the drone places or traverses all modes. 

• Step2. Repeat step 1 until the various drones cannot be placed in the available space.

Team # 1917823 Page 16 of 20 

• Step3. Randomly select an unloaded drone and a mode to randomly pick a loaded drone. 

• Step4. If the unloaded drone is larger than the loaded drone and the unloaded drone can be placed in the container, we replace the loaded drone with the unloaded drone. Otherwise we continue with the previous loading series. 

• Step5. Repeat steps 3 and 4 until the free space of the container cannot accommodate any drones. 

• Step6. Gradually approach the optimal solution and asymptotically converge the packaging process until the result is satisfactory. 

7.2 Simulation 

We use the simulation packing software load expert to simulate the loading capacity of the container according to the type of aircraft given by the optimization algorithm, and finally obtain the following alternatives by comparison. 

Table 10: Alternative option 

D2 34 

D3 

D4 

D5 33 D6 

D7 25 M1 490 M2 80 M3 160 amount of drone 92 amount of Loading goods 730 Space utilization 93.30% 

7.3 Drone packing options 

In the end, we compare the optimization results with the simulation results, and take into account that the smoothness of transportation may cause drone damage, so we use a more compact packing scheme, and take into account the contents of the box as much as possible. Not wasting, and finally got the following packing plan.

Team # 1917823 Page 17 of 20 Table 11: packing plan 

C3 

D2 86 

D3 

D4 

D5 

D6 

D7 

M1 210 

M2 

M3 140 

amount of Loading goods 

weight of goods/lbs 

Space utilization 92.85% 

And we visualized the results and obtained the visualization results as shown .The load steps of three containers are in the appendix. 

Figure 12: C1,C2 

Figure 13: C3 

And we also get the cargo bays packing plan by using the same way. As follows table 12and13.

Team # 1917823 Page 18 of 20 Table 12: bay 1 

L1 

M1 1 M2 1 M3 

amount of Loading goods 2 weight of goods/lbs 4 Space utilization 61.61% 

Table 13: bay 2 

L2 

M1 2 M2 

M3 1 amount of Loading goods 3 weight of goods/lbs 7 Space utilization 13.71% 

8 memo 

To: the CEO of HELP 

From: MCM team 1917823 

Date: 28.Jan.2019 

Subject: modeling results, conclusions, and recommendations The results of the Puerto Rico’s DroneGo model. model 2 solution: 

Table 14: model 1 solution

Team # 1917823 Page 19 of 20

Figure 14: model 2 solution 

Medical route 

The first container is responsible for the medical transportation of Hospital Pavia Arecibo which can guarantee the supply of medicines for the past year. The second container is responsible for the medical transportation of Puerto Rico Children’s Hospital and Hospital Pavia Santurce which can guarantee the supply of medicines for 44 days. 

The third container is responsible for the medical transportation of Hospital HIMA and Caribbean Medical Center which can guarantee the supply of medicines for 70 days. Probe route 

The first container is responsible for the exploration of the first area.After the flight route is planned, the undetected route accounts for 13% of the total route. The second container is responsible for the exploration of the second area.After the flight route is planned, the undetected route accounts for 5% of the total route. The third container is responsible for the exploration of the third area.After the flight route is planned, the undetected route accounts for 2% of the total route. And the total undetected route accounts for 7% of the whole route network. 

To set the DroneGo system in Puerto Rico or in other places , our team provides the following recommendations. 

• 1. Geo-exploration. Good planning is based on accurate geo-information. 

• 2. Information processing.Transform the necessary information into usable forms,like adjacent connected graphs,road network diagrams. 

• 3. Drone capabilities evaluation.Evaluate those capabilities so that you can get the drone with excellent performance. 

• 4. Dividing the core area.Deal to the chosen drones and the realities,few core area could be set.Thus,you can determine the location of the container 

• 5. Determine the location of the container by the precise center of gravity method. • 6. Determine the drone route by the new depth-first search model. 

• 7. Determine the packing ratio of the MED Drone by the drone route and the maximum load capacity of the container.

Team # 1917823 Page 20 of 20 • 8. Determine the packing situation by the ratio and 3D bin packing model. 

References 

[1] chicago5.2019.6 Months After Hurricane Maria Puerto Rico Pleads for Help. https: //www.nbcchicago.com/news/national-international/ 

Puerto-Rico-6-Months-After-Hurricane-Maria-477071943.html [2] bokeyuan.2019.https://www.cnblogs.com/kubixuesheng/p/4399705.html 

[3] Xia Cheng-Ren. Methodology of teaching the principle of optimality. Journal of Anqing Teachers College (Natural Sci- ence), 2003, 9(2): 93¡95 

[4] jiang qi yuan. shuxue boxing. lisanmoxing, 2010, 249.

How could drones help us solve humanitarian crises?