Column generation approach for dynamic berth allocation problem

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.