Research On Multi-objective Routing Optimization Problem In City Logistics Dispatching

With the progress of technology and the transformation of the national consumption pattern,the logistics industry has developed rapidly and has become the basic industry supporting the national economic development,which is regarded as the accelerator to promote the national economic development.As the most important part of the cost in the logistics system,city logistics distribution has attracted more and more attention.However,the urban distribution environment is complex and has many restrictive factors.For example,the difficult and expensive parking situation in urban area,expensive rental fees and daily changes of customer demand in metropolitan areas,and speeds of delivery to customers are increasingly demanding in urban dispatching,which make urban distribution optimization face higher challenges,and it is urgent to explore new city distribution mode.Moreover,most of the existing works generally consider the optimization from a single aspect,e.g.,the delivery company,while the sustainable development of a logistics company must also focus on other subjects in logistics activities,such as customers,delivery employees and environment.It is essentially a multi-objective optimization problem.Based on above discussion,this thesis focuses on city logistics distribution and aims to reduce cost and increase efficiency.Combined with the characteristics of city dispatching,this thesis studies the route optimization problem of city direct and two-echelon distribution,establishes the corresponding multi-objective mathematical model and optimization algorithm.The main work of this thesis are as follows:(1)Considering the issue of the difficult and expensive parking situation in urban area,this thesis introduces a multi-objective vehicle routing problem with time window(VRPTW)model for city logistics dispatching,which optimizes cost and vehicle waiting time simultaneously,and proposes a decomposition-based multi-objective variable neighborhood descent algorithm(D-VND)to solve the multi-objective VRPTW.In D-VND,the multi-objective VRPTW is decomposed into multiple single-objective sub-problems via a set of uniformly distributed weight vectors and then the route-based evolutionary operator is used to generate the offspring.Meanwhile,the objective-wise neighborhood operators are incorporated into the variable neighborhood descent method as local searches to improve qualities of sub-problems.Moreover,we adopt a heuristic initialization strategy and an external archive mechanism based on fast sorting and crowding distance methods to improve the performance of D-VND.Experimental results on benchmarking datasets with different scales show that D-VND outperforms two other representative algorithms regarding convergence and diversity and yields better solutions.Also,the necessity of optimizing vehicle waiting time is verified.(2)Considering the issue of the expensive rental fees and daily changes of customer demand in metropolitan areas,this thesis proposes a two-echelon city dispatching model with mobile satellites(2ECD-MS)for the first-time which locations of mobile satellites change according to demands of customers to ensure the efficiency of delivery routes in every day.Then,the multi-objective 2ECD-MS mathematical model is constructed with each part of the cost as the objective,and a cluster-based variable neighborhood search algorithm is proposed to determine locations of mobile satellites and dispatching routes of trucks and tricycles.Next,the 2ECD-MS is extended to 2ECD-MS-TDD to allow trucks dispatching directly(TDD)for further cost reduction.Experimental results show that the 2ECD-MS significantly reduces the total cost against the model using fixed satellites mode by 3.5% while the 2ECD-MS-TDD further reduces the total cost against the 2ECD-MS significantly by 3.25% in 54 cases with different customer scales,geographical scopes,and distribution types.These show the superiority of the proposed methods in cost reduction for city logistics in comparison to the traditional fixed model.(3)Considering the issue of speeds of delivery to customers are increasingly demanding in urban dispatching,this thesis extends the 2ECD-MS to the 2ECD-MS-CS by adopting the crowd-shipping model in the second-echelon dispatching,which uses occasional drivers of private vehicles to deliver parcels to improve the delivery speed.Then,we define a multiobjective model considering company cost,customer satisfaction,income satisfaction of crowd-shippers,customer time window and two-echelon synchronization constraints simultaneously.The multi-objective of the 2ECD-MS-CS is solved by a multi-directional evolutionary algorithm(MDEA).In the MDEA,multiple neighborhood operators are designed and combined with the multi-directional search strategy to fully explore the Pareto Front.Finally,we generate 40 new 2ECD-MS-CS instances based on existing common vehicle routing datasets.Experimental results show that the 2ECD-MS-CS reduces the average cost by 3.4%and improves the delivery speed by 42% against the 2ECD-MS in 40 instances with different customer scales,numbers of mobile satellites,and geographic scopes.The proposed MDEA outperforms several popular multi-objective optimization algorithms in both convergence and diversity.These illustrate the advantages of the 2ECD-MS-CS especially in terms of delivery speed and the effectiveness of the proposed MDEA.