📋 İçindekiler
1. Gezgin Satıcı Problemi (TSP)
TSP: "Bir satıcı n şehri tam olarak bir kez ziyaret edip başlangıç noktasına dönecektir. En kısa rota nedir"
| Şehir Sayısı (n) | Olası Rota Sayısı | Brute Force Süresi |
|---|---|---|
| 5 | 12 | < 1 ms |
| 10 | 181.440 | ~ 1 sn |
| 15 | 43.589.145.600 | ~ 12 saat |
| 20 | ~6 × 10¹⁶ | ~ 1.900 yıl! |
| 50 | ~10⁶² | Evrenin ömrü yetmez |
Bu yüzden NP-Hard sınıfı problemler için sezgisel (heuristic) ve metaheuristik yöntemler kullanılır.
1.1 Nearest Neighbor Sezgiseli
5 Şehir Örneği — Mesafe Matrisi (km):
A B C D E
A [ 0 10 15 20 8]
B [10 0 35 25 12]
C [15 35 0 30 18]
D [20 25 30 0 22]
E [ 8 12 18 22 0]
Nearest Neighbor (A'dan başla):
A→E (8) → E→B (12) → B→D (25) → D→C (30) → C→A (15)
Toplam = 8+12+25+30+15 = 90 km
Optimal: A→E→C→D→B→A = 8+18+30+25+10 = 91 km
Bu örnekte NN çok yakın ama büyük problemlerde %15-25 sapabilir.
A B C D E
A [ 0 10 15 20 8]
B [10 0 35 25 12]
C [15 35 0 30 18]
D [20 25 30 0 22]
E [ 8 12 18 22 0]
Nearest Neighbor (A'dan başla):
A→E (8) → E→B (12) → B→D (25) → D→C (30) → C→A (15)
Toplam = 8+12+25+30+15 = 90 km
Optimal: A→E→C→D→B→A = 8+18+30+25+10 = 91 km
Bu örnekte NN çok yakın ama büyük problemlerde %15-25 sapabilir.
2. VRP Türleri
| VRP Türü | Ek Kısıt | Gerçek Hayat Örneği |
|---|---|---|
| CVRP | Araç kapasite sınırı | Kargo kamyonu max 1000 kg |
| VRPTW | Müşteri zaman penceresi | "09:00-11:00 arası teslim edin" |
| VRPB | Teslimat + toplama (backhaul) | Mağazaya teslim + iade toplama |
| MDVRP | Birden fazla depo | 3 farklı depodan dağıtım |
| HFVRP | Farklı araç tipleri (heterojen) | Kamyonet + TIR + motokurye |
| EVRP | Elektrikli araç + şarj | Tesla Semi menzil kısıtı |
| SDVRP | Müşteri birden fazla araçla | Büyük sipariş bölünebilir |
3. Clarke-Wright Tasarruf Algoritması
Tasarruf formülü:
S(i,j) = d(0,i) + d(0,j) - d(i,j)
d(0,i): Depo → müşteri i mesafesi
d(0,j): Depo → müşteri j mesafesi
d(i,j): Müşteri i → müşteri j mesafesi
Tasarruf = i ve j'yi ayrı rotaya koymak yerine birleştirmekle ne kadar km kazanılır
S(i,j) = d(0,i) + d(0,j) - d(i,j)
d(0,i): Depo → müşteri i mesafesi
d(0,j): Depo → müşteri j mesafesi
d(i,j): Müşteri i → müşteri j mesafesi
Tasarruf = i ve j'yi ayrı rotaya koymak yerine birleştirmekle ne kadar km kazanılır
3.1 Adım Adım Hesaplama
Depo (0) ve 4 müşteri, araç kapasitesi = 100 birim:
Müşteri talepler: A=40, B=30, C=35, D=25
Mesafeler: d(0,A)=10, d(0,B)=15, d(0,C)=12, d(0,D)=8
d(A,B)=18, d(A,C)=7, d(A,D)=14, d(B,C)=20, d(B,D)=11, d(C,D)=9
Tasarruf hesabı:
S(A,B) = 10+15-18 = 7
S(A,C) = 10+12-7 = 15 ← En yüksek
S(A,D) = 10+8-14 = 4
S(B,C) = 15+12-20 = 7
S(B,D) = 15+8-11 = 12
S(C,D) = 12+8-9 = 11
Sıralama: S(A,C)=15 > S(B,D)=12 > S(C,D)=11 > ...
Rota 1: A+C = 40+35 = 75 ≤ 100 ✅ → 0→A→C→0
Rota 2: B+D = 30+25 = 55 ≤ 100 ✅ → 0→B→D→0
Toplam mesafe: (10+7+12) + (15+11+8) = 63 km
Her biri ayrı olsaydı: 2×(10+15+12+8) = 90 km → %30 tasarruf!
Müşteri talepler: A=40, B=30, C=35, D=25
Mesafeler: d(0,A)=10, d(0,B)=15, d(0,C)=12, d(0,D)=8
d(A,B)=18, d(A,C)=7, d(A,D)=14, d(B,C)=20, d(B,D)=11, d(C,D)=9
Tasarruf hesabı:
S(A,B) = 10+15-18 = 7
S(A,C) = 10+12-7 = 15 ← En yüksek
S(A,D) = 10+8-14 = 4
S(B,C) = 15+12-20 = 7
S(B,D) = 15+8-11 = 12
S(C,D) = 12+8-9 = 11
Sıralama: S(A,C)=15 > S(B,D)=12 > S(C,D)=11 > ...
Rota 1: A+C = 40+35 = 75 ≤ 100 ✅ → 0→A→C→0
Rota 2: B+D = 30+25 = 55 ≤ 100 ✅ → 0→B→D→0
Toplam mesafe: (10+7+12) + (15+11+8) = 63 km
Her biri ayrı olsaydı: 2×(10+15+12+8) = 90 km → %30 tasarruf!
4. Zaman Pencereli VRP (VRPTW)
| Müşteri | Talep | Zaman Penceresi | Servis Süresi |
|---|---|---|---|
| A | 40 | 08:00-10:00 | 15 dk |
| B | 30 | 09:00-12:00 | 10 dk |
| C | 35 | 14:00-16:00 | 20 dk |
| D | 25 | 10:00-14:00 | 10 dk |
Araç 08:30'da A'ya varabilir → pencere içinde ✅. A→B yolculuğu 09:00'da başlar → B'nin penceresi 09:00-12:00 → uygun ✅. C'nin penceresi 14:00 → araç öğleden sonrasını beklemeli.
5. Hub-and-Spoke Ağ Tasarımı
Point-to-Point vs Hub-and-Spoke:
100 şehir, P2P bağlantı: n(n-1)/2 = 100×99/2 = 4.950 doğrudan hat
100 şehir, 3 Hub: 100 bağlantı (spoke) + 3 hub-arası = 103 hat
Hub avantajı:
• Konsolidasyon → araçlar %90+ dolu gider
• Ölçek ekonomisi → ton başına maliyet %40-60 düşer
• Dezavantaj: Teslimat süresi uzar (hub aktarma)
100 şehir, P2P bağlantı: n(n-1)/2 = 100×99/2 = 4.950 doğrudan hat
100 şehir, 3 Hub: 100 bağlantı (spoke) + 3 hub-arası = 103 hat
Hub avantajı:
• Konsolidasyon → araçlar %90+ dolu gider
• Ölçek ekonomisi → ton başına maliyet %40-60 düşer
• Dezavantaj: Teslimat süresi uzar (hub aktarma)
6. Son Mil Lojistiği
| Çözüm | Avantaj | Dezavantaj | Maliyet/Paket |
|---|---|---|---|
| Kurye (motosiklet) | Hızlı, esnek | Düşük kapasite | ₺15-30 |
| Van/kamyonet | Yüksek kapasite | Trafik sorunu | ₺8-15 |
| Akıllı dolap (locker) | 7/24, self-servis | Yatırım, boyut sınırı | ₺3-8 |
| Drone | Ultra hızlı | Menzil, ağırlık, regülasyon | ₺5-12 (gelecek) |
| Otonom araç | İşçilik yok | Teknoloji olgunluğu | ₺4-10 (gelecek) |
7. CVRP Matematiksel Formülasyonu (MILP)
Amaç Fonksiyonu:
min Z = Σi Σj cij · xij
Kısıtlar:
Σj xij = 1 ∀i (her müşteri tam 1 kez ziyaret)
Σi di · yik ≤ Q ∀k (araç kapasite kısıtı)
Σk yik = 1 ∀i (her müşteri 1 araca atanır)
xij ∈ {0,1}, yik ∈ {0,1}
Küçük problemler (n≤25): MILP solver (Gurobi, CPLEX) ile optimal çözüm
Büyük problemler (n>50): Metaheuristik zorunlu
min Z = Σi Σj cij · xij
Kısıtlar:
Σj xij = 1 ∀i (her müşteri tam 1 kez ziyaret)
Σi di · yik ≤ Q ∀k (araç kapasite kısıtı)
Σk yik = 1 ∀i (her müşteri 1 araca atanır)
xij ∈ {0,1}, yik ∈ {0,1}
Küçük problemler (n≤25): MILP solver (Gurobi, CPLEX) ile optimal çözüm
Büyük problemler (n>50): Metaheuristik zorunlu
8. Metaheuristik Çözüm Yöntemleri
| Yöntem | VRP İçin Avantaj | Tipik Sapma (%) |
|---|---|---|
| Genetik Algoritma (GA) | Çaprazlama ile rota kombinasyonu | %2-5 |
| Tavlama Benzetimi (SA) | Yerel optimumdan kaçma | %2-5 |
| Karınca Kolonisi (ACO) | Doğal rota keşfi | %1-3 |
| Tabu Arama | Bellek ile tekrarı önler | %1-3 |
| Adaptive Large NS (ALNS) | VRP için en iyi sonuçlar | %0.5-2 ✅ |
9. Vaka Çalışması 1: Kargo Dağıtım Optimizasyonu
📦 Bölgesel Kargo Firması — İstanbul Anadolu Yakası
| Metrik | Öncesi (Manuel) | Sonrası (VRP) | İyileşme |
|---|---|---|---|
| Günlük araç sayısı | 22 | 17 | -5 araç (%23) |
| Toplam km/gün | 1.850 km | 1.320 km | %29 azalma |
| Yakıt maliyeti/ay | ₺285K | ₺198K | ₺87K/ay tasarruf |
| Zaman penceresi ihlali | %18 | %2 | %89 iyileşme |
| Araç doluluk oranı | %62 | %84 | +22 puan |
10. Vaka Çalışması 2: Gıda Perakende Lojistiği
🛒 Zincir Market — 3 Depo, 180 Mağaza, MDVRP
Problem: 3 bölgesel depodan 180 mağazaya günlük taze gıda dağıtımı. Her mağazanın alım penceresi var. Soğuk zincir kısıtı (max 4 saat araçta).
Çözüm: ALNS metaheuristik + Google OR-Tools ile MDVRP-TW çözümü.
| Metrik | Öncesi | Sonrası |
|---|---|---|
| Araç filosu | 45 araç | 36 araç |
| Günlük toplam km | 8.200 km | 5.900 km |
| Yıllık yakıt tasarrufu | — | ₺3.2M |
| Fire oranı (taze gıda) | %4.5 | %1.8 |
11. Sonuç
Lojistik Ağ Optimizasyon Karar Rehberi:
🚗 Tek araç, n nokta → TSP (Nearest Neighbor, 2-opt)
🚛 Çoklu araç + kapasite → CVRP (Clarke-Wright)
⏰ Zaman penceresi var → VRPTW
🏭 Çoklu depo → MDVRP
🔙 Teslim + toplama → VRPB (Backhaul)
🌐 Büyük ağ tasarımı → Hub-and-Spoke + P-median
📦 Son mil → Drone/locker/otonom araç değerlendir
🚗 Tek araç, n nokta → TSP (Nearest Neighbor, 2-opt)
🚛 Çoklu araç + kapasite → CVRP (Clarke-Wright)
⏰ Zaman penceresi var → VRPTW
🏭 Çoklu depo → MDVRP
🔙 Teslim + toplama → VRPB (Backhaul)
🌐 Büyük ağ tasarımı → Hub-and-Spoke + P-median
📦 Son mil → Drone/locker/otonom araç değerlendir