A new variant of the delivery and pickup transportation problem called mixed delivery and pickup routing problem with unmanned aerial vehicles in case of limited flow is introduced. The objective is to minimize operational costs including total transportation costs and service time at each point. This variant is a solution for the urban congestion, and consequently, it is an improvement of the general transport system. First, the problem is formulated mathematically. It is considered as NP-hard; therefore, the authors proposed an iterated local search algorithm to solve the problem of mixed pickup and delivery without drone. Then, a vehicle first-drone second algorithm is used to solve the mixed delivery and pickup problem with drone. The performance of the method is compared through numerical experiments based on instance derived from the literature as well as on a set of randomly generated instances. Numerical results have shown that proposed metaheuristic method performs consistently well in terms of both the quality of the solution and the computational time when using drone with vehicle.
TopI. Introduction
The distribution of goods is a very important activity in supply chains. This activity, often managed by third-party logistics companies, can be achieved through different transportation modes including the road, air, rail, etc. The road goods transportation is one of the most flexible means to transport goods since the goods are loaded directly to the truck and transported to the place of destination. Note that in 2015, “the road freight transportation accounts for 69.6% of the total freight transported between France and EU countries” (Ministry Of Transition Ecological and Solidarity of France). In the past, goods transportation activities were simple activities of distribution of goods from a distribution center to customers (Labadi et al., 2008) or a collection of commercial goods from facility plants to a depot (Kim et al., 2006). In recent years, with an increasing challenge to provide a higher service quality while reducing the operational costs, goods transportation activities have evolved to more complex activities that consist in delivering/picking up goods to/from many customers by means of multiple vehicles from/to a central depot. Freight transportation has received increasing attention of many researchers and has been the source of the enormous work in the literature of the pickup and delivery problems. From the practical point of view, one of the main objectives of industrial companies is to improve the efficiency of their supply chains so that they can organize better service at lower cost as well as the fluidity of the flow of their goods. Habitually, to handle these tasks vehicles have been used. A new method has recently used where unmanned aerial vehicles known as Drones, are chosen to serve small goods. It’s important to distinguish between military and non-military use of drones. Michael Toscano, president of the association for Unmanned Vehicle Systems International, is quoted in the Washington Times saying, “The word [drone] instantly conjures up mental images of large predators firing missiles at hostile targets around the world”. Until recently, media coverage has focused mainly on military use, coining the term ‘drone’ and leaving many with negative attitudes towards this new technology. There are many advantages of using drone for distribution: it avoids the congestion of traditional road networks, it can be operated without human being, it has much lower transportation costs per kilometre (Wohlsen, 2014), and it is faster than vehicles. However, it has also disadvantages: drone’s flight distance and lifting power are limited because it is powered by batteries.
The purpose of this report is to provide a study to this exciting topic, present use cases from a broad variety of industries, and discuss potential applications in and for the logistics industry. We aim to show the role of the drone in improving the transport service in order to provide a realistic assessment of UAVs. “German postal and logistics group Deutsche Post DHL recently announced that their Parcelcopter, has been authorized to deliver medical supplies to a car-free-island off the coast of Germany” (see Fig.1)(Bryan, 2014).
Figure 1. DHL's Parcelcopter (source: dhl.com)
The remainder is organized as follows. An overview of the relevant literature that deals with the general vehicle routing problem with drone and some solution approaches are presented in Section 2. We provide aF definition, a description and a mathematical formulation of the new variant in Section 3. Our metaheuristic solution method is described in Section 4. Section 5 is devoted to a computational study of the method and the numerical results. Finally, the conclusions of our research and some natural extensions for further work are presented in Section 6.