Bir depodan çıkıp 5-30 müşteriye günlük teslimat yapan distribütörün klasik kararı: kaç araç çıksın, hangi araç hangi müşterileri ziyaret etsin, hangi sırayla — kapasite aşılmasın, toplam mesafe minimum. Akademik adı Capacitated Vehicle Routing Problem (CVRP); Dantzig-Ramser 1959'un başlattığı VRP ailesinin anasıdır.
Kısaca
Tanıdık geliyor mu?
- Depomuzdan günlük 30-100 müşteriye teslimat yapıyoruz; bayilik dağıtımı, B2B yedek parça, gıda-içecek distribütörlüğü gibi tek-depo operasyonu.
- Her müşteri için sipariş kg veya m³ olarak belli; aracın 2-5 ton kapasitesini aşmamak için planlamacı sezgisel olarak müşteri grupluyor.
- Müşterilerin zaman penceresi yok ya da çok geniş (saat 08:00-18:00 arası kabul) — günün herhangi bir saatinde teslim alıyorlar.
- Aynı bölgede yakın müşteriler iki ayrı araca dağılmış olabiliyor — 'bu hafta hangi araç hangi bölgeye gider' kararı eski plana göre yapılıyor.
- Sabah depoya kaç araç çıkması gerektiği planlamacıya kalıyor; bazı günler 3 araç yeterken bazı günler 5 araç çıkıyor — kuralı yok, hisle karar veriliyor.
- Yakıt + sürücü ücreti operasyonel giderin %30-50'sini oluşturuyor; ama hangi rota değişikliği ne kadar km tasarrufu getirir bilinmiyor.
- Yeni müşteri eklendiğinde 'bu hangi araca sığar' sorusu hesaplanmadan, depocu veya planlamacı sezgisiyle yanıtlanıyor.
Niye önemli?
Nasıl çözülür?
Teknik derinlik
Nasıl çözülür?
Teknik derinlikTek cümlede: Her müşteriye depodan ayrı sefer yerine, iki müşteriyi birleştirip aynı araca koyduğunda kaç km kısaldığını hesapla, en büyük tasarrufa sahip çiftleri kapasite yettiği sürece birleştir — saniyelerde uygulanabilir; daha kalitesi için yerel arama operatörleri ekle.
CVRP, yöneylem araştırması (matematik ve bilgisayar kullanarak işletme kararı çözen disiplin) literatüründe VRP ailesinin kanonik ve en eski üyesidir: 1959 yılına uzanan “The Truck Dispatching Problem” makalesi alanı başlattığı kabul edilir. Tek depo, çoklu araç, kapasite kısıtı, müşteri başı talep miktarı; zaman penceresi yok. Çözüm üç aşamalı:
1. Modelleme. Veri girdileri: depo konumu (tek koordinat), müşteri konumları ve talep miktarları (kg, m³, koli sayısı — birim ne olursa olsun toplamı kapasiteyi geçemez), araç filosu (homojen — hepsi aynı kapasitede; heterojen — farklı kapasitelerde), depodan müşteriye ve müşteriler arası mesafe matrisi (simetrik — A→B = B→A; asimetrik — şehir-içi tek yön nedeniyle farklı olabilir). Kısıtlar: her müşteri tam bir kez ziyaret edilir, her tur depoda başlar ve biter, bir tur içindeki toplam talep aracın kapasitesini geçmez. İsteğe bağlı ek kısıtlar: maksimum tur uzunluğu (sürücü vardiyası kısıtı), maksimum müşteri sayısı/tur, açık VRP (araç son müşteride sona erer, depoya dönmez — kiralık araç senaryoları), çok-depo VRP. Hedef fonksiyonu genelde toplam mesafenin (ya da yakıtın) minimumudur; ikinci sıraya araç sayısının minimumu eklenebilir.
2. Çözücü ile karar. Üç ana çözüm yöntemi:
- Klasik sezgisel — Clarke-Wright Savings (Tasarruf Algoritması): Her müşteri kendi turunda başlar (depo→müşteri→depo). İki ayrı turun birleştirilmesinden gelen “tasarruf” hesaplanır: A ve B müşterileri ayrı turlarda iken birleştirilirse mesafe ne kadar azalır? En büyük tasarruflu çiftler kapasite müsait olduğu sürece birleştirilir. Bilgisayar olmadan da hesaplanabilir, 100-200 müşteri için saniyeler içinde çalışır, optimuma genellikle %5-10 uzaklıkta sonuç verir. 60 yıllık olmasına rağmen orta ölçekli operasyonlarda hâlâ pratik bir başlangıç noktasıdır.
- Exact MIP — branch-and-cut-and-price (dallandır-kes-fiyatlandır — sütun üretimiyle güçlendirilmiş ağaç araması): 50-200 müşteri ölçeğinde optimum çözüm verir, ama çözüm süresi dakikalardan saatlere uzayabilir. Operasyonel kararı haftalık veya sezonluk vermek için uygundur — günlük dinamik planlama için ağırdır. MIP = Mixed-Integer Linear Programming (bir kısım değişkeni 0/1 bir kısmı sürekli olan eniyileme).
- Metaheuristikler — 2-opt, Or-opt, ALNS (Adaptive Large Neighborhood Search — uyarlanabilir büyük komşuluk araması; çözümü adım adım iyileştiren akıllı arama yöntemi): Clarke-Wright çıktısı üzerinde “iki kenarı yer değiştir” gibi yerel iyileştirme operatörleri uygulayarak çözümü adım adım daha iyiye taşır. 200-1000 müşteri ölçeği için pratiktir; dakikalar içinde optimumun %2-5’i içinde sonuç verir.
Pratik tercih: 50 müşteri altı için exact MIP (optimum garanti); 50-200 müşteri için Clarke-Wright + 2-opt iyileştirme; 200+ müşteri için ALNS veya benzer metaheuristik.
3. Saha entegrasyonu. Çıktı sürücü tabletine veya yazıcısına gönderilen sıralı listedir: “Araç 1 — saat 08:30 depodan çık → müşteri A (1,2 ton) → müşteri C (0,8 ton) → müşteri F (1,5 ton) → depoya dön.” Sipariş yönetim sistemi (ERP veya bağımsız sevkiyat yazılımı) CVRP çözücüsünü besler: müşteri sipariş listesi, talep miktarları, araç filosu durumu, depodaki stok. Akşam veya sabah erken hesaplanır; gün-içi yeni sipariş gelirse rolling-horizon ile yeniden planlama (genelde 5-15 dakika sürer). Aylık operasyon toplantısı: gerçek vs plan km, gerçek vs plan araç sayısı, tasarruf raporu.
Alternatifler
Manuel + spreadsheet + planlamacı sezgisi
ÜcretsizSıfır lisans
Kim için: 1-3 araç, günlük 15-30 müşteri, sabit bölge
- + Sıfır yazılım maliyeti
- + Planlamacının deneyimi öne çıkar
- + Hızlı değişiklik — telefonla doğrulama
- − 30-50 müşteri üstü ölçekte plan kalitesi düşer
- − Kapasite optimum kullanım garantisi yok
- − Yeni planlamacı yetiştirme süresi uzun
- − Tarihsel km/araç verisi tutulmaz
Yerel rotalama yazılımı (TR pazarı SMB)
Kurumsal10K-40K TRY kurulum + 3K-10K TRY/ay abonelik
Kim için: 5-15 araç, günlük 50-200 müşteri, tek depo
- + TR adres ve harita verisi entegre
- + Türkçe arayüz, yerel destek
- + Sürücü mobil uygulaması dahil
- − Tasarruf-tipi veya en yakın komşu tipi basit motor tipiktir; karmaşık kısıtta zayıf
- − Çok-depo veya farklı kapasiteli karışık filo zayıf
- − Algoritma şeffaflığı kısıtlı — 'neden bu rota' yanıtlanmaz
Uluslararası uzman rotalama yazılımı
Kurumsal100-500 EUR/araç/ay abonelik veya 1,5M-8M TRY/yıl lisans
Kim için: 20-100 araç, çok-depo, heterojen filo, ağır kısıtlar
- + Olgun: kapasiteli rota + uzantıları (karışık filo, depo dönüşsüz açık tur, çok-depo) tam destekli
- + Büyük ölçek için gelişmiş arama motorları içerir
- + Senaryo karşılaştırma ve simülasyon güçlü
- − Yüksek lisans + 3-6 ay kurulum
- − Türkçe destek sınırlı olabilir
- − Operasyon ekibi eğitimi geniş
Açık-kaynak çözücü + iç geliştirme
Açık KaynakLisans ücretsiz; iç geliştirme 8-16 hafta veya 300K-1M TRY danışmanlık
Kim için: Teknoloji ekibi olan distribütör, mevcut ERP entegrasyonu istenen
- + Lisans bedeli yok
- + Kapasiteli rota planlaması için açık kaynak çözüm araçları olgun
- + Tasarruf yöntemi + yerel iyileştirme referans uygulamaları açık kaynakta geniş
- − İçeride optimizasyon ve yazılım uzmanı şart
- − Saha sistemi olgunluğuna gelmek 6-12 ay
- − Bakım sorumluluğu işletmede
Tavsiye
Çözüm görüşmesinde sor
- Motor altyapısı nedir — tasarruf yöntemi, optimum garanti veren çözücü, gelişmiş arama, yoksa basit en yakın komşu? Demoda 50 müşteri için hangi yöntemle sonuç üretiyor?
- Aynı kapasiteli araçlar mı yoksa farklı kapasiteli karışık filo da destekleniyor mu? Karışık filoda hangi araç hangi müşteriye gider kararı motor tarafında mı veriliyor?
- Aracın son müşteride bittiği (depoya dönmediği) kiralık araç turu ve çok-depolu rota destekleniyor mu?
- Mesafe matrisi nasıl hesaplanıyor — düz hat, gerçek yol mesafesi, yoksa trafik-eklemeli süre? Bölgesel doğruluk nasıl test edildi?
- Gün-içi yeni sipariş geldiğinde plan yeniden çözülüyor mu? Kaç saniyede güncel rota sürücüye iletilir?
- Tur uzunluğu kısıtı (örn. maks 6 saat veya 300 km) ve sürücü vardiya kısıtı motor düzeyinde mi kısıtlanıyor, yoksa sonradan filtre mi uygulanıyor?
- Pilot dönemde (8-12 hafta) gerçek operasyon verisi ile manuel planlamaya kıyasla nasıl tasarruf raporu sunabilirsiniz?
- Sözleşme biterse müşteri konum verisi, sipariş geçmişi, rota geçmişi ve mesafe matrisi hangi açık formatta (CSV, GeoJSON veya benzeri) dışa aktarılabilir?
Teknik detay
Editör notu
Bu problem halk dilinde “araç rotası”, “dağıtım planı” veya “sevkiyat sırası” diye anılır. Akademik literatürde adı Capacitated Vehicle Routing Problem (CVRP) — VRP ailesinin en eski ve kanonik üyesidir. Dantzig ve Ramser 1959’da bu problemi tanımlayarak operasyon araştırması alanına bir alt-disiplin armağan etti. Sizin her sabah sorduğunuz soru — “kaç araç çıksın, hangi araç hangi müşterilere uğrasın, hangi sırayla, kapasite aşılmasın” — akademik dünyanın 60+ yıldır çalıştığı sorudur.
Bu sayfa VRPTW (#002) ile karıştırılmamalı: VRPTW her müşterinin teslim almaya hazır olduğu zaman penceresini ekler (“dükkân sadece 09:00-12:00 arası açık”). CVRP’de zaman penceresi yoktur — müşteri tüm gün hazırdır. Vegan teslimat saatleri vs B2B esnek-zamanlı teslimat arasındaki farktır. CVRP daha kolay (yumuşak); VRPTW daha gerçekçi ama matematiksel olarak daha zor. Eğer müşterilerinizin teslim alma saati gerçekten esnek ise — bayilik dağıtımı, B2B yedek parça, su-içecek distribütörlüğü — bu sayfa size aittir. Eğer dar zaman penceresi varsa (e-ticaret kapıda teslimat, soğuk zincir) #002’ye geçin.
Sektörde en sık atlanan nokta: Clarke-Wright savings algoritmasının pratik gücü. 1964’te bilgisayar yokken kâğıt-kalem hesaplanmak üzere geliştirilmiş bu sezgisel, 60 yıl sonra hâlâ ölçek değiştirmemiş orta-ölçekli operasyonlarda optimum’a %5-10 uzaklıkta sonuç verir, dakikalar içinde çalışır. Bir yazılım demosunda satıcı “yapay sezgisel algoritmamız” veya “patentli optimizasyon motorumuz” diyorsa, ondan 50 müşterilik benchmark üzerinde Clarke-Wright + 2-opt iyileştirme ile karşılaştırma çıktısı isteyin. Eğer fark %2’nin altındaysa, ekstra lisans bedeline değmez. İkinci atlanan nokta: mesafe matrisi kalitesi. Çoğu yazılım Öklid (düz hat) mesafe kullanır; gerçek şehir-içi yol mesafesi 1,3-1,8 katına çıkar. Yanlış mesafe yanlış rota demektir; gerçek yol matrisinin pilot dönemde test edilmesi gerekir.
Adım adım yol — KOBİ için
Aşama 1 — Önce ölç, sonra plan. En az 4 hafta tablo tut: araç başı günlük km, müşteri sayısı, kapasite kullanım yüzdesi (yüklü/maks), depodan-depoya tur süresi, sürücü mesai saati. Bu temel olmadan hangi yazılımın hangi sonucu vereceğini ölçemezsin.
Aşama 2 — Müşteri-talep tablosunu çıkar. Her müşterinin tipik sipariş miktarı (kg veya m³), adresi, koordinatı, varsa özel kısıtı (kamyon büyüklüğü sınırı — “büyük araç giremez”, manuel boşaltma süresi). Bu tablo çoğu KOBİ’de planlamacının kafasında durur; yazıya dökmek tek başına %5-10 verim artırır.
Aşama 3 — Pilot. 6-10 hafta. 1-3 araç ile başla. Başarı kriteri önceden yazılı: “60 günde toplam km -%10, kapasite kullanım +%5, günlük araç sayısı -1 adet”. Kriter tutmazsa pilot sona erer — sözleşmede çıkış hakkı korunur.
Aşama 4 — Yaygınlaştırma. 2-4 ayda tam filoya yayım. Sürücü eğitimi 1-2 hafta. Bölge başına bir “şampiyon” sürücü atan. Aylık operasyon toplantısı: gerçek vs plan km, kapasite kullanım, müşteri başına maliyet.
Riskler — ne yanlış gidebilir
- Talep tahmini sapması. Müşterinin günlük siparişi planlanan miktardan %20-50 farklı çıkarsa, kapasite ya yarı boş ya aşıldı. Sipariş kesinleşme saati (cut-off) ile rota hesaplama saati arası mümkün olduğunca kısa tutulmalı; rolling-horizon yeniden planlama altyapısı şart.
- Araç arızası gün-içi. Bir araç yolda arızalanırsa, kalan müşterilerin diğer araçlara yeniden dağıtımı sezgisel yapılırsa kapasite aşılır veya müşteri atlanır. Yazılım gün-içi yeniden çözüm desteklemeli; 30 dakika içinde yeni plan üretmeli.
- Müşteri zaman-talebi sonradan çıkması. “Aslında sadece sabah teslim alıyorum” diyen müşteri CVRP modelini bozar — problem VRPTW’ye dönüşür. Müşteri seti büyürken zaman penceresi sayısı 10-20’yi geçerse, VRPTW çözücüsüne geçiş gerekir.
- Tek tedarikçi (TMS) bağımlılığı. Sözleşmede “müşteri konum verisi, sipariş geçmişi, rota geçmişi yıllık standart format ihracı (CSV veya GeoJSON)” maddesi yoksa, sistemden ayrılmak distribütörün operasyonel hafızasını kaybetmesi anlamına gelir.
Çözüm yöntemine teknik bakış
CVRP literatüründe kullanılan ana yöntemler:
| Yaklaşım | Tipik ölçek | Çözüm süresi | Garantili optimum? |
|---|---|---|---|
| Sezgisel (planlamacı + kural) | 1-3 araç, 15-30 müşteri | anında | Hayır, %50-80 optimum |
| Clarke-Wright savings (1964) | 50-200 müşteri | saniye-dakika | Hayır, optimuma %5-10 |
| Clarke-Wright + 2-opt / Or-opt | 50-300 müşteri | dakika | Hayır, optimuma %3-7 |
| Exact MIP — branch-and-cut-and-price | 50-200 müşteri | dakika-saat | Evet (sınırlı ölçekte) |
| ALNS metaheuristik | 200-1000 müşteri | dakika | Hayır, optimuma %2-5 |
| Sütun üretimi (column generation) | 100-500 müşteri, çok-tur | saat | Pratik olarak yakın-optimum |
Formülasyon seçimi:
- 2-index formülasyon: Her kenar (i, j) için bir karar değişkeni. Anlaşılması kolay, ama alt-tur eliminasyon kısıtları (subtour elimination constraints — SEC) yüzünden büyük ölçek için ağır.
- 3-index formülasyon: Her (i, j, araç k) için karar değişkeni. Heterojen filo, açık VRP gibi uzantılar için daha esnek; değişken sayısı katlanır.
Hedef fonksiyonu seçimi:
- Toplam mesafe minimum: En yaygın; yakıt + bakım odaklı.
- Toplam süre minimum: Sürücü maliyeti yakıttan büyükse.
- Araç sayısı + toplam mesafe (hiyerarşik): Önce araç sayısı, sonra mesafe — filo küçültme kararı için.
- Yakıt + sürücü ücreti birleşik: Operasyonel maliyetin doğrudan modellenmesi.
Genişletmeler — CVRP’nin pratik akrabaları:
- Heterogeneous Fleet VRP: Filoda farklı kapasiteli araçlar — büyük araç şehir merkezine giremez gibi kısıtlarla birleşir.
- Open VRP: Araç son müşteride biter, depoya dönmez (kiralık araç, gig ekonomi şoför).
- Multi-Depot VRP: Birden fazla depo; her müşteri en uygun depoya atanır.
- Distance-Constrained VRP: Tur uzunluğu sürücü vardiyasıyla sınırlı.
- Asymmetric CVRP: Şehir-içi tek yön nedeniyle A→B ile B→A mesafesi farklı.
VRPTW (#002), PDPTW (#046), DARP (#047) ve TSP (#068) CVRP’nin yakın akrabalarıdır. CVRP ailenin en sade ve en eski üyesidir; diğerlerini anlamak için önce CVRP anlaşılmalıdır.
Akademik kaynaklar
Sayfanın frontmatter’ında sources alanında listelidir.
Kaynaklar
- Dantzig, G. B. ve Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. VRP ailesinin temelini atan makale — ‘kapasiteli TSP’ olarak ilk tanımlama.
- Clarke, G. ve Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. Klasik savings algoritması — hâlâ pratik benchmark.
- Toth, P. ve Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2. baskı). SIAM-MOS. VRP alanının kanonik kitabı.
- Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. Tarihsel ve metod karşılaştırma.
- Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P., Reis, M., Uchoa, E. ve Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106(3), 491-511. Modern exact CVRP algoritması.
- YÖK Tez Merkezi — anahtar kelime: ‘kapasiteli araç rotalama’ veya ‘CVRP’ — TR akademisinden 30+ tez. tez.yok.gov.tr
Sözlük
- Kapasiteli Araç Rotalama
- Tek depodan başlayıp depoya dönen, her müşteriyi tam bir kez ziyaret eden ve tur başına toplam talebi araç kapasitesinin altında tutan minimum maliyetli araç rotalarının tasarımı.
- Clarke-Wright Savings
- Kapasiteli Araç Rotalama Problemi için 1964 tarihli klasik sezgisel: her müşteri kendi turunda başlar, iki tur birleştirildiğinde elde edilen en büyük 'tasarruf'lu çiftler kapasite müsait olduğu sürece adım adım birleştirilir.
- VRP
- Bir depo veya birkaç depodan çıkan araçların hangi müşterilere hangi sıra ile gideceği kararı.
- MIP
- Karar değişkenlerinin bir kısmının tam sayı (örn. 'kaç kamyon', 'kaç vardiya') olduğu optimizasyon türü.
Benzer problemler
Bir Düğümden Diğerine En Kısa Yol — Ağırlıklı Graf Üzerinde Nasıl Hesaplarım?
İki nokta arasındaki en hızlı veya en kısa yolu hesaplaması gereken KOBİ'ler içindir: 10-50 araçlı saha servis ekibi (tesisat, elektrik, beyaz eşya tamiri), şehir içi kurye-kargo operasyonu, ya da acil servis koordinasyonu yapan bir merkez. Her gün yüzlerce 'A'dan B'ye en kısa sürede nasıl giderim' sorusu sorulur; cevap trafik, yol kapanması ve araç tipine göre değişir. Yanlış rota teknisyenin günde 1-2 işini eksik yapmasına, kuryenin geç teslimatına ve müşteri kaybına dönüşür. Manuel veya 'gözüyle' verilen rota kararları, ağ üzerinden hesaplanan rotaya kıyasla araç başına günde 20-60 dakika boşa harcatabilir.
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.