An improved variable neighborhood search for parallel drone scheduling traveling salesman problem

Parallel drone scheduling traveling salesman problem (PDSTSP) is a typical optimization problem of the truck-drone hybrid delivery system and hardly solved by using meta-heuristics. In this study, an improved variable neighborhood search (IVNS) is presented to minimize the completion time of all vehicles for serving all delivery tasks. Three methods based on the longest processing time (LPT) rule and two reduced variable neighborhood search (RVNS) algorithms are used to produce an initial solution. Then IVNS based on a shaking method and an adaptive RVNS is used to improve the initial solution. 20 neighborhood structures are proposed, 14 of which are used to assign customers between the truck and drones. A number of experiments are conducted on 90 instances. The results reveal that IVNS is very competitive for PDSTSP and obtains state-of-the-art solutions of 12 instances. (C) 2022 Published by Elsevier B.V.