Araç rotalama problemi

küçükresim|240x240pik|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. \text{min} \sum_{i\in V}\sum_{j \in V}c_{ij}x_{ij} kısıtlar \begin{align} & \sum_{i \in V}x_{ij}=1 ~~~~ \forall j \in V\backslash \left \\{ 0 \right \\} & (1) \\\ & \sum_{j \in V}x_{ij}=1 ~~~~\forall i \in V\backslash \left \\{ 0 \right \\} & (2) \\\ & \sum_{i \in V}x_{i0}=K & (3) \\\ & \sum_{j \in V}x_{0j}=K & (4) \\\ & \sum_{i otin S}\sum_{j\in S}x_{ij} \geq r(S) ~~~~\forall S\subseteq V\backslash \left \\{ 0 \right \\}, S eq \emptyset & (5) \\\ & x_{ij}\in \\{0,1\\} ~~~~\forall i,j \in V & (6) \\\ \end{align} == ARP'nin çözümü için açık kaynaklı yazılımlar == Adı (alfabetik olarak) Lisans API dil Kısa bilgi jsprit LGPL Java ARP ve türevlerinin çözümü için hafif, java tabanlı, açık kaynak kodlu bir yazılım. bağlantı Haritalama, raporlama ve yol düzenleme işlevlerini içeren Excel uyumlu kullanıcı arayüzü mevcuttur. bağlantı Open-VRP LLGPL Lisp Github üzerinde barındırılan, Lisp tabanlı bir yazılım. bağlantı OptaPlanner Apache Lisansı Java ARP örnekleri içeren, Java tabanlı kısıt çözücü (optaplanner.org). SYMPHONY Ortak Kamu Lisansı 1.0 ARP çözüm desteği içeren, karışık tam sayılı doğrusal programlar için açık kaynaklı çözücü. bağlantı VRP Spreadsheet Solver Creative Commons 4.0 Uluslararası Lisansı Atıf Microsoft Excel ve VBA tabanlı açık kaynaklı çözücü. Sürüş mesafe ve sürelerini Bing Maps'ten alır. bağlantı Video öğretici bağlantı == Kaynakça == Kategori:NP-tam problemleri Kategori:Yöneylem araştırması