Route optimization, bir filonun işini en az süre, mesafe veya maliyetle bitirmesi için durakları sıralama ve araç atama pratiğidir. Aynı minibüs ve aynı duraklarla 16:00'da işini bitiren bir teslimat sürücüsü ile 19:00'da bitiren biri arasındaki fark budur. Bir lojistik uygulamasındaki her "rotayı optimize et" düğmesinin altında, milyonlarca olası sıralamayı az önce öğütmüş ve birini seçmiş bir çözücü oturur.
Bu rehber, route optimization'ın gerçekte ne olduğunu, çözücülerin ona nasıl yaklaştığını, gerçek dünyada nerelerde ortaya çıktığını ve hangi kısıtlar ile tuzakların bir demoyu üretimden ayırdığını açıklar.
Route Optimization Gerçekte Nedir
Bilgisayar biliminde route optimization iki klasik problemin içinde yaşar. Travelling Salesman Problem (TSP) sorar: bir şehir listesi ve aralarındaki mesafeler verildiğinde, her şehri tam olarak bir kez ziyaret eden ve başlangıca dönen en kısa rota nedir? Bu tek araç problemidir. Vehicle Routing Problem (VRP) bunu bir filoya genelleştirir: bir depo, bir müşteri kümesi ve birkaç araç verildiğinde, müşteriler araçlar arasında nasıl bölünmeli ve her araç onları hangi sırayla ziyaret etmelidir?
Her iki problem de NP-zor'dur. Olası sıralamaların sayısı durak sayısıyla faktöriyel büyür. Yirmi durak zaten 10 üzeri 18'den fazla olası rota üretir. Hiçbir kesin algoritma o uzayı gerçek zamanlı arayamaz. Üretimde optimization bu yüzden mükemmel cevabı bulmakla ilgili değildir. Üzerine harekete geçecek kadar hızlı, çok iyi bir cevap bulmakla ilgilidir.
Çözücüler Probleme Nasıl Yaklaşır
Arama uzayı çok büyük olduğundan, gerçek çözücüler birkaç tekniği harmanlar.
Küçük problemler için (yaklaşık 15 durağın altında), branch-and-bound veya integer programming gibi kesin yöntemler saniyeler içinde ispatlanabilir biçimde optimal bir çözüm döndürebilir. Bu ölçeğin ötesinde kesin yöntemler pratik olmaktan çıkar ve alan sezgisellere geçer.
Tipik bir hat, başlangıç rotası üretmek için nearest-neighbour veya Clarke-Wright savings algoritması gibi yapıcı bir sezgiselle başlar. O rota daha sonra hedefi iyileştirmek için durakları takas eden, alt turları ters çeviren veya durakları araçlar arasında taşıyan bir metasezgisele teslim edilir. Simulated annealing, tabu search, large neighbourhood search ve genetik algoritmalar en yaygın seçimlerdir. Hepsinin şekli aynıdır: bir değişiklik dene, kabul edip etmemeye karar ver, sabit bir zaman bütçesi boyunca tekrarla.
Diğer kritik girdi distance matrix'tir: her durak çifti arasındaki seyahat süresi ve mesafenin önceden hesaplanmış bir tablosu. Optimizer arama sırasında matrisi milyonlarca kez sorgular, bu yüzden matris bir routing motoru tarafından önceden bir kez oluşturulur ve çözücü çalışırken bellekte tutulur.
Route Optimization Nerede Kullanılır
Route optimization uzun bir operasyonel iş listesini sessizce çalıştırır.
- Son kilometre teslimat: kargo taşıyıcıları, market teslimatı ve e-ticaret fulfilment hepsi minibüs başına günde onlarca ila yüzlerce durağı sıralar
- Saha hizmeti: HVAC teknisyenleri, telekom kurulumcuları ve evde sağlık çalışanları, randevu pencereleri ve yetkinlik gereksinimleriyle bir bölgedeki müşterileri ziyaret eder
- Mobil iş gücü: karışık görev tipleriyle bölgeleri kapsayan altyapı ekipleri, sayaç okuyucular ve denetçiler
- Yemek teslimatı: coğrafya uyduğunda birden fazla siparişi tek bir kurye yolculuğuna toplayan restoran agregatörleri
- Atık toplama: küçük yeniden sıralamaların gerçek yakıt tasarrufu sağladığı sabit haftalık turlar yapan belediye kamyonları
- Satış temsilcileri: bir temsilcinin günde 8-12 hesabı ziyaret ettiği ve sıralamanın sürüş süresi ile toplantı yoğunluğu için önemli olduğu bölge planlaması
Her durumda kullanıcı, durakları doğru sırada bir liste olarak görür. İş, arkasındaki optimizer'da gerçekleşir.
Önemli Olan Kısıtlar
Yalnızca mesafeyi minimize eden bir çözücü oyuncaktır. Üretim routing'i kısıtlarıyla tanımlanır.
- Araç kapasitesi: her minibüsün, atanan durakların aşmaması gereken bir ağırlık, hacim veya palet limiti vardır
- Zaman pencereleri: müşteriler örneğin 09:00 ile 11:00 arasında teslimat bekler ve 11:05'te varmak başarısızlıktır
- Sürücü vardiyaları: maksimum çalışma saatleri, zorunlu molalar ve belirli depolarda başlangıç ve bitiş
- Yetkinlik veya araç eşleştirme: bir buzdolabı kurulumu iki kişilik ekip gerektirir, bir soğuk zincir teslimatı soğutmalı bir minibüs gerektirir
- Çoklu depo: büyük filolar birden fazla depodan sevk eder ve çözücü hangi deponun hangi durağı üstleneceğine karar verir
- Üsse dönüş: bazı rotalar açıktır (sürücü evde biter), diğerleri kapalıdır (sürücü depoya döner)
Her kısıt, uygulanabilir rota kümesini daraltır ve çözücüyü kâğıt üzerinde biraz daha kötü görünen ama gerçekte teslim edilebilir çözümlere doğru iter.
Üretimdeki Tuzaklar
Route optimization, demonun her zaman çalıştığı, rollout'un ise çoğu zaman çalışmadığı bir kategoridir.
Yanlış hedefi optimize etmek. Mesafeyi minimize etmek varsayılandır, ancak birçok filo için gelir veya hizmet seviyesi uyumu, tasarruf edilen kilometrelerden daha önemlidir. Fazladan bir paketi 2 km karşılığında bırakan bir rota genellikle kazançtır.
Free-flow ve trafik farkındalıklı süreler. Ham yol hızlarından üretilen bir matris, yoğun saatte 6 saat süren bir rotanın 4 saat sürdüğünü söyleyecektir. Rotanın çalışacağı günün saati için trafik farkındalıklı seyahat sürelerini açan bir routing motoru kullanın.
Gerçek zamanlı yeniden planlama yok. Bir sürücü beklenmedik trafiğe takıldığında, bir müşteri iptal ettiğinde veya yeni bir durak geldiğinde planlar kayar. Operasyon ekiplerinin sabahın işini çöpe atmadan kalan durakları gün ortasında yeniden optimize etmek için bir yola ihtiyacı vardır.
Donmuş plan bayatlığı. Haftalık sabit bir rota Ocak'ta optimal görünüyordu ve şimdi yüzde 20 daha kötü çünkü müşteriler taşındı, hacimler değişti ve yeni bir tek yönlü cadde ortaya çıktı. Optimization'ı periyodik olarak yeniden çalıştırın ve sürücülere bir değişikliği zorlamadan önce yeni planı canlı olanla karşılaştırın.
MapAtlas'ta Route Optimization
MapAtlas Optimize Route API, tek araç ve filo routing problemlerini, operasyon ekiplerinin gerçekten ihtiyaç duyduğu kısıtlarla çözer: kapasite, zaman pencereleri, vardiyalar, yetkinlikler ve çoklu depo kurulumları. Her araç için sıralı bir plan ve her durak için tahmini varış ve kalkış zamanları döndürür.
MapAtlas yığınındaki diğer iki endpoint ile doğal olarak birlikte çalışır. Distance Matrix API, çözücünün tükettiği seyahat süresi tablosunu trafik farkındalıklı sürelerle oluşturur, böylece planlar yoğun saatte ayakta kalır. Directions API, sıra sabitlendikten sonra ardışık duraklar arasında gerçek sapak sapak yol yollarını çizer; böylece bir sürücü uygulaması düz çizgi yerine gerçek bir polyline gösterebilir.
Route optimization slayt destesinde gösterişli görünmez. Bir çözücü, bir matris ve bir kısıt listesidir. Ama bir filonun gününü zamanında ve bütçe içinde bitirip bitirmeyeceğine karar veren katmandır ve bunu doğru yapmak, gönderilen bir routing özelliği ile sessizce kapatılan birini ayıran şeydir.
Sıkça Sorulan Sorular
Route optimization nedir?
Route optimization, bir durak kümesini ziyaret etmek için en iyi sırayı belirleme ve birden fazla araç söz konusu olduğunda hangi aracın hangi durakları üstleneceğine karar verme sürecidir. Amaç, araç kapasitesi, sürücü vardiyaları ve müşteri zaman pencereleri gibi gerçek dünya kısıtlarına saygı göstererek toplam sürüş süresi, mesafe, yakıt veya maliyet gibi bir hedefi en aza indirmektir. Bilgisayar biliminde iki klasik problemin içinde yer alır: tek araç için Travelling Salesman Problem (TSP) ve filo için Vehicle Routing Problem (VRP).
Route planning ile route optimization arasındaki fark nedir?
Route planning, 'A'dan B'ye nasıl giderim' sorusunu yanıtlar. İki nokta arasında, genellikle sapak sapak yönergelerle, tek bir yol döndürür. Route optimization ise '6 minibüsle bu 80 durağı hangi sırayla ziyaret etmeliyim ve hangi minibüs hangi durağı üstlenmeli' sorusunu yanıtlar. Optimization, planning'in bir katman üstündedir: sırayı ve atamayı belirler, sonra her durak çifti arasında gerçek yol yolunu çizmek için bir routing motoru çağırır.
Route optimization için hangi algoritmalar kullanılır?
Küçük problemler için (yaklaşık 15 durağın altında) branch-and-bound veya integer programming gibi kesin yöntemler ispatlanabilir biçimde optimal bir çözüm bulabilir. Bunun ötesinde arama uzayı patlar ve üretim sistemleri sezgisel ve metasezgisel yöntemler kullanır: ilk çözüm için nearest-neighbour ve savings algoritmaları, ardından iyileştirmek için local search, simulated annealing, tabu search veya genetik algoritmalar. Ticari çözücülerin çoğu bunlardan birkaçını birleştirir ve ispatlanabilir optimaliteye değil sabit bir zaman bütçesine kadar çalışır.
Bir route optimization API hangi girdilere ihtiyaç duyar?
En azından: koordinatlarıyla durak listesi, başlangıç ve bitiş konumlarıyla araçlar ve her durak çifti arasındaki bir mesafe veya süre matrisi. Pratikte ayrıca araç kapasiteleri, müşteri zaman pencereleri, her durakta servis süreleri, sürücü vardiya saatleri, durak başına gerekli yetkinlikler veya araç tipleri ve depo konumları beslenir. En ağır girdi matristir ve genellikle optimizer çalışmadan önce ayrı bir distance matrix API tarafından üretilir.
