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 kullanı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
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ı24 Haziran 2016 tarihinde Wayback Machine sitesinde . Haritalama, raporlama ve yol düzenleme işlevlerini içeren Excel uyumlu kullanıcı arayüzü mevcuttur. bağlantı1 Eylül 2016 tarihinde Wayback Machine sitesinde . |
Open-VRP | LLGPL26 Ekim 2015 tarihinde Wayback Machine sitesinde . | Lisp | Github üzerinde barındırılan, Lisp tabanlı bir yazılım. bağlantı11 Haziran 2018 tarihinde Wayback Machine sitesinde . |
OptaPlanner | Apache Lisansı | Java | ARP örnekleri içeren, Java tabanlı kısıt çözücü (optaplanner.org28 Eylül 2020 tarihinde Wayback Machine sitesinde .). |
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ı28 Şubat 2014 tarihinde Wayback Machine sitesinde . | |
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. Video öğretici bağlantı16 Mart 2016 tarihinde Wayback Machine sitesinde . |
Kaynakça
- ^ Dantzig, George Bernard; Ramser, John Hubert (Ekim 1959). (PDF). Management Science. 6 (1). ss. 80-91. doi:10.1287/mnsc.6.1.80. 12 Kasım 2013 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 5 Temmuz 2016.
- ^ a b c d The vehicle routing problem. Philadelphia: Soc. for Industrial and Applied Mathematics. 2002. ISBN . Yazar
|ad1=
eksik|soyadı1=
() - ^ Comtois, Claude; Slack, Brian; Rodrigue, Jean-Paul (2013). The geography of transport systems (Third edition. bas.). Londra: Routledge, Taylor & Francis Group. ISBN .
- ^ 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 .
- ^ 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 .
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Arac Rotalama Problemi ARP bir veya birkac depodan musterilere hizmet goturecek araclar icin en uygun rotalari belirlemeyi amaclayan bir kombinatoryal eniyileme optimizasyon problemidir Eniyileme literaturunun en iyi bilinen problemlerinden Gezgin Satici Problemi nin daha genel bir halidir ARP ile ilgili ilk makale George Dantzig ve Ramser John tarafindan 1959 yilinda yayinlanmistir ve benzin teslimatinda ortaya cikan ARP ler icin algoritmik ilk yontemi icermektedir Genellikle ARP merkezi bir depodan musterilere siparislerinin tasinmasini planlama amacli cozulur ARP nin amac fonksiyonu toplam yol maliyetini en aza indirmektir 1964 yilinda Clarke ve Wright ARP icin tasarruf algoritmasi adini verdikleri etkili bir acgozlu yontem onermis ve Dantzig ve Ramser in yonteminden daha iyi sonuclar elde etmislerdir Arac rotalama probleminin sekilsel gosterimi ARP problemleri NP zor olarak siniflandirilir Bu sebeple buyuk boyutlu problemlerde en iyi teorik cozumu bulmak mumkun olamamaktadir Ticari ARP yazilimlari gercek veriye dayali problemlerin buyuk boyutlu olmasi ve kisa surede cozume ihtiyac duymasi yuzunden cogunlukla sezgisel yontemler kullanirlar ARP nin sanayide pek cok uygulamalari vardir Ulasim maliyetleri genelde bir urunun maliyetinin onemli bir kismini olusturdugundan 10 ARP eniyileme yazilimlari 5 e varan oranlarda maliyet tasarrufu saglayabilir AB nin GSYIH sinin 10 u ulastirma sektorundeki firmalardan olusmaktadir Sonuc olarak ARP yi cozerek elde edilecek herhangi bir tasarruf 5 ten az bile olsa onemlidir Pekin cozum yontemleriArac akisli formulasyonlar bu tip formulasyonlar her ayritin araclar tarafindan kac kez kullanildiginin sayisini tutan tam sayisal degiskenler icerir Genellikle temel ARP turevlerini cozmekte kullanilirlar Cozum maliyetinin ayritlara iliskin maliyetlerin toplami oldugu durumlara uygundurlar Ancak bircok pratik uygulama icin yetersiz kalirlar Mal akisli formulasyonlar araclarin izledikleri rotalar boyunca ayritlardan akan mal miktarini belirten ek tam sayisal degiskenler icerirler Bu tip formulasyonlar sadece yakin gecmiste kulllanilmaya baslanmistir Kume bolumleme problemi temelli formulasyonlar uslu sayida ikili degisken icerir ve bu degiskenlerin her biri farkli bir olasi arac rotasina karsilik gelir Formulasyon her musterinin bir kere ziyaret edilmesini zorunlu kilan Kume Bolumleme kisitlari kullanilarak tamamlanir Bu yaklasim digerlerine gore amac fonksiyonunda daha genel maliyet fonksiyonlarinin kullanilmasina izin verir Arac akisli formulasyonlar Dantzig Fulkerson ve Johnson tarafindan sunulan Gezgin Satici Problemi formulasyonu genellestirilerek ARP icin iki indeksli arac akisli formulasyonlar olusturmakta kullanilmistir min i V j Vcijxij displaystyle text min sum i in V sum j in V c ij x ij kisitlar i Vxij 1 j V 0 1 j Vxij 1 i V 0 2 i Vxi0 K 3 j Vx0j K 4 i S j Sxij r S S V 0 S 5 xij 0 1 i j V 6 displaystyle begin aligned amp sum i in V x ij 1 forall j in V backslash left 0 right amp 1 amp sum j in V x ij 1 forall i in V backslash left 0 right amp 2 amp sum i in V x i0 K amp 3 amp sum j in V x 0j K amp 4 amp sum i notin S sum j in S x ij geq r S forall S subseteq V backslash left 0 right S neq emptyset amp 5 amp x ij in 0 1 forall i j in V amp 6 end aligned ARP nin cozumu icin acik kaynakli yazilimlarAdi alfabetik olarak Lisans API dil Kisa bilgijsprit LGPL Java ARP ve turevlerinin cozumu icin hafif java tabanli acik kaynak kodlu bir yazilim baglanti24 Haziran 2016 tarihinde Wayback Machine sitesinde Haritalama raporlama ve yol duzenleme islevlerini iceren Excel uyumlu kullanici arayuzu mevcuttur baglanti1 Eylul 2016 tarihinde Wayback Machine sitesinde Open VRP LLGPL26 Ekim 2015 tarihinde Wayback Machine sitesinde Lisp Github uzerinde barindirilan Lisp tabanli bir yazilim baglanti11 Haziran 2018 tarihinde Wayback Machine sitesinde OptaPlanner Apache Lisansi Java ARP ornekleri iceren Java tabanli kisit cozucu optaplanner org28 Eylul 2020 tarihinde Wayback Machine sitesinde SYMPHONY Ortak Kamu Lisansi 1 0 ARP cozum destegi iceren karisik tam sayili dogrusal programlar icin acik kaynakli cozucu baglanti28 Subat 2014 tarihinde Wayback Machine sitesinde VRP Spreadsheet Solver Creative Commons 4 0 Uluslararasi Lisansi Atif Microsoft Excel ve VBA tabanli acik kaynakli cozucu Surus mesafe ve surelerini Bing Maps ten alir Video ogretici baglanti16 Mart 2016 tarihinde Wayback Machine sitesinde Kaynakca Dantzig George Bernard Ramser John Hubert Ekim 1959 PDF Management Science 6 1 ss 80 91 doi 10 1287 mnsc 6 1 80 12 Kasim 2013 tarihinde kaynagindan PDF arsivlendi Erisim tarihi 5 Temmuz 2016 a b c d The vehicle routing problem Philadelphia Soc for Industrial and Applied Mathematics 2002 ISBN 0 89871 579 2 Yazar ad1 eksik soyadi1 yardim KB1 bakim Fazladan yazi yazar listesi link Comtois Claude Slack Brian Rodrigue Jean Paul 2013 The geography of transport systems Third edition bas Londra Routledge Taylor amp Francis Group ISBN 978 0 415 82254 1 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 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