Column generation approach for dynamic berth allocation problem

Abstract

Bu tezde literatürde yer alan Dinamik Rıhtım Tahsis Etme Problemi (DRTEP) üzerindeçalışılmıştır. Rıhtım Tahsis Etme Problemleri rıhtıma yanaşan gemilerin belirlenen biramaca göre en iyi şekilde rıhtımda servis edilecekleri noktalara dağıtılmasıdır. DinamikRıhtım Tahsis Etme Problemi (DRTEP), Statik Rıhtım Tahsis Etme Problemi'nin (SRTEP)aksine rıhtımdaki noktalar gemilere servis vermek için hazır olmadan önce gelebilecek gemileri de içermektedir. Bu, gerçek hayatta olduğu gibi, gemileri planlama ufuğu süresincerıhtıma yanaşabilmelerine olanak sağlamaktadır. Bu esneklik probleme dinamiklik katarken ve problemi daha da zorlaştıran gereksinimlere yol açmaktadır. Dolayısıyla, problem örnekleri büyüdükçe DRTEP'in çözülmesi de daha zor hale gelmektedir. Bu sorunu aşabilmek için büyük ölçekli tam sayı problemlerini çözmekte kullanılan bir kolon üretme algoritması sunuyoruz. Çözüm yönteminde ilk olarak kolon üretme algoritmasını literatürde bilindiği şekilde gevşetilmiş ana problemi indirgenmiş maliyeti eksi olan kolon kalmayana kadar çözdük. Fakat bu yöntem alt problem her rıhtım noktası için ayrı ayrı tam sayı problemiolarak çözüldüğü için çok fazla zaman istemekteydi. Istenilen zamanı azaltabilmekiçin algoritmanın en çok zaman harcayan kısmına, yani alt probleme, sezgisel bir yöntemuyguladık. Alt problemin bazı değişken ve kısıtlarını yok sayarak problemi basit bir atamaproblemine dönüştürdük. Bu problemin çözümüne de basit bir yerel araştırma algoritmasıuyguladık. Bu sezgisel yöntem indirilmiş maliyeti eksi olan kolon üretmediğinde, alt problemkesin çözümlü olarak tekrar çözüldü. Ayrıca algoritma, indirilmiiş maliyeti eksi olankolon bulamayana kadar devam ettirildiğinde çözüm zamanı çok uzadığından algortimanındurma kriteri, ana problemin amaç fonksiyon değeri önceden belirlenmiş bir iterasyondadeğişmezse algoritmayı durdurmak olarak değiştirildi.Onerilen kolon üretme yöntemi literatürden alınan 84 büyük problem örneği ile test edildi.Küçük problem örnekleri test edilmedi. Bu problem örneklerinin test edilmeme nedeni isegerçek çözüm sürelerinin gözardı edilebilecek kadar kısa olmasıdır. Literatürdeki diğeryöntemlerle karşılaştırıldığında önerilen kolon üretme yönteminin 84 problem örneğininhepsi için en iyi çözüm yöntemi olduğu söylenemez. Problem örnekleri büyüdükçe ve parametre yapısı zorlaştıkça önerdiğimiz kolon üretme yönteminin performansı diğerlerindendaha iyi hale gelmeye başlıyor. Önerilen yöntemin çözüm kalitesi çözülebilen problemörnekleri için gerçek çözümle aynıdır. Ayrıca kolon üretme yöntemi literatürde bellek sorunuyüzünden çözülemeyen problemler için en iyi çözüm yöntemi olarak gösterilen DegişkenKomşu Arama yönteminden daha iyi sonuç vermektedir.Sonuç olarak, önerilen kolon üretme yöntemi literatürdeki gerçek çözüm yöntemleriyle çözülemeyen büyük problem örnekleri için en iyi sonucu vermektedir. Kolon üretme yöntemi diğer sezgisel yöntemlerle karşılaştırıldığında çözüm sürelerinin uzunluğuna rağmen, cözüm kalitesindekifarklılıkla konteynır terminali yöneticilerine farklı bir alternatif sunmaktadır.

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.