Research On Three Dimensional Packing Algorithm And Its Application In Vehicle Routing Problem

As a classic combinatorial optimization problem and an NP-hard problem,the research on three-dimensional packing algorithms at home and abroad has been going on for many years and achieved good results.To solve this problem,we propose a hierarchical search algorithm with eight loa.ding reference lines,which adds the matching degree between the block(box)height and the load reference lines of the residual space when selecting the block and the residual space.The experimental results show that even in the case that the space loading rate has reached a very high level,compared with the current optimal algorithm,the algorithm has made some breakthroughs in some data sets.As another NP-hard problem,the vehicle routing problem plays an important role in the logistics industry.We apply the hierarchical search algorithm with eight loading reference lines to the 3L-CVRP that combines the three-dimensional pa.cking problem and the vehicle routing problem.For the constraints of fragility and stability,a variety of dif'ferent residual space types and positions when placing the box are considered.On t.he basis of satisfying the three-dimensional loading constraint,the approximate optimal path solution is constructed by using neighborhood search and tabu search algorithm.The experimental results show that the algorithm can surpass or be equal to the currently known optimal algorithm in most test cases in the total cost of the final path.In real life,the vehicle routing problem with time windows and three-dimensional loading constraints is more difficult to solve.To deal with this problem,we first propose a new three-dimensional container loading grouping algorithm to ha.ndle the loading constraints.By adding a strategy of adjusting the order of the boxes inside each customer,the loading efficiency of the three-dimensional container is improved as a whole.Based on this,a hybrid algorithm combing tabu search and artificial bee colony is used to generate the approximate optimal path.The experimental results show that the proposed method has significa.nt improvements in the final total cost,the number of vehicles used and the running time compared with the latest relevant research results.