Tek araç, kapasitesiz, depo geri-dönüşsüz: bir dizi noktayı her birini tam bir kez ziyaret edip başlangıca dönen minimum-mesafe turunu çıkar. Tüm rotalama OR'unun atası problem — VRP'ler bundan türer (akademik adı: TSP).
Kısaca
Tanıdık geliyor mu?
- Tek araçlı bir saha hizmet operasyonumuz var — günde 8-15 müşteri ziyareti yapan teknisyen, sırayı kendi sezgisi ile koyuyor.
- Orta-ölçekli imalat işletmemizde bir satış temsilcisi haftada bir gün bölge turu yapıyor (15-40 tedarikçi/müşteri ziyareti); tek araç, kapasite kısıtı yok, sıra optimum değil.
- PCB delgi makinası ya da otomatik montaj-takım makinası kullanıyoruz — delgi/lehim başı 500-5.000 nokta arasında dolaşıyor, sıralama makine programcısının elinde.
- Yer altı kablo döşeme rotası ya da boru hatları döşeme sırası planlıyoruz — tek ekip, tek tur, kapasitesiz.
- Otomatik depo robotu (single-pick AS/RS) raf turları çıkarıyor — robot kapasite-sınırı yok ya da tek nesne taşıma.
- Şehir-içi soğuk-zincir tedarikçi turu (tek araç, küçük kontenj yük); sıralamayı şoför rutinine göre yapıyor.
- Düğüm sayımız 50-500 arasında — exact MIP çözücü ile çalışabilir ölçek, ama 'TSP NP-hard, sezgisel olmalı' sezgisi ile heuristic'e koşuyoruz.
Niye önemli?
Nasıl çözülür?
Teknik derinlik
Nasıl çözülür?
Teknik derinlikTek cümlede: Önce noktalar arası mesafe matrisini oluştur (gerçek yol mesafesi, simetrik mi asimetrik mi belirle), sonra ölçeğine göre — 1.000 nokta altı için MIP çözücü ile exact optimum, üstü için k-opt yerel arama (Lin-Kernighan ailesi) — birkaç dakikada sırayı bul.
Bu problem yöneylem araştırması (matematik ve bilgisayar kullanarak işletme kararı çözen disiplin) literatüründe Travelling Salesman Problem (TSP — gezgin satıcı problemi) adıyla 70+ yıldır çalışılır ve modern kombinatoryel optimizasyonun kurucu problemidir. Kanonik tanım: N adet düğüm (şehir, müşteri, delgi noktası, kablo bağlantısı) ve düğümler arası mesafe (ya da süre, maliyet) matrisi verildiğinde, her düğümü tam bir kez ziyaret edip başlangıca dönen minimum toplam-maliyet Hamilton turunu (her düğümü bir kez geçen kapalı tur) bul. Tek araç, kapasite yok, zaman penceresi yok, depo dönüşü her zaman başlangıç noktasına. Çözüm üç aşamalı:
1. Modelleme. Veri girdileri: düğüm listesi (her düğüm için konum ya da kimlik etiketi), düğümler-arası mesafe matrisi (Euclidean mesafe, gerçek yol mesafesi, ya da süre — şehir-içi rotada yol-tabanlı, makine kafasında Manhattan mesafe), simetri özelliği (mesafe A→B = B→A ise simetrik TSP, değilse — örn. tek-yön sokak — asimetrik TSP / ATSP), metrik özelliği (üçgen eşitsizliği sağlanıyorsa metrik TSP, 3/2-yaklaşıklık garantisi veren özel sezgisel uygulanabilir). Hedef: toplam tur maliyeti minimum. Kısıt: her düğüm tam bir kez ziyaret + tek bir kapalı tur (alt-tur — subtour — yasak).
2. Çözücü ile karar. Akademik üç ana yaklaşım: (i) Exact branch-and-cut MIP (dallandır-kes-sınırla — olası çözümleri ağaç gibi tarayıp kesme düzlemleriyle daraltma) — kesme-düzlemi çözümü 1950’lerde başlatıldı; ileri solver’lar bugüne kadar 85K+ düğümlü TSP’leri exact çözmüştür. Saha ölçek (50-500 düğüm) için ticari ya da olgun açık-kaynak MIP (Mixed-Integer Linear Programming — bir kısım değişkeni 0/1 bir kısmı sürekli olan eniyileme) çözücüleri birkaç dakikada exact bitirir. (ii) Dinamik programlama (Held-Karp) — 1960’lardan kalma O(n²·2^n) DP formülasyonu, 20-25 düğüm altı için pratiktir, eğitim referansı; (iii) Sezgisel — Lin-Kernighan ailesi — k-opt yerel arama (turun k kenarını söküp en iyi yeniden bağla); modern LKH (Lin-Kernighan-Helsgaun) uygulaması milyon düğüm ölçeğine kadar optimum’a %0.1-1 yaklaşır, 1.000+ düğümlü saha problemi için referans sezgisel. Yapı taşı sezgiseller: nearest-neighbor (en yakın komşu), Christofides 3/2-yaklaşıklık (metrik TSP için), savings algorithm, 2-opt, 3-opt yerel arama.
3. Saha entegrasyonu. Çıktı kullanıma göre üç katmanlı: (a) saha hizmet operasyonu — sürücü mobil uygulamasında sıralı durak listesi + navigasyon, gün başında atanır, gün-içi güncellenmez; (b) makine programlama — PCB delgi ya da takım makinası NC programına gömülü delgi/takım sırası, parça-grubu başına bir kez hesaplanır; (c) kablo / boru rotası — saha mühendisinin rota planı, kuru-koşu öncesi tek seferlik karar. TSP modülü genelde rotalama yazılımının ya da hat programlama paketinin içine gömülüdür — bağımsız ürün olarak satılması nadirdir. Üç aylık operasyon komitesi: gerçek tur mesafesi vs plan, sürücü zamanı sapması, ek tur sayısı.
Alternatifler
Sezgisel sıralama + spreadsheet
ÜcretsizSıfır lisans
Kim için: Çok küçük ölçek (günlük <10 durak), planlamacının kafasında tutabildiği boyut
- + Sıfır yazılım maliyeti
- + Planlamacının saha bilgisi öne çıkar
- + Anlık ETA değişimine telefonla cevap
- − 20 durak üstü insan zihni optimum'dan %20-40 sapar
- − Tutarsız — günden güne farklı sıralama çıkar
- − Ölçü yok — hangi turun ne kadar mesafe olduğu kayda alınmaz
- − Çoklu araç ya da kapasite gerekirse hızlı çöker (zaten VRP'ye geçilir)
Genel rotalama / saha hizmet yazılımı (TSP modülü gömülü)
Kurumsal100-400 TRY/araç/ay abonelik ya da 200K-800K TRY tek-seferlik lisans
Kim için: Saha hizmet operasyonu (10-50 araç), tek araçlı tur, kapasitesiz
- + Tur sıralama motoru hazır — en yakın komşu + yerel iyileştirme tipik
- + Sürücü mobil uygulaması, navigasyon, müşteri bilgisi entegre
- + TR yerel harita ve trafik verisi var
- − Algoritma şeffaflığı düşük — 'hangi yöntem kullanılıyor' sorulduğunda net cevap nadir
- − Optimum garanti veren çözücü genelde yok, sadece hızlı yaklaşıklık
- − 500+ duraklı turda en iyi turdan sapma artar
Açık-kaynak çözücü + özel TSP modülü
Açık KaynakLisans ücretsiz; iç geliştirme 8-16 hafta ya da 200K-800K TRY danışmanlık
Kim için: Teknoloji ekibi olan işletme, makine programlama (PCB, takım), saha rotası özel uyarlama
- + Optimum garanti veren çözücüler açık kaynakta mevcut
- + Milyon duraklı turda da optimuma yakın sonuç veren endüstri-standardı sezgisel araçlar açık kaynak
- + Tek-yön sokak, kâr-paylı tur gibi varyantlar için uyarlanabilir
- − İçeride optimizasyon uzmanı + entegrasyon ekibi gerekli
- − İlk prototipten saha sistemine geçiş 3-6 ay
- − Bakım sorumluluğu işletmede
Endüstri-özel makine programlama paketi (PCB / CNC)
Kurumsal500K-3M TRY makina yazılım paketi içinde gömülü
Kim için: Otomatik PCB delgi, monte makinası, lazer kesme — makine üreticisinin paketi
- + Delgi/montaj kafası sırası makine üreticisi tarafından kalibre edilmiş
- + Makine programı çıktısı doğrudan tezgâha yüklenir
- + Operatör eğitimi makine üreticisinden gelir
- − Makine üreticisine bağımlı — başka makine için yeniden satın alma
- − Algoritma açık değil, optimumdan ne kadar uzak ölçülemez
- − Özelleştirme (örn. delgi başlığı değiştirme cezası) zor
Tavsiye
Çözüm görüşmesinde sor
- Tur sıralama motorunda hangi yaklaşım kullanılıyor — optimum garanti veren çözücü, en yakın komşu + yerel iyileştirme, endüstri-standardı sezgisel, yoksa sadece en yakın komşu?
- Mesafe matrisi tek-yön sokak veya yön-bağımlı süre içeren asimetrik durumu destekliyor mu? Yoksa A→B ve B→A her zaman eşit mi varsayılıyor?
- Mesafe matrisi nasıl üretiliyor — düz hat mı, gerçek yol-tabanlı mı, trafik-bağımlı süre matrisi mi? Yenileme periyodu?
- Tipik veri seti boyutu (durak sayısı) için çözüm süresi nedir? 100, 500, 1.000 durak için sırasıyla?
- Modülün ürettiği turun en iyi olası tura yakınlığı (yüzde sapma) raporlanır mı?
- Tek araçtan çoklu araç gerektiren kapasiteli rotalamaya geçildiğinde (kapasite kısıtı, çoklu tur, depo dönüşü) aynı altyapı kullanılabilir mi, yoksa farklı modül mü?
- Sözleşme biterse tur verisi (durak konumları, üretilen turlar, mesafe matrisi) hangi formatta dışa aktarılabilir?
Teknik detay
Editör notu
Bu problem halk dilinde “tur planlama”, “ziyaret sırası” ya da “rota sırası” diye anılır. Akademik literatürde çok net bir adı vardır: Travelling Salesman Problem (TSP). TSP, operasyon araştırmasının kurucu problemidir — VRP (#002), PDPTW (#046), Berth Allocation (#026) ve onlarca diğer rotalama / çizelgeleme problemi TSP’nin yapı taşı genişlemeleridir. Yapısal fark net: TSP tek araç, tek tur, kapasitesiz, başlangıca dönüşlü, zaman penceresi yok. VRP çoklu araç + depo + kapasite ekler; VRPTW zaman penceresi ekler; PDPTW kaynak-hedef çifti ve sıralama kısıtı ekler. Bir tedarikçinin “rotalama modülü” pazarlamada hangi yapıyı çözdüğünü test etmeden satın alma kararı vermek, çoklu araç ihtiyacı doğduğunda altyapının yeterli olmadığını ayda anlamak demektir.
Sektörde en sık atlanan nokta: modern exact TSP çözücülerinin uygulama eşiği. Pratisyenin sezgisi çoğu kez “TSP NP-hard (problem büyüdükçe çözüm süresi katlanan zor problemler sınıfı), exact imkansız, sezgisel kullanmak zorundayız” der. Gerçek ise farklı: olgun branch-and-cut solver’ları 85K+ düğüm exact çözmüştür; 100-500 düğümlü saha problemi modern MIP çözücüsü ile birkaç dakikada optimum’a iner. Sezgisel (nearest-neighbor + 2-opt) çoğu pakette varsayılan — saha veri seti üzerinde optimum’dan %15-30 sapar. Pratik kural: 1.000 düğüm altı operasyonel TSP’de exact MIP uygulanabilirdir; 1.000-100K düğüm aralığında LKH sezgiseli optimum’a %0.1-1 yaklaşır. “Sezgisel kullanmak zorundayız” sezgisi yanlış; ölçek bilinmeden karar verilmez.
İkinci atlanan nokta: simetrik vs asimetrik TSP ayrımı. Şehir-içi rotada tek-yön sokak, otoyol giriş-çıkış, ya da yön-bağımlı süre asimetrik mesafe matrisi yaratır — A→B mesafesi B→A’dan farklıdır. Çoğu paketin TSP modülü simetrik varsayar; asimetrik veri sokulduğunda yanlış optimum üretir. Asimetrik TSP (ATSP) ayrı modellemeye ihtiyaç duyar.
Adım adım yol — KOBİ için
Aşama 1 — Önce ölç, sonra plan. En az 8-12 hafta tur verisi: her tur için durak sayısı, durak konumları, gerçek tur mesafesi (araç odometresi), tur süresi, sürücü kim, gün-içi sıra değişikliği oldu mu, müşteri sırasında ziyaret pencereleri uygundu mu. Mesafe matrisi: ziyaret edilen tüm düğüm çiftleri için tipik yol mesafesi ve süresi (zayıf trafik vs tepe trafik). Bu envanter olmadan hangi yazılımın hangi sonucu vereceği bilinmez.
Aşama 2 — Bilgi sermayesini çıkar. Mevcut sezgisel sıralamanın optimum’dan uzaklık tahmini: 30-50 düğümlü bir gün-veri seti üzerinde açık-kaynak MIP çözücü ile exact tur hesapla, sürücünün gerçek turuyla karşılaştır. Tipik fark %15-30 olur. Bu sapma yazılım iş tezinin temel bilgi sermayesidir. Düğüm sayısı her gün değişiyorsa, ortalama / tepe günleri ayrı çıkar.
Aşama 3 — Pilot. 6-10 hafta. Bir araç ya da makina için TSP modülünü mevcut sezgisel sıralama ile paralel çalıştır. Karar sürücüde / operatördedir; sistem öneri verir. Başarı kriteri önceden yazılı: ortalama tur mesafesi -%10 minimum, tur süresi -%8, sürücü memnuniyeti nötr ya da pozitif.
Aşama 4 — Yaygınlaştırma. 4-9 ay sürede tam filo / makine parkı. Üç aylık operasyon komitesi: gerçek tur mesafesi vs plan, sürücü zamanı sapması, müşteri penceresi isabet raporu, makine kafası süresi raporu.
Riskler — ne yanlış gidebilir
- Yol süresi varsayımı statik kalır. Mesafe matrisi tek-noktalı ortalama yol süresine kurulursa, tepe trafik zamanlarındaki gerçek süre %50-100 sapar. Saat-bant bağımlı süre matrisi (örn. her 30 dakikalık arc süresi profili) gerekli; pilot döneminde planlanan vs gerçek süreler karşılaştırılmalı.
- Saha aksiyon süresi modelin parçası mı? Bir saha teknisyeni durakta 30-90 dakika harcar; bu hizmet süresi tur planına dahil değilse, sıralama matematiksel olarak optimum ama saha-uygulanabilir değildir. Hizmet süresi düğüme atanmış sabit ya da olasılıksal değer olarak modellenmeli.
- Düğüm sayısı büyür, sezgisel optimum’dan uzaklaşır. 50 düğümde nearest-neighbor + 2-opt optimum’a %5-10 yaklaşır; 500 düğümde %15-25 sapar; 5.000 düğümde %30+ sapar. Ölçek büyüdükçe LKH ya da exact MIP’e geçiş gerekir; sezgisel sezgi ile sabit tutmak büyüme ile birikimli kayıp yaratır.
- Tek tedarikçi rotalama yazılımı bağımlılığı. Sözleşmede “tur verisi, mesafe matrisi, çözüm geçmişi standart formatta ihracı” maddesi yoksa, sistemden ayrılmak işletmenin saha tur hafızasını kaybetmesi anlamına gelir. Müşteri konumları ve ziyaret pencereleri verisi bu hafızanın çekirdeği.
Çözüm yöntemine teknik bakış
| Yaklaşım | Tipik ölçek | Çözüm süresi | Garantili optimum? |
|---|---|---|---|
| Sezgisel sıralama (planlamacı + kafa) | <20 düğüm | anında | Hayır, %60-80 optimum |
| Nearest-neighbor + 2-opt | 20-200 düğüm | saniye | Hayır, %85-95 optimum |
| Christofides 3/2-yaklaşıklık (metrik TSP) | 50-500 düğüm | saniye | 3/2 yaklaşıklık garantisi |
| Dinamik programlama (Held-Karp) | <25 düğüm | dakika | Evet (exact) |
| Branch-and-cut MIP | 50-100K düğüm | dakika-saatler | Evet (bound içinde) |
| Lin-Kernighan / LKH | 1K-1M+ düğüm | dakika-saat | Hayır, optimum’a %0.1-1 |
| Metaheuristik (tabu, genetik, ant colony) | esnek | esnek | Hayır, iyi pratik kalite |
TSP varyantları — sahaya göre seçim:
- Simetrik TSP: Mesafe A→B = B→A. Şehir-dışı yol, hava-hattı, PCB delgi. En basit ve en çok çalışılmış varyant.
- Asimetrik TSP (ATSP): Mesafe yön-bağımlı. Şehir-içi tek-yön sokak, yön-bağımlı süre. Modelleme biraz daha zor, branch-and-cut yine kullanılır.
- Euclidean TSP: Düğümler düzlemde, mesafe çizgisel uzaklık. PCB delgi, fabrika hat içi.
- Metrik TSP: Üçgen eşitsizliği sağlanır (mesafe A→C ≤ A→B + B→C). Christofides 3/2-yaklaşıklık geçerli.
- TSP with profits / OP: Düğümlerin değeri (kâr) var; tüm düğümleri ziyaret etmek zorunlu değil. Saha hizmet için “öncelikli müşteri” varyantı.
Hedef fonksiyonu seçimi:
- Hedef 1 — Toplam mesafe / yakıt minimum: Yakıt + sürücü süresi odaklı.
- Hedef 2 — Toplam süre minimum: Sürücü zamanı / makine süresi odaklı.
- Hedef 3 — Maksimum durak süresi minimum (minmax TSP): Adil dağıtım ya da iş güvenliği odaklı.
Akademik kaynaklar
Sayfanın frontmatter’ında sources alanında listelidir.
Kaynaklar
- Dantzig, G., Fulkerson, R. ve Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2(4), 393-410. TSP’nin kesme-düzlemi çözüm yönteminin kurucu çalışması.
- Lin, S. ve Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516. Modern sezgiselin temeli.
- Applegate, D., Bixby, R., Chvátal, V. ve Cook, W. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press. Princeton-Georgia Tech araştırma grubunun exact branch-and-cut solver’ı için kanonik kitap.
- Held, M. ve Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210. O(n²·2^n) dinamik programlama formülasyonu.
- Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130. LKH — milyon düğüme kadar optimum’a %0.1-1 yaklaşan sezgisel.
- YÖK Tez Merkezi — anahtar kelime: ‘gezgin satıcı’ ya da ‘TSP’ ya da ’tur optimizasyonu’ — TR akademisinden 30+ tez. tez.yok.gov.tr
Sözlük
- Travelling Salesman Problem
- Bir grafta her düğümü tam bir kez ziyaret edip başlangıca dönen minimum-maliyetli Hamilton turunu bulan, kurucu kombinatoryel optimizasyon problemi.
- Branch-and-Cut
- Dal-sınır (branch-and-bound) ile kesme-düzlemi (cutting plane) yöntemlerini birleştiren exact MIP çözüm çerçevesi — arama ağacının her düğümünde geçerli eşitsizlikler (kesimler) LP gevşemesini sıkıştırır, sonra dallandırma yapılır.
- 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
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.
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.