Research On Optimal Solution Of Cargo Distribution Problem With Three-dimensional Packing Constraint

Under the background of constructing a new economic development pattern with domestic circulation as the main body and domestic and international double circulation promoting each other,automobile cargo transportation has become a more important logistics transportation mode.The high cost of automobile cargo transportation is a practical problem to be solved urgently in the industry.Reducing the distribution cost is an important part of reducing the logistics transportation cost,and the cargo distribution problem with three-dimensional packing constraint can simulate most of the real-life cargo distribution activities,through solving the problem can guide the enterprise to develop the distribution plan,reduce the logistics cost,has high research value.The cargo distribution problem with three-dimensional packing constraints is composed of two classical NP-hard problems: vehicle routing problem and three-dimensional packing problem.The vehicle routing problem with capacity constraint(CVRP)is transformed into the cargo distribution problem with three-dimensional packing constraint(3L-CVRP)when the cargo distribution activities are studied by considering the shape attributes of the cargo and the specifications of the carriage.Some limitations of actual distribution activities should be taken into account in the study of this problem,such as the fragility of goods,the supporting area required for transportation,and the "last in,first out" of loading and unloading of goods.In this thesis,the algorithm used to solve the cargo distribution problem with threedimensional packing constraints is composed of three parts.Among them,tabu search algorithm is used to optimize the distribution route and solve the vehicle routing part of 3LCVRP.The local search algorithm is used to search the packing order,and the heuristic algorithm is used to complete the single container loading and solve the three-dimensional packing part of 3L-CVRP.The three parts are combined into the algorithm of this thesis in the following ways:The local search algorithm of packing order calls heuristic single container loading algorithm in the search process to judge whether all goods on a distribution route can be loaded into the truck according to the current packing order.The tabu search algorithm of optimized distribution routes calls the local search algorithm of packing order in the construction of initial solution and search process to judge whether the distribution routes generated at each stage are feasible.Tabu search algorithm should consider the three-dimensional packing constraint,so the number of distribution routes in the solution is likely to be more than the number of available vehicles,resulting in the solution is not feasible.In order to solve this problem,this thesis constructs a new optimization target for tabu search algorithm.In the new optimization objective,a large penalty factor is given to each distribution route that exceeds the number of available vehicles,in order to control the direction of tabu search,so that the tabu search algorithm for optimizing distribution routes gives priority to optimizing the number of distribution routes in the search process and finds the solution where the number of distribution routes is less than or equal to the number of available vehicles.In the local search algorithm of packing order,a new domain generation rule is proposed to increase the probability of finding the feasible packing order.The local search algorithm of packing order calls DBLF and MIS heuristic algorithms successively for single container loading.Among the two heuristic algorithms,DBLF algorithm is a common algorithm in the field of three-dimensional packing.In this thesis,DBLF algorithm is applied to 3L-CVRP.The algorithm places the goods in the most "bottom-left" position in the current action space,and can quickly complete the loading of single goods.DBLF is an efficient single container loading algorithm,but the space utilization is low.MIS algorithm is a single container loading algorithm proposed in this thesis.Based on the idea of "greedy" algorithm,MIS algorithm is used to judge the case that DBLF algorithm cannot complete the packing.The goal is to find the position that has the least influence on the movement space for the currently loaded goods.MIS algorithm can make better use of compartment space and achieve better packing effect.Finally,data set G27 proposed by Gendreau et al.is calculated to verify the effectiveness and optimization effect of the proposed algorithm.