Multiple Drone Routing Problem for On-Demand Hyperlocal Market

Abstract

Deploying drones for rapid pickup and delivery for on-demand customers in the hyperlocal market is unexplored in literature and demands attention. Maximizing customer pickup and deliveries with a limited drone flight endurance is essential but is hard to achieve in practice because of many service requests by on-demand customers. It mandates that drones cover extra mileage to visit docking stations in between services for recharge. Optimally allocating the services on available flight endurance and minimizing the docking station visits to complete all scheduled services is a predominant requirement for effective drone operations in a hyperlocal market. This problem is formulated as a mixed-integer linear programming model, and a heuristic algorithm is proposed to attempt various practical size problems, with near-optimal solutions reported. The paper offers valuable insights for practitioners and future researchers wishing to analyze the performance of drone operations and determine the appropriate number of drones required for the hyperlocal market based on service demand.

Keywords

drone routing hyperlocal delivery on-demand economy urban air mobility

The tremendous growth of digital business models has familiarized customers with ordering on demand and receiving products in a short lead time. Online platform service providers connect customers to preferred off-line shops in a local market. The last-mile delivery service providers receive orders from an online platform to pick up packages from the customer’s desired local vendor and deliver them to the desired location. However, planning deliveries in a densely populated urban area with conventional vehicles is challenging and expensive. So the logistics companies are looking for various innovative modes of transport (i.e., last-mile robots, drones, and cargo bikes) to minimize the pressure on environmental concerns and city regulations to mitigate the carbon footprint. Drones are also called unmanned aerial vehicles (UAVs), or flying robots with various potentials to effectively cross the last mile of deliveries, specifically for the smallest and lightest packages ( 1 ). Online retail giant Amazon has reported its average payload is below 5 lb, which can be efficiently delivered by airborne vehicles. Drones are even operative for hyperlocal market deliveries like food items, pharma products, postal deliveries, bakery items, groceries, and so forth. Organizations like Zipline, Flirtey, Swiggy, and Domino’s are already experimenting with drones for commercial deliveries. Even companies like DHL and UPS are adopting drones in tandem with trucks as a supporting “sidekick” to handle small and lightweight package deliveries ( 2 , 4 ). These sensing transportation systems are essential for convenient pickup and delivery services in today’s world as they effectively approach operational complexity ( 5 , 6 ). The operational complexity includes the drone routing and allocation problem, appropriate estimation of the battery consumption rate, ensuring a drone safe-fly-and-return strategy, planning docking stations for recharge during flight, optimally sequencing services to minimize the total flight distance, and appropriate selection of the number of drones required for services in the hyperlocal market. Apart from this, other technical constraints such as weather conditions, physical obstacle avoidance, a dedicated facility for landing and take-off in congested cities, and restricted-zone flight control need to be considered for effective drone operations. In this paper, the technical constraints are out of scope and the argument is focused on the operational constraints.

Last-mile logistics service providers need consideration of operational complexity for implementing multiple drones in the hyperlocal market. The docking station facility is essential for recharge and acts as a drone base station from which all drones depart and to which they return for a halt during the non-service period. Planning docking stations for drone routes is another complex challenge in drone operations. Next, an accurate estimation of the battery consumption rate is crucial in a drone operation; for example, underestimated battery capacity during a scheduled service will cause severe accidents and lead to lost opportunities to serve more customers. Further, deciding the number of drones for deliveries is a capacity decision problem for a drone service provider, and it depends on customer service demand. These various practical complexities motivated this study to design a multi-drone operation system, which is coined as a multi-drone routing problem for hyperlocal delivery (MDRP-HD).

The objectives of the proposed paper are threefold. The first is to minimize the total distance traveled by drones to complete the scheduled services. The second is to achieve optimal utilization of battery capacity by adapting the drone safe-return strategy. For the third, a trade-off analysis is conducted to select an appropriate number of drones based on service sizes. This problem is formulated as a mixed-integer linear program (MILP); because of model and exponential time complexity, the problem solution is approached by a robust heuristic procedure called the hyperlocal multi-drone neighbor search algorithm (H-MDNSH). The real-time instances are generated in two aspects. First, local vendor data is collected from the hyperlocal market region of Dehradun, India. Second, customer data is collected randomly from the residential location of Dehradun. This paper shrewdly anchors its data with an alphanumeric geocoding system called the w3w encoding system, used to collect the real-time location of vendors and customers. Further, the sections of the paper are organized as follows. The next section presents the related literature on the drone routing problem. The third section elaborates the problem statements and solution approach. The fourth section discusses the analysis and interpretation of the proposed problem. Finally, the fifth and sixth sections provide insights for future research, limitations of the research, and the conclusion.

Literature Review

The drone routing problem gets special attention in the literature as a result of the tremendous development in drone applications for commercial drone services (drones-as-a-service) ( 7 ). However, deploying drones for various services necessitates a robust routing plan for drone operations ( 8 ) because drones are limited in flight endurance. Most of the studies have focused on the single drone travel capacity (DTC) or battery capacity (BC) and developed a mathematical model for efficient utilization of the battery capacity during the flight ( 1 , 7 , 9 ). In comparison, the model presented in our work considers multiple drones for the pickup and delivery of customer goods and predominantly measures the wasted DTC during the services. The wasted DTC is a vital metric to estimate the cost performance of drone operations for commercial purposes, one which is not addressed in the previous studies. Zhang et al. ( 10 ) proposed a framework to understand the energy conservation model for delivery drones. They documented wide variations in the energy consumption rates (ECR) based on the design, environment, dynamics, and delivery parameters of drones. Dukkanci et al. ( 11 ) calculated the energy consumption of the drones as a function of drone speed with payload and without payload. They developed a nonlinear model for the energy minimizing and range constrained drone delivery problem (ERDDP) and reported that the limitation on deliveries is based on service time limits and range that are a function of battery capacity and the drone speed. Cheng et al. ( 12 ) proposed a multi-trip drone routing problem, where the energy consumption was modeled as a nonlinear function of payload and travel distance. They designed a model in which drones are displaced from the depot, and for each trip the drone starts and ends at the depot. There are no limitations on the number of trips that each drone can perform.

Kirschstein ( 13 ) proposed a stationary parcel delivery system using drones, where the customers are served from the depot. The energy consumption model is measured based on environmental conditions and the flight pattern. Jeong et al. ( 14 ) proposed a truck–drone hybrid delivery system and developed a “flying sidekick traveling salesman problem” (FSTSP) by implementing an energy consumption and no-fly zone model. This model is proposed to overcome drone flight endurance and payload lifting limitations by sharing the delivery schedules with big trucks. The objective is to minimize travel distance and transportation costs to meet customer demand on time ( 15 ). The same problem is extended by Cavani et al. ( 16 ), who proposed a delivery system with a traditional vehicle and multiple drones working in tandem to fulfill customer requests. In the multi-modal delivery, the drones are scheduled according to their travel capacity for short-distance delivery to avoid the congested truck routes ( 2 ) with ground vehicle support. However, hyperlocal market deliveries necessitate an optimal delivery plan for drones without any ground vehicle support. This mandates that drone logistics service providers optimally plan the drone travel (flight) capacity with payload limitation ( 17 ) by attaching docking stations on drone routes. The objective will be to maximize the service density with the appropriate utilization of battery capacity.

Docking stations are required for drone delivery in an urban and rural region to counteract the drone flight limitations. Ghelichi et al. ( 18 ) developed an optimization model for a fleet of drones for timely delivery of medical items by incorporating a docking station. The package was picked up from an urban vendor and delivered to the rural clinic. They implemented charging stations on the drone routes to enrich the flight capacity for long-range delivery. Cokyasar ( 19 ) addressed the battery capacity constraints of drones for e-commerce delivery. A MILP model was proposed to execute efficient drone routing over battery swapping machines, which minimized the delivery lead time. The battery swapping machine is installed at an appropriate location to tackle the flight range limitation of the drones for e-commerce delivery. Many researchers have addressed the battery limitation of drones by incorporating a docking station to enrich the drone endurance. This facilitates the drone service provider in attempting to reach long-range customers and also increases the service density with many customer pickups and deliveries.

In many studies, drones work in tandem with a truck for delivery; at the same time, the truck acts as a pickup point and a recharge/swapping point for the drones. In some studies, warehouses or depots act as the pickup point, recharge station, and stationary point for drones during non-service periods ( 9 ). However, the hyperlocal market scenario for small/lightweight package delivery does not require a permanent depot or fulfillment center. So, in this case, exclusive docking station facilities are required ( 9 , 18 ) for battery recharge/swapping and as a drone halt during the non-service period. The limitations of short flight range and least payload lifting capacity are why the drones are assigned ground vehicle support ( 20 ). Many retail giants do this—specifically: Amazon, which significantly invested in its Prime Air program, which has a travel capacity of 16 km (10 mi) per recharge and a payload capacity of 2.26 kg; Salama and Srinivas ( 21 ), which was approved by the FAA in 2020 ( 22 ); and DHL, which invested in Parcelcopter 4.0, which has a travel capacity of 37 km (22.99 mi) and can carry a payload of 4.38 lb (1.99 kg) ( 23 ), for commercial parcel delivery. The above statements prove that drone operations for hyperlocal market delivery for small/lightweight packages will be feasible in the near future. The proposals in this paper will provide valuable insights for implementation.

To the best of the authors’ knowledge, no literature has investigated the multi-drone pickup and delivery routing problems for a hyperlocal market ecosystem by incorporating a docking station as a facility for recharge. In the proposed model, the drones are not supported by ground vehicles and are not returned to a dedicated depot for recharge. In most of the literature, drones are utilized in a multi-trip delivery model (each trip starts and ends at the depot) ( 12 ) without analyzing the remaining battery utilization metrics. The proposed paper measures the battery utilization metrics, that is, unutilized travel capacity (UTC) and excess travel capacity (ETC), which are indicators for measuring the performance of drone operations. At the same time, the proposed model maximizes the service density of customers by minimizing the number of visits to the docking station. This is the first paper to formulate a multi-drone routing problem for hyperlocal delivery (MDRP-HD) as a MILP model and propose a hyperlocal multi-drone neighbor search algorithm (H-MDNSH) to approach the solution of a practical size problem.

Multi-Drone Routing Problem for Hyperlocal Delivery (MDRP-HD)

Problem Statement

On a typical day, on-demand shoppers place orders through mobile/online platforms. The platform service provider communicates the order fulfillment request to the drone service provider and the corresponding local vendor. First, the platform service provider evaluates the transport mode for delivering the particular service request. Drone delivery has certain criteria, such as the order placed having to be within a stipulated radius distance; the package having to be under drone lifting capacity; route clearance (i.e., restricted fly zones, environmental conditions, etc.), drone landing, and take-off clearance being required at the vendor’s and customer’s location; and a docking station needing to be available. After approving the drone mode of delivery, the platform service provider confirms the availability of drones with drone service providers and simultaneously communicates this to the vendors for the order fulfillment approval. After the approval is received, the customer receives an order confirmation and order delivery time, and is requested to complete the payment for the service. Now the drone heads out to the pickup point, that is, a hyperlocal vendor location, to collect the package and proceed to the delivery point. Customers will be requested to provide a self-confirmation protocol for drone landing and take-off at the delivery point. Self-confirmation protocols are checks such as whether the drone is safe for landing or take-off now, clearance of humans, obstacles, hazardous materials, and so forth. The goal of the platform service provider is to organize the fleet of drones by appropriate route planning to deliver as many orders as possible with minimum operational cost. The cost is a function of the distance traveled by the drones to complete the scheduled services within a service time. Because of this, optimal sequencing of the services with available DTC or flight endurance becomes a primary objective, which minimizes the total distance traveled by the drones to complete the scheduled services.

The problem is defined on a graph, G_k = (V_k, A_k), where k is the number of drones; V_k is several nodes in a network, that is, several customers and vendors with a common docking station (ds); A_k is an arc between the pickup points (p), delivery points (d), and docking station (ds). Set V_k = {o(k), d(k)} is the set of nodes inclusive of the origin, o(k), and destination, d(k), respectively. The subset A_k of V_k*V_k comprises all arcs, that is, any node is connected directly with any other node in the network, forming a Hamiltonian graph. Customer request i (pickup location) to corresponding j (delivery location) on a drone (k) consists of transporting distance q_ijk. This transporting distance (q_ijk) has three categories ( 1 , 24 ), which are measured for the drone pickup and delivery operations as shown in Table 1.

Table 1.

Categories of Distances

	Docking station (ds)	Pickup point (p)	Delivery point (d)
Category 1	◆----------------------------◆
Category 2		◆----------------------------◆
Category 3			◆----------------------------◆

Category 1 is a distance from docking station (ds) to pick up point (p), Category 2 is from the pickup point (p) to delivery point (d), and category 3 is from delivery point (d) to the docking station (ds). Summing up all three categories is a complete service cycle in a hyperlocal market. This complete cycle distance (CCD) acts as a decision criterion for the drone service provider to accept or reject the services. To accept the service, the DTC should be greater than or equal to CCD. In practice, drones are not mandated to return to ds after completing each service. Drones will be allocated to the next service from the current delivery point (d) to the next pickup point (p) and corresponding delivery point (d). Here the CCD is calculated from the current delivery point (d) to the next pickup point (p) to the corresponding delivery point (d) and then to the docking station (ds). This ds distance is always calculated to ensure the drone’s safety without running out of battery. This service schedule continues until DTC falls below the service distances. If the DTC is less than the next service distance, the drones will be routed to the ds to recharge the battery. For example, a 10-service problem (i.e., n = 10) is shown in Table 2.

Table 2.

Sample Results of Two Drones for Ten Services

S. no.	Details	Drone 1	Drone 2	Total
1	Route sequence	ds → 8p → 8d → 3p → 3d → 4p → 4d → 5p → 5d → 6p → 6d → ds	ds → 1p → 1d → 2p → 2d → 9p → 9d → 10p → 10d → ds → 7p → 7d → ds	na
2	Distance traveled by drone to complete all 10 services	17.66 km	33.02 km	50.68 km
3	Number of visits to ds to complete all 10 services	0	1	1
4	Unutilized travel capacity	0 km	12.98 km	12.98 km
5	Excess travel capacity	7.34 km	4 km	11.34 km

Note: S. no. = Serial Number; ds = docking station; 8p = pickup point 8; 8d = delivery point 8; na = not applicable.

The total number of pickups is 10, and the corresponding number of deliveries is 10. With one ds node, there are a total of 21 independent nodes in the network. The parameters are: number of drones (k) = 2, and DTC = 25 km per charge. The results are interpreted as follows. Drone 1 attempted services 8, 3, 4, 5, and 6, with a travel distance of 17.66 km and without any visit to the ds. Drone 2 completed 1, 2, 9, 10, and 7 by traveling 33.02 km with one ds visit. After completing the 10th service, drone 2 was not able to attempt service 7 because the DTC was less than the CCD. So, drone 2 was directed to ds for recharge. At this point drone 1 may be busy with other allocated services. This ds visit increases the surplus distance called UTC. UTC is a remaining charge or mileage existing after the drone reaches ds in between the scheduled services, and it is 12.98 km for drone 2 and 0 km for drone 1. ETC is also a remaining mileage that occurs while reaching ds on completing all scheduled services, and it is 4 km (for drone 2) and 7.34 km (for drone 1).

If the number of drones attempting the set of services decreases, this will increase the ds visits and pile up the UTC mileage; at the same time, if the number of drones increases, it will decrease the ds visits and UTC, but pile up the ETC mileage. This formulates a trade-off analysis between the UTC and ETC to select an appropriate number of drones for the number of services. If the company increases the number of drones for delivery, it will appreciate customer satisfaction. But the company gives equal importance to the operational perspective, that is, maximizing drone capacity utilization. The goal is to identify the optimal balance between the metrics UTC and ETC to increase the operational efficiency of drones. However, operational efficiency depends on minimizing the distance traveled by the drones to complete the scheduled set of services. The mathematical model is formulated to achieve this objective function.

Mathematical Model

The proposed MILP model is an extension of the single-drone pickup and delivery model proposed by Pachayappan and Sudhakar ( 1 ). That proposed model incorporated the operation performance index UTC, ETC, and safe-return strategy of drones in a multiple drone perspective for hyperlocal market delivery. Table 3 summarizes the notations used in the model formulation. The following assumptions are considered for the proposed MDRP-HD.

All customer pickup and delivery locations are known before initiating drone operations, and all customers must be served.

The drone can serve only a single customer pickup and delivery request at a time.

The drone can only serve requests that do not exceed its physical carrying payload capacity of 2 kg.

The drone initiates from the docking station for the first service.

The drone is routed to the docking station after completing the scheduled services.

Drones are routed to the docking station for a halt during the non-service period.

All service requests fall within a 10 km radius.

Min = \sum_{k \in K} \sum_{(i, j) \in N} q_{ijk} x_{ijk}

(1)

subject to

\sum_{k \in K} \sum_{j : (i, j) \int N} x_{ijk} = 1 \forall i \in (P \cup D) \cap ds

(2)

\sum_{k \in K} \sum_{i : (i, j) \int N} x_{ijk} = 1 \forall j \in (P \cup D) \cap ds

(3)

\sum_{j : (0, j) \in N} x_{0 jk} = 1 \forall k \in K

(4)

\sum_{i : (i, n + n' + 1) \in N} x_{i, n + n' + 1, k} = 1 \forall k \in K

(5)

\sum_{i : (i, j) \in N} x_{ijk} - \sum_{i : (j, i) \in N} x_{jik} = 0 \forall j \in (P \cup D) \cap ds, k \in K

(6)

q_{ijk} + q_{jmk} + q_{mik} \leq DT C_{max} (1 - y_{1}) \forall i \in Ds, \forall j \in P, \forall m \in D, \forall k \in K

(7)

RDTC (1 - y_{1}) = DT C_{max} (1 - y_{1}) - (q_{ijk} + q_{jmk}) \forall i \in Ds, \forall j \in P, \forall m \in D, \forall k \in K

(8)

q_{mjk} + q_{jmk} + q_{mik} \leq RDTC (1 - y_{2}) \forall i \in Ds, \forall j \in P, \forall m \in D, \forall k \in K

(9)

RDTC (1 - y_{2}) = RDTC (1 - y_{2}) - (q_{mjk} + q_{jmk}) \forall j \in P, \forall m \in D, \forall k \in K

(10)

q_{mik} \leq RDTC (1 - y_{3}) \forall i \in Ds, \forall m \in D, \forall k \in K

(11)

UTC = RDTC - q_{mik}

(12)

RDTC (1 - y_{3}) = DT C_{max}

(13)

p_{ik} \leq d_{n + i, k} \forall i \in P, k \in K

(14)

\sum_{j : (i, j) \in N} x_{ijk} - \sum_{j : (n + i, j) \in N} x_{n + i, j, k} = 0 \forall i \in P, k \in K

(15)

ETC = RDTC - q_{mik}

(16)

x_{ijk}, x_{jmk}, x_{mjk}, x_{mik} \in {0, 1} \forall (i, j) \in N

(17)

y_{1}, y_{2}, y_{3}, y_{4}, y_{5} \in {0, 1}

(18)

The objective function (1) minimizes the total distance traveled by the drones to complete the services. Constraints (2) and (3) ensure that every vertex has been served exactly once. Constraints (4) and (5) guarantee that the drones begin their tour from ds and return to ds after completing the services. Constraint (6) guarantees flow conservation, where the drone arrives at a node and exits to visit another one until it completes its delivery tour. Constraints (7–13) ensure the safe-return strategy of the drones and ensure the service selection criteria based on DTC. Constraint (7) guarantees that the drone starts from the ds and travels to the linked pickup and delivery with the condition that CCD should be less than or equal to DTC_max. If this condition is accepted, the DTC_max should be updated with the recent drone travel capacity (RDTC). Equation 8 ensures the updated RDTC. Next, the drone may be assigned to the next service or return to ds for recharging the battery. Constraint (9) ensures the selection of the next service from the current delivery point to the next pickup and corresponding delivery point with the condition that CCD should be less than or equal to RDTC. If the service is accepted, then the RDTC will be updated, as shown in Equation 10. Otherwise, the drone will be routed to ds (11) and update the UTC (12). After reaching ds, drones will be enriched with full DTC_max (13). Constraint (14) ensures the delivery can only occur after the pickup of the package. Constraint (15) ensures both pickup and corresponding delivery must be served by the same drone. Constraint (16) updates the ETC mileage that occurs after completing all services. Constraints (17) and (18) ensure the binary variables.

Table 3.

Notations

Parameters
k	Number of drones
p	Pickup point
d	Delivery point
ds	Docking station
UTC	Unutilized travel capacity
ETC	Excess travel capacity
CCD	Complete cycle distance
DTC	Drone travel capacity in kilometers per recharge/swapping
RDTC	Recent DTC in kilometers per recharge/swapping
Sets
S	Number of services
K	Set of drone K = {1,2, ..., k)
n	Set of all nodes in the network
C	Set of customers service request C = {1, 2, 3, ....., n)
C₀	Set of customers and the ds as the starting location. C₀ = {0, 1, 2, 3, …, n}
C_E	Set of customers and the ds as the terminal location. C_E = {1, 2, 3, …, n+1}
Decision variables
$q_{ijk}$	The flight distance from docking station i to pickup point j by drone k
$q_{jmk}$	The flight distance from pickup point j to delivery point m by drone k
$q_{mjk}$	The flight distance from delivery point m to pickup point j by drone k
$q_{mik}$	The flight distance from delivery point m to docking station i by drone k
$q_{jik}$	The flight distance from pickup point j to docking station i by drone k
$q_{imk}$	The flight distance from docking station i to delivery point m by drone k
$x_{ijk}$	Binary variable; 1 if drone k flight from docking station i to pickup point j; 0 otherwise
$x_{jmk}$	Binary variable; 1 if drone k flight from pickup point j to delivery point m; 0 otherwise
$x_{mjk}$	Binary variable; 1 if drone k flight from delivery point m to pickup point j; 0 otherwise
$x_{mik}$	Binary variable; 1 if drone k flight from delivery point m to docking station i; 0 otherwise
$x_{jik}$	Binary variable; 1 if drone k flight from pickup point j to docking station i; 0 otherwise
$x_{imk}$	Binary variable; 1 if drone k flight from docking station i to delivery point m; 0 otherwise

Solution Approach

To solve the MDRP-HD, we developed a heuristic algorithm called the hyperlocal multi-drone neighbor search algorithm (H-MDNSH). It was inspired by the well-known neighborhood search heuristics proposed by Shaw ( 25 ), Mladenović and Hansen ( 26 ), and Ropke and Pisinger ( 27 ). In general, neighborhood search is a simple greedy approach in which moves within the neighborhood are generated in a randomized procedure. A move is agreed if it reduces the distance or cost and is rejected otherwise. The procedure stops after assigning all jobs in a sequence or after a specific time period.

The proposed algorithm initially follows the procedure of searching the nearest neighbor, but in the case of drone pickup and delivery, the nearest neighbor will be based on CCD, as discussed in the previous section. CCD is a distance from ds to pickup point to corresponding delivery point and then to ds. CCD is expressed in Equation 19.

CCD = \sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk} + \sum_{m = 1}^{d} q_{mik}

(19)

Drones initially head up from ds to attempt the scheduled services. CCD act as a metric that intimates the nearest neighbor based on distances. The proposed algorithm assigns the nearest services to the available drones by measuring the safe-return strategy. A safe-return strategy ensures the DTC without running out of battery during the service. Equation 20 expresses the service acceptance condition for the safe flight, where the CCD should be less than or equal to DTC_max.

CCD \leq DT C_{\max}

(20)

In Table 2, drone 1 initiates from ds to attempt the eighth pickup and delivery service, which is the nearest neighbor, with CCD of 0.67 km and DTC_max of 25 km. According to the safe-return strategy CCD is less than DTC_max, which permits the eighth service. After completing the eighth service, the drone is routed to the next nearest service, and there is no obligation that the drone should be routed to ds (q_mik) after completing the eighth service. But Equation 19 includes the q_mik distance for accepting the service, and it is essential for ensuring safe flight in the drone’s operations. This distance is proactive confirmation that the drone has enough flight capacity to return to ds after the delivery, but, in reality, the drone will be assigned to the next nearest service by ensuring the safe-return condition (Equation 20) again. Here, the RDTC should be calculated in this position to assign the next service, as shown in Equation 21. RDTC is the difference between the actual service distance and DTC_max. The actual service distance for the eighth service from ds to the pickup point is 0.264 km, and from the pickup point to the corresponding delivery point the distance is 0.208 km, with the total actual service distance being 0.472 km. This actual distance reduces from the DTC_max to update the RDTC, which is 24.53 km (Table 2).

To assign the next service for drone 1, again, the CCDs should be calculated for the remaining services from the current delivery point. Now the current position of the drone is at the eighth delivery point (8d); from this delivery point, the next nearest service should be determined by CCD, that is, from the recent delivery point to the next available pickup point (q_mjk) and corresponding delivery point (q_jmk), and from the delivery point to the docking station (q_mik). The same is expressed in Equation 22. Now compare the acceptance criteria given in Equation 23, where the CCD should be less than or equal to RDTC to accept the next service. This will continue until the RDTC falls below the CCD of services. If the RDTC falls below the CCD, then the drone should be routed to ds for recharge with the available BC (q_mik). The proposed algorithm ensures this safe-return strategy before accepting the services. For example, in Table 2, the sequence of drone 2’s attempted services is given as ds → 1p → 1d → 2p → 2d → 9p → 9d → 10p → 10d → ds → 7p → 7d → ds; after the 10th service, the drone is routed to ds, as at 10d the drone updates the RDTC (Equation 21) and checks the next nearest service by calculating the CCD (Equation 22). The RDTC is 14.18 km and CCD is 22.19 km, according to the safe-return condition, and therefore RDTC <= CCD, so the drone rejects the service and is routed to ds with UTC 12.98 km, which is underutilized capacity because after reaching ds the drone will recharge or swap the battery to 100%. This performance index represents the solution quality of the proposed algorithm by minimizing the UTC. The framework for one such heuristic is proposed, and the pseudocode is shown in Algorithm 1.

RDTC = DT C_{\max} - [\sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk}]

(21)

CCD = \sum_{m = 1}^{d} q_{mjk} + \sum_{j = 1}^{p} q_{jmk} + \sum_{i = 1}^{ds} q_{mik}

(22)

CCD \leq RDTC

(23)

Algorithm 1 Pseudocode
1. Inputs:S, k, p, d, ds, DTC_max, RDTC, n2. Output: Route sequence, Number of visits to ds, Total distance, UTC, ETC3. Repeat4. $X$ (ds) as a base point for the drone5. From X calculate the CCD for all available services6. Sort the services in an ascending order according to the CCD7. Randomly assign the available drones to the top least services8. Safe-Return Strategy9. If10. $CCD$ $(X) = \sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk} + \sum_{m = 1}^{d} q_{mik}$ 11. $CCD (X) \leq DT C_{\max} then$ 12. Drones Accept the services ←X^’13. End14. Update the RDTC15. $RDTC = DT C_{\max} - [\sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk}]$ 16. Traveled distance = $\sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk}$ 17. Update the index ←X X^’18. Drone Allocation condition19. $K_{k}^{t} = K_{k}^{t'}$ (If all drones complete the assigned services at the same time, then randomly assign the remaining services to the drones)20. $K_{k}^{t} < K_{k}^{t'}$ ( $K_{k}^{t}$ is less than $K_{k}^{t'}$ , then assign next service to K^t)21. $K_{k}^{t} > K_{k}^{t'}$ ( $K_{k}^{t}$ is greater than $K_{k}^{t'}$ , then assign next service to K^t’)22. From X delivery point select the next nearest services23. $CCD (X) = \sum_{m = 1}^{d} q_{mjk} + \sum_{j = 1}^{p} q_{jmk} + \sum_{i = 1}^{ds} q_{mik}$ 24. If CCD (X) ≤ RDTC then25. Accept the service ←X^’ Go to line 3226. Else27. Reject the delivery ←X28. UTC = RDTC –q_mik29. Count = ds30. Go to line 431. End32. Update the RDTC33. $RDTC = RDTC - [\sum_{m = 1}^{d} q_{mjk} + \sum_{j = 1}^{p} q_{jmk}]$ 34. Update the Traveled distance = $\sum_{m = 1}^{d} q_{mjk} + \sum_{j = 1}^{p} q_{jmk}$ 35. Go to line 1736. ETC = RDTC −q_mik37. Until iteration = S38. Add X to the end of the list route39. Return service route, number of ds visit, UTC, ETC, Total distance

Algorithm 1 Pseudocode

1. Inputs:S, k, p, d, ds, DTC_max, RDTC, n2. Output: Route sequence, Number of visits to ds, Total distance, UTC, ETC3. Repeat4.

X

(ds) as a base point for the drone5. From X calculate the CCD for all available services6. Sort the services in an ascending order according to the CCD7. Randomly assign the available drones to the top least services8. Safe-Return Strategy9. If10.

CCD

(X) = \sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk} + \sum_{m = 1}^{d} q_{mik}

11.

CCD (X) \leq DT C_{\max} then

12. Drones Accept the services ←X^’13. End14. Update the RDTC15.

RDTC = DT C_{\max} - [\sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk}]

16. Traveled distance =

\sum_{i = 1}^{ds} q_{ijk} + \sum_{j = 1}^{p} q_{jmk}

17. Update the index ←X X^’18. Drone Allocation condition19.

K_{k}^{t} = K_{k}^{t'}

(If all drones complete the assigned services at the same time, then randomly assign the remaining services to the drones)20.

K_{k}^{t} < K_{k}^{t'}

(

K_{k}^{t}

is less than

K_{k}^{t'}

, then assign next service to K^t)21.

K_{k}^{t} > K_{k}^{t'}

(

K_{k}^{t}

is greater than

K_{k}^{t'}

, then assign next service to K^t’)22. From X delivery point select the next nearest services23.

CCD (X) = \sum_{m = 1}^{d} q_{mjk} + \sum_{j = 1}^{p} q_{jmk} + \sum_{i = 1}^{ds} q_{mik}

24. If CCD (X) ≤ RDTC then25.

Accept the service ←X^’ Go to line 3226. Else27. Reject the delivery ←X28. UTC = RDTC –q_mik29. Count = ds30. Go to line 431. End32. Update the RDTC33.

RDTC = RDTC - [\sum_{m = 1}^{d} q_{mjk} + \sum_{j = 1}^{p} q_{jmk}]

34. Update the Traveled distance =

\sum_{m = 1}^{d} q_{mjk} + \sum_{j = 1}^{p} q_{jmk}

35. Go to line 1736. ETC = RDTC −q_mik37. Until iteration = S38. Add X to the end of the list route39. Return service route, number of ds visit, UTC, ETC, Total distance

Drone Allocation

In the multi-drone routing problem, allocating drones to the services according to the completion time of each service is a challenging task in practice. In reality, the drone service providers may have heterogeneous or homogeneous fleets of drones, which are differentiated by flight endurance and payload lifting capacity. For simplicity, in this paper a homogeneous capacity of drones has been assumed for the experiment, with fixed flight endurance (DTC) of 25 km per recharge and drone lifting capacity of 2 kg. The paper proposes drone allocation criteria based on the completion time of each service. In Algorithm 1, three drone allocation criteria are proposed from lines 19 to 21. These allocation criteria are based on first come first served.

The first criterion relates to allocation of drones when they complete services simultaneously (K^t = K^t’). In the hyperlocal market, there may be many possibilities for the drones to complete services simultaneously, and allocation must be in real time. For example, Table 4 shows the results of Algorithm 1 for a 10-service problem with two drones. According to the service acceptance criteria, the CCDs of all services are calculated and sorted in ascending order. The first two shortest services are selected and randomly allocated to the drones k₁ and k₂. The starting time is zero for both drones, so according to the first drone allocation condition, service 8 is assigned to k₁ and service 1 is assigned to k₂ simultaneously. The service completion times are 0.709 min (k₁) and 1.220 min (k₂). Drone 1 completes the assigned service before drone 2, and immediately drone 1 should be assigned to the next unattempted services (i.e., 2, 3, 4, 5, 6, 7, 9, 10) without waiting for drone 2 to complete.

Table 4.

Two-Drone Route for 10-Service Problem

Drone 1	Service 8	Service 3	Service 4	Service 5	Service 6	ds
Actual distance (km)	0.472	0.760	1.426	4.578	8.772	1.650
Cumulative distance (km)	0.472	1.233	2.659	7.237	16.009	17.659
Service completion time in minutes (assumed customer time window is 40 km)	0.709	1.849	3.989	10.855	24.014	26.489

Drone 2	Service 1	Service 2	Service 9	Service 10	ds	Service 7	ds
Actual distance (km)	0.814	0.774	3.500	5.737	1.196	10.829	10.180
Cumulative distance (km)	0.814	1.587	5.087	10.824	12.020	22.849	33.029
Service completion time in minutes (assumed customer time window is 40 km)	1.220	2.381	7.631	16.236	18.030	34.274	49.544

Note: ds = docking station.

The next service will be allocated again by checking the CCDs of all unattempted services from drone 1’s current delivery position. This allocation refers to the second category of drone allocation, where $K_{1}^{0.709} < K_{2}^{1.220}$ —this condition minimizes the idle time of drone 1 and enriches the capacity utilization. The next nearest service for drone 1 is service 3; the actual distance is calculated from the eighth service delivery point (the current position of the drone) to the third pickup point and to the corresponding delivery point, which gives 1.849 min to complete the service. Now drone 1 is allocated to service 3, and it consumes 1.849 min completing the service. Concurrently drone 2 will complete service 1 by 1.220 min and is required to be assigned the next service. Here the third drone allocation condition needs to be compared, that is, $K_{1}^{1.849} > K_{2}^{1.220}$ , which means drone 2 completes the service before drone 1, so the next preference should be given to drone 2 with the unattempted services (2, 4, 5, 6, 7, 9, 10). According to the CCDs of the remaining services, drone 2 is allocated to attempt service 2. Now service 2 should be removed from the remaining unattempted service list for further allocation.

This flow of drone allocation will not have any issue until the drones request a battery recharge because, according to the safe-return strategy, if the DTC is less than the CCDs, the drone should be routed to the ds for recharge. These ds visits affect the drone allocation decision. For example, in Table 4, drone 2 completes service 10 at 16.236 min, at which point drone 1 is flying to complete service 6, and the completion time is 24.014 min, which is later than drone 2’s completion time. So, the third allocation criterion, $K_{k}^{t} > K_{k}^{t'}$ , is followed and drone 2 is allocated to attempt service 7, but the drone has RDTC of 14.176 (25 – 10.824) km, which is below the minimum to attempt service 7 (CCD is 21.005 km). Drone 2 rejects service 7 and requests a ds visit to recharge or swap the battery. Here, the distance coverage from the service 10 delivery point to ds is only 1.196 km, so the UTC becomes 12.98 km (14.176 – 1.196 km). At this point, drone 2 is at ds with a total time of 18.030 min. Now this ds time should be compared with drone 1’s current status. According to the result, drone 1 is still flying to complete service 6, which takes 24.014 min, greater than drone 2’s position time of 18.030 min. In accordance with the third drone allocation criterion, drone 2 is assigned to service 7, which completes the service by 34.274 min. At this point, all services have been attempted, and the drones are routed to the ds. Drone 1 and 2 have completed the allocated services. However, from the operational perspective, drone 1 reached ds after completing the allocated services with UTC of 0 km and ETC of 7.341 km. Drone 2 increased the UTC to 12.98 km by visiting the ds and reached ds with remaining ETC of 3.991 km. These two metrics UTC and ETC affect drone operations from the cost perspective, and we can consider these metrics as an idle time of drones without services.

Analysis and Interpretation

The proposed problem is analyzed using two sets of real-time instances. The first set of data instances are collected from the hyperlocal market of City Dehradun in India. The service size that ranges from 10 to 100 is collected from the Dehradun region. Instances from 130 to 315 are adopted from Pachayappan and Sudhakar ( 1 ). Each service size is allocated five replications and a total of 55 instances in the experiment; the proposed algorithm handles approximately 8600 customer requests. Dehradun covers 3088 km² with a 1696694 population and a household of 347000. The real-time locations of the local vendors, that is, restaurants, bakers, grocers, pharmacies, and vegetable and fruit sellers, are collected using Google Maps API services. The customer locations are randomly generated within a radius of 10 km, and the center point of the city is assumed as a docking station point for the drones, as shown in Figure 1.

Figure 1.

Geographical representation of Dehradun with docking station (ds) at center.

After the data has been collected from the Google Maps API service, it is converted to a three-letter precision address by using w3w (what3words). This conversion provides two advantages. First, a precision location for the drone’s take-off and landing can be fixed in a 3 m × 3 m space in an available area of vendors and customers. For example, the restaurant vendor can provide a 3 m × 3 m location on an open terrace, an open balcony, or open ground. The customer can also provide a 3 m × 3 m location by using w3w to decide where the drone should land for dropping the package. This geocoding provides a high accuracy for drone service providers for pickup and delivery. Second, remembrance of the three dictionary words provides the advantage to the customers of sharing their current locations for drone delivery. The distance between the vendors and customers is calculated using the Haversian method. The experiment was run on a desktop computer with an Intel® Core i5-6500 CPU @ 3.20GHz processor. The hyperlocal multi-drone neighbor search algorithm (H-MDNSH) was coded in Python 3.7.

The baseline parameters for the experiment are: number of customer requests, in the range 10 to 315 services; number of drones (k), which is 1 to 4 for all services; the number of docking stations (ds), which is 1; assumed flight endurance (DTC), which is 25 km per recharge/swap; that every customer request will be within a 10 km radius; and assumed payload lifting capacity, which is 2 kg. Table 5 shows the results of the different service sizes with replications, number of visits to ds, and total distance (TD) coverage, UTC, and ETC in kilometers for all drones. Figure 2, a to k , shows the dynamics of a varying number of drones on various service sizes. The average of all service sizes is measured and normalized to identify the trade-off between the proposed metrics, that is, between the number of drones, number of ds visits, UTC, and ETC. By observing the results of each service size, it is evident that as the number of drones increases the number of ds visits decreases. Figure 2a is a 10-service size instance which shows that the average number of visits made by one drone is 3.6, that for two drones is 3.4, three drones is 2.2, and four drones visited 1.75 times to complete the scheduled services. The same results exist for all service sizes.

Table 5.

Number of Drones and Solution

S. no.	Service size	No. of experiment	Number of drones
			1				2				3				4
			ds visits	TD (km)	UTC (km)	ETC (km)	ds visits	TD (km)	UTC (km)	ETC (km)	ds visits	TD (km)	UTC (km)	ETC (km)	ds visits	TD (km)	UTC (km)	ETC (km)
1	10	1	1	28.488	3.852	17.659	0	30.168	0.000	19.832	0	33.458	0.000	41.542	0	35.327	0.000	64.673
2		2	6	123.331	41.992	9.677	6	123.637	56.935	19.428	4	124.744	40.579	9.677	3	125.059	30.514	19.428
3		3	6	117.799	48.188	9.013	6	118.420	63.515	18.065	4	118.072	47.915	9.013	2	113.940	17.995	18.065
4		4	5	102.207	38.514	9.279	5	102.773	62.948	9.279	3	102.522	28.265	19.212	2	101.814	28.974	19.212
5		5	0	18.707	0.000	6.293	0	25.115	0.000	24.885	0	24.067	0.000	50.933	0	25.813	0.000	74.187
6	30	1	14	281.923	83.903	9.174	14	284.881	105.946	9.174	13	282.473	87.828	29.699	12	284.509	96.540	18.951
7		2	15	297.504	92.909	9.587	14	302.929	77.874	19.197	13	304.742	85.671	9.587	12	299.402	71.556	29.042
8		3	15	304.512	86.401	9.087	15	309.891	96.924	18.185	13	304.049	68.074	27.877	13	305.442	101.372	18.185
9		4	15	312.298	78.246	9.457	14	317.283	63.710	19.007	13	316.405	74.138	9.457	12	314.047	57.837	28.117
10		5	16	303.026	112.842	9.132	16	308.355	132.513	9.132	14	305.558	100.276	19.167	14	309.380	121.453	19.167
11	60	1	29	569.741	170.708	9.551	28	556.624	174.425	18.951	28	555.103	200.946	18.951	27	564.433	182.042	28.525
12		2	29	554.188	186.693	9.119	28	552.358	179.063	18.579	27	553.237	178.183	18.579	27	565.327	181.491	28.183
13		3	31	589.558	201.378	9.064	29	580.997	184.939	9.064	30	583.958	213.767	27.275	28	595.473	167.732	36.795
14		4	31	583.403	206.898	9.699	30	587.054	203.247	9.699	29	585.800	194.653	19.547	28	585.419	195.034	19.547
15		5	28	543.666	171.960	9.374	27	545.155	170.472	9.374	25	543.122	147.505	9.374	24	542.053	148.574	9.374
16	75	1	38	713.682	252.196	9.122	37	716.288	240.294	18.418	35	710.949	211.247	27.803	35	716.785	230.411	27.803
17		2	36	691.126	224.854	9.020	35	691.652	224.328	9.020	35	702.840	238.140	9.020	34	705.669	226.200	18.131
18		3	36	701.452	214.318	9.230	36	706.686	224.822	18.492	36	710.283	246.225	18.492	34	701.536	229.972	18.492
19		4	39	743.607	247.111	9.282	38	738.727	252.034	9.239	37	737.717	243.761	18.521	36	735.697	245.476	18.826
20		5	42	786.773	279.211	9.016	42	789.969	301.015	9.016	40	790.566	266.397	18.037	39	790.623	266.340	18.037
21	100	1	52	959.765	356.204	9.031	51	954.574	352.255	18.172	50	957.003	340.676	27.320	50	956.904	365.776	27.320
22		2	45	882.798	258.195	9.007	44	879.228	252.723	18.050	42	888.005	209.758	27.237	42	879.684	243.079	27.237
23		3	52	985.840	330.100	9.060	51	987.162	319.696	18.142	51	994.231	346.709	9.060	49	994.126	294.226	36.649
24		4	46	922.266	243.638	9.096	45	923.209	242.695	9.096	44	927.215	220.292	27.493	44	935.733	236.774	27.493
25		5	51	959.235	331.555	9.211	50	963.648	317.893	18.459	49	967.873	304.395	27.732	49	969.106	328.162	27.732
26	130	1	30	683.680	90.507	0.813	30	684.409	108.442	7.149	30	694.303	116.856	13.841	28	694.281	91.878	13.841
27		2	37	799.876	143.038	7.086	36	801.980	140.934	7.086	35	798.837	136.421	14.742	36	810.832	166.051	23.117
28		3	50	1070.405	197.581	7.014	49	1074.216	186.638	14.146	49	1092.854	193.001	14.146	49	1095.997	200.206	28.797
29		4	37	824.525	124.062	1.413	37	846.229	113.721	15.050	36	836.615	123.962	14.423	37	860.305	136.314	28.382
30		5	46	1104.845	69.333	0.822	45	1102.538	71.640	0.822	45	1133.520	63.094	3.387	45	1149.567	74.213	1.220
31	180	1	50	1096.125	167.496	11.380	50	1088.493	188.733	22.774	49	1107.794	180.757	11.449	49	1117.392	183.021	24.587
32		2	46	1029.525	134.184	11.291	45	1006.796	145.612	22.593	45	1035.865	141.542	22.593	45	1046.467	155.941	22.593
33		3	55	1202.207	186.581	11.213	55	1215.214	187.354	22.432	55	1211.729	212.392	25.880	54	1211.212	193.910	44.878
34		4	44	993.455	120.360	11.185	44	995.511	143.303	11.185	43	999.015	127.371	23.614	43	984.534	155.151	35.315
35		5	40	921.524	92.327	11.149	40	933.828	104.391	11.781	40	927.160	125.520	22.320	39	942.500	116.266	16.234
36	245	1	67	1461.428	227.666	10.906	65	1458.237	194.940	21.824	64	1453.315	188.940	32.744	64	1467.727	188.605	43.668
37		2	70	1498.309	265.892	10.800	69	1509.798	243.596	21.606	69	1533.978	233.595	32.427	66	1470.561	256.088	23.351
38		3	64	1406.683	207.603	10.714	67	1437.612	265.951	21.437	66	1431.766	261.061	32.173	65	1450.584	242.259	32.157
39		4	66	1475.828	188.537	10.634	66	1464.416	214.288	21.296	65	1471.073	205.009	23.918	64	1476.681	199.340	23.979
40		5	53	1140.828	197.738	11.433	52	1156.338	170.793	22.869	50	1146.470	155.661	22.869	49	1141.803	152.281	30.916
41	280	1	73	1607.988	232.978	9.034	74	1610.841	270.964	18.195	73	1645.871	235.915	18.214	73	1614.368	283.203	27.429
42		2	74	1638.081	227.284	9.635	74	1657.423	231.723	10.853	74	1665.069	249.078	10.853	72	1659.046	220.510	20.444
43		3	77	1693.593	246.975	9.432	74	1671.541	218.076	10.383	76	1679.159	276.915	18.926	74	1689.979	231.981	28.040
44		4	82	1763.002	303.972	8.026	78	1725.478	258.183	16.339	80	1767.243	283.062	24.696	77	1747.821	257.391	19.788
45		5	81	1759.991	281.969	8.040	80	1720.884	321.076	8.040	78	1751.016	257.823	16.161	78	1736.080	305.880	8.040
46	295	1	77	1666.534	274.442	9.024	77	1689.042	276.259	9.699	76	1679.911	267.611	27.477	75	1697.932	248.625	28.442
47		2	81	1724.851	316.143	9.006	78	1705.018	276.546	18.435	79	1728.721	303.167	18.112	76	1702.319	270.139	27.542
48		3	83	1781.772	309.209	9.019	85	1815.168	350.813	9.019	81	1781.502	290.905	27.592	82	1805.698	316.576	27.726
49		4	81	1743.335	297.646	9.019	80	1765.807	266.099	18.094	79	1760.982	270.924	18.094	76	1745.930	216.846	37.224
50		5	76	1696.807	219.086	9.107	77	1705.089	251.815	18.096	77	1710.942	270.728	18.330	76	1700.429	272.218	27.353
51	315	1	83	1809.735	285.172	5.093	82	1805.978	283.677	10.345	82	1818.972	300.935	5.093	80	1803.313	275.460	21.227
52		2	91	1983.244	311.726	5.030	92	1986.444	358.526	5.030	91	2011.573	323.034	15.393	90	2000.426	334.181	15.393
53		3	95	2064.316	330.650	5.035	94	2058.859	336.106	5.035	94	2074.783	334.815	15.402	94	2079.041	350.338	20.621
54		4	85	1832.457	308.496	9.048	83	1837.232	269.246	18.522	84	1869.660	294.345	10.995	83	1853.744	291.339	29.918
55		5	89	1885.659	355.235	9.105	88	1910.129	330.766	9.105	88	1901.892	345.531	27.578	85	1875.457	321.966	27.578

Note: S. no. = Serial number; TD = total distance; UTC = unutilized travel capacity; ETC = excess travel capacity; ds = docking station.

Figure 2.

Numbers of visits to the docking station (ds), unutilized travel capacity (UTC), and excess travel capacity (ETC) for one to four drones for: (a) 10-service size, (b) 30-service size, (c) 60-service size, (d) 75-service size, (e) 100-service size, (f) 130-service size, (g) 180-service size, (h) 245-service size, (i) 280-service size, (j) 295-service size, and (k) 315-service size.

Increasing the drone capacity will minimize the ds visits and maximize timely deliveries to customers. However, investing in more drones will increase the idle time and non-utilization cost. To balance this scenario, organizations need to select an appropriate number of drones based on service sizes. For example, in Figure 2, a to k , ETC increases whenever the number of drones increases. ETC is an extra mileage that a drone ends up traveling to the ds after completing the scheduled services. If the drone service provider increases the number of drones without analyzing the service sizes, this will evidently increase the ETC mileage, which will increase the cost of asset non-utilization. Meantime, if the drone service provider deploys the least number of drones, this will lead to missing potential customers and maximizing tardy deliveries because of increases in ds visits. These ds visits pile up waste mileage, the UTC. To minimize UTC, drone service providers should increase the number of drones to minimize the ds visits but increase the ETC. The appropriate balance between the UTC and ETC is the most vital information for drone service providers to decide the number of drones required for the hyperlocal market delivery.

This paper has conducted a trade-off analysis between the metrics UTC and ETC for selecting the number of drones necessitated by service sizes. When the number of drones increases, this will cause the ETC to surge while pushing down the UTC. In Figure 2, a to k , an arrow indicates the trade-off balance point between the UTC and ETC. At this point, both UTC and ETC are balanced against each other with a minimum mileage difference. For example, in Figure 2a, when the number of drones increases to attempt the 10-service size, the UTC drops down and ETC gradually increases. In between two drones and three drones, UTC and ETC cross each other. This point is a balancing point between the number of drones and the number of services.

This provides insights for drone service providers to decide the required number of drones for 10-service sizes in a range between two and three drones. Here two important scenarios exist: if the drone service provider selects two drones, the UTC is 36.68 km, and ETC is 18. 30 km, and the difference is 18.38 km; for the three-drone scenario, UTC is 23.35 km and ETC is 26.08 km, and the difference is 2.73 km. This shows that the three-drone solution has a smaller difference than the two-drone. If the drone service provider selects three drones for the 10-service size, that will minimize the wasted mileage (down from 18.30 km to 2.73 km) and also minimize the ds visits, down from 3.4 (approximately 3) to 2.2 times (approximately 2). This reduces the drone idle time and increases drone utilization. At the same time, comparing the TD (in kilometers) between two drones (80.02 km) and three drones (80.57 km) reveals a marginal difference of 0.55 km. If the drone service providers select two drones, that will increase the ds visits and cause tardy deliveries.

Figure 2j shows the results of the 295-service size, for which the balance point between the UTC and ETC falls accurately on three drones. The recommendation is that it is very appropriate for 295-service sizes to have at least three drones to satisfy all customer requests. There are certainly other scenarios in Figure 2f (130-service size), 2g (180-service size), and 2i (280-service size). In Figure 2f, the single drone visited ds 40 times to complete all 130 service requests, so its UTC is 124.90 km, and ETC is 3.43 km. ETC is very minimal because there is only one drone to complete all services, and it maximizes the drone utilization. But completing all 130 services with a single drone is not feasible because service delay will be higher in this case. If two drones are applied for the same 130-service size, the UTC is 124.28 km and has a very marginal difference of 0.62 km. This least marginal difference causes the early balance point between the UTC and ETC, as shown in Figure 2, f , and i , indicated by a dashed arrow.Figure 2i also indicates the same results, for the single-drone UTC is 258.64 km, and ds is visited 77.4 times (approximately 77), and the ETC is only 8.83 km. The two-drone scenario has UTC 260 km, and ds is visited 76 times to complete the 280 services, and the ETC is 12.76 km. The UTC difference between the one-drone and two-drone scenarios is very small, but the ETC is gradually increasing because of the increase in number of drones. This early crossing point is not considered for selecting a drone because there is no change in UTC between the drones. Further, the same trade-off analysis is carried out for all service sizes and a recommendation made for selecting the number of drones based on the number of services.

The results of trade-off analysis between the ds visits, UTC, and ETC are reported in Table 6. According to the trade-off analysis, each service size has a drone range. Service size 10, 30, 75, 100, and 245 require a range of two drones to three drones to satisfy the customer’s request. Service size 130, 180, 280, and 315 require three to four drones to satisfy the service requests by customers. Service size 60 and 295 require three drones to appropriately complete the scheduled services. Based on the minimum difference analysis between UTC and ETC it is possible to define the appropriate drone selection for the listed service sizes. From the results, the single drone is not selected for any service size because of more ds visits and increased UTC. Single-drone service is not feasible in a practical scenario to attempt a huge number of customer requests. Two drones come under the range of service size 30, 75, 100, and 245, but by comparing the distance trade-off between the UTC and ETC two drones are not selected for any of the services. Finally, three drones are selected for the service size 10, 30, 60, 75, 100, 130, 245, and 295, and remaining service sizes are allocated four drones. Suppose the company focuses on the delivery perspective to satisfy the customer’s request without any delay. In that case, it should have more drones, increasing the idle time and non-utilization of drones. The proposed trade-off analysis has balanced these two parameters to select an appropriate number of drones based on service size. The service sizes depend on three categories of distances as discussed in the third section of the paper (“Multi-Drone Routing Problem for Hyperlocal Delivery”). Sequencing the service distances to minimize the total travel distance by the drones is a predominant objective of the paper. The objective is to allocate all services with nil visits to ds. However, the DTC is limited and ds visits for recharge are inevitable. So, minimizing the ds visits and maximizing the service density is a mandate for any drone service providers to improve the delivery and operational efficiency. The proposed algorithm is constructed to address this objective by efficiently sequencing the services, which minimizes the TD, as shown in Table 5.

Table 6.

Selection of Number of Drones Based on Service Sizes

		Drone range
S. no.	Service size	1	2	3	4	Number of drones selected
1	10		x	x		3
2	30		x	x		3
3	60			x		3
4	75		x	x		3
5	100		x	x		3
6	130			x	x	3
7	180			x	x	4
8	245		x	x		3
9	280			x	x	4
10	295			x		3
11	315			x	x	4

Note: S. no. = Serial number.

The two-factorial experiment is designed to compare the mean effects for all categories of drones (i.e., one, two, three, and four drones) based on 11 service sizes. The two factors are the number of drones and the service size. The number of levels of the factor “Number of drones” is 4 and that for “Service size” is 11, with five replications and at the significance level α = 0.05. The result is shown in Table 7.

Table. 7.

ANOVA for Experiment

Source	Sum of squares	df	Mean sum of squares	F	Sig.
Corrected model	72468880.620	43	1685322.805	203.622	.000
Intercept	233409831.593	1	233409831.593	28200.724	.000
Service size	72462580.372	10	7246258.037	875.497	.000
Number of drones	2080.126	3	693.375	.084	.969
Service size × number of drones	4220.122	30	140.671	.017	1.000
Error	1456704.821	176	8276.732	na	na
Total	307335417.034	220	na	na	na
Corrected total	73925585.442	219	na	na	na

Note: ANOVA = analysis of variance; sig. = significance; na = not applicable.

According to the two-factorial ANOVA (analysis of variance), factor one is service size, where the significance value is 0.000 and is less than the corresponding significance level α = 0.05. Therefore it is proved that there is a significant difference between the service sizes. Factor two is the number of drones, and the significance value is 0.969, greater than the significance level α = 0.05, so there is no significant difference between the number of drones. This result supports selecting any number of drones to complete the scheduled services, with no large difference in TD coverage. This result provides a valuable argument that increasing the number of drones will not affect the TD coverage but will minimize tardy delivery. For example, in Table 5 service 10.2 has a TD of 123.33 km to complete all 10 services by single drone, while two drones completed them in 123.63 km, three drones completed in 124.74 km, and four drones completed in 125.05 km. We can witness that there is no significant difference in TD covered to complete all 10 services by increasing the number of drones. This scenario exists for all 55 services as shown in Figure 3.

Figure 3.

Total distance of all 55 services.

However, partial distance coverage of each drone, as shown in Table 8, which shares the services with more drones, leads to minimum distance coverage of each drone and completes the services in a short lead time. For example, Table 8 represents the result of the 10.2 service size for all drones. By observing the single drone, TD is 123.33 km with six visits to ds required. In the two-drone scenario, the load of services is shared between the drones. The first drone attempts the services in a sequence of ds →10p → 10d → 4p → 4d → ds → 6p → 6d → ds → 3p → 3d → ds → 5p → 5d → ds, with three ds visits, and its partial distance coverage is 58.63 km. The second drone’s service sequence is ds → 8p → 8d → 2p → 2d → ds → 9p → 9d → ds → 1p → 1d → ds → 7p → 7d → ds, with three ds visits by covering 65 km. Here the TD covered is the same, at 123.63 km (58.63 km + 65 km), but the individual drone coverage minimizes tardy deliveries by sharing the services. Increasing the number of drones reduces the ds visits (e.g., the three-drone scenario visits ds four times and the four-drone scenario visits ds only three times for battery recharge), which completes the scheduled services in a very short duration. These inferences provide a potential practical benefit for the drone service provider in the hyperlocal market to decide the number of drones according to the service sizes.

Table 8.

Drones Partial Distance Coverage

No. of drones	Route sequence	ds visits	Partial distance (km)	TD (km)
One drone	ds → 10p → 10d → 4p → 4d → 8p → 8d → ds → 6p → 6d → 2p → 2d → ds → 9p → 9d → ds → 3p → 3d → ds → 1p → 1d → ds → 5p → 5d → ds → 7p → 7d → ds	6	na	123.33
Two drones	ds → 10p → 10d → 4p → 4d → ds → 6p → 6d → ds → 3p → 3d → ds → 5p → 5d → ds	3	58.63	123.63
Two drones	ds → 8p → 8d → 2p → 2d → ds → 9p → 9d → ds → 1p → 1d → ds → 7p → 7d → ds	3	65.00	123.63
Three drones	ds→ 10p → 10d → 6p → 6d → ds → 1p → 1d → ds	1	35.92	124.74
	ds → 8p → 8d → 2p → 2d → ds → 9p → 9d → ds → 7p → 7d → ds	2	50.27
	ds → 4p → 4d → 3p → 3d → ds → 5p → 5d → ds	1	38.55
Four drones	ds → 10p → 10d → 2p → 2d → ds → 5p → 5d → ds	1	36.72	125.05
	ds → 8p → 8d → 9p → 9d → ds → 7p → 7d → ds	1	37.13
	ds → 4p → 4d → 3p → 3d → ds	0	23.31
	ds → 6p → 6d → ds → 1p → 1d → ds	1	27.89

Note: no. = number; TD = total distance; ds = docking station; p = pickup point; d = delivery point; na = not applicable. The table represents service size 10.2 shown in Table 5.

Conclusion

To overcome the environmental concerns in large cities, the last-mile delivery service providers are looking for an alternative mode of transport. Drones are electric flying robots that can overcome this issue to satisfy the on-demand customers in congested urban regions. In this paper, the multi-drone pickup and delivery system for the hyperlocal market is proposed and framed as a MILP model. The objectives are to minimize the distance traveled by the drone to complete the scheduled services and select an appropriate number of drones for the service sizes based on trade-off analysis. The model avoids the need for ground vehicle support by enriching the flight endurance by introducing a docking station on a drone route and ensuring a drone safe-fly-and-return strategy. Local vendor and customer real-time locations are collected using an alphanumeric geocoding system to maintain location precision. The practical size instance is experimented with by a robust heuristic algorithm called the hyperlocal multi-drone neighbor search algorithm (H-MDNSH). The experiment is conducted by testing 11 service sizes ranging from 10 to 315 with various drones. A trade-off analysis reports an appropriate number of drones for different service sizes. This identification will significantly benefit the drone service provider wishing to select drones in the real-world scenario.

Further research has possible future directions. The paper has proposed a heuristic algorithm with the scope to develop a meta-heuristic to obtain robust solutions which minimize the ds visits and reduce the UTC and ETC wasted capacity. The paper compares the effectiveness of more drones with fixed flight endurance (25 km) for different service sizes; additionally, researchers can experiment by increasing the flight endurance dynamically. Further, a customer time window with a service distance will be an added advantage and relevant for further research. There are some limitations to the paper. If the size of the customer request increases, the total travel distance and the number of drones required will also increase drastically for the large size problem. It is practically impossible to handle more ds visit requests by the multiple drones in a single docking station. So, it is required to implement multiple docking stations to meet customer demand promptly. Further, while collecting a real-time location of vendors, the restricted drone fly zones in Dehradun have not been considered in this study.

Footnotes

Author Contributions

The author confirms sole responsibility for the following: study conception and design, data collection, analysis and interpretation of results, and manuscript preparation.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Pachayappan

Sudhakar

A Solution to Drone Routing Problems Using Docking Stations for Pickup and Delivery Services. Transportation Research Record: Journal of the Transportation Research Board, 2021. 2675: 1056–1074.

Murray

C. C.

Chu

A. G.

The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-Assisted Parcel Delivery. Transportation Research Part C: Emerging Technologies, Vol. 54, 2015, pp. 86–109.

Carlsson

J. G.

Song

Coordinated Logistics with a Truck and a Drone. Management Science, Vol. 64, No. 9, 2018, pp. 4052–4069.

Moshref-Javadi

Hemmati

Winkenbach

A Truck and Drones Model for Last-Mile Delivery: A Mathematical Model and Heuristic Approach. Applied Mathematical Modelling, Vol. 80, 2020, pp. 290–318.

Sexton

T. R.

Bodin

L. D.

Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling. Transportation Science, Vol. 19, No. 4, 1985, pp. 378–410.

Arslan

A. M.

Agatz

Kroon

Zuidwijk

Crowdsourced Delivery—A Dynamic Pickup and Delivery Problem with Ad Hoc Drivers. Transportation Science, Vol. 53, No. 1, 2019, pp. 222–235.

Alwateer

Loke

S. W.

Fernando

Drones-as-a-Service: A Simulation-Based Analysis for On-Drone Decision-Making. Personal and Ubiquitous Computing, 2021, pp. 1–20. https://doi.org/10.1007/s00779-021-01524-5.

Besada

Campaña

Bergesio

Bernardos

de Miguel

Drone Flight Planning for Safe Urban Operations. Personal and Ubiquitous Computing, 2020, pp. 1–20. https://doi.org/10.1007/s00779-019-01353-7.

Sundar

Rathinam

Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots. IEEE Transactions on Automation Science and Engineering, Vol. 11, No. 1, 2013, pp. 287–294.

10.

Zhang

Campbell

J. F.

Sweeney

D. C.

II. Hupman

A. C.

Energy Consumption Models for Delivery Drones: A Comparison and Assessment. Transportation Research Part D: Transport and Environment, Vol. 90, 2021, p. 102668.

11.

Dukkanci

Kara

B. Y.

Bektaş

Minimizing Energy and Cost in Range-Limited Drone Deliveries with Speed Optimization. Transportation Research Part C: Emerging Technologies, Vol. 125, 2021, p. 102985.

12.

Cheng

Adulyasak

Rousseau

L. M.

Drone Routing with Energy Function: Formulation and Exact Algorithm. Transportation Research Part B: Methodological, Vol. 139, 2020, pp. 364–387.

13.

Kirschstein

Comparison of Energy Demands of Drone-Based and Ground-Based Parcel Delivery Services. Transportation Research Part D: Transport and Environment, Vol. 78, 2020, p. 102209.

14.

Jeong

H. Y.

Song

B. D.

Lee

Truck-Drone Hybrid Delivery Routing: Payload-Energy Dependency and No-Fly Zones. International Journal of Production Economics, Vol. 214, 2019, pp. 220–233.

15.

Nguyen

M. A.

Dang

G. T. H.

Hà

M. H.

Pham

M. T.

The Min-Cost Parallel Drone Scheduling Vehicle Routing Problem. European Journal of Operational Research, Vol. 299, No. 3, 2022, pp. 910–930.

16.

Cavani

Iori

Roberti

Exact Methods for the Traveling Salesman Problem with Multiple Drones. Transportation Research Part C: Emerging Technologies, Vol. 130, 2021, p. 103280.

17.

Otto

Agatz

Campbell

Golden

Pesch

Optimization Approaches for Civil Applications of Unmanned Aerial Vehicles (UAVs) or Aerial Drones: A Survey. Networks, Vol. 72, No. 4, 2018, pp. 411–458.

18.

Ghelichi

Gentili

Mirchandani

P. B.

Logistics for a Fleet of Drones for Medical Item Delivery: A Case Study for Louisville, KY. Computers & Operations Research, Vol. 135, 2021, p. 105443.

19.

Cokyasar

Optimization of Battery Swapping Infrastructure for E-Commerce Drone Delivery. Computer Communications, Vol. 168, 2021, pp. 146–154.

20.

Luo

Liu

Shi

A Two-Echelon Cooperated Routing Problem for a Ground Vehicle and Its Carried Unmanned Aerial Vehicle. Sensors, Vol. 17, No. 5, 2017, p. 1144.

21.

Salama

Srinivas

Joint Optimization of Customer Location Clustering and Drone-Based Routing for Last-Mile Deliveries. Transportation Research Part C: Emerging Technologies, Vol. 114, 2020, pp. 620–642.

22.

Palmer

Amazon Wins FAA Approval for Prime Air Drone Delivery Fleet. CNBC, August31, 2020.

23.

Bryan

Drone Delivery: DHL “Parcelcopter” Flies to German Isle. Reuters, September24, 2014.

24.

Savelsbergh

M. W.

Sol

The General Pickup and Delivery Problem. Transportation Science, Vol. 29, No. 1, 1995, pp. 17–29.

25.

Shaw

A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. APES Group, Department of Computer Science, University of Strathclyde, Glasgow, Scotland, 1997, p. 46.

26.

Mladenović

Hansen

Variable Neighborhood Search. Computers & Operations Research, Vol. 24, No. 11, 1997, pp. 1097–1100.

27.

Ropke

Pisinger

An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, Vol. 40, No. 4, 2006, pp. 455–472.