Birden çok fabrika veya depodan, birden çok müşteri veya dağıtım noktasına sevkiyat — her hat üzerinde ne kadar gönderilmeli ki toplam nakliye maliyeti minimum, kapasiteler aşılmasın, talepler tutulsun. Lineer programlamanın kurucu problemi: Hitchcock (1941) ve Koopmans (1947).
Kısaca
Tanıdık geliyor mu?
- 3-8 fabrika ya da bölge deposundan 20-100 müşteriye haftalık sevkiyat yapıyoruz; hangi fabrika hangi müşteriye gönderecek kararı genelde alışkanlık veya 'en yakın fabrika' kuralıyla veriliyor.
- Süt-toplama kooperatifiyiz; 50-200 üretici çiftlikten 3-6 işleme tesisine günlük akış var — hangi çiftliğin sütü hangi tesise gidecek kararı tarihten geliyor.
- Tekstil hammadde-fason zincirimiz var; merkez deposundan 30-80 fason atölyeye iplik ve kumaş gönderiyoruz — maliyet matrisi 5 yıldır güncellenmedi.
- Yeni bir fabrika veya depo açıldığında veya yeni bir müşteri eklendiğinde, akış paylarını yeniden hesaplamıyoruz — eski-dönem dağılımıyla devam ediyoruz.
- Yakıt fiyatı veya nakliye sözleşmesi değişti, ama hangi fabrikadan hangi müşteriye akış miktarı aynı kaldı.
- Toplam nakliye maliyeti yıllık bütçenin %10-20'sini geçiyor; 'akışları yeniden çizsek ne kazanırız' sorusu yıllardır cevapsız.
- Bir fabrika kapasitesi büyütme yatırımı düşünüyoruz; '1 ton ek kapasite toplam nakliyeye ne katar' sorusunu sayısal cevaplayamıyoruz.
Niye önemli?
Nasıl çözülür?
Teknik derinlik
Nasıl çözülür?
Teknik derinlikTek cümlede: Fabrika-müşteri çiftleri için birim nakliye maliyeti matrisi, fabrika kapasiteleri ve müşteri talepleri verildiğinde lineer programlama çözücüsü her fabrikadan her müşteriye gönderilecek miktarı (xij) saniyeler içinde hesaplar — toplam nakliye maliyeti en az olacak şekilde, kimse aç kalmadan ve kimse kapasiteyi aşmadan.
Bu problem yöneylem araştırması (matematik ve bilgisayar kullanarak işletme kararı çözen disiplin) literatüründe Transportation Problem veya Hitchcock Problem adıyla tanınır; lineer programlamanın kurucu örneklerinden biridir. Çözüm üç aşamalı:
1. Modelleme. Veri girdileri: kaynaklar (m adet fabrika veya depo — her birinin haftalık kapasite si, ton veya palet cinsinden), hedefler (n adet müşteri veya dağıtım noktası — her birinin haftalık talebi dj), maliyet matrisi (cij — fabrika i’den müşteri j’ye birim taşıma maliyeti, TRY/ton veya TRY/palet). Karar değişkeni xij — fabrika i’den müşteri j’ye gönderilecek miktar. Kısıtlar: her fabrikanın gönderdiği toplam ≤ kapasitesi (Σj xij ≤ si), her müşterinin aldığı toplam ≥ talebi (Σi xij ≥ dj), tüm xij ≥ 0 (negatif sevkiyat olmaz). Hedef: toplam nakliye maliyeti minimum (min Σi Σj cij × xij). Dengeli problem: Σ si = Σ dj — toplam kapasite tam toplam talebe eşit; dengesiz problem: kapasite > talep (atıl kapasite var) veya kapasite < talep (eksik üretim), kukla (dummy) kaynak veya hedef eklenerek dengelenir.
2. Çözücü ile karar. Saf bir LP (Linear Programming — kısıtlar altında doğrusal hedef enküçükleme) problemi olduğu için modern LP çözücüleri saniyelerle binlerce kaynak-hedef ölçeğini çözer. Klasik yöntemler: Simplex yöntemi (1950’lerin başında bu problem için geliştirilmiş — köşe-köşe arama ile optimumu bulan kanonik LP algoritması); Network Simplex (problem yapısı bir bipartite çizgeye karşılık geldiği için 5-10 kat daha hızlı); Northwest Corner kuralı ile başlangıç çözümü + MODI (Modified Distribution) / Stepping-Stone yöntemiyle iyileştirme (manuel öğretici yöntem, eskinin masa-üstü çözümü); Vogel’in yaklaşım yöntemi (VAM) ile akıllı başlangıç. Pratikte: orta ölçek (5-50 kaynak × 50-500 hedef) açık-kaynak LP çözücülerle anında, büyük ölçek (yüzlerce-binlerce) Network Simplex veya iç-nokta yöntemiyle dakikalarda. Atama Problemi (Assignment Problem) taşıma probleminin özel durumudur — kaynak ve hedef sayısı eşit, her kaynak tek hedefe (kapasite = talep = 1, xij ∈ {0,1}); Macar Yöntemi (Hungarian) bu özel hali için klasik çözücüdür.
3. Saha entegrasyonu. Çıktı iki tablo: birincil akış matrisi (her fabrika-müşteri çifti için haftalık sevkiyat miktarı — operasyon ekibinin ana çizelgesi), ve dual değişkenler (gölge fiyat — shadow price — her kaynak ve hedef için). Dual değerler yatırım kararının doğrudan girdisidir: ‘fabrika i’nin kapasitesi 1 ton artarsa toplam nakliye maliyeti ne kadar düşer?’ sorusunun cevabı dual değişkeninde yazar. Saha pratiği: haftalık veya aylık yeniden-çözüm; yakıt fiyat değişimi, yeni müşteri/fabrika ekleme, kapasite bakım pencereleri tetikleyicidir. Üç aylık planlama komitesi: gerçekleşen akışlar vs plan, marjinal kapasite analizi, maliyet matrisi tazeleme.
Alternatifler
Manuel + spreadsheet (alışkanlık akışları)
ÜcretsizSıfır lisans
Kim için: Küçük ölçek (≤3 fabrika, ≤20 müşteri), stabil talep
- + Sıfır yazılım maliyeti
- + Operasyon ekibinin alışkanlığına uyar
- + Anında değişiklik (telefonla yön değiştirme)
- − Akışlar optimum değil — tipik %10-20 fazla nakliye
- − Maliyet matrisi güncellenmediği için yakıt şokları akışa yansımaz
- − Marjinal kapasite (yatırım için) analiz edilemez
- − Yeni fabrika/müşteri eklenince yeniden çizim yapılmaz
Spreadsheet üzerinde sezgisel LP eklentisi
ÜcretsizSıfır-düşük lisans (ofis paketi içinde)
Kim için: Orta ölçek (3-8 fabrika, 20-100 müşteri), aylık periyodik karar
- + Operasyon ekibinin kullanabildiği arayüz
- + Klasik taşıma problemi için yeterli ölçek
- + Eğitim yüzeyi düşük
- − Büyük matrislerde (200+ hedef) yavaş veya çözmüyor
- − Dual değişken görselleştirme zayıf — gölge fiyat raporu yok
- − Stokastik talep (talep belirsizliği) modülü yok
- − Sürüm ve revizyon kontrolü zayıf
Yerel tedarik zinciri planlama yazılımı
Kurumsal200K-1M TRY lisans + 60K-300K TRY/yıl bakım (TR pazar gözlemi)
Kim için: Orta-büyük operatör (5-15 fabrika, 100-500 müşteri)
- + Türkçe ekran, yerel destek
- + Operasyon sistemiyle (ERP) entegrasyon kolay
- + Yerel nakliye sözleşme şablonları
- − LP çözücüsü genelde paketli — performans test edilmeli
- − Dual analiz raporu kısıtlı
- − Akademik uzantılar (çok-dönem, stokastik) sınırlı
Uluslararası tedarik zinciri planlama platformu
Kurumsal500K-3M EUR lisans + 150K-700K EUR/yıl bakım
Kim için: Büyük operatör (15+ fabrika, 500+ müşteri, çok-ülke)
- + LP/MIP çözücü olgun, ölçeklenebilir
- + Dual analiz, gölge fiyat, senaryo karşılaştırma zengin
- + Çok-dönem ve stokastik uzantılar mevcut
- − Yüksek lisans + uzun (12-24 ay) kurulum
- − TR mevzuatına özelleştirme proje süresi ekler
- − Operasyon ekibi eğitimi geniş program
Açık-kaynak LP çözücü + iç geliştirme
Açık KaynakLisans ücretsiz; 8-16 hafta iç geliştirme veya 400K-1.2M TRY danışmanlık
Kim için: Teknoloji ekibi olan operatör, ERP'ye eklenti istenen yerler
- + Lisans bedeli yok
- + Klasik taşıma problemi açık-kaynak literatürde iyi tanımlı
- + Çok-dönem, stokastik, ağ akış uzantıları açık-kaynak
- − İçeride OR uzmanı + veri ekibi şart
- − Operasyon ekibine arayüz geliştirilmeli
- − Bakım sorumluluğu işletmede
Tavsiye
Çözüm görüşmesinde sor
- Taşıma problemi için hangi çözücü kullanılıyor — saf simplex, network simplex, iç-nokta yöntemi mi? Tipik çözüm süresi 100 kaynak × 500 hedef ölçeğinde nedir?
- Dengesiz problem (toplam kapasite ≠ toplam talep) otomatik dengeleme (dummy kaynak/hedef) destekleniyor mu? Atıl kapasite raporu üretiliyor mu?
- Dual değişkenler (gölge fiyat) çıktıda ayrı tablo olarak sunuluyor mu? 'Bu fabrikanın kapasitesi 1 ton artarsa' senaryosu otomatik üretilebilir mi?
- Maliyet matrisi güncellendiğinde (yakıt değişti, yeni nakliye sözleşmesi) yeniden çözüm tetikleyici otomatik mi, manuel mi?
- Çok-dönem (haftalık veya aylık planlama ufku) destekleniyor mu? Dönemler arası envanter taşıma var mı?
- Atama probleminin özel durumu (kaynak = hedef sayısı, ikili karar) için özel modül var mı? Macar yöntemi destekleniyor mu?
- Pilot dönemde 8-12 hafta gerçek veri ile önceki manuel akışa kıyasla nasıl tasarruf raporu sunulabilir?
- Sözleşme biterse kaynak-hedef tanımı, maliyet matrisi geçmişi ve çözüm arşivi hangi standart formatta dışa aktarılabilir?
Teknik detay
Editör notu
Bu problem halk dilinde “akış planı”, “sevkiyat dağılımı” veya “fabrika-müşteri matrisi” diye anılır. Akademik literatürde adı Transportation Problem (taşıma problemi), bazı kaynaklarda Hitchcock Problem veya Hitchcock-Koopmans Problem. Frank Hitchcock 1941 yılında MIT’de yayınladığı makalede problemi sayısal olarak ilk kez tanımladı; Tjalling Koopmans 1947’de bağımsız bir ekonomik formülasyon yaptı (bu çalışma 1975 Nobel İktisat’ta atıf gördü); George Dantzig 1951’de Simplex yöntemini özellikle bu problem üzerinden geliştirdi. Lineer programlamanın kurucu problemi ve TSP / VRP / araç rotalama gibi sonraki kuşağın atasıdır.
VRP (#002, #069) ile farkı kritik: VRP araç rotasıdır — depo-müşteri-müşteri-depo turu, hangi araç hangi sırayla gider. Transportation problem akış tahsisi: her fabrika her müşteriye kaç adet gönderir, rota yok, sadece miktar. İkisi tamamlayıcı — önce transportation problem akışları belirler (haftalık miktar), sonra VRP turları belirler (günlük rota). Aynı zincirde sırayla çalışırlar. Tesis konumu (#010) ile farkı: tesis konumu yeni fabrika/depo açma kararıdır (sabit açılış maliyeti), transportation problem mevcut tesisler arası akış tahsisidir (açılış maliyeti yok). p-medyan (#074) ile farkı: p-medyan sabit sayıda tesis seçer, taşıma problemi mevcut tesisler verili kabul eder.
Sektörde en sık atlanan nokta: dual değişkenler ve gölge fiyatlar. LP çözümünün primal akışları (her fabrika her müşteriye kaç ton) pratisyenin gördüğü çıktıdır; dual değişkenler her kaynağa ve hedefe atanan gölge fiyatı verir — “fabrika i’nin kapasitesi 1 ton artarsa toplam nakliye maliyeti ne kadar düşer”, “müşteri j’nin talebi 1 ton artarsa toplam maliyet ne kadar yükselir” sorularının tam cevabı. Bu yatırım kararının doğrudan girdisidir: hangi fabrikaya kapasite eklemenin en yüksek getirisi var, hangi müşterinin marjinal taşıma maliyeti diğerlerinden yüksek. Pratisyen genelde sadece primal akışları kullanır, dualları okumaz — yatırım önceliklendirmesi için kritik bir kayıp. İkinci atlanan nokta: dengesiz problem. Gerçek hayatta toplam kapasite tam toplam talebe eşit nadiren olur (fazla kapasite veya eksik üretim). Çözücü kukla (dummy) kaynak veya hedef ekler — bu kukla satır veya sütun atıl kapasite raporudur, gözden kaçırılırsa atıl kapasitenin neye karşılık geldiği anlaşılmaz.
Adım adım yol — KOBİ için
Aşama 1 — Önce ölç, sonra plan. En az 6-12 ay veri: her fabrika-müşteri çifti için aylık sevkiyat miktarı, birim nakliye maliyeti (mesafe + araç tipi + sözleşme), fabrika haftalık kapasite, müşteri haftalık talep. Maliyet matrisini ayrı bir tabloda topla — her satırda fabrika, her sütunda müşteri, hücrede TRY/ton (veya TRY/palet). Kritik: yakıt fiyatı geçen 12 ayda ne kadar değişti, maliyet matrisi güncellendi mi? Eğer hayır, ilk LP çalışması zaten %5-10 tasarruf gösterir.
Aşama 2 — Bilgi sermayesini çıkar. Hangi fabrikanın hangi müşteriye fiziksel-imkansız olduğunu (uzaklık, ürün uyumu, sözleşme kısıtı) listele — bu kısıtlar modele ‘yasak hücre’ (büyük maliyet) olarak girer. Üretim kapasitesi: gerçek sürekli kapasite mi, bakım pencereleri var mı? Müşteri talebi: sabit mi, mevsimlik mi?
Aşama 3 — Pilot. 8-12 hafta. Bir alt-bölge (örneğin tek bir ürün hattı veya tek bir bölge müşterileri) için LP modelini kur, çözücü çalıştır, sonucu mevcut manuel akışla paralel karşılaştır. Karar yine planlamacıdadır; LP öneri verir. Başarı kriteri önceden belirlenmeli: toplam nakliye maliyeti -%10 minimum, atıl kapasite veya eksik talep raporu net. Dual değişkenleri ayrı tablo olarak istemekten çekinme — yatırım önceliklendirmesi için bu tablo kıymetlidir.
Aşama 4 — Yaygınlaştırma. 6-12 ay sürede tüm ürün hatları ve bölgeler dahil edilir. Aylık yeniden-çözüm haline gelir — yakıt değişimi, yeni müşteri, kapasite bakımı tetikleyici. Üç aylık planlama komitesi: gerçekleşen akışlar vs plan, dual değişken raporu (gölge fiyat), maliyet matrisi tazeleme tarihi.
Riskler — ne yanlış gidebilir
- Fabrika kapasitesi gerçek-zaman değişir. Statik LP modeli haftalık veya aylık kapasiteyi sabit alır; ancak bakım, vardiya kaybı, hammadde kesintisi kapasiteyi günlük dalgalandırır. Çözüm: kısa-dönem (haftalık) yeniden-çözüm + ortalama-üstü güvenlik marjı kapasiteden düşülür.
- Maliyet matrisi güncellenmez. Yakıt %20 zamlanmış ama matris 2 yıl önceki rakamlarla — LP eski matrisi optimum çözer, gerçekte para kaybeder. Çözüm: maliyet matrisi her 3 ayda bir tazelenir (yakıt + nakliye sözleşmesi + araç maliyeti).
- Müşteri özel talepleri modelde yok. Bazı müşterilerin teslim saati penceresi, paket büyüklük kısıtı, ürün karışım kuralı vardır — saf taşıma problemi bunları taşımaz; VRP veya planlama katmanına aktarılmalıdır. Saf LP’nin verdiği akış teknik olarak doğru ama operasyonel olarak uygulanamaz olabilir.
- Tek tedarikçiye bağımlılık (WMS/TMS lock-in). Yazılım kaynak-hedef tanımını, maliyet matrisini, çözüm arşivini özel formatta saklarsa, sistemden ayrılma kararı işletmenin akış hafızasını kaybetmesi demektir. Sözleşmede “akış matrisi geçmişi ve maliyet matrisi yıllık standart format ihracı” maddesi olmalı.
Çözüm yöntemine teknik bakış
| Yaklaşım | Tipik ölçek | Çözüm süresi | Garantili optimum? |
|---|---|---|---|
| Northwest Corner kuralı | Manuel başlangıç, herhangi ölçek | dakika (manuel) | Hayır — sadece başlangıç çözümü |
| Vogel’in yaklaşım yöntemi (VAM) | Akıllı başlangıç | dakika-saniye | Hayır — optimum-yakın başlangıç |
| MODI / Stepping-Stone (manuel) | Küçük (≤10 × ≤10) | saatler | Evet (yöntem doğru uygulanırsa) |
| Simplex (genel) | Orta (≤500 × ≤500) | saniyeler | Evet |
| Network Simplex | Büyük (binlerce kaynak/hedef) | saniyeler-dakikalar | Evet |
| İç-nokta yöntemi (interior point) | Çok büyük | dakikalar | Evet (sayısal hassasiyet içinde) |
| Macar yöntemi (atama özel durumu) | Kare matris (kaynak = hedef) | hızlı | Evet (özel durum) |
Hedef fonksiyonu seçimi:
- Hedef 1 — Toplam nakliye maliyeti minimum: Klasik. FMCG, hammadde-fason zincirleri için tipik.
- Hedef 2 — Toplam mesafe veya yakıt minimum: Karbon ayak izi veya yakıt-baskın operasyonlar için.
- Hedef 3 — Servis süresi (teslim zamanı) ağırlıklı minimum: Hızlı dağıtım gereken segment (gıda, soğuk zincir).
- Hedef 4 — Karma (ağırlıklı): nakliye + servis + ceza: Sözleşmede gecikme cezası olan müşteri tabanı için.
Atama Problemi (Assignment Problem) taşıma probleminin özel durumudur: kaynak sayısı = hedef sayısı, her kaynak tam bir hedefe (kapasite = talep = 1, xij ikili karar). Personel-iş atama, makine-iş atama, gemi-rıhtım atama (#026’da BAP’in bir alt-katmanı), düğüm eşleştirme problemleri bu yapıdadır. Macar yöntemi (Kuhn 1955) atama problemini O(n³) sürede çözen klasik algoritma — taşıma probleminin daha genel simpleksinden çok daha hızlı, ama sadece atama özel durumu için.
Çok-dönemli uzantı: xijt — fabrika i’den müşteri j’ye dönem t’de gönderilen miktar; her dönem kapasite ve talep ayrı, dönemler arası envanter taşıma maliyeti eklenir. Bu çok-dönemli üretim-dağıtım planlama problemine genişler — taşıma problemi temelini korur, lot-sizing ve envanter katmanı eklenir.
Stokastik uzantı: talep dj rastgele değişken; çözüm her senaryoda kapasiteyi aşmayan, beklenen maliyeti minimize eden tahsisi verir — stokastik LP veya senaryo-bazlı MIP.
Akademik kaynaklar
Sayfanın frontmatter’ında sources alanında listelidir. Hitchcock (1941) ve Koopmans (1947) problemin iki kurucu makalesi; Dantzig (1951) Simplex yöntemini bu problem üzerinden geliştirdi. Bazaraa-Jarvis-Sherali (2010) ve Murty (1992) modern ders kitabı kaynakları. INFORMS ve European Journal of Operational Research arşivlerinde tedarik zinciri ve üretim-dağıtım uygulamaları geniş yer kaplar.
Kaynaklar
- Hitchcock, F. L. (1941). The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics, 20(1-4), 224-230. Problemin temel kaynağı.
- Koopmans, T. C. (1947). Optimum utilization of the transportation system. Econometrica, 17 (Supplement: Proceedings of the International Statistical Conferences). Nobel İktisat 1975 atıf kaynaklarından.
- Dantzig, G. B. (1951). Application of the Simplex Method to a transportation problem. In Activity Analysis of Production and Allocation, Wiley. Simplex yönteminin taşıma problemine uygulanması.
- Bazaraa, M. S., Jarvis, J. J. ve Sherali, H. D. (2010). Linear Programming and Network Flows (4. baskı). Wiley. Lineer programlama ve ağ akış problemlerinin standart ders kitabı.
- Murty, K. G. (1992). Network Programming. Prentice Hall. Ağ programlama klasik kaynağı, taşıma probleminin özel-yapı çözümleri.
- YÖK Tez Merkezi — anahtar kelime: ’taşıma problemi’ veya ‘Hitchcock’ veya ‘kaynak-hedef LP’ — TR akademisinden 30+ tez. tez.yok.gov.tr
Sözlük
- Taşıma Problemi
- Sabit kapasiteli m kaynaktan, sabit talepli n hedefe, birim taşıma maliyeti minimum olacak şekilde sevkiyat tahsisi — lineer programlamanın kurucu problemi.
- Northwest Corner Kuralı
- Taşıma problemine başlangıç temel uygulanabilir çözüm üreten en basit klasik sezgisel: maliyet matrisinin sol-üst köşesinden başlayıp arz/talep tükenene kadar sağa veya aşağıya kayarak hücreleri doldurma.
- 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.
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.