Research On Models And Algorithms Of Urban Terminal Distribution Under Two Distribution Modes

With the rapid development of e-commerce and the upgrading of consumption structure,more and more consumers are inclined to do online shopping,which promotes the development of logistics and distribution.As a key linking to realize door-to-door logistics,the timeliness of urban logistics terminal distribution directly affects the improvement of consumer satisfaction.However,with the continuous growth of the demands for delivery,the distribution service of enterprises easily reduces the distribution efficiency and the utilization rate of vehicles,which affects the delivery quality of enterprises and the service experience of consumers.Based on this fact,considering the enterprises’ operation costs and customer time elasticity,this dissertation aims to optimze the urban terminal distribution routes by analyzing orders’ characteristics under the third-party distribution mode and under self-operated distribution mode respectly.The problem is addressed by analyzing the characteristics,constructing models and proposing algorithms,and the main research results are as follows:Firstly,a routing problem under the third-party distribution mode was studied,according to the characteristics of urban terminal distribution under the third-party distribution mode.Many factors including the known supply position and delivery position,order release dates,customer time flexibility,vehicle restrictions were considered.Two mixed integer linear models were constructed.Moreover,a mixed tabu search algorithm was proposed to solve this problem.Experiments results turned out that the mixed tabu search algorithm not only can obtain high quality solutions for the large-scale problem,but also can solve effectively the classic pickup and delivery vehicle routing problem.Secondly,three valid inequalities were proposed and an improved branch-and-cut algorithm was developed to obtain optimal routes in view of the above problem.Experiments results showed that the proposed algorithm not only can obtain optimal solution for small and medium scale instances,but also provide high quality lower bounds or optimal solutions for pickup and delivery routing problem with time windows,which verifies the effectiveness of the exact algorithm.Thirdly,according to the characteristics of urban terminal distribution under selfoperated distribution mode,a routing problem under self-operated distribution mode was studied.This problem considered multiple factors including random customer position,order release dates,flexible time windows,time delay penalty mechanism,multi-vehicles,limited vehicle endurance.Its objective was to decide when vehicles would start delivery and to optimize vehicle routes.A mixed integer linear model was established and an improved tabu search algorithm was proposed to quickly solve this problem.Experimental results showed that the heuristic algorithm not only provides high quality solutions to the studied problems in a short time,but also solves effectively similar problems.Fourthly,six valid inequalities were developed to improve the performance of the proposed model.And an improved branch-and-cut algorithm was proposed to solve the urban terminal distribution routing problem under self-operated distribution mode.This algorithm could obtain the optimal solutions and accurately evaluate the influence of related factors such as the number of vehicles on operating costs.Experimental results showed that the improved branch-and-cut algorithm can obtain optimal solutions for small and medium scale problems;and it also can solve related problems to prove its effectiveness.