Araç Rotalama Problemi (ARP)
Vehicle Routing Problem (VRP) · Ayrıca şöyle bilinir: Capacitated Vehicle Routing Problem, Fleet Routing Problem, Multi-Vehicle Routing Problem, Araç Rotalama Problemi
Araç Rotalama Problemi (ARP), her biri bilinen talebe sahip, coğrafi olarak dağılmış bir dizi müşteriye hizmet vermek üzere bir araç filosunun minimum maliyetli rota setini bulmayı amaçlar; bu rotalar merkezi bir depodan başlayıp yine oraya dönmektedir. Orijinal olarak 1959'da Dantzig ve Ramser tarafından Kamyon Sevkiyat Problemi olarak formüle edilen ARP, lojistik, tedarik zinciri yönetimi ve operasyon araştırmalarında temel bir modeldir ve malların veya hizmetlerin birden fazla durakta verimli bir şekilde teslim edilmesi gerektiğinde uygulanabilir.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Bir filonun paylaşılan bir depodan birden fazla talep noktasına hizmet vermesi gerektiğinde ve araç kapasitesi bağlayıcı bir kısıtlama olduğunda ARP'yi kullanın. Temel varsayımlar, bilinen müşteri konumları ve talepleri, bilinen kapasitelere sahip homojen veya heterojen filo ve simetrik veya asimetrik bir maliyet matrisini içerir. Model, zaman penceresi ARP, bölünmüş teslimat ARP ve stokastik ARP varyantlarına doğal olarak genişler. Müşteri talebinin oldukça belirsiz olduğu, rotaların sözleşmeyle sabitlendiği veya yalnızca tek bir araç söz konusu olduğunda (Gezgin Satıcı Problemine indirgenir) daha az uygundur.
Güçlü yönler & sınırlılıklar
- Operasyonel maliyetleri ve yakıt tüketimini azaltan, kanıtlanabilir şekilde optimal veya optimale yakın rotalar sağlar.
- Yüksek derecede genelleştirilebilir: onlarca farklı formülasyon zaman pencereleri, birden fazla depo, heterojen filolar ve bölünmüş teslimatlar gibi durumları ele alır.
- Olgun çözücüler (CPLEX, Gurobi) ve açık kaynaklı kütüphaneler (OR-Tools, VRPy) tarafından iyi desteklenir.
- Etkili meta-sezgisel ve sütun üretimi algoritmaları aracılığıyla gerçek lojistik ağlarına ölçeklenir.
- Kesin çözüm NP-zorludur; yüzden fazla müşteriye sahip örnekler için ayrıştırma olmadan kesin çözümler hesaplama açısından çözülemez.
- Model kalitesi, doğru maliyet matrislerine ve talep tahminlerine kritik derecede bağlıdır; hatalar doğrudan rota kalitesine yansır.
- Statik formülasyon, trafik aksaklıkları veya son dakika siparişleri gibi gerçek zamanlı olayları doğal olarak barındırmaz.
- Büyük tamsayılı programları kurmak ve çözmek, temel elektronik tablo araçlarının ötesinde özel yazılım ve uzmanlık gerektirir.
SSS
ARP, Gezgin Satıcı Probleminden (TSP) nasıl farklıdır?
TSP, tüm müşterileri bir kez ziyaret eden tek bir minimum maliyetli tur bulur. ARP, TSP'yi her biri kapasite sınırına sahip birden fazla araca genelleştirir, böylece problem aynı zamanda müşterileri araçlara nasıl böleceğini de belirler. TSP, sınırsız kapasiteli tek bir araçla ARP'nin özel bir durumudur; pratikte ARP, bölümleme ve sıralama kararları etkileşimde bulunduğu için önemli ölçüde daha zordur.
ARP zaman pencerelerini ve gerçek zamanlı güncellemeleri işleyebilir mi?
Evet, Zaman Pencereli Araç Rotalama Problemi (VRPTW) varyantı aracılığıyla, her müşteriye bir en erken ve en geç hizmet zamanı verilir ve model zamansal uygunluk kısıtlamaları ekler. Dinamik ARP uzantıları, yeni siparişler veya aksaklıklar gün içinde geldiğinde rotaları yeniden optimize eder, genellikle her karar döneminde azaltılmış bir problemi yeniden çözen yuvarlanan ufuk sezgisel yöntemleri kullanır.
ARP'yi uygulamak için hangi çözücü veya kütüphaneyi kullanmalıyım?
Prototipleme için Google OR-Tools, çoğu standart varyantı ele alan Python ve C++'da ücretsiz, iyi belgelenmiş bir ARP çözücüsü sunar. Üretim ölçekli kesin optimizasyon için, sütun üretimi veya dal-fiyatlandırma (branch-and-price) çerçeveleri ile CPLEX veya Gurobi tercih edilir. Açık kaynaklı VRPy kütüphanesi, VRPTW ve ilgili varyantlara uygun etiketleme algoritmaları için Python sarmalayıcıları sağlar.
Kaynaklar
- Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91. DOI: 10.1287/mnsc.6.1.80 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 2). Vehicle Routing Problem (VRP). ScholarGate. https://scholargate.app/tr/optimization/vehicle-routing
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Tamsayı ProgramlamaOptimizasyon↔ karşılaştır
- Konum-Atama ModelleriMekânsal analiz↔ karşılaştır
- Hizmet Alanı AnaliziMekânsal analiz↔ karşılaştır