Ağırlıklı bir grafta iki düğüm arasındaki minimum toplam ağırlıklı yolu bulma — tek nokta-noktaya, tek kaynak-tüm noktalara ya da tüm-çift varyantlarıyla. Foundational graf-OR problemi; klasik algoritmaları Dijkstra, Bellman-Ford, Floyd-Warshall. Modern endüstride en sık çağrılan OR algoritması.
Kısaca
Tanıdık geliyor mu?
- Yurt-içi kargo rotalama operatörüyüz — günde 5.000-50.000 paket için merkez depodan müşteri adreslerine en kısa süre rotaları hesaplamamız gerekiyor; yol süresi vs mesafe vs yakıt arasında çoklu-kriter optimizasyon ihtiyacımız var.
- Şehir-içi 10-50 araçlı saha-servis operatörüyüz (su tesisatçı, elektrik servisi, beyaz-eşya tamir, klima bakım); teknisyenin müşteriden müşteriye geçiş sürelerini hesaplıyoruz, trafik-aware bir hesap motoru istiyoruz.
- Belediye trafik yönetim merkeziyiz; gerçek-zamanlı trafik yoğunluğu verisi ile statik harita ağı arasında bir köprü kurup acil servis (ambulans, itfaiye, polis) için trafik-aware en kısa yol hesaplaması istiyoruz.
- Telekom omurga ağ planlayıcısıyız; iki anahtar (ya da iki POP — Point of Presence) arasındaki en az gecikmeli paket yönlendirme yolunu hesaplıyoruz; OSPF (Open Shortest Path First) gibi yönlendirme protokollerinin altında bu hesap çalışıyor.
- Tedarik zinciri planlayıcısıyız; bir fabrika-liman-depo-müşteri ağında her çift düğüm arası en ucuz akış maliyetini bilmemiz gerekiyor (all-pairs shortest path) — multi-modal nakliye seçeneklerinde.
- Otoyol işletmesi ya da nakliye şirketiyiz; uzun-yol rotalama için akaryakıt + ücretli yol + sürüş saati üçlü-kriterli en kısa yol hesabı yapıyoruz; statik graf yetmiyor, zaman-bağımlı (time-dependent) shortest path arıyoruz.
- Yazılım takımımız doğrudan Dijkstra implementasyonu ile başladı, ama büyük graflar (1M+ düğüm, ülke ölçeği yol ağı) için gerçek-zaman sorgu yetersiz — preprocessing-tabanlı (contraction hierarchies) çözüm araştırıyoruz.
Niye önemli?
Nasıl çözülür?
Teknik derinlik
Nasıl çözülür?
Teknik derinlikTek cümlede: Düğümler (kavşaklar) + ağırlıklı kenarlar (yol-süre/mesafe) verildiğinde, kenarlar non-negatif ise Dijkstra algoritması (her adımda en yakın komşuyu seç + komşu mesafelerini güncelle), kenarlar negatif olabiliyorsa Bellman-Ford, tüm-çift mesafe matrisi gerekiyorsa Floyd-Warshall — her biri optimum garantisi verir.
Bu problem yöneylem araştırması (matematik ve bilgisayar kullanarak işletme kararı çözen disiplin) literatüründe Shortest Path Problem (SPP — en kısa yol problemi) olarak çalışılır — foundational graf-OR problemi, 60+ yıllık olgunlukta. Üç temel varyant: single-source single-destination (tek nokta-noktaya), single-source all-destinations (tek kaynaktan tüm hedeflere), all-pairs (tüm-çift). Klasik foundational algoritmalar 1950-60’lardan gelir: non-negatif kenarlı graf için Dijkstra, negatif kenarlı için Bellman-Ford, tüm-çift için Floyd-Warshall; modern preprocessing-tabanlı contraction hierarchies ülke ölçeği yol ağında milisaniye-altı sorgu süresi verir. Çözüm üç aşamalı:
1. Modelleme. Veri girdileri: (a) graf yapısı — düğüm seti V (kavşaklar, lokasyonlar, anahtarlar), kenar seti E (yollar, bağlantılar), kenar ağırlıkları w(u,v) (mesafe, süre, maliyet, gecikme), graf yönlendirilmiş mi (tek-yön sokak) ya da yönsüz mü (çift-yön), kenar ağırlıkları non-negatif mi yoksa negatif olabilir mi, negatif cycle var mı, (b) sorgu tipi — tek nokta-noktaya (kaynak s, hedef t), tek kaynak-tüm noktalara (kaynak s, hedef tüm V), tüm-çift (her i,j çifti için), (c) dinamiklik — graf ağırlıkları sabit mi (statik), zaman-bağımlı mı (trafik gibi günün saatine göre değişiyor), gerçek-zamanlı güncellenmeli mi (kazaya bağlı kapanma, hava durumu), (d) çoklu-kriter — tek-amaç (sadece süre) mi, çok-amaçlı (süre + mesafe + yakıt + ücretli-yol) mı; çok-amaçlı ise Pareto-optimum yollar mı yoksa ağırlıklı toplam mı, (e) kısıtlar — yol-tipi yasakları (kamyon belirli yollara giremez, ambulans bazı kısıtlardan muaf), zaman penceresi (mesai saatleri), kapasite (taşınacak yük). Karar değişkenleri: graf üzerindeki kenar dizisi (s → … → t), her kenarın “yolda mı değil mi” değişkeni. Hedef: kenar ağırlıkları toplamı minimum.
2. Çözücü ile karar. Algoritma seçimi grafa ve sorgu tipine bağlı:
(a) Dijkstra — non-negatif kenarlı, tek-kaynak. Greedy (aç gözlü — her adımda anlık en iyiyi seç): her adımda öncelik kuyruğundan en küçük geçici-mesafeli ziyaret-edilmemiş düğümü çıkar, komşularının mesafelerini güncelle. Binary heap implementasyonu O((V+E)logV), Fibonacci heap O(E + V logV). Pratik: tek kaynak-noktaya / tek-kaynak-tüm-noktalara, küçük-orta ölçekli statik graf (1K-100K düğüm).
(b) Bellman-Ford — negatif kenar destekli. Tüm kenarlar üzerinde V-1 kez gevşeme (relaxation — her kenarda “kısa yol bulundu mu” tekrar kontrolü). Kompleksite O(VE). Negatif cycle algılaması: V. iterasyonda hâlâ güncelleme oluyorsa negatif cycle var demektir, shortest path tanımsız. Kullanım: negatif kenarlı graf (finansal arbitraj, network akış geri-akışı), distance-vector yönlendirme protokolleri.
(c) Floyd-Warshall — tüm-çift, küçük graf. Dinamik programlama: O(V³) zaman, O(V²) bellek. Pratik: V ≤ 1.000 düğüm, all-pairs gerekliyse. Negatif kenarları destekler (cycle yoksa).
(d) A — heuristic-guided tek nokta-noktaya.* Dijkstra’nın hedefe-doğru-yönlendirilmiş varyantı; heuristic fonksiyonu h(v) (örn. Euclidean / great-circle mesafe) ile düğüm öncelikleri yönlendirilir. Hart, Nilsson ve Raphael (1968). Pratik: tek-kaynak-tek-hedef coğrafi yol ağı, oyun harita yol bulma. Kompleksite Dijkstra’dan ortalama hızlı; heuristic admissible (h ≤ gerçek-uzaklık) ise optimum garantili.
(e) Bi-directional search. Hem kaynaktan ileri hem hedeften geri Dijkstra/A*; iki arama buluşunca dur. Tek-yön Dijkstra’dan tipik 2-4 kat hızlı.
(f) Contraction Hierarchies (Geisberger ve ark. 2008) — ülke ölçeği yol ağı için modern preprocessing-tabanlı. Graf bir kez preprocess edilir (düğümler hiyerarşik sırayla ‘kontrakte’ edilir, kısayollar eklenir); sonra her sorgu milisaniye-altı sürede cevaplanır. Ülke ölçeği (10M+ kenar) yol ağında gerçek-zaman navigasyon için sahada-standart yaklaşım. ALT (A*, Landmarks, Triangle inequality), Transit Node Routing, Hub Labels diğer modern preprocessing-tabanlı yöntemler.
(g) Time-dependent shortest path — trafik-aware. Kenar ağırlıkları zaman-fonksiyonu w(u,v,t); yola çıkış saati t’ye bağlı süre. Statik Dijkstra genelleştirilir; FIFO özelliği (later-departure-no-earlier-arrival) sağlanırsa polinom-zaman çözülür. Pratik: trafik tahmin verisi ile beslenen rotalama motoru.
(h) Stochastic shortest path. Kenar ağırlıkları rasgele değişken (örn. trafik dağılımı); beklenen-değer ya da risk-ayarlı (CVaR) shortest path; literatür Polychronopoulos-Tsitsiklis (1996).
3. Saha entegrasyonu. Çıktı üç katmanlı: (a) operasyonel — sürücü mobil uygulamasında / kargo dağıtım rotasında / saha-servis teknisyen uygulamasında adres-adres rota gösterimi, navigasyon entegrasyonu, (b) planlama — günlük rota planlama yazılımında shortest path matrisi VRP/TSP optimizasyon altında alt-rutin olarak çağrılır, (c) stratejik / analitik — tedarik zinciri ağ analizi, telekom ağ darboğaz raporu, all-pairs mesafe / süre matrisi karar destek için. Üst-sistem entegrasyonu: ERP (sipariş adresleri), TMS (taşıma yönetim sistemi), harita servisi (geocoding + yol-ağı verisi), trafik veri servisi (gerçek-zaman tahmin), filo takip GPS verisi. Üç aylık operasyon komitesi: shortest path sorgu hacmi, ortalama sorgu süresi, trafik tahmin sapması (gerçek vs plan), rota değişiklik oranı (yeniden-hesap tetikleyiciler).
Alternatifler
Manuel + harita servisi + sürücü tecrübesi
ÜcretsizHarita servisi ücretsiz katmanı, sıfır geliştirme maliyeti
Kim için: Küçük operasyon (1-10 araç/gün), 10-50 nokta/araç, statik bilinen rotalar
- + Sıfır yazılım yatırımı
- + Sürücü saha bilgisi öne çıkar
- + Telefonla gerçek-zaman trafik tepkisi
- − Optimum garantisi yok, sürücü sezgisel rotada %15-30 fazla mesafe
- − Çok-kriter (süre + yakıt + ücretli-yol) hesabı yok
- − Veri kaydı yok — performans ölçülmez
- − 10 araç üstü ölçekte planlamacı kapasitesi aşılır
Harita servisi API + iç entegrasyon
cloudSorgu başına ücretlendirme; 0,003-0,01 USD/sorgu, 50K paket/gün ölçeğinde 50-200K TRY/ay
Kim için: Orta operasyon (50-500 araç, 50K-500K nokta/gün), trafik-aware sorgu istenen
- + Olgun trafik verisi entegre
- + Adres geocoding entegre
- + API kolayca tüketilir, geliştirme süresi kısa
- − Sorgu başına ücret yüksek hacimde maliyetli olur
- − Algoritma kara-kutu, kontrol kısıtlı
- − Veri-tedarikçi kilit riski (harita servisi sözleşmesi)
- − All-pairs / büyük matris sorguları için ölçeklenmez
Açık-kaynak yol-ağı motoru + kendi sunucu
Açık KaynakLisans ücretsiz; iç geliştirme + sunucu 6-12 hafta veya 400K-1.2M TRY danışmanlık + yıllık 60-200K TRY altyapı
Kim için: Teknoloji ekibi olan operasyon, yüksek-hacimli sorgu (1M+/gün), özel kısıt (kamyon yol-tipi yasakları)
- + Lisans bedeli yok, sorgu başına ücret yok
- + Algoritma seçimi kontrolünde (Dijkstra, A*, contraction hierarchies)
- + Özel kısıtları (kamyon erişimi, ambulans muafiyet) gömülebilir
- + Veri sahipliği işletmede
- + TR akademisinden 30+ tez (YÖK) referans implementasyonlar
- − Yol-ağı verisi (OpenStreetMap kalitesi) periyodik güncelleme gerekir
- − Trafik verisi ayrı bir tedarikçi gerektirir
- − İçeride OR uzmanı + altyapı ekibi şart
- − Akademik prototipten saha-hazır sisteme 3-6 ay
Uluslararası rotalama / TMS platform
Kurumsal300K-2M EUR lisans + 100K-500K EUR/yıl bakım
Kim için: Büyük operasyon (500+ araç, çoklu site, 1M+ nokta/gün), tam TMS entegrasyonu
- + Olgun shortest path + VRP modülü entegre
- + Çoklu-kriter (süre + maliyet + yakıt + ücretli-yol) standart
- + Time-dependent + stokastik varyantlar destekli
- + Trafik servisi paketinde gelir
- − Yüksek lisans + uzun (12-24 ay) kurulum
- − TR yol-ağı kalibrasyonu proje süresi ekler
- − Algoritma kara-kutu — preprocessing parametre kontrolü kısıtlı
- − Tek-tedarikçi kilit riski yüksek
Tavsiye
Çözüm görüşmesinde sor
- Shortest path algoritmasında hangi yaklaşım kullanılıyor — Dijkstra (binary heap, Fibonacci heap), A*, bi-directional search, contraction hierarchies, ALT? Ülke ölçeği yol ağı (10M+ kenar) için ortalama sorgu süresi nedir?
- Negatif kenar destekleniyor mu (Bellman-Ford)? Negatif cycle algılaması var mı? Hangi senaryolarda (finansal arbitraj, geri-akış) Bellman-Ford'a düşülür?
- Time-dependent (trafik-aware) shortest path destekleniyor mu? Trafik verisi hangi kaynaktan, hangi sıklıkta güncelleniyor (5-dakika, 15-dakika, saatlik)? FIFO özelliği garantili mi?
- Yol-ağı verisi hangi kaynaktan geliyor (OpenStreetMap, ticari harita servisi, devlet karayolu envanteri)? Veri güncelleme döngüsü nedir? Yol tipi (otoyol, bölünmüş yol, şehir-içi, ağır-taşıt erişimi) kısıt olarak nasıl modelleniyor?
- All-pairs shortest path (Floyd-Warshall, Johnson) destekleniyor mu, hangi ölçeğe kadar (kaç düğüm)? Tedarik zinciri ağ analizi için tüm-çift mesafe matrisi nasıl çıkarılır?
- Çok-kriter (süre + mesafe + yakıt + ücretli-yol) optimizasyon destekleniyor mu — ağırlıklı toplam mı yoksa Pareto-optimum yollar mı? Çoklu-amaç parametre ayarı kullanıcı tarafından yapılabilir mi?
- Pilot dönemde gerçek operasyonel veri ile (8-12 hafta) önceki manuel / mevcut sistem rotasına kıyasla nasıl bir tasarruf raporu sunulabilir — yakıt, teslim süresi, sürücü saati, rota değişiklik oranı?
- Sözleşme biterse yol-ağı verisi, trafik kalibrasyon verisi, sorgu geçmişi ve rota arşivini hangi standart formatta (GeoJSON, GraphML, CSV) dışa aktarabiliriz?
Teknik detay
Editör notu
Bu problem halk dilinde “en kısa yol”, “rota hesaplama” veya “navigasyon” diye anılır. Akademik literatürde kanonik adı Shortest Path Problem (SPP), foundational graf-OR problemi. Edsger Dijkstra (1959) iki sayfalık Numerische Mathematik makalesinde non-negatif kenarlı graf için polinom-zaman algoritmasını tanımladı — bu makale bilgisayar bilimindeki en çok atıf alan makalelerden biridir. Richard Bellman (1958) Quarterly of Applied Mathematics makalesinde negatif kenarlı varyantı çözen Bellman-Ford’u kurdu. Robert Floyd (1962) Communications of the ACM algoritma 97 (tek paragraflık makale) ile tüm-çift Floyd-Warshall’i geliştirdi. Ahuja, Magnanti ve Orlin (1993) Network Flows alanın kanonik ders kitabıdır. Modern preprocessing-tabanlı yaklaşımlar (Geisberger ve ark. 2008 — contraction hierarchies) ülke ölçeği yol ağı için milisaniye-altı sorgu süresi sağlar.
#068 (TSP) ile farkı: TSP tüm-düğümler-gezgin-tur problemi — N düğümün hepsini bir kez ziyaret edip başlangıca dön, NP-hard, foundational kombinatoryal optimizasyon problemi. Shortest path tek nokta-noktaya ya da tek kaynak-tüm noktalara en kısa yol problemi — polinom-zaman (Dijkstra O((V+E)logV), Bellman-Ford O(VE), Floyd-Warshall O(V³)). Kompleksite farkı büyük: 1.000 düğümlü graf için Dijkstra milisaniyeler içinde, TSP saatler-günler sürer. TSP shortest path’i alt-rutin olarak çağırır: nokta-çiftleri arasındaki mesafe matrisi shortest path ile hesaplanır, sonra TSP bu matris üzerinde gezgin-tur problemi çözer.
#069 (CVRP) ile farkı: CVRP kapasiteli filo rotalama — birden çok araç, kapasite kısıtlı, müşterileri paylaşarak ziyaret. CVRP shortest path’i alt-rutin olarak çağırır: müşteri-müşteri ve depo-müşteri mesafeleri shortest path ile hesaplanır, sonra CVRP araç-müşteri atama + rota sırası problemini çözer. Shortest path bu durumda “graf ağırlık matrisini doldur” rolünde, CVRP “araç-müşteri atama + sıralama” rolünde.
#002 (VRPTW) ile farkı: VRPTW zaman pencereli filo rotalama — birden çok araç, kapasite + zaman pencereleri kısıtlı. VRPTW de shortest path’i alt-rutin olarak çağırır. Time-dependent shortest path VRPTW içine gömülürse trafik-aware filo rotalama olur.
Sektörde en sık atlanan nokta: negatif kenar veya negatif-cycle algılaması. Pratisyen Dijkstra’yı her durumda kullanır; ama negatif maliyet (örn. bir bağlantıda tasarruf, sermaye iadesi, geri-akış indirimi, bir döviz kuru arbitraj çevriminde negatif logaritmik kenar) varsa Dijkstra optimum vermez — sessizce yanlış sonuç verir. Bellman-Ford gerekir. Negatif cycle varsa shortest path tanımsızdır (cycle’ı sonsuz dolaş, her döngüde toplam azalır). Birçok finansal arbitraj / network akış / geri-akış senaryosunda bu hata sessizce yapılır. Bellman-Ford’un V. iterasyonunda hâlâ güncelleme varsa negatif cycle algılanır.
İkinci atlanan nokta: algoritma kompleksite seçimi. Pratisyen “Dijkstra her yerde çalışır” der; ama ülke ölçeği yol ağı (10M+ kenar) için klasik Dijkstra’nın tek sorgusu saniyeler sürer — gerçek-zaman navigasyon için kabul edilemez. Modern preprocessing-tabanlı yaklaşımlar (contraction hierarchies — Geisberger ve ark. 2008, Transit Node Routing, Hub Labels) ülke ölçeği graf için milisaniye-altı sorgu süresi sağlar; preprocessing tek seferlik (saatler-günler), ama her sorgu hızlı. Üçüncü atlanan nokta: statik graf varsayımı. Trafik gerçek-zamanlı değişir; statik graf üzerinde shortest path “saat 14:00 için optimum” diye işaret eder ama saat 17:00 trafiğinde çöker. Time-dependent shortest path (kenar ağırlığı zaman fonksiyonu) ya da rolling-horizon yeniden-hesap şart.
Adım adım yol — KOBİ için
Aşama 1 — Önce ölç, sonra plan. En az 6 ay sorgu / rota verisi: günlük sorgu hacmi (kaç A-B sorgu, kaç all-pairs sorgu), ortalama sorgu süresi, trafik tahmin sapması (planlanan süre vs gerçek süre), rota değişiklik oranı (yeniden-hesap tetikleyiciler). Yol-ağı envanteri: kaynak (harita servisi, OpenStreetMap, kendi envanter), kalite (kapsama, güncellik, kenar ağırlık tipi — mesafe / süre / maliyet), yol-tipi (otoyol, bölünmüş, şehir-içi, ağır-taşıt erişimi). Trafik veri kaynağı: yok / harita servisi paketinde / ayrı tedarikçi / kendi GPS filo verisi.
Aşama 2 — Algoritma matrisini çıkar. Sorgu profili: çoğu tek nokta-noktaya mı, çoğu tek-kaynak-tüm noktalara mı, all-pairs analiz var mı? Negatif kenar / negatif cycle senaryoları var mı (finansal arbitraj, geri-akış)? Graf ölçeği: 1K, 10K, 100K, 1M, 10M+ düğüm? Sorgu süre gereksinimi: milisaniye-altı (gerçek-zaman navigasyon), saniyeler (planlama), dakikalar (stratejik analiz)? Bu matrise göre algoritma seç: Dijkstra (küçük-orta, non-negatif), Bellman-Ford (negatif kenar), Floyd-Warshall (all-pairs küçük), A* (coğrafi yol-ağı), contraction hierarchies (ülke ölçeği gerçek-zaman).
Aşama 3 — Pilot. 8-12 hafta. Bir alt-küme operasyon (örn. en yoğun bir bölge, ya da en çok-sorgu yapan bir müşteri segmenti) için yeni shortest path motoru çalışıyor; karar yine planlamacı / sürücüde, motor öneri verir. Başarı kriteri önceden yazılı: pilot bölgede yakıt -%10 minimum, teslim süresi -%15 minimum, sorgu süresi gerçek-zaman gereksinimini sağlıyor.
Aşama 4 — Yaygınlaştırma. 6-12 ay sürede tam operasyon + trafik servisi entegrasyonu + rolling-horizon yeniden-hesap. Üç aylık operasyon komitesi: shortest path sorgu hacmi, ortalama sorgu süresi, trafik tahmin sapması, rota değişiklik oranı, ağ darboğaz raporu (all-pairs analizi).
Riskler — ne yanlış gidebilir
Trafik tahmin sapması (statik graf riski). Statik graf üzerinde shortest path hesabı gerçek trafik koşullarını yansıtmaz; en kritik risk. Yoğun saatlerde “optimum” olarak hesaplanan rota gerçekte daha uzun sürer. Çözüm: time-dependent shortest path (kenar ağırlığı zaman fonksiyonu) + trafik veri servisi (5-15 dakika güncellemeli) + rolling-horizon yeniden-hesap (her 15-30 dakika ya da olay tetikli — kaza, kapanma).
Gerçek-zaman güncelleme gecikmesi. Yol kapanması, kaza, trafik olayı verisi shortest path motoruna geç ulaşırsa, motor bilinmeyen kapanmış yolu önerir — sürücü o yola gider, geri döner, çift sefer maliyet. Çözüm: olay tetikli yeniden-hesap (event-driven recomputation), sürücü mobil uygulamada anlık trafik olay bildirimi, alternatif yol önerisi.
Yol kapanması / yasak bilinmiyor. Yol-ağı verisi (statik) periyodik güncellenmezse, yeni inşaat, mevsimsel kapanma, ağır-taşıt yasağı bilinmez; motor ‘feasible’ olmayan rota üretir. Çözüm: yol-ağı verisi 3-6 aylık güncelleme döngüsü, sürücü saha geri-besleme (mobil uygulamada “bu yol kapalı” raporu), ağır-taşıt için kamyon-özel yol-ağı katmanı.
Tek-tedarikçi rota-yazılımı / harita-servisi kilit riski. Sözleşmede ‘yol-ağı verisi, trafik kalibrasyon verisi, sorgu geçmişi, rota arşivinin yıllık standart format (GeoJSON, GraphML, CSV) ihracı’ maddesi yoksa, sistemden ayrılmak yıllarca biriken operasyonel veri ve kalibrasyon hafızasının kaybedilmesi anlamına gelir. Sözleşmede özellikle yol-ağı veri mülkiyeti, trafik kalibrasyon parametre ihracı ve sorgu API standart format çıktısı maddesi şart.
Çözüm yöntemine teknik bakış
| Yaklaşım | Tipik ölçek | Çözüm süresi | Negatif kenar destekli? |
|---|---|---|---|
| Dijkstra naïve (O(V²)) | Küçük, V ≤ 1.000 | milisaniye | Hayır |
| Dijkstra binary heap (O((V+E)logV)) | Orta, V ≤ 100K | milisaniye-saniyeler | Hayır |
| Dijkstra Fibonacci heap (O(E + VlogV)) | Orta-büyük, V ≤ 1M | saniyeler | Hayır |
| Bellman-Ford (O(VE)) | Küçük-orta, negatif kenarlı | saniyeler-dakikalar | Evet, negatif cycle algılar |
| Floyd-Warshall (O(V³)) | Küçük all-pairs, V ≤ 1.000 | saniyeler-dakikalar | Evet (cycle yoksa) |
| Johnson (O(V² logV + VE)) | Orta all-pairs, seyrek | dakikalar | Evet |
| A* (heuristic-guided) | Coğrafi yol-ağı tek-noktaya | milisaniye-saniyeler | Hayır |
| Bi-directional Dijkstra/A* | Tek-noktaya, büyük graf | milisaniye-saniyeler | Hayır |
| Contraction Hierarchies | Ülke ölçeği yol ağı | milisaniye-altı (preprocess saatler) | Hayır |
| Time-dependent Dijkstra | Trafik-aware yol ağı | milisaniye-saniyeler | Hayır |
Hedef fonksiyonu seçimi:
- Hedef 1 — Toplam süre minimum: Hız odaklı; navigasyon, acil servis, kargo dağıtım için tipik.
- Hedef 2 — Toplam mesafe minimum: Yakıt + araç-aşınma odaklı; uzun-yol nakliye için tipik.
- Hedef 3 — Toplam maliyet minimum: Yakıt + ücretli-yol + sürüş saati ağırlıklı toplam.
- Hedef 4 — Çok-kriterli (Pareto-optimum): Süre + maliyet + yakıt arasında ödünleşme; karar verici Pareto cephesinden seçer.
Çok-amaçlı: ağırlıklı toplam (en yaygın) veya hiyerarşik (önce süre, sonra maliyet, sonra yakıt) veya Pareto-optimum yollar (gelişmiş karar destek için).
Shortest path varyantları — sahaya göre seç:
- Klasik Dijkstra: Non-negatif kenarlı, tek-kaynak, foundational.
- Bellman-Ford (1958): Negatif kenar destekli, negatif cycle algılaması, distance-vector yönlendirme.
- Floyd-Warshall (1962): Tüm-çift, küçük graf, dinamik programlama.
- A (Hart-Nilsson-Raphael 1968):* Heuristic-guided tek-noktaya, coğrafi yol-ağı.
- Contraction Hierarchies: Ülke ölçeği yol-ağı, preprocessing-tabanlı, gerçek-zaman.
- Time-dependent shortest path: Trafik-aware, kenar ağırlığı zaman fonksiyonu.
- Stokastik shortest path (Polychronopoulos-Tsitsiklis 1996): Belirsiz kenar ağırlığı, risk-ayarlı.
- Resource-constrained shortest path (RCSP): Ek kaynak kısıtı (yakıt, zaman penceresi); column generation alt-problemi olarak VRP içine girer.
Akademik kaynaklar
Sayfanın frontmatter’ında sources alanında listelidir.
Kaynaklar
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. Foundational iki-sayfa makale; bilgisayar bilimindeki en çok atıf alan makalelerden biri.
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. Negatif kenarlı varyant için Bellman-Ford’un temel kaynağı.
- Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. Tüm-çift Floyd-Warshall’in tek-paragraflık kanonik kaynağı.
- Ahuja, R. K., Magnanti, T. L. ve Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Network akış ve shortest path alanının kanonik ders kitabı.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. ve Stein, C. (2009). Introduction to Algorithms (3. baskı). MIT Press. Dijkstra / Bellman-Ford / Floyd-Warshall öğretim referansı.
- Geisberger, R., Sanders, P., Schultes, D. ve Delling, D. (2008). Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Experimental Algorithms (WEA 2008), LNCS 5038, 319-333. Ülke ölçeği yol ağı için modern preprocessing-tabanlı algoritma.
- Hart, P. E., Nilsson, N. J. ve Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. A* algoritmasının kurucu makalesi.
- YÖK Tez Merkezi — anahtar kelime: ’en kısa yol’ veya ‘Dijkstra’ veya ‘graf algoritması’ — TR akademisinden 30+ tez. tez.yok.gov.tr
Sözlük
- Shortest Path Problem
- Ağırlıklı bir grafta iki düğüm arasında (tek nokta-noktaya, tek kaynak-tüm noktalara ya da tüm-çift varyantlarıyla) minimum toplam ağırlıklı yolu bulan foundational graf-OR problemi; polinom-zaman algoritmaları Dijkstra (1959), Bellman-Ford (1958), Floyd-Warshall (1962).
- Dijkstra Algorithm
- Edsger Dijkstra'nın (1959) non-negatif kenar ağırlıklı graflarda tek-kaynak shortest path için polinom-zaman algoritması; greedy yaklaşımla öncelik kuyruğundan en küçük geçici-mesafeli düğümü çıkarır, komşuları günceller; binary heap ile O((V+E)logV).
- MIP
- Karar değişkenlerinin bir kısmının tam sayı (örn. 'kaç kamyon', 'kaç vardiya') olduğu optimizasyon türü.
- VRP
- Bir depo veya birkaç depodan çıkan araçların hangi müşterilere hangi sıra ile gideceği kararı.
Benzer problemler
Birden Çok Fabrika, Birden Çok Müşteri — Her Fabrika Hangi Müşteriye Ne Miktarda Sevksin, Toplam Nakliye Minimum?
3-8 fabrika veya bölge deposundan 20-100 müşteriye haftalık sevkiyat yapan gıda, ambalaj veya tekstil üreticileri içindir. Her hafta verilen karar şudur: hangi fabrika hangi müşteriye, ne miktar gönderecek? Fabrika başına kapasiteler, müşteri başına talepler ve her çift için farklı kilometre/araç maliyeti varken — toplam nakliye faturasını en aza indirmek hedeftir. 'En yakın fabrika' veya 'her zaman böyle yapıyorduk' alışkanlığı, sistematik bir hesap karşısında genellikle %10-20 fazla yakıt + araç parası yazdırır.
Birkaç Araç, Birçok Müşteri — Hangi Aracı Hangi Sıraya Versem, Kapasite Aşılmasın, Toplam Yol Minimum?
Tek depodan günlük 10-100 müşteriye teslimat yapan distribütör veya tedarikçi (gıda, içecek, su, B2B yedek parça); araç kapasitesi sabit (2-5 ton, 30 m³), müşteri sipariş miktarı belli, teslim saati esnek. Her sabah üç soru: bugün kaç araç çıksın, hangi araç hangi müşterilere gitsin, hangi sırayla — kapasite aşılmadan toplam yol minimum. Sezgisel planlamacı 15-25 müşteriye kadar zihinsel idare eder; üstünde rota kalitesi düşer, aynı bölgedeki müşteri iki ayrı araca dağılır, günde 1-2 fazla araç yola çıkar. Toplam mesafenin %10-25'i ve günlük araç sayısının 1-2 adedi planlama kalitesine bağlıdır; yakıt + sürücü maliyeti operasyonel giderin %30-50'sini oluşturur.