Vehicle routing in drone-based package delivery services

摘要

The Industry 4.0 enables the operation of new logistics equipment and new logistic solutions based on cyber-physical systems. The usage of new transport devices is discussed in this article in case of the Vehicle Routing Problem. In basic Vehicle Routing Problems, the demands of customers must be served. This article discusses a new Vehicle Routing Problem where drones are also used to improve the flexibility, reliability and cost efficiency of the whole last-mile solution. During the problem, a drone is assigned to the truck performing package delivery services, and some customers are visited by the truck while the drone is sent to certain customers located in the near environment of the truck. The drone has a capacity limit, so it is able to visit only a limited number of customers. After visiting the customers, the drone recovers the goods from the truck and serves the demands of new customers. In this article, the above mentioned problem is solved with construction and improvement algorithms. The construction algorithms are the Nearest Neighbour Algorithm and Arbitrary Insertion Algorithm, the improvement algorithms are the Genetic Algorithm and the Hill Climbing Algorithm.