The use of trucks and drones as a solution to address last-mile delivery challenges is a new and promising research direction explored in this paper. The variation of the problem where the drone can intercept the truck while in movement or at the customer location is part of an optimisation problem called the vehicle routing problem with drones with interception (VRPDi). This paper proposes an evolutionary algorithm to solve the VRPDi. In this variation of the VRPDi, multiple pairs of trucks and drones need to be scheduled. The pairs leave and return to a depot location together or separately to make deliveries to customer nodes. The drone can intercept the truck after the delivery or meet up with the truck at the following customer location. The algorithm was executed on the travelling salesman problem with drones (TSPD) datasets by Bouman et al. (2015), and the performance of the algorithm was compared by benchmarking the results of the VRPDi against the results of the VRP of the same dataset. This comparison showed improvements in total delivery time between 39% and 60%. Further detailed analysis of the algorithm results examined the total delivery time, distance, node delivery scheduling and the degree of diversity during the algorithm execution. This analysis also considered how the algorithm handled the VRPDi constraints. The results of the algorithm were then benchmarked against algorithms in Dillon et al. (2023) and Ernst (2024). The latter solved the problem with a maximum drone distance constraint added to the VRPDi. The analysis and benchmarking of the algorithm results showed that the algorithm satisfactorily solved 50 and 100-nodes problems in a reasonable amount of time, and the solutions found were better than those found by the algorithms in Dillon et al. (2023) and Ernst (2024) for the same problems.

We address the problem of routing a team of drones and trucks over large-scale urban road networks. To conserve their limited flight energy, drones can use trucks as temporary modes of transit en route to their own destinations. Such coordination can yield significant savings in total vehicle distance traveled, i.e., truck travel distance and drone flight distance, compared to operating drones and trucks independently. But it comes at the potentially prohibitive computational cost of deciding which trucks and drones should coordinate and when and where it is most beneficial to do so. We tackle this fundamental trade-off by decoupling our overall intractable problem into tractable sub-problems that we solve stage-wise. The first stage solves only for trucks, by computing paths that make them more likely to be useful transit options for drones. The second stage solves only for drones, by routing them over a composite of the road network and the transit network defined by truck paths from the first stage. We design a comprehensive algorithmic framework that frames each stage as a multi-agent path-finding problem and implement two distinct methods for solving them. We evaluate our approach on extensive simulations with up to $100$ agents on the real-world Manhattan road network containing nearly $4500$ vertices and $10000$ edges. Our framework saves on more than $50\%$ of vehicle distance traveled compared to independently solving for trucks and drones, and computes solutions for all settings within $5$ minutes on commodity hardware.

In this paper, we study novel variants of the well-known two-echelon vehicle routing problem in which a truck works on the first echelon to transport parcels and a fleet of drones to intermediate depots while in the second echelon, the drones are used to deliver parcels from intermediate depots to customers. The objective is to minimize the completion time instead of the transportation cost as in classical 2-echelon vehicle routing problems. Depending on the context, a drone can be launched from the truck at an intermediate depot once (single trip drone) or several times (multiple trip drone). Mixed Integer Linear Programming (MILP) models are first proposed to formulate mathematically the problems and solve to optimality small-size instances. To handle larger instances, a metaheuristic based on the idea of Greedy Randomized Adaptive Search Procedure (GRASP) is introduced. Experimental results obtained on instances of different contexts are reported and analyzed.

This paper addresses the Traveling Salesman Problem with Drone (TSP-D), in which a truck and drone are used to deliver parcels to customers. The objective of this problem is to either minimize the total operational cost (min-cost TSP-D) or minimize the completion time for the truck and drone (min-time TSP-D). This problem has gained a lot of attention in the last few years since it is matched with the recent trends in a new delivery method among logistics companies. To solve the TSP-D, we propose a hybrid genetic search with dynamic population management and adaptive diversity control based on a split algorithm, problem-tailored crossover and local search operators, a new restore method to advance the convergence and an adaptive penalization mechanism to dynamically balance the search between feasible/infeasible solutions. The computational results show that the proposed algorithm outperforms existing methods in terms of solution quality and improves best known solutions found in the literature. Moreover, various analyses on the impacts of crossover choice and heuristic components have been conducted to analysis further their sensitivity to the performance of our method.

The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones, present substantial application opportunities in several industries in the last years. Notably, the logistic companies gave close attention to these vehicles envisioning reduce delivery time and operational cost. A variant of the Traveling Salesman Problem (TSP) called Flying Sidekick Traveling Salesman Problem (FSTSP) was introduced involving drone-assisted parcel delivery. The drone is launched from the truck, proceeds to deliver parcels to a customer and then is recovered by the truck in a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic that the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the General Variable Neighborhood Search is used to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve the delivery time significantly. Furthermore, we provide a new set of instances based on well-known TSPLIB instances.

Tekcapital PLC (LON:TEK) has licensed a patent developed by the Florida Agricultural and Mechanical University that could be the backbone of software for autonomously controlling cars, trucks and drones using artificial intelligence. The company, which is wrapping the intellectual property into its Guident business, says the technology may one day be used to develop an app that will dispatch vehicles to find a parking spots and then retrieve them again. Ford chief executive Jim Hackett spoke recently of solving that exact problem. "You waste more time trying to find a parking place than you do being stuck in traffic," he said. "That's because you're trying to match the open parking place with where the car needs to go. We have a dream where they can actually tell each other that. The car and the parking spot are talking to each other. The autonomous vehicles market is forecast to grow at a compound annual rate of almost 40% in the next 10 years and is expected to be worth US$127bn by 2027. No financial details of the Tekcapital patent deal were given. The company's chairman, Clifford Gross, said; "We are excited that Guident has acquired the exclusive rights to this novel IP aimed at improving the utility of autonomous vehicles.