A mathematical model and two-stage heuristic for the container stowage planning problem with stability parameters

Abstract

Over the past two decades there has been a continuous increase in demand for cost efficient containerized transportation. To meet this demand, shipping companies have deployed larger container vessels, which can nowadays transport more than 20000 TEUs (Twenty-Foot Container Equivalent Units). These vessels sail from port to port loading and unloading thousands of containers. As the size of the vessels increases, the loading sequence of containers onto the vessels presents an important challenge for planners since the liner companies try to shorten their stay at ports in order to improve their profits. An efficient stowage plan which delineate the location of each container is required to keep the vessel duration at port minimum. Because containers must be stacked on top of each other, unloading and loading of a container at the same port results from over stowage. Over-stows arise either when planners want to unload containers destined for current port which however are beneath those destined for subsequent ports, or when planners want to reorder the sequence of containers to prevent more over-stows in the future. Usually it is called necessary shifting in the former case and voluntary shifting in the latter. Shifting containers are time-consuming and money-consuming activities. Therefore, the arrangement of containers on board is crucial to achieve effective operations by reducing the number of over-stows. The task of determining the arrangement of containers is called stowage planning. On the other hand, while keeping the number of over-stows at the minimum level, the stowage plan must comply with the stability requirements of the ship`s sailing safely. Fail to meet basic stability constraints may lead to catastrophic consequences in terms of both ship and cargo safety. Moreover, container ships with loading plans that no not meet the stability requirements are not allowed to sail by port authorities. Therefore, over-stow instances and stability parameters play a crucial role for the efficiency of the loading plan. In this study, the container stowage planning problem with stability constraints (e.g. shear force, bending moment, trim) is considered and a mixed integer linear programming (MILP) formulation which generates load plans by minimizing total cost associated with the over-stows and trimming moments is developped. The study adopts a holistic perspective which encompasses several real-world features such as different container specifications, a round-robin tour of multiple ports, technical limitations related to stack weight, stress, and ballast tanks. A two-stage heuristic solution methodology that employs an integer programming (IP) formulation is proposed along with a swapping heuristic (SH) algorithm. This approach first acquires a lower bound on the total over-stow cost with the IP model, thereby creating an initial bay plan. Then, it applies the SH algorithm to this initial bay plan to minimize cost resulting from trimming moments. The efficiency of the MILP formulation and heuristic algorithm is investigated through numerical examples. The results have shown that the heuristic has greatly improved the solution times as well as the size of the solvable problems compared to the MILP formulation. In particular, the two-stage heuristic can solve all size problem instances within an average optimality gap of 0-25% in less than 8 minutes, whereas the MILP can only achieve an approximate optimality gap of 55-80% in 2 hours.

Günümüzde dünya büyük bir küreselleşme çağı yaşamaktadır. Bunda şüphesiz en büyük katkı deniz ticareti ve bilişim teknolojilerinden gelmiştir. Dünya okyanus ve denizleri dünya küresel ticaretinin yaklaşık %90'ını taşıyan, her çeşit kargo ulaştırmasını kapsayacak şekilde ticaret yapan 150'nin üzerinde ülkeye kayıtlı 50 bin ticaret gemisine ev sahipliği yapmaktadır. 2007 yılında denizler üzerinde toplam 20 bin liman arasında 15 milyar ton yük taşınmıştır. Örneğin; 5000 denizcilik şirketi tarafından işletilen 200 deniz ulaştırma rotası ile birlikte, 600 büyük limanı birbirine bağlayan bir düğüm noktası olan Asya'nın ağzı, Singapur'da, bir günde 80 bin, yılda 25 milyon konteyner (kutu yük) ve 1500 ticaret gemisi işlem görmektedir. Kutu yük taşımacılığı deniz ticaret sektöründe devrim yaratmıştır. Küresel deniz ticaretinin alyuvarları sayılacak konteynerlerin ortalama bir adedi, senede yaklaşık 8,5 kez dünya turu yapmaktadır. On binlerce ticaret gemisi farklı işletmecinin elinde, onlarca değişik ulusa ait gemicilerle donatılmış bir şekilde küresel yükleri taşımaktadır. Bu gemilerin sahipleri, bayrakları, kiralandığı veya çalıştığı devletler ayrı ayrıdır. Bir örnek verilirse, donatanı Alman bir konteyner gemisi, Panama kolaylık bayrağına sahip, Filipinli bir mürettebat tarafından donatılmış, Türk bir kaptan tarafından kumanda edilen, Malta'ya ait bir deniz işletmesi tarafından kiralanarak, Rusya Federasyonu'na ait ihraç yüklerini taşıyor olabilir. Günümüzde küreselleşmenin en yoğun yaşandığı deniz ticareti alanında hizmet alımı, her yerde ve her zaman mümkündür. Bu sistem sayesinde gemilerin yükleme boşaltma süreleri o denli kısalmıştır ki, gemilerin limanlara uğrama frekansı haftalardan günlere düşürülebilmiştir. Benzer şekilde eskiden bir malın navlunu, o malın piyasadaki perakende fiyatının kabaca %5-10 arasındaki bir değere sahipken, günümüzde kutu yük sayesinde örneğin 6000 dolarlık bir motosiklet 85 dolara taşınabilmektedir. Konteyner taşımacılığının getirdiği bu kolaylıklar, bu yükleri taşıyan gemilerin de ebat ve özelliklerinde zaman içerisinde değişiklikler meydana getirmiştir. Örneğin; konteyner taşımacılığının ilk başladığı 1956 yılında en fazla 60 adet konteyner taşıyabilen gemiler mevcutken, günümüzde gemi dizayn parametreleri 18-20 bin adet konteyner (18000-20000 TEU-Twenty-Foot Equivalent Unit) taşıyan gemilerin inşasına imkân vermektedir. Tüm bu gelişmeler, özellikle de gemilerin taşıma kapasitelerinde meydana gelen artışlar, konteyner terminallerinin dizaynını, bu terminallerde bulunan ve konteyner taşımaya yarayan büyük kreynlerin sayısını ve kapasitesini de etkileyerek yeni problem sahalarının ortaya çıkmasına neden olmuştur. Bu problem sahalarından en önemlisi "Container Stowage Plan (CSP)" olarak adlandırılan konteyner istifleme planının uygun şekilde hazırlanmasıdır. Konteyner istifleme planı, konteynerin bir gemide hangi konumda olacağını gösteren plandır. Bu plan, yükün boşaltılması esnasında konteynerlerin birbirlerini engel teşkil etmeyecek şekilde daha önceden istiflenmesini sağlamalıdır. Konteynerlerin kreynler vasıtasıyla sadece üstten alınabildiği dikkate alındığında, istif planının ilave kreyn hareketine olanak vermeyecek şekilde hazırlanması gerekmektedir. Bu probleme literatürde "Overstow" denmektedir. Kısacası "Overstow", önceki limanda boşaltılacak konteynerin, daha sonraki limana gidecek konteynerin altına istiflenmesidir. Bu hata neticesinde önceki limana gidecek konteynerin tahliye edilmesi için üstteki konteynerlerin boşaltılıp tekrar gemiye yüklenmesi gerekir ki bu da ilave bir maliyeti ortaya çıkarır. Bir konteynerin gemiden kreynler ile boşaltılmasının yaklaşık maliyetinin 100-150 dolar arasında değiştiği dikkate alınırsa, hazırlanan planın zaruret haricinde "Overstow"`a müsaade etmemesi gerekmektedir. Bununla birlikte, oluşturulan planının gemi dengesini de olumsuz etkilememesi gerekmektedir. Usulüne uygun olmadan yapılan istifleme geminin enine ve boyuna denge parametrelerini olumsuz etkileyecek ve hem gemiye hem de mala zarar gelmesine sebebiyet verecektir. Bu kapsamda hazırlanan istif planının hem konteynerlerin rahatça tahliye edilmesine imkân vermesi hem de gemi dengesini gözetmesi gerekmektedir. Ancak, tanımlanan bu problemin tüm kısıtlara cevap verecek şekilde çözümü hâlihazırda NP-Zor (NP-Hard) olarak nitelendirilmektedir. Buna karşılık, özellikle 1980'li yıllardan itibaren yapılan akademik çalışmalar neticesinde, bazı basitleştirici varsayımlarla yaklaşım algoritmaları uygulanmış ve değişik çözümler bulunmuştur. Ancak bu çözümlerin büyük çoğunluğunun pratik uygulaması bulunmamaktadır. Bu çalışma ile NP-Zor olarak nitelenen problem "Bay Planning" ve "Slot Planning" olarak iki aşamaya ayrılmış ve birinci problem olan "Bay Planning" probleminin çözümüne yönelik hem matematiksel hem de sezgisel model geliştirilmiştir. Çalışma kapsamında geliştirilen modeller gerçek hayatta mevcut birçok kısıtı dikkate almaktadır. Öncelikli olarak problemin çözümüne yönelik olarak "Mixed Integer Linear Programming (MILP)" modeli geliştirilmiştir. Bu modelin amaç fonksiyonunda yükleme esnasında oluşabilecek "overstow" sayısı minimize edilmiş ve gemi denge parametreleri belirtilen sınırlarda tutulmaya çalışılmıştır. Geliştirilen MILP model 4000, 6000, 8000 ve 10000 TEU kapasiteli gemiler için 1 saat, 12000, 14000 ve 20000 konteyner kapasiteli gemiler için 2 saat olacak şekilde koşulmuştur. Söz konusu model 4000, 6000 ve 8000 değerleri için belirtilen sürede oldukça tatminkâr sonuçlar vermiştir. Ancak, problemin boyutu arttıkça MILP modelin belirtilen süreler içinde optimal koşullara ulaşamadığı tespit edilmiştir. Bunun üzerine müteakip aşamada 2 basamaklı sezgisel yöntem geliştirilmiştir. Bu modelin ilk basamağında "Integer Programming (IP)" ile denge kriterlerini dikkate almadan sadece "overstow" değerini minimize edilmesi amaçlanmıştır. İkinci aşamada ise "Swapping Heuristic (SH)" olarak adlandırılan sezgisel yöntem geliştirilmiştir. Bu ikili model ile amaç; ilk aşamada IP modelin "overstow" değerini minimize ettiği optimal bir çözümün elde edilmesidir. Burada elde edilen çözüm ikinci aşamadaki sezgisel algoritmanın girdisini oluşturmaktadır. Bu kapsamda; "Swapping Heuristic" olarak adlandırılan sezgisel yöntem, IP modelin çözümünü girdi olarak almakta ve optimaliteyi bozmadan konteynerler üzerinde yer değiştirme işlemi yaparak denge değerlerini arzu edilen limitler dahiline getirmektedir. Bahse konu "Swapping Heuristic" algoritması Python 3.6 ile kodlanmış ve bu yazılım alatyapsısında çalıştırılmıştır. Geliştirilen bu yöntem de yukarıda belirtilen tüm test değerleri için ayrı ayrı koşulmuştur. 4000, 6000 ve 8000 TEU kapasiteli gemiler için MILP model daha iyi sonuçlar vermiştir. 10000 TEU için ise iki model de birbirine yakın değerler üretmiştir. Ancak, konteyner kapasitesi arttıkça SH algoritmasının daha iyi sonuçlar ürettiği gözlenmiştir. Bu bağlamda; 12000, 14000 ve 20000 konteyner kapasiteli gemiler için sezgisel yöntem daha kaliteli çözümler üretmiştir. Müteakip dönemlerde "Slot" planlamasınında yapılan bu çalışmaya ilave edilmesi durumunda geliştirilen modellerin ticari piyasada etkin bir şekilde kullanılabileceği gözlenmiştir. Özellikle ülkemizin yaptığı ticaretin yaklaşık %90'ının deniz yolları üzerinden gerçekleştirildiği ve bu %90'lık kısmın da yaklaşık %70'inin konteyner taşımacılığı ile yapıldığı dikkate alındığında, kıyılarımızda mevcut Mersin, Antalya, İzmir, İstanbul, Derince, Yarımca, Gemlik, Samsun, Trabzon gibi büyük konteyner terminallerinin operasyonlarında bu modelden istifade edilebileceği değerlendirilmektedir.