Optimal Research On Sequencing And Bin Packing Problem With Uncertain Collection Process Of Containers

The containership stowage mainly involves the ship stowage in full route and single node port ship stowage,the latter is the basis of the former research.Single node port ship stowage plan involves decision of the master bay plan and the slot plan,the slot plan is divided into single destination port and mixed destination port,the former is a special case of the latter.This paper taking the decision of the slot plan in single node port ship stowage as the research object,considering the impact of uncertain events such as the provisional customs inspection and the lag or absence of information,describing decision of the slot plan as the bin packing problem,combining the yard delivery order decision into decision of the slot plan,proposing a kind of sequencing and bin packing problem with uncertain collection process of containers.This paper adopt the idea of hierarchical progression.Firstly,the mathematical model and optimization algorithm of the sequencing and bin packing problem under certain collection process are constructed.And then,the multi stage rolling planning theory is introduced on this basis,the model and solution algorithm for the sequencing and bin packing problem with uncertain collection process of containers are constructed.Finally,the simulation results are compared with the branch and bound algorithm in the commercial optimization software CPLEX to verify the research results of this paper.The main researches of this paper are as follows:(1)Optimal research on sequencing and bin packing problem.Taking the process of practical vessel stowage as the research object,using the Bay in ship as a container for loading containers,combining the stacking rules and operation of the yard,this paper concluded the sequencing and bin packing problem.Present an Integer Linear Programming model with the realistic consideration of port and ship,the model considers these constraints such as retrieving sequence,weight grade,destination port,blocking container and stress limit.The software CPLEX is used to solve the model,the correctness of the model is verified,and the model is improved according to the optimization results.For large scale problems,the optimal solution can not be given in the real time requirement,so an exchange and search based composite heuristic algorithm is developed.The core of the algorithm is to construct initial solution of the problem based on the actual operating rules in port,and then search the neighborhood constructed by column switching and slot exchange,to improve the quality of the solution.Effectiveness of the algorithm is validated by computational experiments.(2)Optimal research on sequencing and bin packing problem with uncertain collection process of containers.Based on the study of the collection process and the collection environment,conclude the random factors that interfere with containers in collection process.According to the characteristics of the random factors with no aftereffect,based on the idea of the interference repair,the multi-stage planning model is constructed by dividing planning window through the time series.The optimal solution is obtained by rolling of each window,to get the stowage plan of each stage and implement dynamic decision.In consideration of the existing methods is difficult to solve it directly,an insertion-segment based composite heuristic algorithm is developed.The algorithm is to construct initial stage solution of the problem by using the exchange and search based composite heuristic algorithm presented in this paper.Time series rolling trigger insertion-segment mechanism,and then select the container successively as the insertion point according to the container number,the segment is calculated by using the point as the boundary,to reduce the search space and improve the search speed.The simulation results show that the algorithm is effective.