Metaheuristic algorithm for solving the multi-objective vehicle routing problem with time window and drones
Yunqi Han, Junqing Li, Zhengmin Liu, Chuang Liu, Jie Tian
Abstract
In some special rescue scenarios, the needed goods should be transported by drones because of the landform. Therefore, in this study, we investigate a multi-objective vehicle routing problem with time window and drone transportation constraints. The vehicles are used to transport the goods and drones to customer locations, while the drones are used to transport goods vertically and timely to the customer. Three types of objectives are considered simultaneously, including minimization of the total energy consumption of the trucks, total energy consumption of the drones, and the total number of trucks. An improved artificial bee colony algorithm is designed to solve the problem. In the proposed algorithm, each solution is represented by a two-dimensional vector, and the initialization method based on the Push-Forward Insertion Heuristic is embedded. To enhance the exploitation abilities, an improved employed heuristic is developed to perform detailed local search. Meanwhile, a novel scout bee strategy is presented to improve the global search abilities of the proposed algorithm. Several instances extended from the Solomon instances are used to test the performance of the proposed improved artificial bee colony algorithm. Experimental comparisons with the other efficient algorithms in the literature verify the competitive performance of the proposed algorithm.