A Development of Optimal Algorithm for Integrated Operation of UGVs and UAVs for Goods Delivery at Tourist Destinations

Abstract

Although the actual use of delivery robots like UGVs and UAVs has not yet been generalized, they are also used for additional purposes like fun and enjoyment in some limited areas such as tourist destinations. In this study, an optimal algorithm is proposed that operates a delivery service through an integrated system of UGVs and UAVs at certain tourism destination. It is assumed that both UGVs and UAVs or only one means could be used depending on the type of goods delivered and the topographical characteristics. The mathematical model-based optimization technique is applied to generate the delivery service route of both UGVs and UAVs that can maximize total customer satisfaction. The developed mathematical model is solved through CPLEX and genetic algorithm, and the results are compared by dividing into case 1 in which UAVs move freely and case 2 in which UAVs can move only in a limited path since there is a risk of accidental falling when moving. As a result, when UAVs move freely, the total customer satisfaction is higher while the total complete time increases. However, it is suggested that an appropriate operation policy should be determined considering the risk of accidental falling.

1. Introduction

As the COVID-19 pandemic ends, economies around the world tend to recover. In addition, a lot of labor is required in various industries again due to social distancing is abolished. However, during the COVID-19 pandemic, people have already found employment in industries that are not affected by it, and they are still working in those fields. Therefore, lots of industries that require new labor are experiencing a labor shortage [1]. Recently, there are efforts to solve this problem of labor shortage by using robots. There have been attempts in the past to use robots for tasks that are difficult or dangerous for humans to do, but now people are trying to use robots because people hate simple labor and the labor force itself is insufficient [2]. As a result, various types of robots such as assembly robots, guide robots and logistics robots are actually being used in industrial fields and people also take it for granted that robots are used in everyday life without any objection [3].

Among them, the logistics field is one of the representative industrial fields in which various types of robots are used. Fundamentally, the operations of loading and unloading, moving heavy goods or transporting goods from one place to another are performed usually in the logistics industry. Therefore, people traditionally manipulated mechanical devices to perform those tasks instead of directly doing them. Nowadays, logistics robots are performing various types of logistics tasks using pre-programmed or artificial intelligence without human operators [4]. Logistics giants such as Amazon are known to use robots to transport rack itself or to storage or retrieval items from racks in the warehouse, and Samsung Electronics’ semiconductor factories also apply unmanned ground vehicles (UGVs) to transport work-in-process inventories within factories.

As social distancing has become routine due to the COVID-19 pandemic, people have been unable to visit restaurants to eat but order their food by using food delivery applications. In the meantime, many people who have lost their jobs have entered the food delivery business, but as the demand for non-face-to-face food delivery increases, many attempts are being made to utilize delivery robots. The use of UGVs or unmanned aerial vehicles (UAVs) is generally considered as a candidate for delivery robots, and UGVs have already been recognized for their utility as logistics robots [5]. In the case of UGVs, many applications and success cases have been reported for transport in a closed environment, but lots of studies for practical use are being conducted because of the high complexity of using them as a delivery robot in an open environment. In the case of UAVs, they are free to several problems that recognizing the obstacles and so on because they can move through the sky. However, more efforts are needed for practical use because they can endanger people or objects on the ground due to the possibility of the accidental fall of transported object or the UAVs themselves. Nevertheless, since the advantages of delivery robots using UGVs and UAVs are clear, many studies are being conducted for practical use, and lots of companies are actually making various attempts [6].

There are still limitations to providing a satisfied customer service through robots as well as delivery robots. However, in the tourism field, a service using robots is being presented on a trial basis due to the additional purposes such as fun and enjoyment. Recently, guide robots that can provide airport usage information to tourists are easily found at airports in many countries, and hotels often use delivery robots for customer service, such as room service [3]. In particular, the customer can have a special experience through the services providing by robots. Therefore, the ‘Henn-na Hotel’ in Japan proposed a check-in service and luggage storage service using robots even though the service itself is a little bit incomplete as shown at Figure 1 [7]. Currently, there may be some possible problems in active introduction of service robots because there is still a limit to provide services through it, but robots can be considered as an alternative to solve the fundamental problem of the tourism sector such as the labor shortage.

In this study, considering this situation, it is tried to develop an optimal algorithm for an integration system of both UGVs and UAVs to provide delivery services at certain tourist destinations such as beaches or riverside parks. The objective of proposed optimal algorithm is to maximize the satisfaction of tourists because the purpose of providing such a service in tourist destinations is to give a fun and enjoyment to tourists rather than economic profit so far. It is assumed that UGVs can move on a fixed ground route while there are no restrictions on the goods that can be transported, but certain delivery points are not accessible due to the topographical characteristics. In addition, it is assumed that UAVs have restrictions on the goods that can be transported, while it can move freely and fast in the sky. However, there are two operation scenarios that case 1 in which UAVs move freely and case 2 in which UAVs can move only in a limited path since there is a risk of accidental falling when moving. Under such circumstances, this study intends to derive an optimal operation route of each UGV and UAV per unit time while there are limited number of UGVs and UAVs through a mathematical model-based optimization technique.

This paper is organized as follows. In Section 2, the literature review is prepared by previous related studies to confirm the contribution of this study. In Section 3, the problem description, assumptions, and notations are presented to develop a mathematical model and the mathematical model is proposed to maximize the satisfaction of tourists by derive an optimal operation route of both UGVs and UAVs per unit time. The solution procedure for proposed mathematical model is explained in Section 4 while the numerical experiments are introduced by dividing into two cases according to the operation of UAVs to verify the proposed optimal algorithm in Section 5. Lastly, the conclusion part is presented with the findings and insights of this study in Section 6.

2. Literature Review

UAVs are being used for many different purposes in a variety of industries like military, transportation, communications, and so on. As the use of UAVs has become common throughout the industry, research on the efficient operation of UAVs has been actively conducted. Song and Ko [8] dealt with the situation where UAVs are introduced and used for recreation and safety purposes at certain sightseeing places. They designed overall UAVs system and decided the number of required UAVs and depots to minimize total in-vestment cost. In a follow-up study, Ko and Song [9] addressed the system design and operation of UAVs in the tourism industry. They assumed that various types of UAVs are used for patrolling and monitoring purpose. UAVs, which are higher cost to purchase, have long operating times and fast movement speed. They proposed a mathematical model that can minimize the sum of total travel distance and purchase cost of the required UAVs. Sundar and Rathinam [10] studied UAV routing problem to minimize fuel consumption with the fuel constraint. There were several depots to refuel and targets to visit. They developed an approximation algorithm to find the possible path to visit all targets without violating the fuel constraints and compared the results with the optimal solution through CPLEX. Song et al. [11] focused on UAVs being used in the delivery industry. UAVs have distinctive characteristics from other means of transportation used for delivery such as limited flight time, loadable capacity and so on. They developed a delivery scheduling model that can maximize the sum of the weights of the total number of deliveries and the traveled distance by considering the characteristics of UAVs. UAVs are often used in areas that are difficult for humans to access or for tasks that are hard for humans to perform. Chen et al. [12] proposed damage degree evaluation model and developed image analysis method in earthquake area using images of ground targets captured by UAVs. UAVs are also used for surveying purposes in the civil engineering industry. Conventional surveying techniques have disadvantages that are time consuming and can be dangerous to operators. Siebert and Teizer [13] proposed photogrammetric surveying system using UAVs and measured the performance by comparing with the results using the conventional surveying method. Gul and Erkmen [14] studied the problem of data collection by mobile sinks of UAVs with limited battery capacity in a robot network divided into several robot clusters. The main contribution of this study was a development of genetic algorithm called Multi Shortest Path Data Forwarding Strategy (MSPDFS) that uses minimal energy for data forwarding. Numerical results showed that the proposed algorithm was more effective than the approaches in the previous literature. Gul et al. [15] presented the pathways of UAVs for energy-aware data collection in robot network clusters. To find the optimal strategy for UAVs, an algorithm called Quality and Energy-Aware Data Collection Strategy (QEADCS) was developed. The proposed algorithm reduced energy consumption by up to 50% compared to the previous approach.

UAVs are sometimes used alone, but they can be used for more purposes when working with other devices like CCTV (Closed-Circuit Television), UGV (Unmanned Ground Vehicle), UMV (Unmanned Marine Vehicle) and so on. Ko and Song [16] derived the optimal location of CCTVs and operation schedule of UAVs when CCTV and UAVs cooperate to monitor major tourist spots. They considered budget, service range of CCTV, security requirements as constraints with maximizing the total sum of priority of the monitored spots. Compared to UGVs, UAVs have the advantage of being able to access hard-to-reach places on land. Several studies have been conducted to collaborate with UGVs by utilizing this advantage of UAVs. Akhloufi et al. [17] investigated previous studies of the use of UAVs in wildfires and suggested cooperative autonomous systems for wildland firefighting using both UAVs and UGVs. In this case, UGVs are used to transport small UAVs to fire areas and as refueling stations. Asadi et al. [18] proposed the system to collect data autonomously using UAVs and UGVs together at a construction site. Since the UGVs have a problem in that it is difficult to move in places with many obstacles, in this case, the UAVs can be used to scan the point of interest. They tested the proposed system in an indoor environment with obstacles like reality and evaluated the performance. Li et al. [19] developed an efficient route planning to build ground maps using UAVs and UGVs cooperatively. They collected the ground information and then suggested route planning algorithms to minimize the total travel distance of vehicles. Stolfi et al. [20] designed surveillance system using UAVs, UGVs and UMVs simultaneously to find someone trying to escape from a restricted area early. The proposed model was verified through a case study, and as a result, it showed better performance in terms of early detection and detection area compared to the existing model.

Several studies have been conducted to design the optimal route when UAVs, vehicles, or UGVs is simultaneously put into the delivery business. Chiang et al. [21] established the optimal routing plan when using drones in the existing vehicle-only delivery system with minimizing total CO₂ emissions as well as delivery costs of both vehicles and UAVs. They used genetic algorithms to solve the presented problems and experimental results showed that using UAVs for delivery is more effective in terms of both cost saving and CO₂ emission reduction. Gu et al. [22] dealt with the instant delivery by combining vehicles and UAVs. It is assumed that a vehicle carrying a multiple UAVs operates at multiple stop points, and the UAV performs a single delivery at each stop point. They decided the location and the number of vehicles stops, and delivery routing of each vehicle and UAV with minimizing the number of vehicles put into delivery and total travel time. Deng et al. [23] is similar to [22], except that the UAV covers multiple deliveries. In addition, they considered the change in energy consumption according to the payload of the UAV and developed hybrid heuristic algorithm with minimizing total service time including delivery and operation time. Li et al. [24] dealt with vehicle-UAV routing problem of delivery services considering traffic restrictions. When a vehicle equipped with a UAV starts from a warehouse and operates a delivery route, it is assumed that a UAV is used for delivery to a place where the vehicle cannot enter due to traffic restrictions such as vehicle-type restriction and half-side traffic. They found the optimal routing plan for each vehicle and UAV with minimizing total cost and energy consumption. Genetic algorithm was used to solve the presented problem and proposed model was evaluated through experimental analysis. Murray and Chu [25] established an optimal operation plan that can minimize the service time so that the delivery means returns to the point of departure as quickly as possible when parcels are delivered by trucks and UAVs. In previous studies, it was common for UAVs to depart from ground vehicles after being loaded onto them. However, their study differs in that it also deals with cases where parcels are delivered by UAVs directly from the distribution center to customers. Ropero et al. [26] considered a scenario in which UAVs and UGVs collaborate to explore the planetary surface. In general, UAVs have an energy constraint, but they have the advantage of being able to reach the target points that UGVs cannot. Based on these general characteristics of UGVs and UAVS, they proposed a UGV-UAV hybrid system that utilizes UGVs as a moving charging station for UAVs and UAVs as a means to reach a target point.

Studies on UGVs and orienteering problem (OP) have also been continuously studied. Shi and Zhang [27] studied the output-feedback path following controller to reduce the computational load for path following control of UGVs. For this, a learning-based least squares support vector machine (LS-SVM) model was used. The experimental results validated the effectiveness of the proposed control strategy. Ju et al. [28] investigated the attack/anomaly detection and resilience strategy of connected and automated vehicles (CAVs). Attack/anomaly on the perception sensor and communication channel causes safety issues in CAVs. The results according to the positions where the attack/abnormality occurred were analyzed. Vansteenwegen et al. [29] addressed the OP on a set of vertices each with a score. The goal of OP is to visit some vertices and determine a path, limited in length, that maximizes the sum of the collected scores. For this, previous studies on the orienteering problem and its application were reviewed.

Recently, research on the integrated operation of UGVs and UAVs has been in the spotlight and is a subject that is being continuously studied. In addition, most of the research is focused on the operation scheduling or the establishment of the system with the objective of minimizing total investment cost. However, the purpose of this study is to maximize the satisfaction of tourists by providing a delivery service through UGVs and UAVs in specific tourist destinations, while offering differentiated satisfaction according to the delivery means to tourists. In addition, both types of delivery means are assumed to transport either single delivery and multiple deliveries by applying that there are capacity restrictions in terms of weight and volume for goods carried by UGVs and UAVs. Moreover, for the safety of tourists, the case where the UAVs freely move in the sky and the case where the UAVs fly in a detour using the outskirts of the tourist destination are investigated together by assuming the accidental falling of both the objects carried by UAVs and the UAV itself. Through two cases of numerical experiments, the relationship between total customer satisfaction and total completion time for orders is analyzed. This study is expected to provide insights when designing integrated goods delivery systems using UGVs and UAVs in tourist destinations.

3. Model Development

3.1. Problem Description

In the summer of 2022, a food delivery pilot service using UAVs started at Mangsang Beach in the East Sea of Korea. This beach is inconvenient for tourists who use the beach because the shopping area is several kilometers apart from the beach. Therefore, it starts to connect tourists from shopping areas to beaches through UAVs-based food delivery services. Although there were occasional errors because it was a pilot service, tourists were amazed and enjoyed the advanced delivery system using UAVs [30].

In this study, it is tried to develop an optimal algorithm of the integrated operation for the last-mile delivery service using both UGVs and UAVs in tourist destinations with the objective of maximizing the satisfaction of tourists by reflecting the situation of providing pilot delivery service using UGVs or UAVs for tourists. To understand the problem situation easily, a hypothetical beach as shown in Figure 2 is introduced as a potential tourist destination. Since last mile delivery is considered in this study, it is assumed that goods ordered by tourists on the beach arrive at the depot first from the outside area and then are delivered using UGVs and UAVs. In addition, a certain number of UGVs and UAVs are prepared in the depot, and in the case of UGVs, there are areas that are inaccessible due to topographical reasons (the nodes represented by gray squares in Figure 2), therefore, delivery service is only possible with UAVs in these areas. However, it is assumed that UAVs move in two cases: case 1 where the UAVs move freely in the sky to the target node, and case 2 where the UAVs move outline of the beach to prevent damage from an accidental falling of either the transported goods or the UAV itself. In case 2, UAVs can only provide delivery service to some nodes along the gray path in Figure 2. The goods arriving at the depot are collected for a certain period and delivered to the destination node through UGVs and UAVs, and during that period, UGVs and UAVs can visit the depot multiple times and deliver multiple times. The goods requested for delivery can be broadly classified into food and general item, and each delivery order has a certain weight and volume. Because UGVs and UAVs have capacity limitations in terms of weight and volume, single delivery or multiple delivery is possible, taking into account the weight and volume of each delivery order. Since this integrated delivery system is operated for fun and enjoyment for tourists in a certain tourist destination, it is assumed that customer satisfaction varies depending on the means of delivery (UGVs or UAVs) and decreases depending on the delivery elapsed time. Lastly, UGVs providing these services generally have sufficient battery capacity to operate at period of time, and UAVs are operated in the form of battery replacement, maintenance time is assumed to be neglected in this study.

3.2. Notations

In this study, a mathematical model-based optimization technique is applied to derive the optimal delivery routes for both UGVs and UAVs. Therefore, some notations denoted the decision variables, parameters, indices, and index sets are defined as follows to develop the mathematical model.

Decision Variables
$y_{n,m}^{k,r}$	:	A binary decision variable with a value of 1 if the order r is assigned to a means of delivery k and it is delivered the mth sequence of the nth round, otherwise it has value of 0
$t^r$	:	A decision variable representing the delivery arrival time of order r [second]
$s_f^{k,r}$	:	A decision variable representing the customer satisfaction when an order r consisting of a type of goods f is assigned to a means of delivery k and delivered by it (0 ≤ $s_f^{k,r}$ ≤ 1)
$z^r$	:	A decision variable of customer satisfaction when order r is delivered (0 ≤ $z^r$ ≤ 1)
Parameters
$a_{f,d}^r$	:	A constant representing the order information with a value of 1 if order r which consists of type of goods f should be arrived at a node d, otherwise it has a value of 0
$g^r$	:	A constant representing the weight of the order r [kg]
$v^r$	:	A constant representing the volume of the order r [cm3]
$T$	:	A constant representing the time at which delivery of all orders should be finished [second]
$G^k$	:	A constant representing the limitation of weight capacity of the means of delivery k [kg]
$V^k$	:	A constant representing the limitation of volume capacity of the means of delivery k [cm3]
$t_{d,d^{\prime }}^k$	:	A constant representing the elapsed time when means of delivery k is moved from node d to node d′ [second]
$t_s^k$	:	A constant representing the service time to process an order r by means of delivery k other than elapsed time due to moving [second]
${\beta }_{1,f}^{k,r}$	:	A constant representing the fundamental customer satisfaction when an order r consisting of a type of goods f is assigned to a means of delivery k and delivered by it (0 ≤ ${\beta }_{1,f}^{k,r}$ ≤ 1)
${\beta }_{2,f}^{k,r}$	:	A constant representing the reduced customer satisfaction according to the elapsed time when an order r consisting of a type of goods f is assigned to a means of delivery k and delivered by it (0 ≤ ${\beta }_{2,f}^{k,r}$ ≤ 1) [/second]
$B$	:	A constant representing a very large number
Indices and index sets
$K$	:	A set representing the means of delivery k
$N$	:	A set representing the delivery round (=n) of a means of delivery, while a round is defined as the number of departure from depot
$M$	:	A set representing the delivery sequence (=m) of nth delivery round
$R$	:	A set representing the delivery order numbers (=r)
$F$	:	A set representing the type of goods to be delivered (f = 1:food, f = 2:general items)
$D$	:	A set of nodes (=d) representing the destination of the goods to be delivered

3.3. Mathematical Model

The purpose of developed mathematical model is to maximize the total customer satisfaction. It is assumed that customer satisfaction when order r is processed depends on what type of goods f the order is and what means of delivery k is assigned. In addition, it is further assumed that customer satisfaction decreases with the elapsed time of delivery. Therefore, the objective function can be modeled as Equation (1).

Maximize

$${\displaystyle \sum }_{r=1}^R{z}^r where z^r\le s_f^{k,r} \forall r,\forall f,\forall k$$

(1)

Subject to

$$s_f^{k,r}\le {\beta }_{1,f}^{k,r}-{\beta }_{2,f}^{k,r}·t^r+\left(1-{\displaystyle \sum }_{n=1}^N{\displaystyle \sum }_{m=1}^M{\displaystyle \sum }_{d=1}^D{y}_{n,m}^{k,r}·a_{f,d}^r\right)·B \forall r,\forall f,\forall k$$

(2)

Equation (2) calculates the customer satisfaction according to the elapsed time to deliver when an order r consisting of a type of goods f is processed to a means of delivery k. In this constraint, the value of customer satisfaction is greater than 1 by multiplying a very large number B when an order r consisting of type of goods f is not processed with a means of delivery k. Therefore, as shown in Equation (1), the smallest value among the customer satisfaction values of order r becomes the actual customer satisfaction of order r.

$${\displaystyle \sum }_{k=1}^K{\displaystyle \sum }_{n=1}^N{\displaystyle \sum }_{m=1}^M{y}_{n,m}^{k,r}=1 \forall r$$

(3)

$${\displaystyle \sum }_{r=1}^R{y}_{n,m}^{k,r}\le 1 \forall k,\forall n,\forall m$$

(4)

$${\displaystyle \sum }_{r=1}^R{y}_{n,m}^{k,r}\ge {\displaystyle \sum }_{r^{\prime }=1}^R{y}_{n,m+1}^{k,r^{\prime }} \forall k,\forall n, m=1,\dots ,M-1$$

(5)

$${\displaystyle \sum }_{m=1}^M{\displaystyle \sum }_{r=1}^R{y}_{n,m}^{k,r}\ge {\displaystyle \sum }_{m^{\prime }=1}^M{\displaystyle \sum }_{r^{\prime }=1}^R{y}_{n+1,m^{\prime }}^{k,r^{\prime }} \forall k, n=1,\dots ,N-1$$

(6)

Equation (3) indicates that each order r can be assigned to only one delivery sequence m of a specific round n of a specific means of delivery k, while Equation (4) also represents that only one order can be assigned to a specific delivery sequence m in a specific round n of means of delivery k. In addition, as shown in Equation (5), in the nth round of means of delivery k, orders can be assigned to the (m + 1)th delivery sequence only when orders are assigned at the mth delivery sequence. In the similar manner, Equation (6) is restricted that the (n + 1)th round can be created only when the nth round is made by order allocation.

$${\displaystyle \sum }_{m=1}^M{\displaystyle \sum }_{r=1}^R{g}^r·y_{n,m}^{k,r}\le G^k \forall k, \forall n$$

(7)

$${\displaystyle \sum }_{m=1}^M{\displaystyle \sum }_{r=1}^R{v}^r·y_{n,m}^{k,r}\le V^k \forall k, \forall n$$

(8)

Equations (7) and (8) represent the weight and volume constraints that means of delivery k can carry at once in specific round n, respectively. In this study, it is assumed that UGVs and UAVs can visit at the depot multiple times to newly load the goods within period of time. Therefore, the capacity constraints are presented according to the weight and volume.

$$0\le t^r\le T \forall r$$

(9)

$${\displaystyle \sum }_{d=1}^D{\displaystyle \sum }_{f=1}^F{y}_{1,1}^{k,r}·a_{f,d}^r·t_{0,d}^k\le t^r \forall k, \forall r$$

(10)

The elapsed time taken to process the order r should be greater than 0 and less than the maximum period of time T, as shown in Equation (9). In addition, Equation (10) indicates that if order r is assigned to the first delivery sequence of the first round at the means of delivery k, then the delivery arrival time of order r is equal or greater to the elapsed time for moving from depot to destination node d.

$$\begin{gathered} t^{r^{\prime }}+t_s^k+{\displaystyle \sum }_{d=1}^D{\displaystyle \sum }_{d^{\prime }=1}^D{\displaystyle \sum }_{f=1}^F{\displaystyle \sum }_{f^{\prime }=1}^F{y}_{n,m-1}^{k,r^{\prime }}·a_{f^{\prime },d^{\prime }}^{r^{\prime }}·t_{d^{\prime },d}^k·a_{f,d}^r \\ -B·\left(2-y_{n,m}^{k,r}-y_{n,m-1}^{k,r^{\prime }}\right)\le t^r \forall k, \forall r^{\prime },\forall r,\forall n,m=2,\dots , \end{gathered}$$

(11)

$$\begin{gathered} t^{r^{\prime }}+t_s^k+{\displaystyle \sum }_{d=1}^D{\displaystyle \sum }_{d^{\prime }=1}^D{\displaystyle \sum }_{f=1}^F{\displaystyle \sum }_{f^{\prime }=1}^F{y}_{n-1,m^{}}^{k,r^{\prime }}·a_{f^{\prime },d^{\prime }}^{r^{\prime }}·\left(t_{d^{\prime },0}^k+t_s^k+t_{0,d}^k\right)·a_{f,d}^r \\ -B·\left(2-y_{n,1}^{k,r}-y_{n-1,m}^{k,r^{\prime }}\right)\le t^r \forall k, \forall r^{\prime },\forall r,\forall m,n=2,\dots ,N \end{gathered}$$

(12)

Equations (11) and (12) are developed to calculate the order arrival times of both order r and order r′ when order r and order r′ are sequentially processed. At this time, if two orders are either included in the same nth round of means of delivery k and assigned to a continuous delivery sequence, then Equation (11) is applied. In addition, while order r′ and order r are processed sequentially by means of delivery k, when order r′ is assigned to the last delivery sequence of (n − 1)th round, and order r assigned to the first delivery sequence of nth round, then Equation (12) is applied. Otherwise, when order r and order r′ are not sequentially processed, Equations (11) and (12) are not applied as a very large number B is multiplied.

$${\displaystyle \sum }_{r=1}^R{\displaystyle \sum }_{n=1}^N{\displaystyle \sum }_{m=1}^M{\displaystyle \sum }_{f=1}^F{y}_{n,m}^{k,r}·a_{f,d}^r=0 k\in K_A, d\in D_{\overline{A}}$$

(13)

$${\displaystyle \sum }_{r=1}^R{\displaystyle \sum }_{n=1}^N{\displaystyle \sum }_{m=1}^M{\displaystyle \sum }_{f=1}^F{y}_{n,m}^{k,r}·a_{f,d}^r=0 k\in K_G, d\in D_{\overline{G}}$$

(14)

In the case of UGVs, delivery may not be possible to a specific destination node due to the topographical characteristics, while in the case of UAVs, delivery may only be possible to a specific destination node to prevent damage from the accidental falling of either the goods to be delivered or the UAV itself. Finally, Equations (13) and (14) express a destination node d that cannot be delivered to UAVs and a destination node d that cannot be delivered to UGVs, respectively.

4. Solution Procedure

In this study, an optimal solution solver and a genetic algorithm, one of meta heuristic methods, are used to derive the optimal solution of the developed mathematical model. For small-sized problems, an optimal solution can be easily derived with an optimal solution solver such as CPLEX, but even if the problem size is slightly increased, the optimal solution solver cannot derive the optimal solution within a specific time because of the exhausted computation time. Therefore, in this study, the performance of the proposed genetic algorithm is confirmed by comparing the results and computation time of the optimal solution solver and the genetic algorithm for a small size problem. Then, insights are derived by calculating the near-optimal solution by applying the genetic algorithm to the problem for a reasonable size problem.

4.1. Optimal Solution Solver

In this study, a mathematical model-based optimization technique is used. In mathematical model-based optimization, a series of equations is developed by defining the decision-making factors in management as the decision variables of the equation and using various resource constraints in management as constraints. The developed series of equations can derive the optimal solution of the decision variable using a mathematical solver programmed in a computer language. Microsoft’s Excel, which is used in general-purpose, also has a solver for mathematical models under the name of ‘Excel Solver’, and various solver programs exist for professionals. In here, the optimal solution of the developed mathematical model is derived using IBM’s ILOG CPLEX. IBM’s ILOG CPLEX is the most widely used mathematical model solver for professionals and is known for deriving optimal solutions in a relatively short time for linear programming or mixed-integer programming.

4.2. Genetic Algorithm

A genetic algorithm inspired by Darwin’s theory of natural selection was introduced by Holland [31]. It can derive a near-optimal solution in a feasible time. Baker and Ayechew [32] found that in vehicle routing problems, genetic algorithms can compete with other modern heuristic techniques in terms of solution time and quality. Hanshar and Ombuki-Berman [33] demonstrated its effectiveness in vehicle routing problems. The overall procedure of the genetic algorithm is shown in Figure 3.

4.2.1. Chromosome Design

Initially, chromosome design is conducted to encode possible solutions for the described problem. The chromosome consists of a string of genes which stands for the index of the assigned order. All assigned orders are encoded as each chromosome as shown at Figure 4. The maximum space of order assignment (=i) is set to reflect the maximum elapsed time for each vehicle. Every ith number of genes denote order assignment of each vehicle. The vector of each pair represents the sequence of visit schedules for all orders. The population in genetic algorithm is defined as a set of chromosomes. The initial population consists of the chromosomes that are randomly generated. Each gene space is filled with random order numbers within the number of total given orders. Then, an evolutionary computing approach is conducted to find near-optimal solution. The number of gene spaces that are not filled by random integers is $i·k-{\sum }_{r=1}^R{\sum }_{d=1}^D{\sum }_{f=1}^F{a}_{f,d}^r$. For those empty gene spaces, zeros are filled instead of random order numbers. The parameters of the genetic algorithm used for analysis in the study are shown in

Table 1. Set parameters for the genetic algorithm.

Parameter	Value
Number of populations	500
Number of generations	1000
Crossover probability	0.3
Mutation probability	0.3
Elitism rate	0.3

.

4.2.2. Fitness Function

The fitness function is generated to calculate the fitness value, which evaluates the survival probability through every reproductive process of genetic algorithm. The fitness function are modeled by reflecting the objective function of the proposed mathematical model in Equation (1) of Section 3. Each chromosome is decoded to the overall vehicle operation scheme to calculate the total elapsed time on each node. The calculation process of elapsed time reflects Equations (10)–(12). To calculate total elapsed time of x_i,k, which denotes ith assigned order for vehicle i, service time for processing previous order x_i−1,k and travel time of arc (x_i−1,k, x_i,k), are added on total elapsed time of x_i−1,k. Note that service time for x_i,k is considered on the next order x_i+1,k. If the inventory of vehicle cannot meet the capacity constraint which reflects Equations (7) and (8), travel time of arc (x_i−1,k, x_i,k) is replaced by the sum of travel time of arc (x_i−1,k, depot), arc (depot, x_i,k) and service time.

4.2.3. Selection, Crossover, and Mutation

The next generation is structured as follows. First, chromosome with the highest fitness value from the previous generation is selected and included in the next generation. To assure chromosomes with high fitness values survive through the generations, the chromosomes with the number of elitism size are selected. The crossover is performed with these selected chromosomes. Applying the basic crossover process can generate the chromosomes that violate Equations of the mathematical model. These might include overlapped order and omitted order which violate Equations (3) and (4). To avoid generating such infeasible solutions, the repairing process is done after every crossover. If any of the genes outside the randomly set two points is already included in the set of genes of relative chromosome inside the points, the repairing process is done to ensure the feasibility of the chromosome. The overall process of crossover is shown in Figure 5. Like the crossover process, the basic mutation process can also generate infeasible solutions. Thus, in this study, swap node mutation is applied instead. In the swap node process, two genes are randomly selected. Then, the locations of selected genes are swapped.

5. Numerical Experiment

5.1. Preparation of Experiment

The models in Cases 1 and 2 are hypothetically created by the author as actual possible situations to consider the reveal the problem nature. In order to design the optimal integrated operation system of delivery service using UGVs and UAVs, the beach as shown in Figure 2 is assumed for the numerical experiment. Each destination node is located in a square grid, while it is set to take 20 s for UGVs and 15 s for UAVs to move to a nearby grid. In addition, it is assumed that UGVs move between nodes in Manhattan distance, whereas UAVs move in Euclidean distance to consider the characteristics of both UGVs and UAVs.

In this study, two kinds of experiments are designed to derive the insights. In the case of a small size problem, it is assumed that there are only eight orders during the period of time, whereas in a reasonable size problem, it is assumed that there are 20 orders during the period of time to reflect the actual situation. In addition, each problem is assumed to have two kinds of cases according to the moving constraint of UAVs, case 1, in which the UAV can move freely, and case 2, in which the UAV can only move to the outline of the beach. Moreover, it is further assumed that there are three UGVs and three UAVs as the means of delivery (=k) while from 1 to 3 stands for UGVs, and 4 to 6 denotes to UAVs. To evaluate the validity of proposed genetic algorithm, the results of the small size problem obtained by applying each of CPLEX and genetic algorithm are compared and analyzed. Then, it is tried to investigate the result of reasonable size problem by applying only a genetic algorithm because the CPLEX cannot solve that size of problem within adequate computation time.

As mentioned earlier, the purpose of this study is to provide a delivery service using UGVs and UAVs to tourists in specific tourist destinations so that they can feel fun and enjoyment. Therefore, the objective of the algorithm developed in this study is to maximize total customer satisfaction. In case of UGVs, it is already operated for serving in several restaurant now. Therefore, it is assumed that the customer’s fundamental satisfaction is higher when they receive the delivery service by UAVs, and with the similar reason, the rate of satisfaction that decreases with delivery elapsed time is also assumed that UAVs are lower than that of UGVs. In addition, it is further assumed there are two kinds of goods to be delivered such as food and general item and the parameters related to customer satisfaction are set differently according to the kinds of goods. To perform the numerical experiment, a set of the system parameters are prepared as

Table 2. System parameters for vehicles, orders, and satisfaction.

Parameter			Value
$g^r$			{2, 3, 2.5, 3.2, 2.6, 2.4, 3.2, 1.1, 5, 4, 1.1, 4.1, 2, 3, 3.5, 3.2, 1.3, 3, 2, 2}
$v^r$			{100, 200, 125, 250, 130, 240, 500, 300, 240, 320, 150, 400, 200, 320, 340, 400, 150, 260, 240, 200}
$G^k$			{30, 30, 30, 10, 10, 10}
$V^k$			{3000, 3000, 3000, 1000, 1000, 1000}
$t_s^k$			{30, 30, 30, 40, 40, 40}
(r, f, d) when $a_{f,d}^r=1$			(1,1,4) (2,2,4) (3,1,1) (4,1,15) (5,2,13) (6,1,13) (7,1,7) (8,1,6) (9,2,18) (10,2,14) (11,1,9) (12,2,16) (13,1,9) (14,2,9) (15,2,2) (16,2,15) (17,1,20) (18,2,11) (19,1,3) (20,2,19)
${\beta }_{1,f}^{k,r}$	k = 1,2,3	f = 1	0.9
		f = 2	0.8
	k = 4,5,6	f = 1	1.0
		f = 2	1.0
${\beta }_{2,f}^{k,r}$	k = 1,2,3	f = 1	0.004
		f = 2	0.002
	k = 4,5,6	f = 1	0.002
		f = 2	0.001

.

5.2. Small Size Problem

5.2.1. Case 1: UAVs Move Freely

Small cases are examined to evaluate the performance of a genetic algorithm by comparing the optimal solution derived by CPLEX. There are two situations that are considered in this paper. Situation 1 is that one UAV and one UGV deliver eight orders. The other one is that three UAVs and three UGVs deliver eight orders. The derived results are shown in

Table 3. The result of small size problem (Case 1).

Situation	Vehicle	Round	Travel Schedule: Node (Type of Goods)	Satisfaction	Total Complete Time
Situation 1 1 UAV 1 UGV 8 orders	UAV1	1st	0 → 4(1) → 6(1) → 13(1) → 13(2) → 0	5049	513.09
		2nd	0 → 7(1) → 4(2) → 0
	UGV1	1st	0 → 1(1) → 15(1) → 0
Situation 2 3 UAVs 3 UGVs 8 orders	UAV1	1st	0 → 1(1) → 13(1) → 13(2) → 0	6803	171.49
	UAV2	1st	0 → 4(1) → 6(1) → 0
	UAV3	1st	0 → 7(1) → 15(1) → 4(2) → 0
Situation 3 2 UAVs 2 UGVs 8 orders	UAV1	1st	0 → 4(1) → 6(1) → 13(1) → 13(2) → 0	6492	225
	UAV2	1st	0 → 7(1) → 15(1) → 4(2) → 0
	UGV1	1st	0 → 1(1) → 0
Situation 4 3 UAVs 3 UGVs 7 orders	UAV1	1st	0 → 1(1) → 4(1) → 4(2) → 0	6134	140
	UAV2	1st	0 → 13(1) → 13(2) → 0
	UAV3	1st	0 → 7(1) → 15(1) → 0

.

Most orders are normally delivered by UAVs first due to faster speed, higher fundamental satisfaction, and lower decrease in satisfaction per elapsed time. Orders from nodes where only UAVs can move and others from distant nodes are delivered by UAVs. Orders from relatively close nodes are delivered by UGVs. If there are enough vehicles, the delivery is completed in the 1st round. Food is delivered earlier than general items because the decrease in satisfaction per elapsed time is large. In Situation 1, the order of node 7 is food but delivered in the 2nd round. This is because its large weight and volume affect reducing the number of orders if it is delivered in the 1st round. However, food is delivered first in the 2nd round due to the priority of the delivery. In general, when two orders occur on the same node, one vehicle delivers two orders in a row, such as the orders of node 13 in situation 1. However, if two orders occur at the same time from a nearby node, such as the order of node 4 in situations 1 and 2, a different result is shown. Food of node 4 is delivered first and the general item is deferred. This is because delivering food first helps maximize customer satisfaction. Total complete time is the time when is spent delivering all orders. If the number of vehicles increases, customer satisfaction increases and total complete time decreases. The results of situations 3 and 4 support the implications derived from situations 1 and 2.

5.2.2. Case 2: UAVs Move Outline of the Beach

In Case 2, two situations are provided as well as Case 1. The derived results are shown in

Table 4. The result of small size problem (Case 2).

Situation	Vehicle	Round	Travel Schedule: Node (Type of Goods)	Satisfaction	Total Complete Time
Situation 1 1 UAV 1 UGV 8 orders	UAV1	1st	0 → 1(1) → 4(1) → 4(2) → 6(1) → 0	4.46	395
		2nd	0 → 7(1) → 0
	UGV1	1st	0 → 15(1) → 13(1) → 13(2) → 0
Situation 2 3 UAVs 3 UGVs 8 orders	UAV1	1st	0 → 7(1) → 0	5.98	140
	UAV2	1st	0 → 4(1) → 4(2) → 0
	UAV3	1st	0 → 1(1) → 6(1) → 0
	UGV1	1st	0 → 13(2) → 0
	UGV2	1st	0 → 13(1) → 0
	UGV3	1st	0 → 15(1) → 0
Situation 3 2 UAVs 2 UGVs 8 orders	UAV1	1st	0 → 15(1) → 0	5.74	170
	UAV2	1st	0 → 1(1) → 4(1) → 4(2) → 0
	UAV3	1st	0 → 7(1) → 6(1) → 0
	UGV1	1st	0 → 13(1) → 13(2) → 0
Situation 4 3 UAVs 3 UGVs 7 orders	UAV1	1st	0 → 7(1) → 0	5.24	140
	UAV2	1st	0 → 1(1) → 4(2) → 0
	UAV3	1st	0 → 4(1) → 0
	UGV1	1st	0 → 15(1) → 0
	UGV2	1st	0 → 13(2) → 0
	UGV3	1st	0 → 13(1) → 0

.

Since UAVs can only move in the outline of the beach, orders from distant nodes are delivered by UGVs. In situation 2, two orders from node 13 are delivered by different vehicles. This is because one order should wait while the other order is served if one vehicle delivers two orders. Therefore, when multiple vehicles are operated, orders from the same node may be delivered by different vehicles. In situation 2 of Case 1, UAVs deliver all orders, whereas in Case 2, orders are evenly assigned due to the movement restrictions of UAVs. Movement restrictions of UAVs reduce customer satisfaction but shorten total complete time. Customer satisfaction is decreased by 11.67% (situation 1), 12.10% (situation 2), 11.58% (situation 3) and 14.57% (situation 4). Total complete time is decreased by 23.02% (situation 1), 18.36% (situation 2), 24.44% (situation 3) and 0% (situation 4).

5.2.3. Comparison of Results of CPLEX and the Genetic Algorithm

To evaluate the performance of a genetic algorithm, the results derived from CPLEX and the genetic algorithm are compared. The derived results, and the calculation time are shown in

Table 5. The results of CPLEX and the genetic algorithm.

Case (Number of Vehicles, Number of Orders)	CPLEX		Genetic Algorithm
	Result (Satisfaction)	CPU Time (Second)	Result (Satisfaction)	CPU Time (Second)
Case 1 (2,8)	5049	338.24	5049	596.11
Case 1 (6,8)	6803	17,156.01	6803	561.31
Case 1 (4,8)	6492	2835.86	6492	564.10
Case 1 (6,7)	6134	2427.79	6134	580.27
Case 2 (2,8)	4.46	31.16	4.46	561.63
Case 2 (6,8)	5.98	328.55	5.98	577.01
Case 2 (4,8)	5.74	92.80	5.74	572.07
Case 2 (6,7)	5.24	66.96	5.24	576.88

. It is shown that the genetic algorithm has the same results as CPLEX in all cases. Moreover, the computation time of Case 1 that has six vehicles, and eight orders is even faster when using the genetic algorithm than CPLEX. It is confirmed that the computation time of CPLEX can take very long in certain cases, and if there are six vehicles and the number of orders exceeds eight, it is not possible to derive a solution within 30,000 s. However, in the case of genetic algorithms, there is no significant change in computation time even if the number of orders is increased.

5.3. Reasonable Size Problem

When three UGVs and three UAVs are operated, the number of orders needs to be increased to ensure that each UGV and UAV are operated for more than two rounds, and only then will more diverse insights be derived from the results. Therefore, a reasonable size problem is presented assuming that there are six vehicles and 20 orders. The derived results are shown in

Table 6. The result of reasonable size problem.

Case	Vehicle	Round	Travel Schedule: Node (Type of Goods)	Satisfaction	Total Complete Time	CPU Time (Second)
Case 1	UAV1	1st	0 → 9(1) → 3(1) → 4(1) → 4(2) → 0	14.68	474.30	591.47
		2nd	0 → 2(2) → 11(2) → 0
	UAV2	1st	0 → 1(1) → 9(1) → 6(1) → 13(1) → 13(2) → 0
		2nd	0 → 14(2) → 0
	UAV3	1st	0 → 7(1) → 20(1) → 19(2) → 0
		2nd	0 → 16(2) → 18(2) → 0
	UGV1	1st	0 → 15(2) → 0
	UGV2	1st	0 → 15(1) → 0
	UGV3	1st	0 → 9(2) → 0
Case 2	UAV1	1st	0 → 7(1) → 14(2) → 0	13.12	285	530.26
		2nd	0 → 2(2) → 0
	UAV2	1st	0 → 1(1) → 4(1) → 4(2) → 19(2) → 0
	UAV3	1st	0 → 3(1) → 6(1) → 0
	UGV1	1st	0 → 9(1) → 9(2) → 16(2) → 18(2) → 0
	UGV2	1st	0 → 15(1) → 15(2) → 20(1) → 0
	UGV3	1st	0 → 9(1) → 11(2) → 13(1) → 13(2) → 0

.

6. Conclusions

This study aims to derive an optimal route for robot-based delivery service at tourist destinations. The mathematical model-based optimization technique is applied to generate such an optimal route which maximizes total customer satisfaction. Two cases are analyzed in the aspect of safety concerns. Each case stands for the case assuming UAVs freely fly through entire nodes and the case assuming UAVs only move through the outline of the beach, respectively. Both cases are tested by controlling the number of vehicles and the number of orders assigned to find out the validity of the proposed mathematical model.

The results of the small size problem show that the orders tend to be assigned to the UAVs due to less travel time to arrive at each node compared to UGVs. Additionally, even some distant nodes where UGVs can reach earlier are assigned to UAVs. This is due to higher fundamental satisfaction when the service is done compared to UGVs and a lower decrease in satisfaction per delivery time. This implies that minimizing arrival time does not always match customer needs. However, in Case 2, it is found that the number of assigned orders to UGVs has increased. It is because, unlike Case 1, available routes for UAVs have been restricted to the outline of the beach. The slower movement speed of UGVs decreases customer satisfaction. Even in the nodes where orders are assigned to UAVs, customer satisfaction has decreased because of the limited available direction for UAVs. The results of the reasonable size problem well reflect the characteristics discussed for the small size problem. The overall customer satisfaction is 11.89% higher in Case 1 and the complete time of service is 39.91% lower in Case 2. The orders are preferentially assigned to UAVs when there are no restrictions compared to the case with restrictions. However, the result of the reasonable size problem implies that if there are more orders to deal with, the number of order assignment to UGVs increase because of the larger capacity of the weight and volume.

This study is expected to become an essential source for practitioners to get insights when designing integrated goods delivery systems for UGVs and UAVs at tourist destinations. Such considerations include the suitable number of UGVs and UAVs in the aspect of customer satisfaction and availability of each vehicle. Furthermore, by considering components including multiple types of goods, safety concerns, limited capacity of vehicles, and upper limit time for service, the proposed mathematical model is expected to be practical for real-world application.

As a further study, it is suggested to consider the traveling speed and energy consumption dependent on the weight. During every delivery, the total weight of the vehicle will change, and this may affect the traveling speed and energy consumption of the vehicle. In addition, additional time components can be considered in the aspect of the real-world application. The additional time caused by the loading, unloading, and charging time of vehicles and the location of the charging station can be considered.