Yük gemileri için matematiksel optimizasyon teknolojisi
(research.google)- Google Research’ün Operations Research ekibi, tarifeli konteyner gemileri için ağ tasarımı, çizelgeleme ve konteyner rotalarını birlikte optimize eden Shipping Network Design API’yi yayımladı
- Bu problem, gemilerin limanları hangi sırayla ziyaret edeceğini, varış-kalkış saatlerini ve konteynerlerin çıkış-varış rotalarını aynı anda belirlemeyi gerektirdiği için WorldLarge ölçütünde 500 gemi ve 200 liman ölçeğine kadar karmaşıklaşıyor
- İlk yaklaşım olan çift kolon üretimi ve CP-SAT, küçük ve orta ölçekte kanıtlanabilir en iyi çözümleri buldu; ancak büyük ölçekli problemler için büyük komşuluk araması ile değişken komşuluk aramasını birleştiren sezgisel yöntemler gerekti
- LINERLIB benchmark’ında WorldSmall, EuropeAsia, Pacific ve Mediterranean senaryolarında konteyner elleçleme hacmi sırasıyla %35, %14, %35, %32 arttı; kullanılan gemi sayısı ise %7, %15, %4, %23 azaldı
- Google, bu yöntemi WorldLarge ölçeğinde ağ tasarımı ve çizelgeleme problemlerini çözebilen ilk yöntem olarak görüyor ve Shipping Network Design API’yi gelecekte Operations Research APIs’in bir parçası olarak sunuyor
Konteyner deniz taşımacılığı ağını eşzamanlı optimize etme problemi
- Dünyadaki ürünlerin %90’ı deniz yoluyla taşınıyor; büyük yük gemileri 0,25 mil uzunluğunda, 250 bin ton ağırlığında olabilir ve 12 bin konteyner ile toplam 1 milyar dolar değerinde yük taşıyabilir
- Yük gemileri, uçaklar, trenler ve kamyonlardan farklı olarak neredeyse sürekli çalışır ve deniz üzerinde döngüsel rotalar izler
- Verimsiz rotalar ve çizelgeler, konteynerlerin limanda beklemesine, gemilerin denizde beklemesine, lojistik akışlarında gecikmelere yol açar ve ürün fiyatlarını da etkiler
- Google’ın Shipping Network Design API’si bu problem için yeni bir çözüm uyguluyor
- Daha önce bilinen denemelerden daha hızlıdır ve daha iyi ölçeklenir
- Konteyner hatlarının kârını iki katına çıkarabilir, %13 daha fazla konteyner taşıyabilir ve %15 daha az gemiyle çalışabilir
LSNDSP’nin birlikte çözmesi gereken üç karar
- Liner Shipping Network Design and Scheduling Problem, yani LSNDSP, üç kararı aynı anda ele alır
- Ağ tasarımı: Gemilerin limanları hangi sırayla ziyaret edeceğini belirler
- Ağ çizelgelemesi: Gemilerin ne zaman varıp ayrılacağını belirler
- Konteyner rotalama: Konteynerin çıkış noktasından varış noktasına kadar hangi yolculuğu izleyeceğini seçer
- Konteyner deniz taşımacılığı şirketleri bu üç problemin tamamını çözmek zorundadır, ancak genellikle bunları sırayla ele alır
- Üç problemi aynı anda çözmek zorluğu artırır; ancak daha iyi çözüm bulma olasılığını da yükseltir
- Ağ tasarımının sonucu, az sayıda geminin izlediği servis hatlarına dönüşür
- Örneğin Doğu Asya’dan Süveyş Kanalı üzerinden Güney Avrupa’ya giden bir rota olabilir
- Servis hatları tarihlerle birlikte yayımlanır; böylece yük sahipleri konteynerleri ne zaman ve nerede hazırlamaları gerektiğini bilir
Limana yanaşma, aktarma ve gecikmelerin oluşturduğu kısıtlar
- Konteyner gemileri istedikleri zaman limana yanaşamaz; önceden belirlenmiş yanaşma slotlarını kullanmak zorundadır
- Gemi limana yaklaştıktan sonra yanaşabileceği ana kadar denizdeki demirleme alanında demir atıp bekleyebilir
- Liman yoğunsa demirleme alanında saatlerce veya günlerce kalabilir
- Doğru bir ağ çizelgesi yalnızca hangi gün yanaşılacağını değil, hangi saatte yanaşılacağını da içerir
- Belirli bir saate yetişmek için hız artırılabilir
- Yakıt tasarrufu için hız düşürme seçeneği de vardır
- Limana yanaşıldığında vinçler konteynerleri indirir ve bir sonraki seferde taşınacak konteynerleri tekrar gemiye yükler
- Çizelge sarkarsa, planlanan konteynerlerin tamamı yüklenmeden limandan ayrılma anlamına gelen cut-and-run yaşanabilir
- Kalan konteynerleri daha sonraki bir gemi alır
- Bir konteynerin çıkış noktasından varış noktasına giderken ara limanda zaman geçirmesine aktarma denir
- Aktarma, LSNDSP’nin olası çözüm sayısını daha da artırır
- Konteyner rotası oluşturmada etkili olan çeşitli kısıtlardan biridir
Optimizasyon yöntemi: Kolon üretiminden komşuluk aramasına
- Tüm optimizasyon problemleri değişkenler, değişkenlere ilişkin kısıtlar ve minimize ya da maksimize edilecek bir amaç fonksiyonundan oluşur
- Örn: gemiler ve limanlar değişkendir
- Örn: bir gemiye yüklenebilecek konteyner sayısı bir kısıttır
- Örn: taşınan konteyner sayısını maksimize etmek amaç fonksiyonudur
- Değişkenler ve kısıtlar genellikle matrislerle ifade edilir; sütunlar değişkenleri, satırlar kısıtları temsil eder
- Büyük ölçekli problemleri parçalamak için yaygın bir teknik olarak kolon üretimi kullanılır
- Başta değişkenlerin yalnızca bir kısmı dikkate alınır
- Ardından asıl problemi daha iyi yaklaştırmak için yeni değişkenler, yani yeni sütunlar üretilir
- Google, hangi sütunların üretilmesinin iyi olacağını tahmin eden bir yazılım kütüphanesi geliştirdi
- Bu kütüphane, matematiksel programlama framework’ü MathOpt üzerinden açık kaynak olarak yayımlanacak
İki temel yaklaşımın sınırları
- Çift kolon üretimi, ağ tasarımı ile konteyner rotalamayı birbirine bağlı iki problem olarak görür
- Her problem, en iyi seçenekleri seçen ana seçim problemi ve makul seçenekleri bulan yardımcı üretim probleminden oluşur
- Her problem çiftine makul seçenekleri üretmek için en kısa yol algoritması uygulanır
- Ardından doğrusal programlama çözücüsü Glop kullanılarak her problemin en iyi seçenekleri seçilir
- Kolon üretimi iki probleme aynı anda uygulanır ve bir problemin ara sonuçlarının diğer problemin ilerleyişini etkilemesi sağlanır
- Kanıtlanabilir en iyi çözümler bulunabildi, ancak yalnızca orta ölçekli problemlere kadar iyi ölçeklendi
- CP-SAT tabanlı bir uygulama da denendi
- Google’ın kısıt programlama çözücüsü CP-SAT kullanıldı
- Orta ölçekli ağlara kadar iyi çalıştı, ancak küresel deniz taşımacılığı problemi ölçeğine genişleyemedi
- Her iki yaklaşım da küçük ve orta ölçekli problemlerde kanıtlanabilir en iyi çözümler buldu, fakat büyük ölçek için yeterli ölçeklenebilirlik sunmadı
Büyük ölçek için sezgisel yöntemler
- Ölçeklenebilirliği artırmak için mevcut çözümün çevresindeki komşuluklara bakıp iyileştirme fırsatları arayan iki yerel arama varyantı uygulandı
- Büyük komşuluk araması, çözümün bir bölümünü sabitledikten sonra önceki yöntemleri uygular
- Örn: “Bu gemi iki haftada bir Salı günü Los Angeles’ı ziyaret eder” gibi bir koşulu sabitler
- Arama alanını küçülterek ölçeklenebilirliği artırır
- Değişken komşuluk araması, hem ağ hem de çizelge tarafındaki komşulukları araştırır
- Aramayı paralelleştirir ve birçok komşuluğu aynı anda değerlendirmek için birden fazla makineye dağıtır
- Arama alanını sınırlarken Operations Research ve deniz taşımacılığı sektörüne ait bilgiyi yansıtabilir
- Her iki yaklaşım da umut vadeden çözüm parçalarını kilitleyip, zaten iyi olan bir çözümden başlayarak daha iyi çözümlere ilerleyen aşamalı bir yöntem kullanır
- Önceki denemeler, problemi çözmeyi çok daha zorlaştırdığı gerekçesiyle taşıma sürelerini dikkate almamıştı; ancak Google, taşıma süresini dahil etmenin çözüm kalitesini önemli ölçüde artırdığını gördü
LINERLIB benchmark sonuçları
- Performans değerlendirmesinde, deniz taşımacılığı ağ tasarımı problemleri için sektör benchmark’ı olan LINERLIB kullanıldı
- Benchmark; konteyner deniz taşımacılığı senaryolarındaki filo, liman ve konteyner talebini içerir
- Test senaryoları WorldSmall, EuropeAsia ve WorldLarge’ı içerir
- WorldLarge, 500 gemi, 200 liman ve yaklaşık 140 bin konteyner içerir
- Optimizasyon amacı yalnızca konteyner sayısını maksimize etmek ya da gemi sayısını minimize etmek değildir
- Yalnızca konteyner sayısını maksimize etmek, daha fazla gemi devreye alıp operasyon maliyetlerini artırabilir
- Yalnızca gemi sayısını minimize etmek, tüm konteynerleri tek gemiyle taşıma gibi gerçekçi olmayan derecede uzun teslimat süreleri doğurabilir
- LINERLIB, zamanında teslimat gelirinden seyir maliyetleri ve liman konteyner elleçleme maliyetlerini çıkaran tahmini kâr ile denge kurar
- Referans çizgiyle karşılaştırıldığında Google’ın yöntemi, daha az gemiyle daha fazla konteyneri rotaladı
- WorldSmall: konteyner elleçleme hacmi %35 arttı, gemi sayısı %7 azaldı
- EuropeAsia: konteyner elleçleme hacmi %14 arttı, gemi sayısı %15 azaldı
- Pacific: konteyner elleçleme hacmi %35 arttı, gemi sayısı %4 azaldı
- Mediterranean: konteyner elleçleme hacmi %32 arttı, gemi sayısı %23 azaldı
- LINERLIB’in ekonomik varsayımlarına dayanarak beklenen kâr marjı da önemli ölçüde iyileşti
API ve sonraki yayınlanacak materyaller
- Google, bu yöntemi WorldLarge ölçeğinde ağ tasarımı ve çizelgeleme problemlerini çözebilen ilk yöntem olarak görüyor
- Sonuçlar LSNDSP benchmark sayfasında daha ayrıntılı olarak incelenebilir
- Shipping Network Design API, ileride eklenecek Operations Research APIs arasında yer alıyor
1 yorum
Hacker News yorumları
Bu sektörün terminal tarafındayım; ilginç ama çok akademik görünüyor
Bunun gerçekten bir denizcilik şirketiyle birlikte geliştirilip geliştirilmediğini merak ediyorum. Terminal tarafında şu anda konteyner optimizasyonunun oldukça derinine iniyoruz ve gerçekten kâbusa yakın. Aynı şirketin sahip olduğu terminaller arasında bile operasyon biçimleri ciddi ölçüde farklı, hatta terminoloji bile çoğu zaman şirket içinde değişebiliyor. Bir terminale göre optimize etseniz bile bir sonraki terminalde %80’ini yeniden yapmak gerekiyor; bu yüzden herhangi bir çözümü ölçeklendirmek çok zor
Örneğin Alman mühendisler, seri üretim öncesi araçların özelliklerinin kilitlenmesine karşı çıkmıştı; çünkü o zaman onları eğlence amaçlı kullanamıyorlardı. Sağlık alanında fazla mesai maliyetleri milyarlar düzeyindeydi ve çizelgelemeyi iyileştirmek kolay görünüyor gibiydi, ama sendika kısıtları çoktu ve işe alım arzı da yetersizdi. Google’ın çözümünün ne kadar gerçekçi olduğunu merak ediyorum. Husi füzeleri gibi kısıtlar da dahil mi? Deneyimlerime göre, kanıtlanabilir optimal çözümden ziyade beklenmedik değişikliklere kolayca uyarlanabilen çözümler çoğu zaman daha değerliydi
Nesnel optimizasyonun genel olarak akademik kaldığına katılıyorum. Standartlaştırılmış bir sürecin en verimli sürümünü aynen izlemeyi zor ya da imkânsız kılan nedenler her zaman vardır. Bazen bunlar insanlardan kaynaklanan “aptalca” nedenlerdir; çoğu zaman da hava durumu, duruş süreleri, tedarik zinciri kesintileri, mevsimselliğe bağlı talep sinyalleri ve tahminlerdeki pürüzler gibi dışsallıkları yansıtan makul nedenlerdir. Yine de bilinen istisnalara göre standart süreç oluşturmak yerine, en verimli süreçten başlayıp istisna işlemeyi eklemenin neredeyse her zaman daha iyi olduğunu düşünüyorum. İstisnanın kural haline gelmesine izin verirseniz, her zaman optimalin altında verimle çalışırsınız
Bu sektör zor; liman işçileri sendikaları geleneksel olarak güçlü olduğu için siyasi zemin daha da zor. Temizce ayırıp adlandırabileceğiniz problemler pratikte birbirine dolanmış durumda ve algoritmanın kullanıcı adına “sihirli biçimde” çözeceğini beklerseniz neredeyse kesin başarısız olursunuz. “Sadece gezgin satıcı problemi / kısıt çözücü / istediğimiz yaklaşımı çalıştırmak yetmez mi?” diye düşünüp bu sektöre dalan güçlü yazılım oyuncularını sektör kolayca yutar. Akıllı insanlara kesinlikle ihtiyaç var, ama mütevazı başlamak ve önce gerçek kullanıcılarla konuşmak gerekiyor. Profilinizde iletişim bilgisi göremedim; bu sektördeki başka bir şirketle fikir alışverişi yapmak isterseniz bana e-posta atmanızı isterim. Özellikle intermodal taşımacılık payı yüksek olan yılda 1 milyon TEU’nun altındaki terminaller segmentinde ilginç işler yapıyoruz
Konteynerleşmenin erken dönem tarihini anlatan The Box’ı okuyorum; gerçekten çok keyifli
Mühendislik, tasarım, iş dünyası ve tarihin karıştığı keyifli bir okuma arayanlara şiddetle tavsiye ederim. Karşılaştığım küçük kodlama problemlerini de gülünç gösteriyor
Çok itiraz geleceğini biliyorum ama içtenlikle söylemek gerekirse, 20 fitlik deniz konteynerinin dünya üzerindeki etkisinin, büyük dil modellerinin gelecekte ulaşması muhtemel etkiden daha büyük olduğunu düşünüyorum. Önce o kitabı okuyun, sonra neden yanıldığımı söyleyin. Elbette yanılmıyorum
Çok büyük filolarda konteyner optimizasyonu hâlâ çözülmemiş bir problemmiş gibi görünüyor. Bilmiyordum
Google yöneylem araştırması, mevcut çözümlere kıyasla kullanım oranını %10–20 iyileştirdiyse bu şaşırtıcı düzeyde
https://en.wikipedia.org/wiki/Packing_problems
Yayına açılan şu API endpoint’ini gerçekten kullanan bir yer olup olmadığını çok merak ediyorum: https://developers.google.com/optimization/service/shipping/...
Yine de oldukça güzel
Örneğin Route Optimization API de kurum içi yöneylem araştırması ekibi tarafından bu şekilde yayınlandı; ardından birkaç alfa müşteriden gelen girdilerle bunun üzerine Fleet Engine çözümü inşa edildi. Yöneylem araştırması API’leri Google Cloud üzerinden sunulana kadar SLA ya da güvenilirlik garantisi yoktur; bu nedenle akademik kullanım dışında kullanılmamasının daha iyi olduğunu düşünüyorum. Benim naçizane görüşüm
https://developers.google.com/maps/documentation/transportat...
[1]: https://killedbygoogle.com/
Demuraj hesaba katılmıyorsa gerçekten denemeye değer mi bilmiyorum
https://developers.google.com/optimization/service/reference...
Omega Tau Podcast, konteyner taşımacılığı üzerine çok iyi bir bölüm[0] yayımladı; konteyner yerleşim optimizasyonu ve rota planlamasını da ele alıyor. Şiddetle tavsiye ederim
[0]: https://omegataupodcast.net/146-container-shipping/
“Uçakların aksine yük gemileri neredeyse sürekli çalışır” ifadesi biraz tartışmaya açık
Yük gemilerinde seyir sırasında çok bakım yapılıyor olsa da bunun dışında farkın çok daha küçük olduğunu düşünüyorum. Limanlarda birkaç güne yayılan boşaltma ve yükleme ile dönüş yaparlar; rıhtım beklerken saatlerce ya da günlerce de bekleyebilirler. Delta A350 örneğine bakınca, havalimanında 3 saatlik dönüş süresini çıkarırsanız fiilen günün 24 saati hareket hâlinde: https://www.flightradar24.com/data/aircraft/n513dz
Mahalle restoranı gibi yerlerdeki işletme sahiplerinin veya yöneticilerin yarı zamanlı çalışanların vardiya çizelgesini hazırlamakta zorlandıklarını, hatta bu yüzden iyi para kazandıklarını söylemelerini hatırlatıyor
Bunu algoritmayla çözmek gerekmez mi diye düşünmüştüm
Çalışanların yarısının Taylor Swift’i izlemeye gittiği bir geceyi kapatabilirsiniz; ama insanları böyle çağırdığınızda onların bir sonraki vardiyasını da yine birilerinin doldurması gerekir ve bu böyle devam ederse, hiç birlikte çalışmamış insanlardan oluşan tamamen farklı bir çizelge ortaya çıkar. Daha fazla kısıt ekleyerek düzeltilebilir ama bunların hepsini yazıya dökmek ve önceliklendirmek bile basit değil. İnsanlar Lego blokları değildir
Operasyon araştırması geçmişim olduğu için bu bana hep tuhaf geliyor. Problemler, genel amaçlı çözücülerle modellenip çözülemeyecek kadar karmaşık görünmüyor; ileri teknikler olmadan bile değeri büyük görünüyor. Sorun, operasyon araştırmasının genel olarak erişilebilirliğinin düşük olması. İyi desteklenen çözücülerin çoğu problemi matematiksel bir paradigma içinde tanımlatıyor; “sıradan insan” bunu görür görmez bunalmış hissediyor. Yaygın çizelgeleme sorunları için hazır çözümler de var, ama baştan beri kullanılmadılarsa her işletmenin kendine özgü varyasyonları olduğu için tam benimseme zor oluyor. Ya o varyasyonu desteklemiyorlar ya da aracın içine nasıl sığdırılacağı anlaşılamıyor. Çizelgeleri daha iyi çözme isteği olsa bile bulunan dersler genellikle ciddi düzeyde programlama veya matematik ön bilgisi varsayıyor. Excel’in yetmediği ama operasyon araştırması uzmanı tutamayan “sıradan insanların” da kullanabileceği, çizelgeleme problemlerine yönelik no-code modelleme ortamı yapılabilmesi gerektiğini düşünüyorum
Neredeyse tüm büyük HR/iş gücü yönetimi sistemlerinde bununla ilgili seçenekler var. Örneğin https://www.workday.com/en-us/products/workforce-management/... ve https://www.oracle.com/human-capital-management/workforce-ma... var; ayrıca çok sayıda özel sağlayıcı da mevcut. Ancak başkalarının da söylediği gibi bu sistemler tartışmalara da konu oldu. Çünkü bazıları normal insani ihtiyaçları dikkate almayan biçimde kullanılıyor. Örneğin arka arkaya vardiya yazmak, kısa bildirimle çizelge değiştirmek ya da insan bir yöneticinin hesaba katabileceği çocuk bakımı gibi gerçek yaşam koşullarını dikkate alamamak gibi durumlar var
Ama sorun, her işletmenin kısıtlarının farklı olması. Bir vardiyada en az 1 ilk yardım bilen kişi bulunması gerektiği, Alice ile Bob’un arasının kötü olduğu, cumartesi günleri 2 hafta üst üste çalışılmaması gerektiği, vardiyaların 2 haftada bir değiştiği, vardiyalar arasında en az 12 saat olması gerektiği gibi. Çok sayıda kuruluşun kullanabileceği kadar esnek bir araç, sonunda muhtemelen fazla karmaşık olup kullanımı zorlaşacaktır
Bu tür gemilerin istif planı hâlâ merakımı çekiyor
Her konteynerin rota planlamasından sonraki aşamada yaklaşık olarak çözülmesi gereken bir problem gibi görünüyor. İstif planı daha sonra devreye giriyor ve küresel sistem düzeyi bakış açısından çok daha duruma bağlı kısıtlara sahip. Kabaca iyimser bakıldığında bile rıhtım vinçleri saatte 30-50 hareket yapıyor; gemi başına 2 ya da 4, çoksa 6 vinç bağlanıyor ve katman katman, kabuk soyar gibi çözülmesi gerekiyor. Ultra Large Container Vessel 14.501 TEU ve üzeri, New Panamax 10.000-14.500 TEU, Post-Panamax 5.101-10.000 TEU, Panamax ise 3.001-5.100 TEU. 24.000 TEU'yu 12 bin adet 40 fitlik konteyner olarak alırsak: 4 vinç × vinç başına saatte 50 konteyner × günde 24 saat = günde yaklaşık 1.200 konteyner eder.
https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
Gemi istif planında limandaki erişilebilirliğin yanı sıra ağırlık, denge, güç ve yük değeri kabul kriterleri de var. Yazıda limandan erken ayrılmadan bahsedildiği için bu tür ek yükler merakımı çekti ve kabaca bir hesap yaptım.
Bu alanda fiilen çalışan biri olarak bakınca, işi kendiniz için kolaylaştırmanın birçok yolu var. Ambar kapağı başına bloklar halinde plan yapmak ve konteynerleri varış noktası, boyut ve ağırlığa göre gruplayıp birbirinin yerine geçebilir kabul etmek temel yaklaşım. Sonra operasyon başlamadan önce plan gemiden terminale gönderilirse, terminal de sahadaki konteyner konumlarını bildiği için optimizasyon ve yeniden yerleştirme yapabilir. Her konteynerin ayrıntılarını yok sayıp yalnızca gruplara odaklanmaya karar verirseniz istif planı çok daha kolaylaşır. Çok daha az işle neredeyse aynı sonuç alınır ve terminalin operasyonu optimize etme esnekliği de artar.