Research On Aerial-Ground Collaborative Routing Problems For Logistics Based On Multi-Objective Optimization Algorithms

The aerial-ground collaborative logistics mode that combines the advantages of the aerial unmanned vehicle(UAV)and the ground vehicle would be a promising choice for increasing efficiency and reducing the cost of logistics companies.Designing reasonable aerial-ground collaborative routes is crucial to the implementation of the aerial-ground collaborative logistics mode.Current studies mainly investigate the aerialground collaborative routing problems that consider only an optimization objective such as delivery cost and delivery time.However,the decisionmaking of logistics companies in practical applications should consider the benefits of companies,customers,and employees simultaneously,which yields multi-objective optimization demands.Therefore,by summarizing the application modes and work process of aerial-ground collaborative logistics,this dissertation builds a decision-making framework for lastmile logistics.Based on the above works,this dissertation investigates three multi-objective aerial-ground collaborative routing problems and corresponding solution methods for three common last-mile logistics scenarios.The main contributions and novelties are summarized as follows:(1)This dissertation investigates a multi-objective aerial-ground collaborative routing problem considering soft time windows.In this problem,multiple UAVs and a ground vehicle are used to provide delivery services,and the delivery time instance is allowed to be earlier or later than the time windows expected by customers.By considering minimum transportation costs and maximum customer satisfaction as optimization objectives,this dissertation constructs a mixed integer programming model and proposes a corresponding multi-objective evolutionary optimization algorithm hybridizing a Pareto local search(HMOA).Based on the knowledge of the problem,this dissertation designs the problem-specific solution representation,initial solution construct method,neighborhood structures,genetic operations,as well as an improved Pareto local search for the proposed algorithm.Meanwhile,this dissertation designs an adaptive mechanism to combine local search and global search.Finally,based on a random benchmark and a real-world data-generated instance,this dissertation verifies the proposed algorithm and discusses routing schemes selected by different preferences as well as the impacts of the soft time window on routing results.(2)This dissertation studies a multi-objective aerial-ground collaborative routing problem considering delivery and pick-up services.This problem not only assumes that multiple UAVs and a ground vehicle are used to provide logistics services but also allows UAVs to visit multiple customers in a flight with precedence constraints,to provide delivery,pickup,as well as simultaneous delivery and pick-up services to customers.By considering three objectives simultaneously,including transportation costs,service stability,and waiting time between UAVs and the ground vehicle,this dissertation proposes the corresponding mixed integer programming model and a multi-objective evolutionary optimization algorithm based on objective space decomposition and resource allocation(ODEA-ARA).The proposed algorithm decomposes the objective space into a set of subspaces to maintain the diversity of the population.Meanwhile,the algorithm adopts a resource allocation strategy to give more computational resources to the subspaces that have more potential to be improved,thereby striking a good balance between convergence and diversity.Finally,this dissertation verifies the proposed algorithm based on a random benchmark and a real-world data-generated instance.Furthermore,several managerial insights are presented by analyzing the impacts of the drone number on algorithm results.(3)This dissertation investigates a multi-objective aerial-ground collaborative routing problem considering the ground vehicles that allow swapping batteries.In this problem,multiple electric vehicles and multiple UAVs are implemented to provide delivery services.The UAVs can provide services to multiple customers in a flight and the ground vehicles need to refresh their batteries at battery swap stations.By considering minimum transportation costs and work-time balance among different fleets as optimization objectives,this dissertation constructs a mixed integer programming model and proposes a parallel multiple adaptive large neighborhood search algorithm(PMALNS).Based on the divide and conquer strategy,the proposed algorithm divides a multi-objective optimization problem into a set of independent sub-problems and solves these sub-problems in parallel to improve the coverage speed.For each sub-problem,this dissertation proposes an adaptive large neighborhood search to conduct the local search and ensembles the scalar objective function-based and Pareto dominance-based methods to guide the movements of the local search.Finally,extensive experiments on the wellknown benchmark verify the performance of the proposed algorithm.Moreover,the method of selecting a reasonable routing scheme from a set of routing schemes without providing preference information is discussed.The work of this dissertation would accelerate the real-world application of the aerial-ground collaborative logistics mode,and enrich the variants of aerial-ground collaborative routing problems as well as the research of multi-objective combinatorial optimization theories.