Static and dynamic container relocation problems: formulations and efficient heuristic procedures

Abstract

Özet : Konteyner yer değiştirme problemi (KYP) liman sahasında istiflenmiş ve istiften alınış sırası bilinen S adet konteyner içeren bir konteyner sırasının tamamen boşaltılması için yapılacak toplam yer değiştirme sayısının enküçüklenmesi ile ilgilenir. NP-zor olduğu bilinmektedir. Gerçek uygulamalarda ise konteynerler sıralara eklenebilir ve aynı şekilde sıradan alınıp gemilere veya liman sahasını terketmek üzere kamyonlara yüklenebilir. Bu çalışmada hem konteynerlerin sadece sıradan ayrılabildiği KYP hem de dinamik konteyner yer değiştirme problemi (DKYP) olarak adlandırılan ve konteynerlerin hem konteyner sırasına eklendiği hem de sıradan ayrılabildiği genel hali ele alınmıştır. KYP'yi genelleyen DKYP'nin çözümü daha zordur. Problemlerin çözümleri için gösterimler geliştirilmiştir ve bu gösterimlerden yola çıkarak sezgisel yöntemler elde edilmiştir. Problemlerin sezgisel olarak çözümü için KYP için path index sezgiseli, DKYP için tabu arama sezgiseli, min-max (MMD) sezgiseli yaklaşımı geliştirilmiştir. Rassal olarak türetilen örnek problemler üzerinde bilgisayısal deneyler gerçekleştirilmiştir. KYP ve DKYP için geliştirilen gösterimlerin ve DKYP için geliştirilen MMD sezgisel yaklaşımının yazındaki çalışmalardan daha etkin sonuçlar ürettiği gözlenmiştir. Anahtar Kelimeler: Konteyner depolama, tam sayılı programlama, konteyner yer değiştirme, sezgiseller.

Abstract : The container relocation problem (CRP) which is known to be NP-hard, tries to empty a single yard-bay which contains S containers each having a given retrieval order so as to minimize the total number of relocations performed. The DCRP is an extension of the CRP where containers are both received and retrieved from a single yard-bay and the arrival and departure sequences of containers are assumed to be known in advance.Two enhanced Binary Integer Programming (BIP) formulations for the CRP and a novel BIP formulation for the DCRP are devised. Computational experiments are performed to analyze new formulations by using standard test instances from the literature. Our results show that, new formulations are promising and yield better results in general for both CRP and DCRP. A new heuristic called as Path Index heuristic, is proposed to solve the CRP. Tabu search based heuristic approaches are proposed to solve the DCRP. In addition, two Index Based heuristics are developed and tested for the DCRP. Computational experiments are performed on an extensive set of test instances from the literature. Our results indicate that the proposed algorithms are efficient and yield promising outcomes. Especially, IB heuristics show a superior performance than the ones from the literature on a set of standard test instances for the DCRP.Keywords: container stacking, integer programming, container relocation, heuristics, container terminals.