Yard allocation problem in bulk port terminals

Abstract

Kuru dökme yük terminalleri dünya ticaretinde önemli bağlantı noktalarını oluşturduğundan terminaller tarafından sunulan operasyonların verimli ve etkili olması gerekmektedir. Bu operasyonlar rıhtımların gelen gemilere atanması, kuru dökme yüklerin elleçlenmesi ve depo alanında depolanması, ve yükleri depo alanından toplayan boşaltıcıların atanması ve çizelgelemesini içermektedir. Yük depolama problemi konteyner terminallerinde çokça çalışılmış olsa da kuru yük terminallerinde yük depolama problemi hak ettiğinden daha az ilgi görmüştür.Çoğu dökme yük terminalinde, kuru yükler düzenli olarak depolanmakta ve sevk edilmektedir. Bu tezde, dökme yük terminallerinde kuru yükleri depolama problemi (YDP) üzerinde çalışılmıştır. Bu araştırmanın amacı, yüklerin depo alanında aldığı yolu ve elleçlenmek için bekledikleri süreyi enazlayacak depo alanındaki yerleri belirleyen bir yöntembilimi geliştirmektir. Bu amaca ulaşmak için bu tez çalışmasında, YDP'yi çözmek üzere Karma Tam Sayılı Doğrusal Programlama (KTSDP) modelleri ve üstsezgisel algoritmalar sunulmaktadır.Sunulan ilk iki model YDP'yi sürekli zaman ve aralıkta ele almaktadır. Sürekli YDP depolama alanı uzunluğu ve planlama dönemi sürekli olduğunda çalışılmaktadır. Öte yandan, üçüncü model YDP'yi kesikli zaman ve aralıkta incelemektedir.Geliştirilen modellerde iki tip depolama alanını ele alınmıştır: şerit alanlardan oluşan depolar ve bölüntüsüz tek alandan oluşan depolar. Şerit depo alanlarının yokluğunda, stok yığını depolama alanı üzerinde alan sınırlarına paralel olacak şekilde serbestçe yerleştirilebilir. Bunun sonucunda, ilk model yığınların depolama yerinin yanı sıra yığınların alandaki yönünü de belirler. Sayısal deneyler, modellerin küçük ve orta ölçekli gerçek hayat örneklerini çözebildiğini göstermektedir. Bunun yanı sıra YAP'ın bir özel hali olan çok boyutlu kutulama problemleri halihazırda NP-zor problemler kategorisinde olduğu için verimli bir KTSDP modeli sunmak zorlu olmaktadır. Bu nedenle büyük ölçekli limanlarda YDP'nin çözümünde kullanılmak üzere Tabu Arama ve Değişken Komşu Arama algoritmalarını birleştiren karma bir üstsezgisel algoritma (YATS_VNS) önerilmiştir. Son olarak, sunulan KTSDP modellerinin ve üstsezgisel algoritmanın performansı gerçek hayat verilerini de içeren dört farklı veri kümesi ile test edilmiştir.Küçük ölçekli örneklerde, KTSDP modelleri ve üstsezgisel algoritma YDP için eniyi sonucu makul bir sürede elde edebilmektedir. Büyük ölçekli örneklerde ise ikinci KTSDP modeli ile eniyi çözüme yakınsayan sonuçlar elde edilmiştir. Bunlara ek olarak, üstsezgisel algoritmanın çözümleri KTSDP modelinden elde edilen sonuçlar ile karşılaştırılmıştır. Sonuçlara göre, YATS_VNS algoritması ile çözüm kalitesi ve çözüm süresi büyük ölçekli örneklerden oluşan dördüncü veri setindeki neredeyse tüm örneklerde iyileştirilmiştir.

The bulk port terminals are important links in world trade; therefore the operations offered by the terminals should be efficient and effective. These operations include allocating berths to the upcoming vessels, storing and handling bulk materials on the stockyard, and assigning and scheduling stacker and reclaimers to collect the material from the yard and convey to the vessels. Although yard assignment or storage allocation problems at the yard side of the ports have been studied for many years, most of the studies mainly focus on storing containers, and bulk port terminals receive less attention than they deserve.In many port terminals, dry bulk materials are stored and shipped on a regular basis. In this thesis, we investigate the yard assignment of dry bulk materials, such as coal, in bulk ports. The ultimate goal of this study is to develop a methodology to determine the location of stockpiles on the stockyard while minimizing the total travel distance and the total dwell time of materials that are handled in ports. Therefore, we present mathematical models which address this yard assignment problem by generalizing the well-known multi-dimensional packing models.The first two models proposed in this thesis address the yard allocation problem (YAP) in a continuous time and continuous space. Continuous YAP is studied where the length of the stockyard as well as the planning time horizon is continuous. On the other hand, the third model we propose discusses the YAP in discrete time and discrete space.In our models, we consider two types of stockyards: with pads and without pads. In the absence of pads, the stockpiles can be stored freely provided that they are parallel to the edges of the stockyard. Therefore, in addition to the assignment of materials to the storage locations, the first model also determines the orientation of the bulks given that the dimensions of each bulk are known. We perform computational experiments which indicate that the models can solve small- and medium-sized real life instances. However, since the underlying multi-dimensional packing problems are NP-hard, developing a computationally efficient mathematical model is challenging. Thus, a hybrid metaheuristic (YATS_VNS) which is based on Tabu Search and Variable Neighborhood Search to solve YAP in large-scaled bulk port terminals is presented. Finally, we analyze the performance of both the mathematical models and the metaheuristic algorithm with four sets of generated data including instances based on real life data.For small-sized instances, mathematical models as well as heuristics can solve YAP to optimality within a reasonable time. For large data sets, we manage to obtain small gaps at least with one of the mathematical models. Moreover, we compare the metaheuristic results with the best obtained solutions. The results indicate that we improve the solution quality and running time with YATS_VNS in almost every instance.