Heuristic approaches for multi depot vehicle routing problems with heterogeneous vehicle fleet
Çok depolu heterojen araç filolu araç rotalama problemleri için sezgisel yaklaşımlar
- Tez No: 722254
- Danışmanlar: PROF. DR. GÖZDE YAZGI TÜTÜNCÜ AŞÇI
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Matematik, İstatistik, Industrial and Industrial Engineering, Mathematics, Statistics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: İzmir Ekonomi Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Uygulamalı Matematik ve İstatistik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 124
Özet
Bu tezde, Çok-depolu Geri-toplamalı Heterojen ARP (ÇGHARP) araştırılmıştır. Problem, mevcut üç rotalama probleminin (çok-depolu ARP, heterojen araç filolu problem ve geri-toplamalı rotalama problemi) bir genellemesi olmasına rağmen, bu birleştirilmiş rotalama problemi ilk kez araştırılmıştır. Önce matematiksel bir model sunulmuş, ardından bazı kısıtları daraltılmıştır. Değişken Komşuluk Araması (DKA) ile Aç gözlü Rastsal Adaptif Hafıza Programlama Araması (ARAHPA), kısaca DKA-ARAHPA, birleştirilerek güçlü ve özgün bir birleşik meta-sezgisel önerilmiştir. Kıyaslama ve değerlendirme yapabilmek için herhangi bir problem örneği bulunmadığından, mevcut araç rotalama problem örneklerini birleştirerek veri setleri oluşturulmuştur. Önerilen meta-sezgisel, küçük örnekler için bir dizi optimal çözüm elde edebilmiş ve sırasıyla CPLEX ve temel DKA ile elde edilen yaklaşık %40 ve %20 ortalama aralık değerlerine kıyasla alt sınırlardan yaklaşık %13 aralık değeri elde etmiştir. Tek depo, çok depo, heterojen araç filosu ve geri toplama özelliklerine sahip araç rotalama problemlerini DKA-ARAHPA meta-sezgiseli ile çözebilen bir Karar Destek Sistemi (KDS) geliştirilmiştir. Geliştirilen KDS, ADVISER2 olarak adlandırılan görsel etkileşimli bir çözüm aracıdır. Kullanıcı, çözülmesi gereken problemleri ve elde ettiği çözümleri KDS veritabanına kaydedebilmekte ve kaydedilen çözümün raporunu yazdırabilmektedir. Kullanıcı, çözülecek problemi seçtikten sonra DKA-ARAHPA ile problemi çözebilmekte ve çözüm üzerinde interaktif değişiklikler yapabilmektedir. Geliştirilen KDS, 5 farklı problem için literatürde önerilen problem örnekleri üzerinde test edilmiş ve Geri toplamalı Çok-depolu ARP hariç en iyi bilinen çözümlerden maksimum %5,87 ortalama aralık değeri ile kısa bir CPU süresinde çözüm bulabilmiştir. Ayrıca, DKA-ARAHPA ile Sabit Filolu ve Karma ARP için bir problemin ve çok-depolu ARP için 3 problemin yeni en iyi çözümleri bulunmuştur.
Özet (Çeviri)
In this thesis, we investigated the Multi-Depot Heterogeneous Vehicle Routing Problems (VRP) with Backhauls. Though the problem is a generalisation of three existing routing problems: Multi-depot VRP, the heterogeneous vehicle fleet problem and the routing problem with backhauls, this is the first time this combined routing problem was investigated. A mathematical formulation was first presented followed by some tightening. A powerful and novel unified hybridisation of Variable Neighbourhood Search (VNS) with the Greedy Randomized Adaptive Memory Programming Search (GRAMPS), VNS-GRAMPS for short, was proposed. As there are no problem instances available for bench-marking, we generated data sets by combining those from existing VRPs. The proposed meta-heuristic obtained a number of optimal solutions for small instances and yields about 13% gap from the lower bounds compared to nearly 40% and 20% average gap values for our CPLEX implementation and the VNS without hybridisation, respectively. Moreover, a Decision Support System (DSS) was developed that can solve VRPs with single-depot, multi-depot, heterogeneous vehicle fleet and backhaul features with VNS-GRAMPS meta-heuristic. The developed DSS is a visual interactive solution tool called as ADVISER2. The user can save the problems to be solved and the solutions obtained into the database of DSS, and print the report of the saved solution. After selecting the problem to be solved, the user can solve the problem with VNS-GRAMPS and can make interactive changes on the solution. The developed DSS was tested on the problem instances suggested in the literature for 5 different problems, and it was able to find solutions in a short CPU time with a maximum average gap value of 5.87% from the best known solutions, except for the Multi-depot VRP (MVRP) with backhauls problem. Moreover, new best solutions of one problem for fleet size and mix VRP and 3 problems for MVRP were found with VNS-GRAMPS.
Benzer Tezler
- Belirsizlik altında heterojen filo ve zaman pencereli rotalama problemi: Hızlı tüketim sektöründe bir uygulama
Heterogeneous vehicle routing with time windows under uncertainty: Implementation in fast moving goods industry
ELÇİN ÖZEN KURU
Yüksek Lisans
Türkçe
2018
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. FERHAN ÇEBİ
- 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İ
- Tedarik süreçlerinde döngüsel sefer sistemlerinin yol ve kapasite ölçütlerine dayalı modellenmesi ve uygulanması
Optimization of milk run systems based on distance and capacity criteria
MEHMET YAHYA DURAK
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET BÜLENT DURMUŞOĞLU
- Stokastik talepli çok depolu araç rotalama problemi için sezgisel bir çözüm yaklaşımı
The heuristic solution approach for stochastic demand multidepot vehicle routing problem
KÜBRA KIZILOĞLU
Yüksek Lisans
Türkçe
2017
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. SELÇUK KÜRŞAT İŞLEYEN
- Çok depolu araç rotalama probleminin karınca kolonisi optimizasyonu ile modellenmesi ve bir çözüm önerisi
Modelling of multi depot vehicle routing problem with ant colony optimization and a solution approach
ŞULE YILMAZ
Yüksek Lisans
Türkçe
2008
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Bölümü
YRD. DOÇ. DR. TUFAN DEMİREL