Dinamik rıhtım tahsis etme problemi için kolon üretme yöntemi

Berth allocation problem (BAP) is to find the best allocation of berths (i.e., sections ofthe quayside) to the incoming ships at a container terminal and the definition of the problemis usually dictated by the objective function used and the constraints imposed. In this thesiswe addressed the well known berth allocation problem called Dynamic Berth AllocationProblem (DBAP). The DBAP involves a set of ships that may not be ready for handlingbefore the berths become available as opposed to the Static Berth Allocation Problem(SBAP). This means that the ships will arrive during the planning horizon which makesthe problem much harder than the SBAP because requirements of the problem formulationincrease in terms of introducing new variables and constraints to cover this relaxation.The DBAP gets more difficult to solve exactly as the problem size increases (i.e., numberof berths and ships increases). In order to tackle this difficulty we proposed a ColumnGeneration (CG) Algorithm for DBAP. CG is a common method to solve large scale integerprogramming (IP) problems. We first implement CG procedure similar to its application inthe literature where the relaxation of the master problem is solved at each iteration and thesubproblems are solved exactly to find the schedule (column) that has the minimum reducedcost for the associated berth. The drawback of this approach is the high computation timebecause the subproblems are Mixed Integer Programming (MIP) models and are solvedexactly at each iteration for a number that is equal to the number of berths in the probleminstance. In order to decrease the computational burden of the proposed CG algorithm,a heuristic approach is developed for the subproblems. First, we relaxed the subproblemby ignoring the constraints and the variables that complicates the problem. Consequently,subproblem is turned into a simple assignment problem. This assignment problem is solvedexactly and the ships that are included in the optimal solution of the assignment problemare used to find a better solution for DBAP's subproblem by including the ignored variablesand constraints. This solution is found by a local search algorithm. If this heuristic cannotfind a schedule that has a negative reduced cost, the exact procedure is employed to ensurethat there exist no more schedules that has a potential to improve the objective function ofthe master problem for the berth related to the current subproblem.The proposed CG algorithm is tested on 84 large scale DBAP instances which are takenfrom the literature. Results of the small instances are not tested since the computationtimes needed to find the optimal solution with the exact algorithm are almost negligiblein these instances. When the proposed decomposition based CG algorithm compared withthe other solution procedures in the literature, it does not perform the best for the entire84 problem instances. The performance of the proposed algorithm is better than otherapproaches on the instances that are more difficult than others in terms of the structureof the parameter setting. Solution quality of the proposed algorithm is the same with theexact solution for the instances that are solvable exactly. Moreover, CG algorithm givesbetter solutions than the Variable Neighborhood Search (VNS) algorithm provided in theliterature which gives the best results in terms of computational time for the instances thatare not solvable by the exact procedure because of the out of memory error.We conclude that the proposed CG algorithm provides the optimum solution for largesize instances which cannot be solved by the exact algorithms. Eventhough the computational time of the algorithm is large for these instances, as we can obtain exact solutions compared to the heuristic methods, the CG algorithm provides an alternative for the managers of the container terminals with respect to the quality of the solutions.