Periodic vehicle routing problems with visual attractiveness and driver consistency
Görsel elverişlilik ve sürücü tutarlılığı kısıtları ile periyodik araç rotalama problemi
- Tez No: 895114
- Danışmanlar: ASSISTANT PROF. AMİNE GİZEM TİNİÇ
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Mühendislik ve Doğa Bilimleri Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 133
Özet
Bu tezde, periyodik araç rotalama problemi (PARP) ve varyantlarına yönelik yenilikçi ve etkin çözüm yaklaşımları geliştirilmesine odaklanılmıştır. İlk olarak, PARP için yeni bir araç akış formülasyonu önerilmiş ve geçerli eşitsizliklerle güçlendirilmiştir. Ayrıca, literatürde PARP için mevcut olan iki önemli formülasyon incelenmiştir: yük-temelli formülasyon ve başlangıçta PARP'nin bir varyantı için geliştirilmiş bir formülasyondan uyarlanan kesi-temelli formülasyon. Bu formülasyonlar, zaman pencereli PARP'yi (PARP-ZP) modelleyecek biçimde genişletilmiş ve elde edilen formülasyonları güçlendirmek için yine geçerli eşitsizliklerden ve optimalite kesilerinden faydalanılmıştır. Farklı özelliklere sahip çeşitli problem örnekleri üzerinde, alternatif PARP ve PARP-ZP formülasyonlarının performanslarını karşılaştırmak için kapsamlı bir hesaplama çalışması gerçekleştirilmiştir. Sonuçlar, özellikle büyük örnekler için, önerilen formülasyonun ve güçlendirilmiş versiyonlarının, iyi kalitede çözümler üretme konusunda gürbüzlüğünü ve tutarlılığını doğrulamakta, ancak yük-temelli formülasyonların küçük ve orta örneklerde üstün performans gösterme eğiliminde olduğuna işaret etmektedir. Ardından, PARP'yi çözmek için bir mantık temelli Benders ayrıştırma (MTBA) yaklaşımı ve sütun türetmeye dayalı bir sezgisel yöntem geliştirilmiştir. Elde edilen bulgular, sütun türetme algoritmasının, literatürde bilinen en iyi çözümlere kıyasla ortalamada yalnızca %0.21 sapmaya sahip çözümler belirleyebildiğini ortaya koymuştur. Son olarak, PARP-ZP'ye görsel elverişlilik ve sürücü tutarlılığı kısıtlarının eklenmesiyle elde edilen genişletilmiş problem (PARP-ZPGEST) için bir karışık tamsayılı programlama formülasyonu geliştirilmiştir. Problemi etkin bir şekilde çözmek için bir adaptif geniş komşuluk arama algoritması ve buna dayalı bir paralel temperleme yöntemi önerilmiş ve önerilen algoritmanın performansı, yapılan hesaplama çalışmaları ile doğrulanmıştır.
Özet (Çeviri)
This thesis explores advanced methodologies and innovative approaches to the Periodic Vehicle Routing Problem (PVRP) and its variants. Initially, we propose a new vehicle flow formulation for the PVRP and strengthen it with valid inequalities. We also investigate two prominent formulations for the PVRP available in the literature: a commodity flow formulation, referred to as the load-based formulation, and a cut-based formulation which is adapted from a formulation originally developed for a variant of the PVRP. We also extend these formulations to model the PVRP with time windows (PVRPTW) and employ valid inequalities to tighten the resulting formulations. A comprehensive computational study is then carried out to compare the performances of alternative PVRP and PVRPTW formulations on various sets of benchmark instances with different characteristics. The results attest to the robustness and the consistency of the proposed formulation and its strengthened versions in producing good quality solutions, especially for large instances although the load-based formulations tend to perform well in small instances. Subsequently, we address the PVRP using a Logic-Based Benders Decomposition approach and a Column Generation-based heuristic. Our findings reveal that the Column Generation algorithm achieves near-optimal solutions, deviating by an average of only 0.21% from the best-known solutions in the literature. Further, we incorporate visual attractiveness and driver consistency constraints into the PVRPTW, developing a Mixed-Integer Linear Programming formulation for this extended problem (PVRPTWVADC). To solve the PVRPTWVADC, we propose an Adaptive Large Neighborhood Search (ALNS) algorithm and a Parallel Tempering-based ALNS (PTALNS). Comprehensive computational studies highlight the robustness and superior performance of the PTALNS algorithm.
Benzer Tezler
- Sıfır atık projesi kapsamında geri dönüşümlü atıkların toplanması: Kırıkkale'de heterojen çok araçlı araç rotalama uygulaması
Collection of recyclable wastes within the scope of zero waste project: Heterogeneous multi-vehicle routing case in Kırıkkale
ŞAFAK KIZILTAŞ
Yüksek Lisans
Türkçe
2019
Endüstri ve Endüstri MühendisliğiKırıkkale ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ HACI MEHMET ALAKAŞ
PROF. DR. TAMER EREN
- Multi-trip periodic vehicle routing problem with time windows, split delivery for simultaneous pick-up and delivery
Başlık çevirisi yok
YILDIZ ÖZDEMİR
Yüksek Lisans
İngilizce
2020
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÖRKEM YILMAZ
- Dinamik eş zamanlı topla-dağıt araç rotalama problemi için matematiksel model ve sezgisel yaklaşımlar
Mathematical formulations and heuristic approaches for the dynamic vehicle routing problem with simultaneous pickup and delivery
BURAK AYDOĞDU
Doktora
Türkçe
2017
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. BAHAR ÖZYÖRÜK
- Selective and periodic inventory routing problem for collection of end-of-life products
Yaşam döngüsünü tamamlamış ürünler için seçimli ve periyodik envanter rotalama problemi
YELİZ AKÇA
Yüksek Lisans
İngilizce
2011
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. F. SİBEL SALMAN
YRD. DOÇ. DR. ONUR KAYA