Araç rotalama problemi

[bullvar_katip]

küçükresim|upright=1.09|Araç rotalama probleminin şekilsel gösterimi Araç Rotalama Problemi (ARP), bir veya birkaç depodan müşterilere hizmet götürecek araçlar için en uygun rotaları belirlemeyi amaçlayan bir kombinatoryal eniyileme (optimizasyon) problemidir. Eniyileme literatürünün en iyi bilinen problemlerinden Gezgin Satıcı Problemi'nin daha genel bir halidir. ARP ile ilgili ilk makale George Dantzig ve Ramser John tarafından 1959 yılında yayınlanmıştır ve benzin teslimatında ortaya çıkan ARP'ler için algoritmik ilk yöntemi içermektedir. Genellikle, ARP merkezi bir depodan müşterilere siparişlerinin taşınmasını planlama amaçlı çözülür. ARP'nin amaç fonksiyonu toplam yol maliyetini en aza indirmektir. 1964 yılında Clarke ve Wright, ARP için "tasarruf algoritması" adını verdikleri etkili bir açgözlü yöntem önermiş ve Dantzig ve Ramser'in yönteminden daha iyi sonuçlar elde etmişlerdir. ARP problemleri NP-zor olarak sınıflandırılır. Bu sebeple büyük boyutlu problemlerde en iyi teorik çözümü bulmak mümkün olamamaktadır. Ticari ARP yazılımları gerçek veriye dayalı problemlerin büyük boyutlu olması ve kısa sürede çözüme ihtiyaç duyması yüzünden çoğunlukla sezgisel yöntemler kullanırlar. ARP'nin sanayide pek çok uygulamaları vardır. Ulaşım maliyetleri genelde bir ürünün maliyetinin önemli bir kısmını oluşturduğundan (%10) ARP eniyileme yazılımları %5'e varan oranlarda maliyet tasarrufu sağlayabilir. AB'nin GSYİH'sının %10'u ulaştırma sektöründeki firmalardan oluşmaktadır. Sonuç olarak, ARP'yi çözerek elde edilecek herhangi bir tasarruf, %5'ten az bile olsa, önemlidir. Pekin çözüm yöntemleri Araç akışlı formülasyonlar - bu tip formülasyonlar her ayrıtın araçlar tarafından kaç kez kulanıldığının sayısını tutan tam sayısal değişkenler içerir. Genellikle temel ARP türevlerini çözmekte kullanılırlar. Çözüm maliyetinin ayrıtlara ilişkin maliyetlerin toplamı olduğu durumlara uygundurlar. Ancak birçok pratik uygulama için yetersiz kalırlar. Mal akışlı formülasyonlar - araçların izledikleri rotalar boyunca ayrıtlardan akan mal miktarını belirten ek tam sayısal değişkenler içerirler. Bu tip formülasyonlar sadece yakın geçmişte kulllanılmaya başlanmıştır. Küme bölümleme problemi temelli formülasyonlar - üslü sayıda ikili değişken içerir ve bu değişkenlerin her biri farklı bir olası araç rotasına karşılık gelir. Formülasyon her müşterinin bir kere ziyaret edilmesini zorunlu kılan Küme Bölümleme kısıtları kullanılarak tamamlanır. Bu yaklaşım diğerlerine göre amaç fonksiyonunda daha genel maliyet fonksiyonlarının kullanılmasına izin verir. Araç akışlı formülasyonlar Dantzig, Fulkerson ve Johnson tarafından sunulan Gezgin Satıcı Problemi formülasyonu genelleştirilerek ARP için iki indeksli araç akışlı formülasyonlar oluşturmakta kullanılmıştır. kısıtlar ARP'nin çözümü için açık kaynaklı yazılımlar Kaynakça Kategori:NP-tam problemleri Kategori:Yöneylem araştırması