Constraint programming approach to quay crane scheduling problem

Abstract

Gemilerin rıhtıma bağlı kalma sürelerinin en azlanması konteyner terminallerinin önemli sorunlarındandır. Bu çalışmada konteyner terminallerindeki rıhtım vinci çizelgeleme problemi incelenmiştir. Rıhtım vinci çizelgeleme probleminde (RVÇP) rıhtıma yerleşmiş bir gemideki tüm konteynerlerin boşaltılması ve yerine yeni konteynerlerin yüklenmesi işlemlerinin tamamı gerçekleştirilir. Bu problem için vinçlerin hareket süreleri, güvenlik mesafeleri, işlerin öncelik ilişkileri, vinçlerin birbirini geçmemesi gibi birçok kısıt içeren zengin bir kısıt programlama (KP) modeli geliştirilmiştir. Bu KP modeli, literatürde daha önce yapılmış düzeltmeler dikkate alınarak, tamamen evrensel kısıtlar ve basit mantıksal kısıtlarlarla oluşturulmuştur. Geliştirilen KP modelinin performansı, literatürde sunulan en güçlü çözüm yöntemleriyle karşılaştırılmıştır. Hesaplamalı deneyler, RVÇP için geliştirilen KP modelinin istikrarlı bir biçimde en iyiye çok yakın sonuçlara daha önceki çözüm sürelerini önemli miktarda azaltarak ulaştığı göstermiştir. Yöntemin esnekliğini göstermesi için de, bu problemin vinçlerin hazır olma sürelerinin ve zaman pencerelerinin olduğu çeşitleri de çalışılmıştır.

Minimizing the average vessel berthing time is one of the challenges for container terminals. Since containers are deployed from vessels by a quay crane, operations of this huge equipment may cause a bottleneck for the overall performance of a terminal. This study examines the quay crane scheduling problem (QCSP) at the seaside of container terminals. The QCSP requires completion of all loading and unloading operations of a berthed vessel. A constraint programming (CP) model, which consists of global constraints and propositional logic, is constructed by taking numerous properties of the problem such as safety margins, travel times and precedence relations into account. The performance of the proposed CP model is compared with algorithms presented in recent QCSP literature. The result from the computational experiments indicates that the proposed CP model is able to produce good results for the QCSP while reducing the computational time. Lastly, to show the robustness and the flexibility of the proposed model, extensions of the problem with ready times and time windows are also discussed.