Two Optimization Models And Algorithms In Yard Planning

In this thesis,two combinatorial optimization problems in container yard operations are studied.One is the parallel stack loading problem,the other is the container trans-shipment problem.We mainly focus on the computational complexity of the above two problems(polynomial time solvable or NP-hard),the integer linear programming mod-el,the design of approximation algorithms and its performance ratio analysis,as well as Heuristic algorithm which was proposed to meet the actual needs of application and was tested through computer programming.The full thesis is divided into four chapters,the specific contents of each chapter are as follows.The first chapter gives the definition of combinatorial optimization problems,then introduces the concept of computational complexity,approximation algorithm,worst-case ratio and so on,and finally provide detailed description for these two optimization prob-lems in yard planning.The second chapter studies parallel stack load problem,given a set of containers with arrival order which were temporarily stored in several parallel stacks,each container i has a priority p_i.Assume that p_i<p_jand i<j,i.e.container i arrived before container j.In a loading scheme,if container i and j are assigned to the same stack and container j is just above on the container i,then there is a blockage between container i and j.Our goal is to find a loading scheme such that the total number of blockages is minimized.We first formulate the integer programming model.If the number of stacks s=2 and height of stack is unbounded,polynomial time optimal algorithm is proposed.If the parallel number of s=2,the stack height is bounded,the problem is proved to be NP-hard via a reduction from partition problem.Finally,Heuristic algorithm is provided and its performance is evaluated through computer programming.The third chapter studies the container transshipment problem.In rail-road terminal-s,gantry cranes transship containers between trains and trucks.The positions of containers and parking slots are predefined and known.The problem is to assign each container to a parking slot so that the maximum sum of transportation time of the component will be minimal.This problem may be modeled in terms of the Min-max weighted perfect match-ing problem in the bipartite graph.If the number of the component is equal to 2,we first formulate the integer programming and prove it is NP-hard via a reduction form odd-even partition problem,then minimum weight based approximation algorithm with worst-case ratio 3/2 is proposed and improved approximation algorithm with worst-case ratio 4/3 is ob-tained.Chapter ? summarizes the main contents of the first three chapter and puts forward future study direction.