Data Mining Based Research On Optimization Algorithm For Container Relocation During Loading Operations

Sea transportation occupies an extremely important position in the transport system and is an important transport channel for import and export trade.With the continuous increase of cargo volume,the number of terminals continues to increase,and the competition between terminals is becoming fiercer.The operational efficiency of container terminals is an important index to measure their competitiveness,among which the efficiency of container loading is an important factor to the throughput of terminals.In reality,due to the customer's requirements on the service time,as well as weather factors,berth depth and so on,the container loading efficiency is increasingly crucial.As the container arrives at the terminal randomly,its stacking situation in the yard can't fully meet the requirements of the loading plan,thus relocation operation is inevitable,that is to say,we need to relocate the current blocking container to other stacks.Under the same conditions,a group of operations with fewer relocation operations tend to have shorter operation time,which can greatly improve the efficiency of loading.Therefore,our goal is to give a sequence of operations aiming at minimizing the relocation operation number when given container retrieving order.In this paper,a new and more compact upper bound is proposed.We use the look-ahead method to get upper bound,all feasible nodes are obtained by fully branching in the front D layers,and the minimum upper bounds among these nodes is taken as the final upper bound.In order to overcome the exponential growth of nodes number by the increase of the problem scale,we extract features from the exact solution of small-scale problems,and construct a pruner through data mining to improve the upper bound calculating efficiency of large-scale problems.In this paper,we construct pruners based on random forest and association rules,among which association rule pruner is mainly used to overcome the drawbacks of high calculation cost and inadequate precision in the practical application of random forest pruner.Aiming at the problem studied,an improved branch-and-bound algorithm is proposed to obtain exact solutions as well as an improved beam search algorithm to obtain heuristic solutions in short time for large-scale problems.Both algorithms use the proposed new upper bound.In the exact algorithm,we change the original lower bound priority branching strategy to the upper bound priority branching strategy and improve the original aimless search method.In the heuristic algorithm,we use the upper bound as a criterion to judge whether the nodes are reserved or not.In order to further improve the effectiveness of the algorithm,several unpromising node deletion rules are proposed and a different method to selection nodes with the same upper bound is established.the verification of new upper bound is given by detailed numerical experiment,and it shows that the pruner can help improve the calculation efficiency.The comparison proves that the upper bound priority branch method and targeted search strategy explore fewer nodes when finding exact solutions.Experiments on heuristic method show that the upper bound with associated branch pruner performs best in combination of relocation number and algorithm running time.The proposed unpromising node deletion and method to break tie are also verified and sensitivity analysis of branch depth D and beam width W are also given in this paper.