VRP nedir
VRP (Vehicle Routing Problem — araç rotalama problemi), bir depodan çıkan araç filosunun kapasite ve zaman kısıtları altında tüm durakları en az toplam maliyetle ziyaret etmesi problemidir.
Problem iki ayrı karar içerir ve zorluğu da buradan gelir: hangi durağın hangi araca atanacağı ve her aracın duraklarını hangi sırayla gezeceği.
TSP'den (gezgin satıcı problemi) farkı iki noktadadır: VRP'de birden fazla araç vardır ve her aracın kapasite sınırı vardır. TSP "hangi sırayla gezsin", VRP önce "kim gezsin" sonra "hangi sırayla" sorusunu cevaplar.
Kargo operasyonunda önemi maliyet dağılımından gelir: son kilometre dağıtımı, toplam lojistik maliyetinin en büyük kalemidir. Rota uzunluğundaki %10'luk bir iyileşme doğrudan yakıt, araç ve sürücü saatine yansır.
Kısıt türleri
| Kısaltma | Kısıt | Kargo karşılığı |
|---|---|---|
| CVRP | Araç kapasitesi | Araç hacmi veya taşıma kapasitesi |
| VRPTW | Zaman penceresi | Alıcının belirli saat aralığında evde olması |
| MDVRP | Birden fazla depo | Birden çok aktarma merkezi |
| VRPPD | Toplama ve dağıtım | Aynı turda hem teslim hem iade alma |
| HFVRP | Heterojen filo | Farklı boyutta araç ve motosiklet karması |
Gerçek bir operasyon bu kısıtların birkaçını aynı anda içerir: araçlar kapasiteli, teslimatlar zaman pencereli, turlar iade toplamalı ve filo karmadır. Kısıtlar üst üste bindikçe problem hızla büyüdüğü için pratikte kesin çözüm aranmaz, yeterince iyi bir çözümle yetinilir.
Neden zor
VRP, hesaplama kuramında NP-zor sınıfına giren bir problemdir. Bunun pratik anlamı şudur: durak sayısı arttıkça olası çözümlerin sayısı doğrusal değil katlanarak büyür ve belirli bir noktadan sonra hepsini denemek fiziksel olarak imkânsız hale gelir.
| Durak sayısı | Olası rota sırası (tek araç) |
|---|---|
| 5 | 120 |
| 8 | 40.320 |
| 10 | 3.628.800 |
| 15 | 1,31 × 10¹² |
| 20 | 2,43 × 10¹⁸ |
Tasarruf algoritması
Clarke-Wright tasarruf algoritması 1964'ten bu yana kullanılan en yaygın sezgisel yöntemdir. Kalemle kâğıtla bile izlenebilecek kadar basit, büyük problemlerde bile saniyeler içinde sonuç verecek kadar hızlı ve basitliğine göre şaşırtıcı ölçüde iyi çözümler üretir.
Tasarruf değeri şu formülle hesaplanır: S(i,j) = d(D,i) + d(D,j) − d(i,j)
Formülün anlattığı şey basit: i ve j duraklarına ayrı ayrı gidip dönmek yerine ikisini aynı turda birleştirirsen ne kadar mesafe kazanırsın. Tasarruf ne kadar büyükse o iki durağı aynı rotada toplamak da o kadar mantıklıdır.
Adımlar:
Algoritma dört adımda ilerler. Önce her durak için ayrı bir tur varsayılır; yani araç depodan çıkıp tek bir durağa gider ve geri döner. Ardından tüm durak çiftleri için tasarruf değeri hesaplanır ve liste büyükten küçüğe sıralanır. Üçüncü adımda liste sırayla taranır: iki durak farklı turlardaysa, her ikisi de bulundukları turun ucundaysa ve birleşik yük araç kapasitesini aşmıyorsa o iki tur birleştirilir. Bu tarama liste bitene kadar sürdürülür.
Çözümlü örnek
1 depo, 8 durak, araç kapasitesi 700 koli
| Durak | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Talep (koli) | 180 | 220 | 150 | 260 | 190 | 210 | 170 | 140 |
Kapasiteye göre teorik minimum araç = 1.520 ÷ 700 = 2,17 → 3 araç
Başlangıç: her durak ayrı sefer
Tasarruf listesi (ilk 6)
| Çift | Tasarruf (km) |
|---|---|
| (3, 4) | 23,89 |
| (2, 3) | 21,63 |
| (1, 2) | 19,28 |
| (4, 5) | 18,94 |
| (2, 4) | 17,02 |
| (1, 3) | 16,21 |
Birleştirme adımları
| Adım | Çift | Sonuç | Neden |
|---|---|---|---|
| 1 | (3, 4) | [3, 4] kuruldu — yük 410 | En büyük tasarruf, kapasite uygun |
| 2 | (2, 3) | [2, 3, 4] — yük 630 | 630 ≤ 700, uygun |
| 3 | (1, 2) | Reddedildi | 180 + 630 = 810 > 700 |
| 4 | (4, 5) | Reddedildi | 630 + 190 = 820 > 700 |
| … | diğerleri | [1, 5, 6] ve [7, 8] oluştu | Kalan tasarruflar sırayla değerlendirildi |
3. ve 4. adımlar öğreticidir: listenin en üstündeki tasarruflar bile kapasite kısıtı yüzünden reddedilebilir. Kapasite kısıtı olmasaydı çözüm tamamen farklı çıkardı — bu, VRP'yi TSP'den ayıran şeyin tam olarak ne olduğunu gösterir.
Sonuç
| Rota | Yük / Kapasite | Doluluk | Mesafe |
|---|---|---|---|
| Depo → 2 → 3 → 4 → Depo | 630 / 700 | %90,0 | 40,00 km |
| Depo → 1 → 5 → 6 → Depo | 580 / 700 | %82,9 | 39,92 km |
| Depo → 7 → 8 → Depo | 310 / 700 | %44,3 | 22,53 km |
| Toplam | 1.520 / 2.100 | %72,4 | 102,45 km |
Araç sayısı: 8 → 3 (teorik minimuma eşit)
Ortalama araç doluluğu = %72,4
Üç gözlem:
- Araç sayısı teorik minimuma indi. 1.520 koli için kapasiteye göre en az 3 araç gerekiyordu, algoritma 3 buldu. Bu her zaman garanti değildir — sezgisel yöntem bazen fazladan araç kullanır.
- Üçüncü rota zayıf: %44,3 doluluk. 7 ve 8 numaralı duraklar coğrafi olarak diğerlerinden uzakta. Bu, rotanın kötü olduğu anlamına gelmez — o bölgeye gitmek zorunludur. Ama doluluk oranı düşükse serpme diyagramı örneğindeki gibi teslim başına maliyeti yükseltir.
- Sonuç en iyi çözüm değildir. Clarke-Wright sezgiseldir; tipik olarak en iyi çözümün %5–10 üstünde bir sonuç verir. Ticari çözücüler bunu başlangıç noktası alıp yerel arama ile iyileştirir.
Sık karşılaşılan hatalar
Kuş uçuşu mesafe kullanmak. Gerçek sürüş mesafesi düz çizgiden tipik olarak %20 ile %40 arasında uzundur; şehir içinde tek yönlü sokaklar ve trafik bu farkı daha da büyütür. Yanlış mesafe matrisiyle hesaplanan rota, kâğıt üzerinde en iyi ama sahada işlemez çıkar.
Mesafeyi tek amaç olarak almak. Süre, yakıt, sürücü mesaisi ve zaman penceresi ihlalinin bedeli çoğu zaman mesafeden daha pahalıdır. Amaç fonksiyonunun bu kalemleri de içermesi gerekir.
Servis süresini hesaba katmamak. Durak başına teslim süresi rotaya eklenmediğinde plan sahada tutmaz; özellikle zaman pencereli teslimatlarda birkaç dakikalık eksik tahmin zincirleme gecikme üretir.
Çözümü sahaya sormadan uygulamak. Kuryenin sahip olduğu bilgi modelde bulunmaz: kapalı sokak, park zorluğu, apartmana erişim süresi. İlk uygulama mutlaka sahayla birlikte gözden geçirilmelidir.
Kapasiteyi tek kısıt sanmak. Zaman penceresi genellikle kapasiteden daha bağlayıcıdır ve çözümü tümüyle değiştirebilir.
Sezgisel sonucu en iyi çözüm diye sunmak. Clarke-Wright iyi bir başlangıç noktasıdır ve tipik olarak en iyi çözümün %5–10 üstünde kalır. Ticari çözücüler bu sonucu alıp yerel arama ile iyileştirir.