David Sanchez-Wells¹ and Pedro L. Gonzalez-R¹

¹ Department of Industrial Engineering and Management Science. School of Engineering, University of Seville, Seville, Spain

davsanwel@alum.us.es, pedroluis@us.es

Keywords: Drones, Logistics, Optimization.

1. Introduction

Once the technological and economic viability of UAVs in the mass market has been achieved, sectors in which last mile logistics has a great weight within their operating costs have shown to be making great efforts to progress in the implementation of the use of UAVs in their ecosystem. Our research is focused on the last mile collaborative logistics between a truck and several drones with limited autonomy, wherein both the truck and the drones make deliveries simultaneously and the drones use the truck as a mobile battery change station that allows them to fully recover their autonomy.  We propose an optimization-based approach to this problem and develop an iterated greedy heuristic supported in turn by a bivector coding based on a binary approach as and efficient method for its resolution.

2. Literature review

The main reference for our research is the one truck – one drone approach from González-R et al. [1], whose problem is called TDTL (Truck-Drone Team Logistic), in which both vehicles synchronize and cooperate to satisfy the service plan without an initially predefined route or any restriction on the type of vehicle that can visit certain nodes. The truck acts simultaneously as a courier and a mobile battery change station for the drones, and a tuple-based encoding of sequence vectors is used for the encoding of the problem, which we will develop for our multi-drone case.

3. Problem description

During the delivery process, the drones use the truck as a mobile battery change station that allows them to fully recover their autonomy. The problem to solve assumes the following: 1. All nodes must be visited, using the truck or a drone; 2. The service starts at a source node and ends at a destination node; 3. If a node is visited by a drone and the truck, the drone performs a battery change and fully recovers its autonomy; 4. The drone is considered to have a higher speed than the truck.

4. Problem analysis and resolution

The coding of the TDTL problem is here modified to cope with the k-drones’ case. For this purpose, a binary transformation is used in order to maintain the bivector tuple structure, defined as follows. Our problem will be henceforth referred as TMDTL.

In [1] it is established that every solution 𝜋 is encoded with a tuple formed by two vectors, 𝜋𝑡 and 𝜋s. The vector 𝜋𝑡 is called resource vector, and it establishes the type of vehicle that performs the visit to the node. The vector 𝜋s, called node vector, defines the order in which these visits are performed. In our multiple drones’ case, as we need to express the possibility of multiple vehicles visiting the same node while maintaining the simplicity of the bivector tuple, we stablish a binary correspondence between a vehicles 1s and 0s vector and its decimal interpretation of this binary vector values join.

Due to its similarity with sequencing problems, this new codification for the TMDTL problem is introduced in an internally developed adaptation of an iterative greedy heuristic, efficiently used in permutation planning problems [2]. The heuristic is globally guided by a simulated annealing algorithm. Once the vehicles speed and the drones’ autonomy has been defined, the heuristic is ready to go and produce fast and high-quality results.

5. Experimentation

Our experiment solves a 20 clients uniform instance using from 1 to 4 drones. As expected, the use of the developed iterated greedy heuristics has led us to achieve the fast resolution of the challenging TMDTL. It is observed that a smaller temperature gradient in the simulated annealing algorithm does not necessarily imply better results.

6. Conclusions

A resolution method for the TMDTL problem is validated. Benefits from this method are its flexibility and speed of resolution. Its main limitation is that it only contemplates using one truck. Further research may rely on including several trucks or additional functions for the drones. No similar problems have been solved yet, so a fair comparation is not possible at this moment.

7. References

1. P. L. Gonzalez-R, D. Canca, J. L. Andrade-Pineda, M. Calle y J. M. Leon-Blanco, «Truck-drone team logistics: A heuristic approach to multi-drop route planning,» Transportation Research Part C, vol. 114, pp. 657-680, 2020.
2. R. Ruiz and T. Stützle, «A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,» European Journal of Operational Research, vol. 44, nº 3, pp. 2033-2049, 2007.