Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Araç Rotalama Problemleri

No description
by

Betül Yılmaz

on 4 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Araç Rotalama Problemleri

END 492 BİTİRME ÇALIŞMASI
Araç Rotalama Problemi
Proje Danışmanı: Prof.Dr. Birol Elevli

Araç Rotalama Problemi Nedir?
Araç Rotalama Problemi ile ilgili ilk çalışmalar Dantzig ve Ramser tarafından 1959 yılında yapılmıştır.
Clarke ve Wright 1964 yılında Dantzig ve Ramser’in metodunu geliştirerek, klasik tasarruf metodunu önermişlerdir
Üzerinde en fazla çalışılan ve yöntem geliştirilen optimizasyon probleminin Araç Rotalama Problemi olduğu söylenebilir
ARP Kısıtları
1) Araçlarla ilgili kısıtlar

ARAÇ ROTALAMA PROBLEMLERİ
HAZIRLAYAN:

10060463 BETÜL YILMAZ
ARP'de dağıtım rotaları aşağıdaki şartları içerir:
Her müşterinin isteği karşılanmak zorundadır.

Her müşteri sadece bir araç rotasında olmak zorundadır.

Bir rota için kat edilen toplam mesafe, önceden belirlenen yapılabilecek maksimum rota mesafesini geçmemelidir.

Her rota için başlangıç yeri depo ve bitiş yeri depo olmak zorundadır.

ARP Temel Bileşenleri
Talep Yapısı:
Talep statik veya dinamik olabilir.

Malzeme Tipi:
Araçlarla farklı tür araçlar taşınabilir.

Dağıtım/Toplama Noktaları:
Dağıtım noktaları müşterinin bulunuğu yer iken, toplama noktaları depo olur.

Araç Filosu:
ARP'de araç kapasitesinin bilindiği ve bütün araçların aynı kapasitede olduğu varsayılır.
ARP Sezgisel algoritmaları 3'e ayrılır:
Tur Kurucu Sezgiseller: Tasarruf Algoritması
Araç rotalama problemi; araç kapasite kısıtlayıcılarına uygun olarak toplam mesafeyi minimize edecek taşıma güzergahının belirlenmesi
SUNUM İÇERİĞİ
1. ARP'nin tanımı ve içeriği
2. ARP Çeşitleri
3. ARP Çözüm Yöntemleri
4. Sonuç
Araç Rotalama Probleminin şebeke gösterimi
Araç kapasite kısıtı
Toplam zaman kısıtı
Sürücünün çalışma saatleri için yasal kısıtlar
2) Müşterilerle ilgili kısıtlar
Her bir müşterinin bir ürünü istemesi
Dağıtımın yapılabilmesi için gereken zaman aralıklarının tespiti
3) Diğer kısıtlar
Birden fazla depo olması
Bir turun uzunluğunun bir günden uzun sürmesi
Araç rotalama problemi, NP Hard Problemler çeşidine dahildir. Bu çeşit problemlerde sonuca hızlı ulaşabilmek için yaklaşık sonuçlar dikkate alınır.
Bu görev sezgisel yöntemlerle yerine getirilir.
Tur Geliştirici Sezgiseller: Gezgin Satıcı Problemi
İki Aşamalı Metotlar: Süpürme Algoritması
ARP Uygulama Alanları
Araç Rotalama Problemi Genel Matematiksel Modeli
Ürün ve hizmetlerin bir veya birden fazla sayıdaki depodan, farklı müşteri noktalarına dağıtımı
Hammadde, yarı mamul ve mamullerin fabrikalar arası taşınması
İnternetten yapılan alışverişlerin(E-ticaret) teslimatı
Çöp toplanması ve çöplerin boşaltma noktalarına taşınması
Posta hizmetleri
ARP ÇEŞİTLERİ
Rota Süresi Sınırsız Rotalama Problemleri
Problemin amacı, toplam tur uzunluğunu veya toplam maliyeti minimize etmektir. Bu problemde, düğümlere uğrama zamanları ve rota süresi ile ilgili girdiler ve kısıtlar
bulunmamaktadır
.
Rota Süresi Sınırlı Rotalama Problemleri
Bu problem türünde amaç, araçların kat ettikleri toplam uzunluğu
minimize
etmektir.
Depodan ayrılan araçlar belirli adreslere (düğümlere) uğradıktan sonra yine aynı depoya dönmeleri gerekir.
Aşılan her birim süre için ceza maliyeti verilir.

Zaman Pencereli Rotalama Problemleri
Her bir müşteriye ait belli bir zaman aralığı kısıdı olan araç rotalama problemi türüdür.
Çoğunlukla raf ömrünün kısa olduğu ürünlerin dağıtımının yapıldığı ya da dağıtım süresinin kısa olduğu sistemlerde tercih edilmektedir.
Eşzamanlı Rotalama ve Çizelgeleme Problemleri
İlk kez Min tarafından 1989 yılında ele alınmıştır.
Eşzamanlı araç rotalama problemleri, rota boyunca müşterilerin
dağıtım talepleri
ile
toplama taleplerinin
eşzamanlı olarak gerçekleştirildiği problemlerdir.
Eşzamanlı rotalama probleminde dikkate alınan kısıtlar şunlardır:
Her bir görev, belirli bir zaman kısıdında tek bir araç ile ve
yalnızca bir kez
gerçekleştirilmelidir.
Bir depodan ayrılan her bir araç, rotasını tamamladıktan sonra başladığı depoya
geri dönmelidir.
Rota üzerinde, aracın topladığı ve aracın dağıtacağı yük miktarının toplamının araç kapasitesini
geçmemesi gerekir
.

Kapasiteli Araç Rotalama Problemleri
Merkezi bir depoda teslimat işini gerçekleştiren kapasiteli araçların, düzgün bir şekilde farklı noktalara dağılmış müşterilerin taleplerini en az maliyetle karşılaması için kullanması gereken en uygun rotaların bulunması problemidir.
Çoklu Depoya Sahip Araç Rotalama Problemleri
Önce Dağıt Sonra Topla Araç Rotalama Problemleri
Araçların dağıtım planı şekli, önce dağıtım yapılacak müşterilere uğramak, daha sonrasında ise toplama yapılacak müşterilere uğrayıp depoya dönecek şekildedir.

Dağıtım firmasının müşterilere hizmet vermek için birden fazla deposunun olması durumudur. Bu problemde araçlar depolara atanır ve her bir araç ait olduğu depodan çıkarak müşteriye hizmet verir ve yine aynı depoya geri döner.
Bölünmüş Talebe Sahip Rotalama Problemleri
Bölünmüş talebe sahip araç rotalama problemi, aynı müşteriye birden fazla aracın servis yapabilmesine olanak veren araç rotalama problemidir.
Belirsiz Talebe Sahip Rotalama Problemleri
Talebin belirsiz olduğu araç rotalama problemidir. Dağıtım aracı müşteriye vardığı zaman o müşterinin talebinin ne olacağı belli olur.
Geri Toplaması Olan Araç Rotalama Problemleri
Gezgin Satıcı Problemleri
Geri toplaması olan araç rotalama problemi, müşterilerin depozito, ambalaj ve paket gibi, ürünlere ait bazı parçaları iade etme durumu olabilen araç rotalama problemidir.

Gezgin satıcı problemi ile ilgili ilk yayın yapan kişi
Karl Menger
'dir.
Basit bir şekilde gezgin satıcı probleminin çözümü;
Başlangıç için seçilebilecek
n
tane şehir bulunmaktadır.
Bu şehirlerden birisinin başlangıç noktası olduğu düşünülürse, satıcı
n-1
farklı şehirde satış yapabilmektedir.
İkinci şehirde, satıcının
n-2
farklı şehir yolu arasında seçim hakkı bulunmaktadır.
Gezgin Satıcı Probleminde amaç bir satıcının, bulunduğu şehirden başlayıp, her şehre yalnızca bir defa uğrayıp, ardından başladığı noktaya geri dönen
en kısa turu
bulmaktır.
Hamilton'un, "Bir problem de herhangi bir ayrıttan birden fazla geçmemek kuralıyla her bir düğümü yalnızca bir defa ziyaret edip başladığımız yere geri dönebilmemiz mümkün mü?” sorusuna verdiği cevap gezgin satıcı probleminin temelini oluşturmaktadır.
Sonuç olarak
(n-1)!
değişik durum söz konusudur. Hamilton yolu ters sırada da ziyaret edilebilir bu yüzden
(n-1)!/2
değişik tur bulunmaktadır.
Ör; 25 şehirlik bir tur için
24!/2=3,1*1023
demektir. Her bir yolu izlemenin
10^(-9)
saniye aldığı düşünülürse bu işlem yaklaşık
10 milyon yıl
sürmektedir. Bu yüzden GSP'nin çözümünde sezgisel algoritmalar tercih edilmektedir.
ARP Çözüm Yöntemleri
En Kısa Yol Yöntemi
Kesin çözüm yöntemlerinden biri olan en kısa yol yönteminin temel amacı, müşteri noktaları arasındaki yakınlık ve uzaklık durumu ve araç yükleme kapasitelerine göre araçlara müşteri atanmasıdır.

Minimum Yayılan Ağaç Yöntemi
Bir şebekedeki bütün düğümleri minimum maliyetle birbirine bağlayan yaylar grubnu bulan şebeke modelleri bu isimle anılmaktadır.
Tasarruf Algoritması
Bu yöntem, her bir müşteri ikilisi arasındaki maliyet tasarrufunu hesaplayarak başlar. Maliyet tasarrufları hesaplanarak iki müşteri arasına bir müşteri eklenir.
Süpürme Yöntemi
Rotalarda yer alacak müşteriler, depo merkezli bir doğrunun döndürülmesi ile elde edilirler. Döndürme esnasında doğrunun üzerinden geçtiği müşteriler bir gruba ayrılır ve kapasite veya mesafe kısıtı aşıldığında grup kapatılarak yeni bir grup ile devam edilir. Oluşturulan nokta gruplarına merkez depo da eklenerek, genel olarak GSP gibi çözülerek rotalar belirlenir.
Genetik Algoritmalar
Genetik algoritmaların en önemli özelliklerinden biri, çözüm seti ile başladıktan sonra, geliştirme için biyolojik evrimi esas alan bir prosesin kullanılmasıdır. Bu prosesin sonunda en iyi kromozoma ulaşmak amaçlanır. Problemle ilgili parametreler, genler halinde bir araya gelerek kromozomu oluşturmakta; en iyi kromozoma ulaşma ise genlerin kromozom içindeki dizilişini değiştirerek yapılmaktadır.
Tabu Arama Yöntemi
Tabu arama algoritması oldukça yeni ve zor problemlerin çözümünde kullanılan yönlendirilmiş bir meta sezgisel algoritmadır. Çok modlu problemler için global optimum çözümleri bulma yeteneğine sahiptir. Tabu araştırma algoritmasında daha önceden denenen çözümler, tekrar tekrar denenmeyerek, araştırma yönünün, denenmeyen alanlara yönlendirilmesi amaçlanmıştır.
Karınca Kolonisi Optimizasyonu
Karıncalar yiyecek ararken geçtikleri yollara kimyasal feromen (pheromone) maddesini bırakırlar.
Bu çalışmada ARP ile ilgili genel bilgi verildikten sonra, farklı çeşitleri tanıtılmıştır. Farklı kısıtlar altında ki Araç Rotalama Problemlerine değinilerek, formülasyonlar incelenmiştir. Matematiksel çözüm yöntemleri ve sezgisel çözüm yöntemleri arasındaki farklar yansıtılmıştır.
Bu araştırmanın amacı, firmaların maliyetlerini azaltmak yolunda ihtiyaç duyacakları bilimsel metot ve çözüm yöntemlerini detaylandırarak, yardımcı olması ve litaratüre katkı sağlamasıdır.
DİNLEDİĞİNİZ İÇİN TEŞEKKÜRLER
SONUÇ
Full transcript