Research On Vehicle Routing Problem In Tandem With Drones Basesd On Artificial Bee Colony Algorithm

Due to the rapid development of drone technology,the application of drones in logistics,aerial photography,traffic monitoring and other fields is becoming more and more popular.To cut completion time and operational cost,more and more logistics and e-commerce companies are using drones for "last-mile delivery".The introduction of drones into conventional truck delivery gives rise to truck-drone hybrid delivery.It combines the advantages of truck including large capacity and long range as well as those of drone like high speed and not restricted by terrain,and has received much attention in recent years.In this thesis,two types of vehicle routing problems in tandem with drones are studied one by one: traveling salesman problem with drone(TSP-D)and vehicle routing problem with drones(VRP-D).They are common optimization problems for truck-drone hybrid delivery and the latter is an extension of the former.The mathematical models of the above two problems are formulated and two new artificial bee colony(ABC)algorithms are developed to solve them respectively.A number of experiments are conducted and the computational results demonstrate the effectiveness of the algorithms.The main contents of this thesis are listed below:(1)The research background and significance of the problems are introduced.The research status of TSP-D and VRP-D at home and abroad and the application of ABC algorithm in routing problem are summarized.The theoretical basis of intelligent optimization algorithm is described.The basic concepts of ABC algorithm and multi-objective optimization problem related to the work of this thesis are introduced emphatically.(2)TSP-D is addressed and a new bi-directional artificial bee colony(BABC)is developed to minimize completion time and operational cost simultaneously,in which a coding method with a truck’s path and a set of drone nodes is used and an effective decoding is presented.Bi-directional communication is constructed between employed bees and onlooker bees and the differentiated search processes are implemented on these two groups of bees.Food source of onlooker bee is selected in a dynamic way.A number of experiments are conducted and the computational results reveal that BABC has good performance on TSP-D.(3)VRP-D is studied and a dynamical artificial bee colony(DABC)is employed to minimize the overall operational cost.Two bee swarms are produced in the initialization and an effective evaluation process is used to determine employed bee swarm and onlooker bee swarm dynamically in the subsequent search process.Variable neighborhood descent(VND)is constructed by using 15 neighborhood structures and adopted in employed bee phase and onlooker bee phase in different ways.A number of experiments are conducted on 112 instances and the computational results reveal that DABC provides new best known solutions for 37 instances and has promising advantages on VRP-D.