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

çnli

No description
by

Betül Yılmaz

on 28 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of çnli

Çöp Toplamada Araçların Rotalanması ve Çinli Postacı Turu Yaklasımıyla Problemin Çözülmesi :
19 Mayıs Yerleskesinde Örnek Uygulama

ARAÇ ROTALAMA PROBLEMLERI NEDIR?
Araç Rotalama Problemi (ARP), bir veya birkaç depodan, belirli müşterilere ürün dağıtımı veya toplanması olarak tanımlanır.
Bu problem, araç kapasiteleri ve müşterilerde ortaya çıkan servis süresi kısıtlarını dikkate alarak dağıtım yapan, belirli bir kapasiteye sahip araçların etkin olarak kullanılmasına yoğunlaşır.
Bazı gerçek hayat uygulamaları ise
okul servisleri, yakıt, gazete ve posta dağıtımı, perakende ürün dağıtımı, çöp toplanması
gibi uygulamalardır.
Yrd.Doç.Dr. Gül Gökay EMEL
(Uludağ Üniversitesi İ.İ.B.F., İşletme Bölümü)

Arş.Gör. Çağatan TAŞKIN
(Uludağ Üniversitesi İ.İ.B.F., İşletme Bölümü)

Emtullah DİNÇ
(Uludağ Üniversitesi S.B.E., İşletme Yüksek Lisans)
Bursa’nın 10 Mahalleli Bir Bölgesi ve Polis Devriye Aracının
Geçmesi Gereken Caddeler
PROBLEMIN TANIMLANMASI
Çalışmamızda, rotalama problemlerinden Çinli postacı problemi incelenmektedir. Çinli postacı probleminin gerçek hayatta; mektup dağıtımı, yol bakımı, polis devriye araçlarının ve kar temizleme araçlarının rotalarının belirlenmesi ve otobüs çizelgelemesi gibi pek çok uygulamasını görmek mümkündür.

ÇÖZÜM YOLLARININ ANALIZI
Araç rotalamasına dahil edilebilecek örneklerden biri polis devriye araçları için yapılan uygulamadır.
Makale Uludağ Üniversitesi Sosyal Bilimler dergisinin 2003-2004 yıllarındaki basımında yayınlanmıştır.
YAZARLAR
SONUÇ
Turun toplam uzunluğu
12940
metredir. Bu mesafenin
11585
metresi çizgedeki her bir ayrıtın bir kez,
1355
metresi ise çözüm sonucu belirlenen ayrıtlarının ikinci kez geçilmesiyle oluşmuştur.
GEZGIN SATICI PROBLEMI
● Verilen n tane şehir için
Her şehre bir kez uğramak
Ve başlanan noktaya geri dönmek
Şartlarıyla en az maliyeti içeren turu bulma
● Tanımlanması kolay, çözümü zor bir problemdir.
"GSP ile çözülmek istenen problemlerde karmaşıklık ve çalışma süresi artmaktadır.
Bu yüzden GSP problemimize uygun değildir'
Yönsüz Çinli Postacı Problemi

İlk önce, Çinli postacı probleminin çözümünde önemli bir yeri olan Euler tur ve Euler turun oluşumunu açıklayalım.

Problem, bir kişinin Königsberg’deki bir noktadan başlayarak, yedi köprünün her birinden yalnız bir kez geçerek, başladığı noktaya geri dönüp dönemeyeceğidir.
Königsberg’in Yedi Köprü Problemi
Königsberg’deki Yedi Köprünün Çizgesi
Euler incelemeleriyle böyle bir yolun Königsberg’deki köprülerle oluşmasının
mümkün olmadığını
, oluşabilmesi için çizgenin bağlı ve her bir düğümün
çift dereceli
olması gerektiğini ortaya koymuştur
Çinli Postacı Problemi Çesitleri
1)
Yönsüz Çinli postacı problemi (Undirected Chinese postman problem)
2)
Yönlü Çinli postacı problemi (Directed Chinese postman problem)
3)
Karma Çinli postacı problemi ( Mixed Chinese postman problem)
4)
k-Çinli postacı problemi (k-Chinese postman problem)
5)
Min-Max k-Çinli postacı problemi ( Min-Max k-Chinese postman problem)
6)
Hızlı Çinli postacı problemi (Windy Chinese postman problem)
7)
Hiyerarşik Çinli postacı problemi (Hierarchical Chinese postman problem)
8)
Kapasite Kısıtlı Çinli postacı problemi (Capacitated Chinese postman problem)
Çinli Postacı Problemi İçin Çözüm Yöntemleri
Yönsüz Çinli Postacı Problemi
Yönsüz bir çizge üzerindeki her bir ayrıta
en az bir kez uğrayarak
, başlanılan düğüme
geri dönmek
koşuluyla en kısa yolun bulunması istenir.
Tekrarlanan ayrıtların toplam uzunluğunun en küçüklenmesi problemin en iyi sonucunu verir.
Problemin çözümünde kullanılan algoritma ve yöntemler;
Floyd algoritması, Dijkstra algoritması, Euler turu
ve
en kısa mesafeli eşleştirme
olarak sayılabilir. Ayrıca,
tamsayılı doğrusal programlama yöntemleriyle
çözülebilmektedir.
En Kısa Mesafeli Eslestirme Yöntemi
ilk önce çizgedeki tek dereceli düğümler tespit edilir
Burada amaç, oluşturulacak yeni çizgede yer alan tek dereceli düğümlerin olası eşleştirilmiş çiftlerini ve bunların arasındaki en kısa uzunluğu saptamaktır.
Tamsayılı Doğrusal Programlama Yöntemi
Ana amaç :
Kullanılacak olan araç sayısını minimize etmek ve toplam mesafeyi veya toplam zamanı minimuma indirmektir.
Graf en kısa tanımıyla ayrıtlar ve düğümlerden oluşan bir topluluk kümesidir.
GRAF NEDIR ?
G = (V, E)
V = V(G) = dügümler kümesi
E = E(G) = kenarlar kümesi
Örnek:
V = {s, u, v, w, x, y, z}
E = {(x,s), (x,v)1, (x,v)2, (x,u),
(v,w), (s,v), (s,u), (s,w), (s,y),
(w,y), (u,y), (u,z),(y,z)}
EULER TURU
UYGULAMA
Yapmış olduğumuz uygulama çalışmasında 19 Mayıs yerleşkesinde bulunan çöp araçlarının toplandığı depodan başlayarak
12 Düğüm ve 16 Cadde
üzerinden
minimum 1 kere
geçmek suretiyle çöp arabasının yolunu minimize etmeye çalıştık.
Çalışma Yapılan Bölgenin Uydu Görüntüsü
EL ILE COZUM
BILGISAYAR UYGULAMASI
Mesafelerin Belirlenmesi ve Graf Olarak Gösterim
Üstte çalışmanın yapıldığı bölgeye ait harita görünümü verilmektedir. Görüntü Google Maps den sağlanmıştır. İlk olarak elimizdeki 1/200 ölçekli harita vasıtası ile
düğümler arasındaki gerçek mesafeler
ölçülmüştür.
Çözülecek problem Graf haline dönüştürülerek çizge üzerindeki her bir ayrıtın mesafesi graf üzerinde belirtilmiştir.
Tek Dereceli Düğümlerin Belirlenmesi
Düğümlerin dereceleri ; düğümden çıkan çizge sayısının tek sayı yada çift sayı olması anlamına gelmektedir.

*BU DURUMDA HARİTADA Kİ TEK DERECELİ DÜĞÜMLER ;

-2
-5
-6
-8
-10
-12 olarak belirlenmektedir.
Edmond'un En Kısa Mesafeli Eslestirme Yöntemi
Bu metot belirlenen tek dereceli düğümlerin birbirleriyle eşleştirilmek suretiyle en düşük maliyetli eşleştirmeyi bulmayı amaçlamaktadır. Yani çözmüş olduğumuz uygulamada hangi çizgeler üzerinden 2 kez geçersek toplamda minimum yolu katettiğimizi bulmamızı sağlayacaktır.
*(2,5)(6,8)(10,12) = 5400m
*(2,5)(6,10),(8,12) = 5400m
*(2,5),(6,12)(8,10) = 5400m
*(2,6)(5,8)(10,12) = 5400m
*(2,6)(5,12)(8,10) = 5400m
*(2,6)(5,10)(8,12) = 3400m
*(2,8)(5,6)(10,12) = 4860m

*(2,8)(5,10)(6,12) = 4020m
*(2,8)(5,12)(6,10) = 6020m
*(2,10)(5,6)(8,12) = 5400m
*(2,10)(5,8)(6,12) = 6560m
*(2,10)(5,12)(6,8) = 6560m
*(2,12)(5,6)(8,10) = 5400m
*(2,12)(5,8)(6,10) = 6560m
*(2,12)(5,10)(6,8) = 4560m

Rotanın Belirlenmesi
Problemimizde zaten tüm ayrıtlardan geçilmesi zorunlu olduğu için aracımızın minimum
16140 metre
mesafeyi katetmesi gerekmektedir.
Fakat çizgemizin bir euler turu oluşturmaya yetmediği tespit edilmiş ve minimum mesafe karşılaştırma yöntemi ile hangi çizgelerden iki kere geçilirse minimum maliyete sahip olunacağı tespit edilmiştir. Problemde bir çok alternatif rota tespit edilebilir.
ROTA
(1,2)(2,3)(3,4)(4,5)(5,6)
(6,2)(2,6)
(6,7)(7,10)
(10,5)(5,10)
(10,11)(11,12)
(12,7)(7,8)(8,7)(7,12)
(12,9)(9,8)(8,1)
ÇÖZÜM
Problemimizde zaten tüm ayrıtlardan geçilmesi zorunlu olduğu için aracımızın minimum
16140 metre
mesafeyi katetmesi gerekmektedir.
Minimum eşleştirme metodu sonrasında belirlenen çizgelerden 2 defa geçmek suretiyle
3400 metrelik
ek bir mesafe katedilecektir.

Rotamızın toplam uzunluğu
19540metre
bulunmuştur.
Çözüm Algoritmasına Genel Bir Bakıs
Toplam düğüm sayısı ve ayrıt sayısı belirlenir
Düğümlerin birbirlerine bağlılıkları kontrol edilir , çakışmalar yada hatalı veri girişinin önüne geçilir
Tek dereceli düğümler belirlenir
Döngüler aracılığı ile minimum mesafe karşılaştırma metodu ile en kısa kombinasyon bulunur
Her bir düğümü ve komşusunu depolamak vasıtasıyla, bulunan çizgelerin üzerinden 2 defa geçerek optimum rota belirlenir.
SONUC
Ayrıt rotalama problemleri günlük hayatta geniş kullanım alanına sahip ve uzun zamandır pek çok kişinin üzerinde çalıştığı bir en iyileme problemidir.
Gerçek hayatta mektup dağıtımı, yol bakımı, kar temizleme, çöp toplama, devriye araçları ve yol tuzlama konularında pek çok uygulaması vardır.
Gerek hükümetler gerekse de işletmeler her yıl bu işlemler için önemli harcamalar yapmaktadırlar. Fakat planlamanın etkin olarak yapılamaması nedeniyle önemli miktarlarda kaynak israfı söz konusudur. Bu durum Çinli postacı probleminin önemini daha da artırmaktadır.
PEK YAKINDA
GIS ENTEGRASYONU
ZAMAN, BÖLGE SEÇİMİ GİBİ KISITLARIN EKLENMESİ
PROBLEMİ ÇÖZEBİLECEK KULLANIŞLI ARAYÜZE SAHİP BİR YAZILIMIN BETA VERSİYONUNUN GELİŞTİRİLMESİ
Sunumumuzda önce Çinli postacı problemiyle ilgili temel kavramlar, problemin çeşitleri ve yönsüz Çinli postacı probleminin çözüm yön- temleri incelenmektedir. Daha sonra ise, belli caddelerden geçmek zorunda olan bir çöp aracının en iyi rotasının bulunması, yönsüz Çinli postacı problemi olarak ele alınmaktadır.

DINLEDIĞINIZ IÇIN TESEKKÜRLER
MUHAMMED EMIN AYAR ve BETÜL YILMA
Z
Full transcript