An adaptive large neighborhood search algorithm for selective and periodic inventory routing problem
Seçici ve periyodik envanter rotalama problemi için uyarlanmış geniş komşu arama sezgisel algoritması
- Tez No: 332229
- Danışmanlar: DOÇ. DR. FATMA SİBEL SALMAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 107
Özet
Bu çalışmada, tersine lojistik alanında karşımıza çıkan seçici ve periyodik envanter rotalama problemi için literatürdeki ilk sezgisel methodu geliştiriyoruz. Bu problemde, restoran ve otel gibi büyük miktarda bitkisel yağ tüketimi yapan ve ?stanbul?un anadolu tarafına yayılmış bu kaynak noktalarından atık bitkisel yağ toplayan bir biyodizel üretim tesisini inceliyoruz. Toplanan atık yağlar bu tesiste biyodizel üretmek için hammadde olarak kullanılmaktadır. Üretim tesisinin yöneticisi mevcut kaynak noktalarından hangilerini atık toplama programına dahil edilmesi gerektiğine; hangilerinin her gün ziyaret edilmesi gerektiğine; sonsuz süre zarfında hangi periyodik rotalama çizelgesinin tekrarlanması gerektiğine karar vererek, üretim gereksinimleri ile operasyonel kısıtlar altında araç kullanımı, rotalama, envanter ve satın alma maliyetlerin toplamını minimize etmeyi amaçlamaktadır. Bu seçici ve periyodik envanter rotalama problemi için yakın geçmişte ilk olarak akış tabanlı bir doğrusal tamsayılı programlama (DTP) modeli geliştirildi ve 40 kaynak noktasına kadar gerçek hayat problemleri üzerinde test edildi. Kaynak nokta sayısı 25?i aştığında, bu modelin 3 saat limitli çözümlerinin uygunluk düzeyinin %10?u aştığı belirtildi. Bu problemi daha fazla kaynak sayısı ile uygun zaman limitleriyle daha etkili çözebilmek için 11 farklı komşu yapısından oluşan bir uyarlanmış geniş komşu arama sezgisel algoritması geliştirdik. Bazı komşu yapıları kaynak noktasının ziyaret programını ve araçların rotalamasını modifiye ederken, diğerleri ziyaret edilen kaynak nokta listesini de değiştirebiliyor. Algoritmamızın sonuçlarını DTP modeli ile karşılaştırdığımızda, bizim methodumuzun birkaç saniye içinde bulduğu çözümü DTP modelinin bir kaç saate bulduğunu gördük. Kaynak nokta sayısı 30?u geçtiğinde bizim algoritmamız, DTP modelinden daha iyi sonuçlar vermektedir. Aynı zamanda, algoritmamızı 100 kaynak noktasına kadar büyük problemlerde de test ettik. 50 ile 100 arasında kaynak noktasına sahip problemlerin çözümlerini hesapladığımız alt limitlerle karşılaştırdığımızda, algoritmamızın bu problemleri ortalama %10.7 uygunluk düzeyinde çözdüğünü gözlemledik.
Özet (Çeviri)
In this thesis we develop the first metaheuristic method for a selective and periodic inventory routing problem (SPIRP) that arises in reverse logistics. The problem concerns a biodiesel production company collecting used vegetable oil from restaurants and hotels which are the source nodes using and wasting vegetable oil in considerable amounts. The production facility reuses the waste oil as raw material to produce biodiesel and meets the raw material requirement for each day from daily collection, inventory and by purchasing oil. The manager needs to decide which of the present source nodes to include in the collection program, and which periodic routing schedule to repeat in every planning horizon to visit these nodes accumulating vegetable oil. His objective is to minimize the total collection, inventory and purchasing costs while the production requirements and operational constraints are met. Recently, a flow-based mixed integer linear programming (MILP) formulation was proposed for this problem, and solved on a real-world case with up to 40 source nodes. However, it was observed that the average optimality gap attained by the commercial MILP solver in three hours exceeds 10% when there are more than 25 nodes present. In order to solve large sized instances of SPIRP more effectively in a reasonable time, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm by using a rich neighborhood structure comprised of 11 distinct moves. Some of these moves modify the visiting schedule and vehicle routes, while others change also the subset of visited source nodes. We test our algorithm on small size instances and compare the results with the MILP model. While our algorithm solves the small instances in several seconds, the MILP model runs for hours to find similar results. When the number of source nodes is 30 and more, our algorithm outperforms the MILP model. We also test our algorithm on larger instances with up to 100 nodes and present the related computational results. For the instances with 50 to 100 nodes, the problem is solved with around 10.7% gap.
Benzer Tezler
- Karma filolu elektrikli araç rotalama problemi ve çözüm yaklaşımları
Mixed fleet electric vehicle routing problem and solution methods
SERCAN DÖNMEZ
Doktora
Türkçe
2022
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. FULYA ALTIPARMAK BAYKOÇ
DOÇ. DR. ÇAĞRI KOÇ
- Sürdürülebilir toplu konut yerleşmesi tasarımı için Pareto genetik algoritmaya dayalı bir model önerisi: SSPM
A model for sustainable site layout design with pareto genetic algorithm: SSPM
YAZGI AKSOY
- Advanced statistical methods for intelligent transportation systems
Akıllı ulaşım sistemleri için ileri istatistiksel yöntemler
BÜŞRA GÜNGÖR
Doktora
İngilizce
2022
İstatistikDokuz Eylül Üniversitesiİstatistik Ana Bilim Dalı
PROF. DR. SELMA GÜRLER
- AN ADAPTIVE LARGE NEIGHBORHOOD SEARCH APPROACH FOR SOLVING THE ELECTRIC VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
ZAMAN PENCERELİ ELEKTRİKLİ ARAÇ ROTALAMASI PROBLEMİ İÇİN BİR UYARLANABİLİR GENİŞ KOMŞULUK ARAMA YÖNTEMİ
MERVE KESKİN
Yüksek Lisans
İngilizce
2014
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. BÜLENT ÇATAY
- Vehicle routing problem with vendor selection, intermediate pick-ups and deliveries
Tedarikçi seçimli, ara dağıtım ve toplamalı araç rotalama problemi
UGUR EMEC
Yüksek Lisans
İngilizce
2013
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. BÜLENT ÇATAY
DOÇ. DR. BURÇİN BOZKAYA