# Drone Assisted Robust Emergency Service Management for Elderly Chronic Disease

Authors: Shengqiang Jiang; Yong Jin; Kaijian Xia
Journal: Journal of Healthcare Engineering
 (2021)

---

## Abstract

It is important to monitor the early screening of chronic diseases, predict the risk, and provide the comprehensive management of chronic diseases for the elderly. However, it is difficult to provide the robust and real-time emergency service for elderly chronic disease because of the complex social network and diversity of elderly chronic disease service. To address these issues, we design a new drone assisted robust emergency service system. We formulate the Drone assisted Management (DM) problem to minimize the total time cost of drone subject to all elderly chronic disease services which can be guaranteed exactly once by the drone under its energy constraint. Then, we propose the DRS algorithm to solve the DM problem. To provide the robust and real-time service, we further formulate the Charging driven Drone assisted Management (CDM) problem and present the CDRS algorithm to solve the CDM problem. Through the theoretical analysis and numerical simulation experiments, we demonstrate that DRS and CDRS can decrease the total time cost by 37.61% and increase the QoE by 112.80% through the designed system, respectively.


---

## Body

## 1. Introduction

The HelpAge International has released the report of the global aging business observation index 2015 [1]. According to the report, there are about 901 million people aged 60 and above, accounting for 12.3% of the world’s population. By 2030, this proportion will reach 16.5%. Globally, the number of people over the age of 60 exceeds the number of children below 5 years of age. By 2050, the number of people over 60 will exceed the number of people below 15 years of age. According to the report, China has the largest aging population in the world, with 209 million. By 2025, the total number of China’s elderly population will be nearly 300 million. By 2035, there will be 400 million elderly people in China; that is, one in every three people is an elderly person. In the past 20 years, the proportion of the aging population has increased from 20% to 30%, and the development is very rapid [2].The World Health Organization (WHO) reported that 63% of all deaths globally are due to chronic diseases, such as cardiovascular diseases, diabetes, cancers, and chronic respiratory illnesses. The care of elderly may involve multiple healthcare professionals in different locations, as well as a variety of medications and treatments. Thus, good management and a proactive approach to diagnosis and treatment are important [3]. Therefore, chronic noncommunicable diseases and their risk factors are regularly detected, continuously monitored, evaluated, and comprehensively intervened. The main contents include early screening of chronic diseases, risk prediction of chronic diseases, early warning and comprehensive intervention, and comprehensive service management of chronic diseases. The evaluation of chronic disease service management effect is particularly important.However, chronic disease service management faces many difficulties. First of all, the doctor centered chronic disease service results in resource mismatch and lack of personalized service. Secondly, the core of chronic disease service management is user education and follow-up supervision or incentive mechanism, which is difficult to adapt to the particularity of elderly patients. It is necessary to integrate hospitals, communities, and families to improve the real-time performance of chronic disease service management, with poor robustness and reliability.Fortunately, drones have performed well in many service areas. Kim et al. [4] addressed the drone-aided delivery and pickup planning of medication and test kits for patients with chronic diseases who are required to visit clinics for routine health examinations and/or refill medicine in rural areas. Nenni et al. [5] redesigned the entire Emergency Medical Services model by including drones. Radosveta et al. [6] introduced some of the most recent and interesting applications that drones can find in creating ambient assisted living environments for the elderly.However, the battery of drone is limited, so it is necessary to solve the dual constraints of scheduling ground charging stations and the demand of elderly chronic disease management. The existing research mainly focuses on how to improve the chronic disease service level of drone, but there is little research on how to improve the service cycle, efficiency, effect, and the robustness of elderly chronic disease emergency service. We designed a drone assisted elderly chronic disease management system, as shown in Figure1. When the elderly are in the outdoor shopping center, train station, park, bus stops, apartment, suburban house, city house, and stadium, the drones can carry the drugs and emergency medical supplies and have the capacity to carry modest payloads and can transport them quickly to their destination in case of sudden chronic disease when the real-time emergency service is needed.Figure 1
Scenario of drone assisted emergency service management.However, in the above scenario, we face many challenges. First of all, the energy of drone is limited, and a flight can serve the elderly and the service time is limited. How to provide the most effective service for the elderly in the limited time makes it very difficult to optimize the drone scheduling and chronic disease resource matching. When the residual energy of drone is insufficient, it needs to go to the charging stations deployed on ground or roof to replenish energy. Secondly, there is a time conflict between drone charging scheduling and the robustness of chronic disease emergency service management. It is very difficult to consider charging demand and robust service simultaneously in drone scheduling.Our key contributions can be summarized as follows:(i)
We design a new drone assisted robust emergency service system through the drone assistance.(ii)
We formulate the problem of Drone assisted Management (DM) to minimize the total time cost of drone subject to all elderly chronic disease services which can be guaranteed exactly once by the drone under its energy constraint and propose the Drone assisted Robust emergency Service (DRS) algorithm to solve the DM problem.(iii)
Considering the guarantee of robustness and real time of emergency service for elderly chronic disease, we further formulate the Charging driven Drone assisted Management (CDM) problem to maximize the service utility and we present an algorithm to solve the CDM problem.(iv)
We conduct extensive simulations for the designed system and proposed algorithms. The results show that the DRS algorithm and CDRS algorithm can decrease the total time cost by 37.61% and increase the Quality of Experience (QoE) by 112.80% through the designed system, respectively.The rest of the paper is organized as follows. We review the state-of-the-art research in Section2. We present the system model and formulate the CDM problem in Section 3. We formulate the DM problem and propose the corresponding algorithm in Section 4. We design the algorithm for solving CDM problem in Section 5. We conduct the simulations in Section 6, respectively. We conclude this work in Section 7.


## 2. Related Work

The current situation of chronic disease management in the elderly is discussed as follows. Lima et al. [7] studied the impact of chronic disease and the number of diseases on the various aspects of health-related quality of life among the elderly in São Paulo, Brazil. Lawlor et al. [8] researched the associations between having had a fall and chronic diseases and drug use in elderly women. Rocha and Ciosak [9] found that the changes brought about the diagnosis of chronic disease and its implications for the adaptation to the new way of life. The management of these changes is complex, and many factors influence positively and negatively.About the status of drone service, Cheskes et al. [10] examined the feasibility of a novel Automated External Defibrillators (AED) drone delivery method for rural and remote sudden cardiac arrest and showed that the AED drone is feasible with the potential for improvements in response time during simulated sudden cardiac arrest scenarios. Angurala et al. [11] used the drone service to reduce the risk of infection to the doctors or other medical staff, thereby preventing the disease spread. Hart et al. [12] studied the acceptability and perceived utility of Unmanned Aerial Vehicle (UAV) technology to Mass Casualty Incidents (MCI) scene management.About the drone scheduling, Boysen et al. [13] designed a drone schedule to minimize the total duration of the delivery tour subject to supplying all customers under considering a fixed sequence of stops constituting a truck route and a set of customers to be supplied. Kim et al. [14] proposed a robust optimization approach to find the optimal flight schedule including the number of drones and flight paths in the flight network considering uncertain battery duration. Wang et al. [15] proposed a novel routing and scheduling algorithm, referred to as hybrid truck-drone delivery algorithm, to solve the hybrid parcel delivery problem.About the charging scheme of drone, Hu et al. [16] proposed a fully automatic charging station which operates wirelessly. Raciti et al. [17] proposed a current tuning mechanism that compensates for this variability in a single-inverter multipad charging station. Kim et al. [18] proposed a cloud-based drone navigation system for efficient drone battery charging in drone networks.The system we designed is different from the above research. Our system integrates the ground charging stations and the elderly points that need emergency chronic disease services. In particular, we consider the charging efficiency of drone, the real-time response of emergency chronic disease service, and the emergency service management robustness of the elderly chronic disease all together. We solved two problems. The first problem maximizes the management utility of drone to the elderly chronic disease emergency service without considering the charging. In order to expand the scope of drone service and improve the emergency service management robustness of elderly chronic disease, the second problem consider the drone charging and the elderly chronic disease emergency service requirements.


## 3. Energy Constrained Drone Assisted Management

### 3.1. System Model and Problem Formulation

We consider the living quarters for the elderly, including the outdoor shopping center, train station, park, bus stops, apartment, suburban house, city house, and stadium. The locations of these venues are known and fixed. We define them as emergency service points. There is a drone in the area to provide emergency services for chronic diseases. The elderly people may make the chronic disease emergency service requests for cardiovascular diseases, diabetes, cancers, and chronic respiratory illnesses at any time in the living area.Firstly, the distance between any two emergency service points in the living area is less than the maximum flight distance of drone. Therefore, drone can provide relevant medical services for multiple emergency service points without charging. Secondly, the elderly are not in a completely helpless state; that is, they can simply interact with drone and save themselves. Therefore, the emergency service of drone can be completed in a short time. Then, the impact of external natural environment such as wind and complex environment of buildings on drone flight energy consumption and time is not considered. Therefore, the drone always keeps constant speed. Flight time and energy consumption are only related to traveling distance. Finally, we assume that the charging stations deployed on the ground or roof can satisfy the charging requirements of drone at any time.Without loss of generality, leto be the set of n elderly people and let ri be the time cost of emergency service for the i-th elderly chronic disease service. Let S be the set of m charging stations and let φ be the charging power of charging station. Note that the charging power of each charging station is the same. Let ν,σh,σf, and Cmax be the flying speed, the unit hovering energy consumption, the unit flying energy consumption, and the battery capacity of drone, respectively. The drone is initially located at the depot, denoted by d0.To formalize the emergency service management for elderly chronic disease, we use the undirected graphG=O∪S,E to represent the emergency service management network. E represents the set of service segments that connect the adjacent elderly people and/or charging station. The weight on any edge e∈E is time cost te, which represents the consumed time when the drone passes through the edge e. Let T be the tour of drone and let β be the energy consumption of drone providing service for the elderly chronic disease. Let ce be the energy consumption of drone passing through the edge e. In addition, let Ci be the residual energy of drone after passing through the edge e and completing the i-th elderly chronic disease service. Let Ti⊆T be the drone subtour from the depot to the i-th elderly chronic disease service. Let τk be the charging time for drone at charging station sk∈S. We define the function OTi to indicate the elderly people serviced by the drone and STi to indicate the charging stations visited by the drone in the tour Ti, respectively. Let c0 be the initial energy of drone launching at d0. Then, Ci can be calculated by the following equation:(1)Ci=c0−∑e∈Tice−∑oi′∈OTiri′β+∑sk∈STiτkφ.We define the service utility of thei-th elderly chronic disease service as function foi listed as follows:(2)foi=limn⟶∞ri∑i′=1iri′+∑e∈Tite.The objective of CDM is to design a drone tour starting fromd0 to provide the chronic disease emergency service for the elderly exactly once to maximize the service utility under the energy constraint of drone. xi,j is a binary variable to indicate whether the drone passes through the edge i,j∈E,∀oi,oj∈O. xi,j=1 if the drone passes through the edge i,j and xi,j=0 otherwise. The CDM problem can be formulated as follows:(3)CDMmax∑i=1n∑j=1nxi,j∑oj∈Ofojs.t.axi,j∈0,1,∀oi,oj∈Ob∑i=1nxi,j=1,∀oj∈Oc∑j=1nxi,j=1,∀oi∈Odcij+riβ≤Ci,∀oi,oi∈OTi,Ti⊆TConstraint (a) gives the value range ofxi,j. Constraints (b) and (c) ensure that each elderly chronic disease service is visited by the drone exactly once; that is, the drone can provide the corresponding elderly chronic disease service for all elderly people. Constraint (d) ensures that the sum of flying energy consumption of drone and providing the corresponding elderly chronic disease service is not larger than the residual energy of drone after visiting oi.We listed the frequently used notations in Table1.Table 1
Frequently used notations.
NotationDescriptionOSet ofn elderly peopleriTime cost of emergency service for thei-th elderly chronic disease serviceSSet ofm charging stationsφCharging power of charging stationνFlying speed of droneσhUnit hovering energy consumptionσfUnit flying energy consumptionCmaxBattery capacity of droned0Depot for droneGEmergency service management networkESet of service segmentsteTime cost of edgee∈ETTour of droneβEnergy consumption of drone providing serviceceEnergy consumption of drone passing through the edgeeCiResidual energy of drone after passing through the edgee and completing the i-th elderly chronic disease serviceτkCharging time for drone at charging stationsk∈STiDrone subtour from the depot to thei-th elderly chronic disease serviceOTiElderly people serviced by the drone inTiSTiCharging stations visited by the drone inTi


## 3.1. System Model and Problem Formulation

We consider the living quarters for the elderly, including the outdoor shopping center, train station, park, bus stops, apartment, suburban house, city house, and stadium. The locations of these venues are known and fixed. We define them as emergency service points. There is a drone in the area to provide emergency services for chronic diseases. The elderly people may make the chronic disease emergency service requests for cardiovascular diseases, diabetes, cancers, and chronic respiratory illnesses at any time in the living area.Firstly, the distance between any two emergency service points in the living area is less than the maximum flight distance of drone. Therefore, drone can provide relevant medical services for multiple emergency service points without charging. Secondly, the elderly are not in a completely helpless state; that is, they can simply interact with drone and save themselves. Therefore, the emergency service of drone can be completed in a short time. Then, the impact of external natural environment such as wind and complex environment of buildings on drone flight energy consumption and time is not considered. Therefore, the drone always keeps constant speed. Flight time and energy consumption are only related to traveling distance. Finally, we assume that the charging stations deployed on the ground or roof can satisfy the charging requirements of drone at any time.Without loss of generality, leto be the set of n elderly people and let ri be the time cost of emergency service for the i-th elderly chronic disease service. Let S be the set of m charging stations and let φ be the charging power of charging station. Note that the charging power of each charging station is the same. Let ν,σh,σf, and Cmax be the flying speed, the unit hovering energy consumption, the unit flying energy consumption, and the battery capacity of drone, respectively. The drone is initially located at the depot, denoted by d0.To formalize the emergency service management for elderly chronic disease, we use the undirected graphG=O∪S,E to represent the emergency service management network. E represents the set of service segments that connect the adjacent elderly people and/or charging station. The weight on any edge e∈E is time cost te, which represents the consumed time when the drone passes through the edge e. Let T be the tour of drone and let β be the energy consumption of drone providing service for the elderly chronic disease. Let ce be the energy consumption of drone passing through the edge e. In addition, let Ci be the residual energy of drone after passing through the edge e and completing the i-th elderly chronic disease service. Let Ti⊆T be the drone subtour from the depot to the i-th elderly chronic disease service. Let τk be the charging time for drone at charging station sk∈S. We define the function OTi to indicate the elderly people serviced by the drone and STi to indicate the charging stations visited by the drone in the tour Ti, respectively. Let c0 be the initial energy of drone launching at d0. Then, Ci can be calculated by the following equation:(1)Ci=c0−∑e∈Tice−∑oi′∈OTiri′β+∑sk∈STiτkφ.We define the service utility of thei-th elderly chronic disease service as function foi listed as follows:(2)foi=limn⟶∞ri∑i′=1iri′+∑e∈Tite.The objective of CDM is to design a drone tour starting fromd0 to provide the chronic disease emergency service for the elderly exactly once to maximize the service utility under the energy constraint of drone. xi,j is a binary variable to indicate whether the drone passes through the edge i,j∈E,∀oi,oj∈O. xi,j=1 if the drone passes through the edge i,j and xi,j=0 otherwise. The CDM problem can be formulated as follows:(3)CDMmax∑i=1n∑j=1nxi,j∑oj∈Ofojs.t.axi,j∈0,1,∀oi,oj∈Ob∑i=1nxi,j=1,∀oj∈Oc∑j=1nxi,j=1,∀oi∈Odcij+riβ≤Ci,∀oi,oi∈OTi,Ti⊆TConstraint (a) gives the value range ofxi,j. Constraints (b) and (c) ensure that each elderly chronic disease service is visited by the drone exactly once; that is, the drone can provide the corresponding elderly chronic disease service for all elderly people. Constraint (d) ensures that the sum of flying energy consumption of drone and providing the corresponding elderly chronic disease service is not larger than the residual energy of drone after visiting oi.We listed the frequently used notations in Table1.Table 1
Frequently used notations.
NotationDescriptionOSet ofn elderly peopleriTime cost of emergency service for thei-th elderly chronic disease serviceSSet ofm charging stationsφCharging power of charging stationνFlying speed of droneσhUnit hovering energy consumptionσfUnit flying energy consumptionCmaxBattery capacity of droned0Depot for droneGEmergency service management networkESet of service segmentsteTime cost of edgee∈ETTour of droneβEnergy consumption of drone providing serviceceEnergy consumption of drone passing through the edgeeCiResidual energy of drone after passing through the edgee and completing the i-th elderly chronic disease serviceτkCharging time for drone at charging stationsk∈STiDrone subtour from the depot to thei-th elderly chronic disease serviceOTiElderly people serviced by the drone inTiSTiCharging stations visited by the drone inTi


## 4. Drone Assisted Management Scheme

### 4.1. Problem Formulation

Before solving the CDM problem, we first design the DM problem, which is formulated as follows:(4)DM max∑i=1n∑j=1nxi,j∑oj∈Ofojs.t.axi,j∈0,1,∀oi,oj∈Ob∑i=1nxi,j=1,∀oj∈Oc∑j=1nxi,j=1,∀oi∈Od∑e∈Tce+∑oi∈Oriβ≤Cmax.Constraint (d) ensures that the energy consumption sum of flying and elderly chronic disease service is not larger than the battery capacity of drone.From the primal dual theory, we define theDual DM (DDM) problem listed in the following equation:(5)DDMmin∑e∈Tce+∑oi∈Oriβs.t.axi,j∈0,1,∀oi,oj∈Ob∑i=1nxi,j=1,∀oj∈Oc∑j=1nxi,j=1,∀oi∈Od∑i=1n∑j=1nxi,j∑oj∈Ofoj≥ρ.Constraint (d) ensures that the utility of elderly chronic disease service is not less thanρ, where ρ indicates the lower bound of quality of elderly chronic disease service.


### 4.2. Algorithm Design and Analysis

The objective of DDM problem is to find a drone tour to provide the elderly chronic disease service for all elderly people with minimum energy consumption under the constraint of energy of drone. Note that the solution for the DDM problem is the solution for the DM problem following Theorem1.Theorem 1.
DM problem is equivalent to the DDM problem.
Clearly, the DDM problem is NP-hard to find the optimal tour for the drone from the following theorem.Theorem 2.
DM problem is NP-hard.Proof.
The problem is to visit all elderly people on the route of drone exactly once and return the depot with the minimum energy cost. This problem is aTraveling Salesman Problem (TSP) actually. Since the TSP is a well-known NP-hard problem, the DM problem is NP-hard.Moreover, we design theDrone assisted Robust emergency Service (DRS) algorithm to solve the DM problem. The basic idea is given as follows: First, we used the primal dual algorithm for minimum weight vertex-covering problem to finish the transformation equivalently from the DM problem to the DDM problem [19]. Second, we solve a TSP following the NITSP algorithm [20]. The above process is illustrated in Algorithm 1.There are five steps in Algorithm1, which are listed as follows:Step 1: Construct the graphG according to the set of O (Line 1);Step 2: Construct the dual linear programming problem (Line 2);Step 3: Updateyi,k when there exists an edge satisfying the conditions in Line 6;Step 4: Initialize the setzi,i=1,2,…,n (Lines 8–12);Step 5: Find the tourT through NITSP based on zi|i=1,2,…,n (Line 13).Algorithm 1: DRS.
Input:OOutput:T(1)
constructing graphG;(2)
transformation from the DM problem to DDM problem;(3)
for eachi,j∈E,i≠j do(4)
yi,j⟵0;(5)
for eachi,i′∈E,i≠j do(6)
if∑j:i,j∈Eyi,j≥ρi and ∑j:k,j∈Eyi,j≥ρk then(7)
yi,k⟵yi,j+min∑j:i,j∈Eyi,j−ρi, ∑j:k,j∈Eyi,j−ρk;(8)
for i = 1 to n do(9)
if∑j:i,j∈Eyi,j=ρi then(10)
zi⟵1;(11)
else(12)
zi⟵0;(13)
T⟵NITSPzi|i=1,2,…,n;Theorem 3.
DRS is a polynomial-time approximation algorithm for DM problem.Proof.
The running time of Lines 1–12 isOn3.5. The running time of Line 13 is polynomial.
Letopt denote the optimal solution of the DM problem. Let y˜i,j be the final solution of Lines 1–12 for each edge i,j∈E,i≠j. From Lines 5–7, there is at least one vertex oi of edge i,j∈E, which satisfies the following equation:(6)∑j:i,j∈Eyi,j=ρi
Hence, each edgei,j∈E is covered by the set ℛ.
We found thaty˜i,ji,j∈E is a dual feasible solution for the primal dual linear programming problem, that is, DDM problem. So, we have(7)∑j:i,j∈Ey˜i,j≤opt.
Note that, for eachi=1,2,…,n, we have(8)z¯i=1if  andonly  if∑j:i,j∈Eyi,j=ρi.
Therefore, we have(9)∑i=1nρiz¯i=∑z¯i=1ρi=∑z¯i=1∑i,j∈Ey˜i,j≤2∑i,j∈Ey˜i,j≤2opt.
So, the process of Lines 1–12 can find an approximation solution for the DDM problem.
Finally, the NITSP algorithm can find an approximation solution for DM problem based on the setzi|i=1,2,…,n.
Above all, DRS is a polynomial-time approximation algorithm for solving the DM problem.


## 4.1. Problem Formulation

Before solving the CDM problem, we first design the DM problem, which is formulated as follows:(4)DM max∑i=1n∑j=1nxi,j∑oj∈Ofojs.t.axi,j∈0,1,∀oi,oj∈Ob∑i=1nxi,j=1,∀oj∈Oc∑j=1nxi,j=1,∀oi∈Od∑e∈Tce+∑oi∈Oriβ≤Cmax.Constraint (d) ensures that the energy consumption sum of flying and elderly chronic disease service is not larger than the battery capacity of drone.From the primal dual theory, we define theDual DM (DDM) problem listed in the following equation:(5)DDMmin∑e∈Tce+∑oi∈Oriβs.t.axi,j∈0,1,∀oi,oj∈Ob∑i=1nxi,j=1,∀oj∈Oc∑j=1nxi,j=1,∀oi∈Od∑i=1n∑j=1nxi,j∑oj∈Ofoj≥ρ.Constraint (d) ensures that the utility of elderly chronic disease service is not less thanρ, where ρ indicates the lower bound of quality of elderly chronic disease service.


## 4.2. Algorithm Design and Analysis

The objective of DDM problem is to find a drone tour to provide the elderly chronic disease service for all elderly people with minimum energy consumption under the constraint of energy of drone. Note that the solution for the DDM problem is the solution for the DM problem following Theorem1.Theorem 1.
DM problem is equivalent to the DDM problem.
Clearly, the DDM problem is NP-hard to find the optimal tour for the drone from the following theorem.Theorem 2.
DM problem is NP-hard.Proof.
The problem is to visit all elderly people on the route of drone exactly once and return the depot with the minimum energy cost. This problem is aTraveling Salesman Problem (TSP) actually. Since the TSP is a well-known NP-hard problem, the DM problem is NP-hard.Moreover, we design theDrone assisted Robust emergency Service (DRS) algorithm to solve the DM problem. The basic idea is given as follows: First, we used the primal dual algorithm for minimum weight vertex-covering problem to finish the transformation equivalently from the DM problem to the DDM problem [19]. Second, we solve a TSP following the NITSP algorithm [20]. The above process is illustrated in Algorithm 1.There are five steps in Algorithm1, which are listed as follows:Step 1: Construct the graphG according to the set of O (Line 1);Step 2: Construct the dual linear programming problem (Line 2);Step 3: Updateyi,k when there exists an edge satisfying the conditions in Line 6;Step 4: Initialize the setzi,i=1,2,…,n (Lines 8–12);Step 5: Find the tourT through NITSP based on zi|i=1,2,…,n (Line 13).Algorithm 1: DRS.
Input:OOutput:T(1)
constructing graphG;(2)
transformation from the DM problem to DDM problem;(3)
for eachi,j∈E,i≠j do(4)
yi,j⟵0;(5)
for eachi,i′∈E,i≠j do(6)
if∑j:i,j∈Eyi,j≥ρi and ∑j:k,j∈Eyi,j≥ρk then(7)
yi,k⟵yi,j+min∑j:i,j∈Eyi,j−ρi, ∑j:k,j∈Eyi,j−ρk;(8)
for i = 1 to n do(9)
if∑j:i,j∈Eyi,j=ρi then(10)
zi⟵1;(11)
else(12)
zi⟵0;(13)
T⟵NITSPzi|i=1,2,…,n;Theorem 3.
DRS is a polynomial-time approximation algorithm for DM problem.Proof.
The running time of Lines 1–12 isOn3.5. The running time of Line 13 is polynomial.
Letopt denote the optimal solution of the DM problem. Let y˜i,j be the final solution of Lines 1–12 for each edge i,j∈E,i≠j. From Lines 5–7, there is at least one vertex oi of edge i,j∈E, which satisfies the following equation:(6)∑j:i,j∈Eyi,j=ρi
Hence, each edgei,j∈E is covered by the set ℛ.
We found thaty˜i,ji,j∈E is a dual feasible solution for the primal dual linear programming problem, that is, DDM problem. So, we have(7)∑j:i,j∈Ey˜i,j≤opt.
Note that, for eachi=1,2,…,n, we have(8)z¯i=1if  andonly  if∑j:i,j∈Eyi,j=ρi.
Therefore, we have(9)∑i=1nρiz¯i=∑z¯i=1ρi=∑z¯i=1∑i,j∈Ey˜i,j≤2∑i,j∈Ey˜i,j≤2opt.
So, the process of Lines 1–12 can find an approximation solution for the DDM problem.
Finally, the NITSP algorithm can find an approximation solution for DM problem based on the setzi|i=1,2,…,n.
Above all, DRS is a polynomial-time approximation algorithm for solving the DM problem.


## 5. Charging Driven Drone Assisted Management

In this section, we present theCharging driven Drone assisted Robust emergency Service (CDRS) algorithm to solve the CDM problem. Obviously, the CDM problem is also NP-hard because the CDM problem is a tightened version of DM problem under considering the charging of drone. Hence, we have the following theorem.Theorem 4.
The CDM problem is NP-hard.
The basic idea of CDRS is illustrated as follows: we first complete the transformation from CDM problem to CDDM problem following primal dual theory, and we solve the CDDM problem through the solution of primal dual scheme for solving the generalized covering problem [21], and then we solve a TSP following the NITSP algorithm [20]. The above process is illustrated in Algorithm 2.
After primal dual theory, we define the CDDM problem listed in the following equation:(10)CDDMmin∑e∈Tce+∑oi∈Oriβs.t.axi,j∈0,1,∀oi,oj∈Ob∑i=1nxi,j=1,∀oj∈Oc∑j=1nxi,j=1,∀oi∈Odci,j+rjβ≤Ci,∀oi,oj∈OTi,Ti⊆Te∑i=1n∑j=1nxi,j∑oj∈Ofoj≥ρ.There are four steps in Algorithm2, which are listed as follows:Step 1: Construct graphG by considering set O and S (Line 1);Step 2: Initialize the set ofℬ and Q (Line 2);Step 3: The following process is invoked when there existsb∈ℬ is not the primal feasible solution,(1)
Initialize setJg as j when bj,g=0,1≤j≤n (Line 4);(2)
Initialize setℒg as i when ∑j=1nci,jbj,g≤0,1≤i≤n (Line 5);(3)
Findb˜ from Jg satisfying the following equation (Lines 6–9): cb˜−∑i=1nci,rqi,g/∑i∈ℒgci,r=η=mini∈ℒkcj−∑i=1nci,gqi,g/∑i∈ℒgci,j (6)(4)
Updatebi,g+1 to 1 when j=b˜ and bi,g otherwise (Lines 10–14);(5)
Updatedi,g+1 when i belongs to set ℒg and di,g(Lines 15–19);Step 4: Find the tourT through NITSP based on zi|i=1,2,…,n (Line 22).Algorithm 2:CDRS.
Input:O,SOutput:T(1)
constructing graphG;(2)
ℬ⟵0;Q⟵0;g⟵0;(3)
whilebg is not the primal feasible do(4)
Jg⟵j|1≤j≤n,bj,g=0;(5)
ℒg⟵i|1≤i≤n,∑j=1nci,jbj,g≤0;(6)
foreachj^∈Jg do(7)
η=mini∈ℒkcj−∑i=1nci,gqi,g/∑i∈ℒgci,j;(8)
ifcj^−∑i=1nci,rqi,g/∑i∈ℒgci,r=η then(9)
b˜⟵j^;(10)
forj=1 to n do(11)
ifj=b˜ then(12)
bi,g+1⟵1;(13)
else(14)
bi,g+1⟵bi,g;(15)
fori=1 to n do(16)
ifi∈ℒg then(17)
di,g+1⟵di,g+1;(18)
else(19)
di,g+1⟵di,g;(20)
g⟵g+1;(21)
ℬn⟵bg;(22)
T⟵T⟵NITSPℬn;Theorem 5.
CDRS is a polynomial-time approximation algorithm for CDM problem.Proof.
Step 1 takesOn2 time. Steps 2 and 3 take On2 time. Step 4 can be finished in polynomial time.
Letopt denote the optimal solution of the CDM problem. The CDRS satisfies the following conditions when g=0,b0=0, and q0=0.(1)
Qg is a dual feasible solution;(2)
ce∈T−Qgℬg=0.
We assume that conditions (1) an (2) are true wheng≥0.
About condition (1), we find thatQg is a dual feasible solution after the coupling hypothesis of condition (1). Thus, η is nonnegative. Then, we have di,g+1≥di,g≥0 when i is from 1 to n.
According to condition (2), we havecj−∑j=1ncj,gqj,g=0 when j∉ℒg. Then, we have ∑i=1nci,gbi,g=0 for each i∉Jg. So, ci,j=0 when j∉ℒg.
Moreover, we have the following equation:(11)cj−∑j=1ncj,gqj,g=cj−∑j∉ℒgcj,gqj,g+1=cj−∑j∉ℒgcj,gqj,g.
From the process of Lines 6–9, we have(12)η∑i∈Jgci,j≤cj−∑i=1nci,jqj,g
Furthermore, we have the following equation whenj∈ℒg:(13)cj−∑i=1nci,jqj,g+1=cj−∑i=1nci,jqj,g−η∑i∈Jgci,j≥0.
Therefore,Qg+1 is a dual feasible solution.
For condition (2), we analyze the factor satisfying the inequality∑i=1nci,jqj,g+1≤cj. We have the equation ∑i=1nci,jqj,g≤cj when qj,g≤qj,g+1. Based on dual hypothesis, we have bj,g=0. In addition, according to the process of Lines 6–9, we also have(14)∑i=1nci,b˜qj,g+1=∑i=1nci,b˜qj,g+∑i∈Jgηcj,g=∑i=1nci,b˜qj,g+cb˜−∑i=1nci,b˜qj,g=cb˜
Finally, leth be max1≤i≤n∑j=1nci,j; we have(15)QgCℬg=∑i=1nqj,g∑j=1nci,jbj,g≤∑i=1nqj,g∑j=1nci,j≤h∑i=1nqj,g=hQg1n.
Hence, the process of Lines 2–21 can return an approximation solution.
The NITSP algorithm can find an approximation solution based on setℬn.
Above all, CDRS can find an approximation solution for solving the CDM problem in polynomial time.


## 6. Numerical Experiments

In this section, we conduct extensive simulations to verify the performance of our proposed algorithms with different number of elderly people, battery capacity of drone, initial energy of drone, and number of charging stations.


### 6.1. Simulation Setup and Benchmark

We assume that there are some emergency service request points for the elderly chronic disease deployed in Jiangning Campus of Nanjing Medical University. The elderly people will send the emergency service request at the fixed points. The parameters of drone are from Mavic 2 [22]. In our simulation, we evaluate the total time cost of drone and QoE calculated by the ratio of waiting time to request time. All the simulations were run on a cloud server ECS [23] with 12-core Intel Xeon Platinum 8269CY and 48 GB memory. The other parameter settings of our simulations are listed in Table 2.(1)
GT: the Greedy Time (GT) algorithm for solving the DM problem. The algorithm always finds the minimum time cost subtour for the drone greedily starting fromd0 and providing all elderly chronic disease emergency services that satisfy the energy constraint of drone.(2)
CGE: the Charging driven Greedy Energy (CGE) algorithm for solving the CDM problem. The algorithm always finds the maximum charging energy subtour for the drone greedily starting fromd0 and providing all elderly chronic disease emergency services that satisfy the energy constraint of drone.Table 2
Parameter settings.
ParameterValuen100m10β1.5 kWφ10 kWCmax90 Whc020 Whri[1, 5] hWe develop the following benchmark algorithms for comparison:


### 6.2. Performance Evaluation

In this subsection, we evaluate the performance of GT, DRS, CGE, and CDRS in the network shown in Tables3 and 4, which give the locations of emergency service request and charging stations, respectively. The above information is calculated based on the Google map.Table 3
Locations of emergency service request.
iLongitudeLatitude131.93433246922838118.89411397044051231.9385259860767118.89252407466076331.939684813314848118.89375307677773431.94081787467635118.88827567242747531.940289972836105118.88897362421234631.935422888622234118.88966481070858731.939230738279367118.8847133422139831.93754295175468118.8876962509683931.93555357640813118.892361906994131031.937852577865236118.89467251853483Table 4
Locations of charging stations.
iLongitudeLatitude131.933466228677545118.89180138538082231.93638454072936118.89252429138394331.93824267776691118.89280903796829431.938177713559316118.89275162333368531.937955752188387118.88729085352668631.93751465301634118.89001293552754731.942046989944334118.88759508254144831.935615904900363118.88827172056612931.934351759640094118.891399835614181031.93628201571477118.89392111202842Figures2 and 3 show the impact of number of elderly people on total time cost of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can reduce 57.38% and 64.06% of total time cost of GT and CGE on average, respectively. This indicates that the proposed algorithms significantly outperform GT and CGE, respectively. This is because the outputs of DRS and CDRS are better than the paths obtained by GT and CGE, respectively.Figure 2
Total time cost versus number of elderly people.Figure 3
Total time cost versus number of elderly people.Figures4 and 5 show the impact of battery capacity of drone on total time cost of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can reduce 26.20% and 55.63% of total time cost of GT and CGE on average, respectively. Figures 6 and 7 show the impact of initial energy of drone on total time cost of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can reduce 21.09% and 56.41% of total time cost of GT and CGE on average, respectively. Figure 8 shows the impact of number of charging stations on total time cost of CGE and CDRS, respectively. The result shows that CDRS reduces 24.53% of total time cost of CGE on average.Figure 4
Total time cost versus battery capacity of drone.Figure 5
Total time cost versus battery capacity of drone.Figure 6
Total time cost versus initial energy of drone.Figure 7
Total time cost versus initial energy of drone.Figure 8
Total time cost versus number of charging stations.Figures9 and 10 show the impact of number of elderly people on QoE of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can increase 55.63% and 89.12% of QoE of GT and CGE on average, respectively. Figures 11 and 12 show the impact of battery capacity of drone on QoE of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS increase 39.09% and 90.75% of QoE of GT and CGE on average, respectively. Figures 13 and 14 show the impact of battery capacity of drone on QoE of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS increase 18.61% and 320.8% of QoE of GT and CGE on average, respectively. Figure 15 shows the impact of number of charging stations on QoE of CGE and CDRS, respectively. The result shows that CDRS increases 58.31% of QoE of CGE on average.Figure 9
QoE versus number of elderly people.Figure 10
QoE versus number of elderly people.Figure 11
QoE versus battery capacity of drone.Figure 12
QoE versus battery capacity of drone.Figure 13
QoE versus initial energy of drone.Figure 14
QoE versus initial energy of drone.Figure 15
QoE versus number of charging stations.Overall, DRS and CDRS can not only significantly decrease the total time cost but also increase the QoE through the designed drone assisted emergency service system and its management schemes for elderly chronic disease, respectively.


## 6.1. Simulation Setup and Benchmark

We assume that there are some emergency service request points for the elderly chronic disease deployed in Jiangning Campus of Nanjing Medical University. The elderly people will send the emergency service request at the fixed points. The parameters of drone are from Mavic 2 [22]. In our simulation, we evaluate the total time cost of drone and QoE calculated by the ratio of waiting time to request time. All the simulations were run on a cloud server ECS [23] with 12-core Intel Xeon Platinum 8269CY and 48 GB memory. The other parameter settings of our simulations are listed in Table 2.(1)
GT: the Greedy Time (GT) algorithm for solving the DM problem. The algorithm always finds the minimum time cost subtour for the drone greedily starting fromd0 and providing all elderly chronic disease emergency services that satisfy the energy constraint of drone.(2)
CGE: the Charging driven Greedy Energy (CGE) algorithm for solving the CDM problem. The algorithm always finds the maximum charging energy subtour for the drone greedily starting fromd0 and providing all elderly chronic disease emergency services that satisfy the energy constraint of drone.Table 2
Parameter settings.
ParameterValuen100m10β1.5 kWφ10 kWCmax90 Whc020 Whri[1, 5] hWe develop the following benchmark algorithms for comparison:


## 6.2. Performance Evaluation

In this subsection, we evaluate the performance of GT, DRS, CGE, and CDRS in the network shown in Tables3 and 4, which give the locations of emergency service request and charging stations, respectively. The above information is calculated based on the Google map.Table 3
Locations of emergency service request.
iLongitudeLatitude131.93433246922838118.89411397044051231.9385259860767118.89252407466076331.939684813314848118.89375307677773431.94081787467635118.88827567242747531.940289972836105118.88897362421234631.935422888622234118.88966481070858731.939230738279367118.8847133422139831.93754295175468118.8876962509683931.93555357640813118.892361906994131031.937852577865236118.89467251853483Table 4
Locations of charging stations.
iLongitudeLatitude131.933466228677545118.89180138538082231.93638454072936118.89252429138394331.93824267776691118.89280903796829431.938177713559316118.89275162333368531.937955752188387118.88729085352668631.93751465301634118.89001293552754731.942046989944334118.88759508254144831.935615904900363118.88827172056612931.934351759640094118.891399835614181031.93628201571477118.89392111202842Figures2 and 3 show the impact of number of elderly people on total time cost of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can reduce 57.38% and 64.06% of total time cost of GT and CGE on average, respectively. This indicates that the proposed algorithms significantly outperform GT and CGE, respectively. This is because the outputs of DRS and CDRS are better than the paths obtained by GT and CGE, respectively.Figure 2
Total time cost versus number of elderly people.Figure 3
Total time cost versus number of elderly people.Figures4 and 5 show the impact of battery capacity of drone on total time cost of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can reduce 26.20% and 55.63% of total time cost of GT and CGE on average, respectively. Figures 6 and 7 show the impact of initial energy of drone on total time cost of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can reduce 21.09% and 56.41% of total time cost of GT and CGE on average, respectively. Figure 8 shows the impact of number of charging stations on total time cost of CGE and CDRS, respectively. The result shows that CDRS reduces 24.53% of total time cost of CGE on average.Figure 4
Total time cost versus battery capacity of drone.Figure 5
Total time cost versus battery capacity of drone.Figure 6
Total time cost versus initial energy of drone.Figure 7
Total time cost versus initial energy of drone.Figure 8
Total time cost versus number of charging stations.Figures9 and 10 show the impact of number of elderly people on QoE of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS can increase 55.63% and 89.12% of QoE of GT and CGE on average, respectively. Figures 11 and 12 show the impact of battery capacity of drone on QoE of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS increase 39.09% and 90.75% of QoE of GT and CGE on average, respectively. Figures 13 and 14 show the impact of battery capacity of drone on QoE of GT and DRS, as well as CGE and CDRS, respectively. The results show that DRS and CDRS increase 18.61% and 320.8% of QoE of GT and CGE on average, respectively. Figure 15 shows the impact of number of charging stations on QoE of CGE and CDRS, respectively. The result shows that CDRS increases 58.31% of QoE of CGE on average.Figure 9
QoE versus number of elderly people.Figure 10
QoE versus number of elderly people.Figure 11
QoE versus battery capacity of drone.Figure 12
QoE versus battery capacity of drone.Figure 13
QoE versus initial energy of drone.Figure 14
QoE versus initial energy of drone.Figure 15
QoE versus number of charging stations.Overall, DRS and CDRS can not only significantly decrease the total time cost but also increase the QoE through the designed drone assisted emergency service system and its management schemes for elderly chronic disease, respectively.


## 7. Conclusion

In this article, we have designed the drone assisted emergency service system and its management schemes for elderly chronic disease. There is a drone in the area to provide emergency services for chronic diseases, where the drone can be charged by the ground charging stations. Thus, the drone has sufficient energy to provide the emergency service for elderly chronic disease. We have formulated DM problem to minimize the total time cost of drone subject to all elderly chronic disease services which can be guaranteed exactly once by the drone under its energy constraint and proposed the DRS algorithm. To address the limitation of drone, we further formulated the CDM problem to maximize the service utility under the energy constraint of drone and proposed the CDRS algorithm. Through the theoretical analysis and numerical simulation experiments, we demonstrated that DRS and CDRS can decrease the total time cost by 37.61% and increase the QoE by 112.80% through the designed system, respectively.



---

*Source: 5552350-2021-04-09.xml*