A Genetic algorithm based meta-heuristic for capacitated vehicle routing problem with simultaneous pick-up and delivery
Eş zamanlı dağıtım ve toplama içeren kapasiteli araç rotalama problemi için genetik algoritma bazlı sezgisel yaklaşım
- Tez No: 139607
- Danışmanlar: YRD. DOÇ. DR. BÜLENT ÇATAY
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2003
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 63
Özet
ÖZET Bu çalışmada gerçek hayatta örnekleri görülebilen özel bir karar problemi için kuramsal bir yapı oluşturma üzerine odaklanılmışlar. Problemin kendisi aynı büyüklükte olan dağıtılacak ve iade malların kapasiteleri belirlenmiş özdeş araçlardan oluşan bir filo ile dağıtılması ve aynı anda depoya götürülmek üzere toplanması olarak tanımlanabilir. Literatürde benzer problemler“geri seferli toplama ve iade problemleri”ve“kırsal kesim postacı problemleri”başlıkları altında incelenmektedir. Oluşan NP- hard problemin çözümü için genetik algoritma (GA) kullanılmıştır. İşlemsel verimlilik ve iyi çözüm performansı aranmıştır. Araç rotalama problemleri üzerine olan geniş literatür taranmış, en çok kullanılan çözüm yöntemleri kendi aralarında sınıflandırılmış ve kısaca tanıtılmıştır. Dethloff (2001) tarafından önerilen doğrusal tamsayı programlama modeli baz alınarak genetic algoritma esaslı bir model geliştirilmiş ve bunun üzerinde denemeler gerçekleştirilerek yüksek kalitede sonuç üretebilen sağlam bir yaklaşım geliştirilmesine çalışılmıştır. Üzerinde çalıştığımız modeller benzer özellikler sergileyen makine çizelgeleme literatüründen alınarak problemimize uyarlanmıştır. Araştırmamız, üzerinde çalıştığımız problem için henüz GA'lan kullanarak çözüme ulaşmış herhangi bir çalışma olmadığım göstermiştir. Dolayısıyla yaptığımız çalışma mevcut haliyle alanında bir ilktir. ikinci olarak önerilen geliştirilmiş algoritmamız oldukça başarılı sonuçlar üretirken rastsal anahtarlama metodu ile üretilen sonuçların oldukça kötü olduğu gözlenmiştir. Çözümlerimiz, yayınlanmış ve akademik literature girmiş olan Min'in (1989) tek ve Dethloff un (2001) kırk örnekli problemlerinin girdileri esas alınarak üretilmiş ve yayınlanmış, bilinen en iyi sonuçlarla karşılaştrnlmıştır. Parametre testleri
Özet (Çeviri)
ABSTRACT In this study, we focus on the theoretical framework of a decision model for a real world problem. The problem reveals itself as simultaneous distribution of commodities and recollection of empty packages the same size as the initial state with a single depot and a fleet of uniform vehicles with limited capacities. Resembling instances pile a profound literature under the category of“pick-up and delivery problems with backhauls”and“rural postman problem.”To solve the arousing NP-hard problem we use genetic algorithm approach. Computational efficiency and a good solution performance are sought. We have studied the wide literature of the vehicle routing problems, classified and briefly introduced the previous asserted algorithms, which provide considerably high quality solutions. We have developed a genetic algorithm based meta-heuristic on a linear IP model proposed by Dethloff (2001) and conducted tests to come up with a robust heusritic producing results with a reasonable quality. The models we studied were mainly taken from the machine scheduling literature and adapted to handle our problem. Our research has revealed that no resembling problem has ever been proposed to be solved using the genetic algorithms approach. Thus, this work is a first in its field. The improvement algorithm is found to be considerably good performing while the random keys method failed to produce reasonable solutions. We have tested our algorithm on two benchmark problems introduced by Min (1989) and Dethloff (2001). The latter is composed of 40 problem instances generated. We have performed parameter tests to tune our algorithm and shown that our algorithm produced the best ever solution for the first problem and considerably good solutions for the second one.
Benzer Tezler
- Kapasite kısıtlı araç rotalama probleminin yabani ot ve hibrit metasezgisel algoritmalarla çözümü
Solution of capacitated vehicle routing problem with invasive weed and metaheuristic algorithms
ÜMİT YILDIRIM
Yüksek Lisans
Türkçe
2019
Endüstri ve Endüstri MühendisliğiÇukurova ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ YUSUF KUVVETLİ
- The capacitated vehicle routing problem with simultaneous pickup-delivery and time windows in the sustainable food supply chains
Sürdürülebilir gıda tedarik zincirlerinde zaman pencereli ve eşzamanlı toplama-teslimatlı kapasite kısıtlı bir araç rotalama problemi
MAHDI FARSHCHI
Doktora
İngilizce
2021
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. FATMA SEDEF MERAL
PROF. DR. FERDA CAN ÇETİNKAYA
- Araç rotalama problemleri için matematiksel modeller ve subgradyant temelli çözüm yaklaşımı
Mathematical models and subgradient based solution approach for the vehicle routing problems
MELİS ALPASLAN TAKAN
Doktora
Türkçe
2019
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. REFAİL KASIMBEYLİ
- A genetic algorithm for the location-routing problem with time windows
Zaman kısıtlı yerleşim-rotalama problemi için bir genetik algoritma
HANDE ÖZGÖNENÇ
Yüksek Lisans
İngilizce
2006
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. SEDEF MERAL
- Genetic algorithm based hybrid approaches to solve the capacitated lot sizing problem with setup carryover and backordering
Hazırlık taşımalı, birikmiş siparişli kapasite kısıtlı parti büyüklüğü problemi için genetik algoritma tabanlı melez çözüm yaklaşımları
HACER GÜNER GÖREN
Doktora
İngilizce
2011
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. DR. SEMRA TUNALİ