Araç rotalama problemi

Vikipedi, özgür ansiklopedi
Gezinti kısmına atla Arama kısmına atla
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 Seyyar 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[1] 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[2] 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) [3] ARP eniyileme yazılımları %5'e varan oranlarda maliyet tasarrufu sağlayabilir[4]. 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.[4]

Pekin çözüm yöntemleri[değiştir | kaynağı değiştir]

  1. 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.[2]
  2. 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.[2]
  3. 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.[2]

Araç akışlı formülasyonlar[değiştir | kaynağı değiştir]

Dantzig, Fulkerson ve Johnson tarafından sunulan Seyyar 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[değiştir | kaynağı değiştir]

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ı [5]
Open-VRP LLGPL Lisp Github üzerinde barındırılan, Lisp tabanlı bir yazılım. bağlantı [5]
OptaPlanner Apache Lisansı Java ARP örnekleri içeren, Java tabanlı kısıt çözücü (optaplanner.org). [5]
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ı [5]
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ı [5]

Kaynakça[değiştir | kaynağı değiştir]

  1. ^ Dantzig, George Bernard; Ramser, John Hubert (October 1959). "The Truck Dispatching Problem" (PDF). Management Science. 6 (1), s. 80–91. doi:10.1287/mnsc.6.1.80. 
  2. ^ a b c d The vehicle routing problem. Philadelphia: Soc. for Industrial and Applied Mathematics. 2002. ISBN 0-89871-579-2.  Yazar |ad1= eksik |soyadı1= (yardım)
  3. ^ Comtois, Claude; Slack, Brian; Rodrigue, Jean-Paul (2013). The geography of transport systems (Third edition. bas.). London: Routledge, Taylor & Francis Group. ISBN 978-0-415-82254-1. 
  4. ^ a b editors, Geir Hasle, Knut-Andreas Lie, Ewald Quak,; Kloster, O (2007). Geometric modelling, numerical simulation, and optimization applied mathematics at SINTEF ([Online-Ausg.]. bas.). Berlin: Springer Verlag. ISBN 978-3-540-68783-2. 
  5. ^ a b c d e Editors, Sergey Balandin , Sergey Andreev, Yevgeni Koucheryavy (2015). Waste Management as an IoT-Enabled Service in Smart Cities. Switzerland: Springer International Publishing. ISBN 978-3-319-23126-6.