Research On Vehicle Routing Problem With Cross-Docking And Three-Dimensional Loading Constraints

Chinese logistics industry currently has prominent problems such as high logistics costs,low efficiency,and waste of resources.Therefore,reducing transportation costs and improving logistics distribution efficiency are of great significance for reducing overall logistics costs and improving the quality of logistics services.As a relatively new distribution strategy,cross-docking has significant advantages in improving logistics and distribution efficiency,reducing inventory costs,and accelerating cargo turnover.Based on this realistic background,this thesis studies the vehicle routing problem with crossdocking and three-dimensional loading constraints(3L-VRPCD).The main research outputs are summarized as follows:Firstly,this thesis investigates the many-to-many vehicle routing problem with cross-docking,and a mixed integer linear programming model is proposed,aiming to minimize the transportation cost.Furthermore,an adaptive large neighborhood search(ALNS)algorithm is proposed to solve this problem,and a large number of instances with respect to various characteristics are generated.Based on these instances,the impacts of different characteristics of the problem on the scheduling scheme are analyzed,such as node distribution location density,location of cross-dock center,supply-demand ratio.Experimental results show that a smaller supplier-customer supply-demand ratio is beneficial to reduce the total cost of distribution.The simulation results illustrate that when the cross-docking facility is located at the center of the distribution network can achieve the reduced transportation cost.Secondly,the vehicle routing problem with three-dimensional loading constraints(3L-CVRP)is studied.The basic concepts of the threedimensional bin packing problem and 3L-CVRP are described.According to the characteristics of 3L-CVRP,an ALNS algorithm is proposed to optimize the routing part,and a packing heuristic incorporating local search strategy is proposed to solve packing sub-problem.Experimental results demonstrate that the local search strategy can significantly enhance the performance of the packing heuristic.Finally,the vehicle routing problem with cross-docking and threedimensional loading constraints(3L-VRPCD)is investigated.Considering the three-dimensional loading,cross-docking and vehicle routing constraints,a mixed integer linear programming model is proposed,aiming to minimize the transportation cost.To efficiently solve the medium-and large-scale instances,a hybrid heuristic method that incorporates the ALNS and multi-order local search packing(LSP)algorithm(i.e.,ALNSLSP)is proposed.To verify the correctness of the model and performance of the algorithm,a large number of experiments are conducted based on the different scale instances.Computational experiments show that the proposed ALNS-LSP algorithm has strong stability and each operator of ALNS is beneficial to the solving process.There are altogether 26 figures,14 tables and 101 items of bibliography in the thesis.