In this contribution we explore how a cyber physical system of drones can be used for the delivery of parcels. The basic question is: How can such a delivery system, that is congested, be improved in terms of its delivery time? To nd an answer, we model a system like this using timed Petri nets. Simulations are then carried out using this model where the capacities of the system and the capabilities of some drones are manipulated. These simulations show that a small population of improved drones produces similar improvements in delivery times as doubling the charging capacities at saturated points in the system.
The term cyber physical system (CPS) characterises a system that integrates
software and physical processes. Here, a physical process is monitored and
controlled by embedded, interconnected computers. Typically there is an
interdependence and the physical process in uences the computations performed by
a software component [
There are di erent factors that favour the trend towards CPS. Powerful
sensor technology is becoming increasingly cheaper and smaller in form factor. The
possibilities of wireless networks have increased rapidly in recent years and the
emergence of alternative technologies for energy generation and storage are
factors [
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Logistics o ers great potential for the use of CPS too. The industry is already
considering the use of drones for the delivery of parcels [
Key questions that arise when using drones in logistics are the distribution of warehouses and charging stations in the area of operation and what types of drones are used. The di erence can be, for instance the battery size of a drone. The impact of the topology of a drone network is also an interesting aspect. When using such a system with di erent topologies for charging stations, the outcomes may vary.
Our general research interest is the adaptivity of distributed cyber physical
systems. Therefore, we are particularly curious about strategies that can be
applied when a delivery system of drones is saturated. How can delivery times
be reduced under these circumstances? The two most obvious parameters are the
capabilities of the drones and the capacity of the charging stations. To examine
this, we perform a simulation using timed Petri nets [
With this aim in mind, this paper is structured as follows: Section 2 presents literature on other analyses of drone-based delivery systems conducted using simulations. It also presents and justi es the use of timed and coloured Petri nets to analyse issues of logistics. The designed model is presented in Section 3. Exactly how it is parameterised for the experiments is then explained in Section 4. The results of these experiments are examined in Section 5 and the paper closes with a conclusion. 2
Initial considerations on the use of drones in parcel delivery have been around
since 2013 [
Petri nets can be used to simulate such a system. Particularly in the eld
of logistics, a wide variety of experiments are carried out in this way. In the
recent past, processes for transporting cotton by train [
A Petri net is very suitable for modelling because of its clear formalisms and
structure. One way of using Petri nets for simulation on a model is also described
in the work of Strumpel [
Drones are much more limited in their range than delivery trucks, a modern
drone can y an average of 4 km [
In order to represent the concurrency of our drone system, we use Petri nets.
We design our model in a similar way to the one described by Strumpel [
As the rst step, the application domain is structured following the
Smart-GridReference-Architecture (SGAM) approach [
Each level has two dimensions, the domains and the zones. Domains represent the di erent localities involved in the process for the drone delivery system, i.e.
Physical
Control
Operational
Enterprise Warehouse
Hub
Drone Customer
Loading Bay Charging Station Charging Station
Charge Battery Charge Battery
Load Parcel
Flight Planning
Send Parcel
Customer
Flight Control Deliver Parcel
Decide Parcel and Route Inform Customer
Parcel Tracking
Customer the central warehouse, the stations where drones are charged (hubs), the drone itself and the customer. As shown in Figure 1, the zones are then divided into the physical zone, the control zone, the operational zone and the enterprise zone.
These zones each cover a sub-area of the delivery system, e.g. the physical level in Figure 1 contains the physical functions that are provided. The warehouse has been modeled in a way where it directly plans the ight route for received parcels because it knows all hubs. The drones then receive a ight plan along the hubs together with a package. Where a drone charges its battery, however, is decided by its control system, referred to as the ight control in Figure 1.
This architecture is mainly used to create an overview of the delivery system and the context in which it is used. Nevertheless, conclusions can already be drawn from the architecture for the modelling of Petri nets. Especially the function layer shown in Figure 1 is used for this purpose. The planning of ights is done by a planning system at the warehouse. The drone carries the predetermined ight out independently and decides when to charge its battery. A drone can charge at the warehouse or at a hub. Hubs and the warehouse have limited charging stations, but the warehouse has an unlimited capacity of landing spots. If a drone wants to charge at a hub that has no capacity, it must wait. Only one central warehouse exists in the model, there parcels can be picked up by drones.
Units are then selected for the simulation. In one elapsed time unit in RENEW, a drone can cover one way unit. For a regular drone, this consumes one energy unit. Charging one energy unit also takes one time unit. However, these two parameters are adjusted in the simulations to simulate adding more e cient drones to a congested delivery system. For modelling in RENEW, the model splits into ve nets, taking the warehouse, the hub and the drone from the domains of the architecture. The customer is present in the hub net. In addition, the ight planning system is mapped to a path generator net. Since many simulation runs with di erently set parameters have to be started for the experiments a fth net is used. This master net works in conjunction with the four nets that form the model of our delivery system. It has the sole task of starting simulation runs with the correct parameters. An overview of the model is shown in Figure 2. The boxes represent the individual nets of the model, and the arrows are used to illustrate the relationships between the nets. The nets themselves can be seen in detail in Appendix A.
Master Net PathGenerator Net Uses Drone Net
as a token Warehouse Net
Drone Net The Master Net uses the Warehouse as a token to start simulation runs with
different parameters Flight Paths for
parcels are generated by the PathGenerator
Net
Drone travels between Hub and Warehouse Net
Uses Drone Net
as a token
Hub Net The warehouse net is the starting point of the model, here all drones are instantiated. They then move through the warehouse as tokens. At the centre of the warehouse is a landing pad for drones, into which a drone moves after it has been instantiated. From here, the drone can go to a charging station where it can charge its battery. The capacity of these charging stations is limited.
Secondly, a drone that is not loaded with a parcel can go to a loading bay, which are also limited in capacity. There the drone loads a parcel and receives a ight path determined for it by the path generator and moves back to the landing pad. A loaded drone can take o from there into the hub net to deliver its parcel to the customer. On the other hand, drones that have delivered a parcel can return to the warehouse from the hub net and land at the landing pad. 3.2
In the warehouse, ight paths are determined for each parcel, which the drone will move along to deliver the parcel. This system is simulated by the path generator net. A ight path is a tuple consisting of an id and two lists. The rst list represents the route that still has to be covered for the ight path to the customer, the second represents the route that has already been covered. Using the second list, a drone can then navigate from the customer back to the warehouse. The entries in both lists are tuples consisting of the id of the next hub and the distance from the current hub. Customers are represented as hubs with the id zero.
A topology le is used as the basis for the topology of the hub net. In this le, the hub net is described as a tree. This approach is chosen because we presume that our hubs are placed in the optimal location for our service area. Over the graph of all connections from hub to hub and warehouse to hub we build a spanning tree. This tree then becomes the topology of our delivery system.
The topology of the delivery system is also a parameter that can be set. RENEW o ers the possibility to import user-developed Java classes and to use their methods. The actual generation of the paths takes place in a Java class developed for the net. The resulting list then travels through the path generator net as a token and is converted by it into the form of a ight path described above. This is then combined in the warehouse net to a token with a parcel and waits in the warehouse for a drone to load the parcel and complete the path. 3.3
All actions that a drone can perform are modelled by the drone net. The net travels as a token through the warehouse and hub net. Internally, the drone net has space for a parcel. It delivers the parcel according to the ight path that is associated with it. Like shown in the architecture, the drone itself decides when to charge its battery. The default strategy is to charge only when the next route cannot be covered with the available energy. Drones that arrive at the warehouse are always charged so that they need to charge as little as possible when ying to a customer. The energy that a drone consumes during the ight is modelled using this function: batt = batt 1 d (1 + ) (1)
The energy level of a drones battery at time t is given by batt, this is calculated from the energy level at a previous time t 1 minus the distance d travelled. The e ect that the weight of a parcel has on the range of a drone is given by . For the simulation, the weight of the parcels is set to ve weight units. Our is then modelled as:
= p=10
Where p is the weight of the parcel indicated. For a parcel with 5 weight units, this results in a value of 0.5 for . This value is provisionally used for the simulation. Of course, can be changed with more data so that it corresponds to the real e ect of additional weight on a drone.
Hub The hub net represents the system of charging stations in our delivery system. As described in Section 3.2, the topology of the charging stations is determined by a topology le. In order not to design a new hub net for each topology it is parameterised. For this purpose, the hub net holds the states of the respective hubs in tuples consisting of the hub's id and the capacity of charging stations at that hub. The place hub only represents a generic hub; it is only when its battery has to be charged that it is relevant to a drone at which hub of its ight path it is located. This is due to the capacity of charging places at the current hub, which must be checked and a drone may have to wait for a free spot.
By launching at the warehouse, a drone enters the hub net. To simplify the modelling, a drone cannot y directly from the warehouse to a customer, but must go to at least one hub. At a hub, a drone can then y to the next hub, charge its battery if needed, or y to a customer and unload its package. If a drone has to y to the customer next, it recognises this by the hub id zero in its ight path, which is reserved for a customer. When a drone has dropped o its parcel at a customer, it follows its ight path in reverse order. If there are no entries in its ight path, the drone moves to the warehouse and enters the warehouse net. 4
In our experiments, a situation where a delivery system of drones is under heavy
load and its hubs are close to their maximal capacity is recreated [
{ Hub capacity: Indicates how many charging stations are available at a hub.
The charging strategy and package size remain static for our experiments. Drones implement a charging strategy in which they charge their entire battery whenever they do not have enough energy to complete the next section of their journey or when they arrive at the warehouse. This should not have much e ect on the generalisability of the experiments. Other charging strategies will achieve this goal more optimally, but the aim remains the same. The maximum range is calculated according to the formula for the energy consumption of a drone given in Section 3.3. For the selected parcel size, the maximum loaded range for the drones is 95:23 way units.
56 9 41 1 4 60
55 Warehouse 45
2 32 10 50 5 29 6 36 11 3 7 55
33 62 12 8
Hubs are shown in both Figures 3 and 4 as nodes of each tree and are labelled with their id. The edges represent the ight routes between hubs, the number indicates how many way units lie between both hubs. Customers are modelled as hubs with an id of zero and can be approached from any hub except the warehouse at a distance less than half the maximum range of a regular drone. The probability that a drone is already at the correct hub and must y to a customer next is determined during path creation. For each node of the tree, it is checked whether it is the last one before a customer.
The two topologies were chosen in order to obtain a broad and a deep tree. Deep or broad are the two dimensions a tree can have. Why trees are used to represent our topologies was explained in Section 3.2. Of course, many more topologies than just these two are possible. But the computation e ort to support randomly created topologies is very high, as for each topology all tests using the same parameters have to be performed again. In order to be able to generalise the results, the two di erent topologies were designed. Nevertheless, other topologies may have di erent e ects and results.
Warehouse 87 2 36 10 63 4 74 6 44 11 94 7 27 12
The charging speed of regular drones, as described in Section 3.3 , is one-toone with the time a drone spends at a charging station. For the more powerful drones, this value becomes faster by a factor of 20%, 25% or 30%. To implement this the function for calculating the charging time is supplemented by the factor ct.
tcharge = (cap batt) (1 ct) (2)
Here, tcharge is the time until the battery is fully charged, this results from the capacity of the battery (cap) minus the current charge level of the battery (batt) and is then multiplied with the speed factor ct. The factor ct must be selected between 0 and 1, for ct = 0 there is no improvement in charging speed.
The values for improvement are chosen in such a way that at the lower limit a clear improvement can already be observed when charging a completely empty battery from 100 time units to 80 time units. The upper limit is chosen to show that the more powerful drones use similar battery technology that is more e cient but does not rely on a completely di erent method, such as modular batteries that are only swapped at the hub.
As described above, a drone without cargo consumes one unit of energy for one unit of travel. A loaded drone consumes more energy because the weight of the package being transported is included in the calculation (Section 3.3). This factor is changed for the more powerful drones, which, for example, use more e cient motors or rotor blades to generate lift. This allows for the more e cient drones without cargo to use 20%, 25% or 30% less energy units to y a path unit. For loaded drones, the corresponding factor is taken into account.
In the formula shown above, you can see the modi cation to the formula from Section 3.3 for the energy consumption of a drone. The factor con indicates how many percent less energy is consumed during ight. A drone that is 20% more energy-e cient thus only consumes 0.80 energy units to y one way unit.
In all experiments, at least 400 drones are used. This limit was experimentally determined for both topologies as the point at which adding regular drones leads to a worsening in delivery time. The population of drones remains constant over the respective simulation run. However, the proportion of additional more e cient drones is increased over the experiments from zero to proportions of 20%, 25% or 30% of the regular drone population. In a second trial, improved drones replace 20%, 25% or 30% of the regular drone population. To make a comparison, trials are also conducted in which the population of drones is not being changed. Instead, the capacity of two particularly overloaded hubs is increased by 10%, 20%, 30%, 50% and 100%. This allows us to assess whether changing the population of drones or changing the capacity of congested hubs can prevent or reduce congestion in the system and thus reduce delivery times.
Due to our decision to charge all drones arriving at the warehouse, we set the capacity of charging stations there to 50. At this capacity, there will be no queues at the warehouse. This was also determined by experiments. The regular capacity of a hub is 10 charging stations. 5
For the rst experiment with topology one, additional drones were added to the system. These were improved as described in Section 4. Results from the rst topology show that using additional drones whose charging speed is improved keeps the average delivery speed in the range of 700 to 800 time units, but the delivery speed is not improved compared to a system with only 400 regular drones.
This is di erent for the trials in which the drones were improved in terms
of their energy consumption. In the trials with drones that consume less energy,
parcels are delivered in under 550 time units on average. This is a signi cant
improvement over the system without additional drones. Nevertheless, it can
be observed here that our delivery system is getting worse on average with
more than 480 drones, this applies to two of the three levels of performance
improvement. For drones that use 20% less energy, the trend is reversed. This
could be a statistical e ect, as each test was only performed twice, or it may be
an e ect similar to the Braess paradox [
It is obvious that the delivery times for topology two are signi cantly longer than for topology one. With 400 regular drones, parcels are delivered in an average of 1761.93 time units. The addition of improved drones does not lead to any improvement. Any additional drone population worsens the delivery times, some even signi cantly. The di erence between drones that charge faster and those that use less energy is not as obvious as in topology one. But even here, statistical e ects can be observed, especially for the drones that charge faster. At 80 additional drones with less energy consumption, an e ect similar to the Braess Paradox can be observed again. More e cient drones need longer to deliver a package. What caused this e ect needs to be researched further.
It seems that additional drones with improvements can only help to a limited extent and the reduction in load is dependent on the topology. However, from Tables 1 and 2, it can be concluded that improving energy consumption is more bene cial than faster charging times. 5.1
It may be that the approach of improving the performance of the overall system by adding more powerful drones is wrong in a situation where the system is already operating at its capacity limit. Conceivably much better results can be achieved by replacing some of the regular drones with more capable drones. So that the system continues to have only 400 drones in operation.
For the delivery time of a parcel, Table 3 shows a clear advantage when using improved drones. On average, the systems with drones that consume less energy achieve better results than the systems with drones that can recharge their batteries faster. The mean delivery time for both improvements is better on average than in a system that relies only on regular drones. Compared to the trials with additional drones, replacing drones achieves lower average delivery times for both improvements. However, again some statistical anomalies can be seen in this table. Delivery time increased for drones that charged faster in the trials with 80 and 120 replaced drones. Such an e ect was not observed for drones that used less energy. Nevertheless, in a population of 120 improved drones, the improved e ciency of 30% less energy consumption brought only a minimal reduction in delivery time compared to an improved e ciency of 25%. Whether this is a statistical e ect or whether this is an e ect of Braess Paradox would have to be investigated in further simulations.
For the second topology, statistical e ects are once again observed in Table 4, which can possibly be explained by the low number of simulations for each trial. For example, a population of 12 drones charging 20% faster reduces the delivery time more than the same population charging 30% faster. However, this e ect could also be an analogy to the Braess paradox. Further research is needed here. Nevertheless, it can be said that replacing drones with a population of improved drones can reduce delivery times. The di erence between drones that recharge faster and drones that use less energy is not as pronounced as for topology one. In summary, replacing drones with improved drones brings an improvement in delivery times for our system. This approach is more promising than adding additional drones to a congested system and is a more intuitive strategy.
The third conceivable strategy to improve delivery times is to increase capacity at the hubs. In Section 4 it was described that this is only done at the two most congested hubs. To do this, we need to determine which ones are most congested. Since the warehouse has enough capacity, the most overloaded hubs are presumably the ones that come after the warehouse. Based on our model design, all drones must y to at least one of these hubs before ying to a customer. If we look at the waiting times per hub, this assumption is con rmed. For topology one, hubs one and three are the most crowded. In topology two, drones have to wait the longest at hubs one and two. The capacities at these hubs will now be increased for the trials.
This has an immediate e ect. Drones don't have to wait to charge at the hubs where capacity was increased. For topology one, the waiting times are distributed fairly evenly over the remaining hubs. The waiting times in topology two only shift to the level below hubs one and two. Now hubs three and four are congested but noticeably less. This can be explained by the depth of the tree spanned by topology two. These hubs are still in a position where they become bottlenecks. Still, in both topologies, the average delivery time of a parcel decreases.
In the case of topology one, we can see that the increase in capacity at the hubs is re ected in the delivery time. For 10%, 20% or 30% more capacity, the mean delivery time remains greater than using drones that consume less energy. Compared to the faster charging drones, however, the adjustments are advantageous. What is surprising is that a 100% increase in capacity brings only a small improvement over a 30% drone population that uses less energy. We expected a larger di erence.
We observed a similar reduction in mean delivery time for topology two as well. The improvement in hub capacity is bene cial for this topology in comparison to a drone population that charges faster. However, compared to drones that consume less energy, increasing capacity by 10%, 20% or 30% is not advantageous. Comparing to topology one, we see a clear improvement with a 100% increase in capacity over drone populations that use less energy. This is more in line with our expectation. But it also shows that there is a dependency between the degree of improvement in delivery times and the topology.
This paper presents a model for a drone-based parcel delivery system. We implemented this model using timed Petri nets. Subsequently, we performed simulations with the model to test di erent strategies for reducing the load on such a system.
Our results suggest that both increasing the capacity of charging stations and replacing regular drones with improved drones are valid strategies. Both approaches can reduce delivery time in a congested delivery system. As an upgrade to the drones, lower energy consumption was clearly found to be better. Faster charging drones reduced delivery time but only marginally. This result is consistent across all of our experiments. Simply adding drones, even if they are improved, to the system has not led to much improvement and in some cases to a degradation, so it does not play a role in the further evaluation.
The question of what can be done to reduce the load in a situation like this, which is important for the operation of such a system, can only be answered with reservations. Our results suggest that by replacing drones with better performing drones, delivery times can be reduced. The reduction is noticeable in comparison to doubling the capacity at particularly busy hubs, as it is greater than expected. In this context, economic considerations and the environment in which the system is embedded will play a key role in deciding. Since a drastic development like this is not always possible.
However, we also observe a dependency between the degree of improvement and the topology of the delivery system in our results. For the experiments, a broad and a deep topology were chosen to represent the two dimensions of a spanning tree. This does not seem to be su cient to determine if the dependency is only a statistical e ect or the topology really has an impact on the size of improvements in delivery time. Further simulation experiments in which the topologies are randomly generated could help shed light on this. 7
We would like to thank Torben Christian Schrader for his help in designing and implementing the model of our delivery system. A
Improving Drone-based Parcel Delivery