A comparative analysis on undirected cut-based formulations of periodic vehicle routing problem
Periyodik araç rotalama probleminin kesi temelli formülasyonları üzerine karşılaştırmalı bir inceleme
- Tez No: 762078
- Danışmanlar: DR. ÖĞR. ÜYESİ AMİNE GİZEM TİNİÇ
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 53
Özet
Klasik Araç Rotalama Problemi (ARP), tek bir planlama periyodu içerisinde bir müşteri grubunun taleplerini karşılamak amacıyla türdeş araçlardan oluşan bir araç filosu için en düşük maliyetli rotaları belirlemeye çalışan bir kombinatoryal eniyileme problemidir. Periyodik Araç Rotalama Problemi (PARP), planlama döneminin birden çok periyottan oluştuğu ve her müşterinin bir dizi olası ziyaret çizelgesine sahip olduğu klasik ARP'nin bir genellemesidir. Literatürde bu problemi çözmek amacıyla önerilmiş kesin çözüm yöntemleri, sezgisel algoritmalar ve metasezgisel çözüm yaklaşımları bulunmaktadır. Bununla birlikte PARP literatüründe, kesi temelli formülasyonlara odaklanan kapsamlı çalışma eksikliği bulunmaktadır. Bu tezde, yönsüz bir çizge üzerinde tanımlanan bir PARP için, bir temel modeli ve beş alternatif kesi temelli formülasyon öneriyor ve bunları inceliyoruz. Alternatif formülasyonlar geliştirmek için bağlantı kısıtlarının ve çizelgeleme seçimi kısıtlarının farklı türevleri kullanılmaktadır. Ayrıca, PARP için araç indislerinin kullanımını ortadan kaldıran bir yönsüz ve kesi temelli formülasyon da ortaya çıkarılmıştır. Tüm formülasyonlar sayıca üstel olarak büyüyen bağlantı kısıtları içerdiğinden, önerilen formülasyonların kesin çözümüne ulaşabilmek amacıyla dal-ve-kesi algoritması tasarlanmış ve kullanılmıştır. Formülasyon ve çözüm yöntemlerinin belirlenmesinin ardından, tüm formülasyonlar için hesaplamalı deneyler hazırlanmış ve uygulanmıştır. Deneylerin sonuçları, bazı alternatif formülasyonların çözüm performansını iyileştirme potansiyeline sahip olduğunu göstermektedir. Araç indisleri olmayan model, en iyi sonuca ulaşma ve çözüm süreleri açısından iyileştirme sağlarken, alternatif çizelge seçim kısıtlarına sahip modeller, çözüm kalitesi ve ortalama çözüm süreleri açısından umut verici sonuçlar vermektedir.
Özet (Çeviri)
The classical Vehicle Routing Problem (VRP) is a well-studied combinatorial optimization problem whose aim is to identify optimal routes for a fleet of homogeneous vehicles to satisfy the demands of a geographically dispersed set of customers, considering a single planning period. The Periodic Vehicle Routing Problem (PRVP) is a generalization of the classical VRP in which the planning horizon consists of multiple periods and each customer has a set of associated possible visit schedules. In the literature, there are many solution approaches proposed such as exact solution methods, heuristic algorithms, and metaheuristics. However, exact solution methods are much fewer in number compared to heuristic methods, and a comprehensive study focused on cut-based formulations of the problem is not available in the literature. In this thesis, we propose and study several cut-based formulations of the PVRP defined on an undirected network. Different versions of connectivity constraints and schedule selection constraints are used to develop alternative formulations. Moreover, new cut-based formulations which eliminates the use of vehicle indices are also introduced. Since the proposed formulations contain exponentially many connectivity constraints, we devise and implement branch-and-cut procedures to solve them exactly. The computational experiments are prepared and conducted for all of the formulations. The results of the experiments indicate that some of the alternative formulations have the potential to improve computational performance. The model without vehicle indices provides improvement in terms of reaching optimality and computation times, while the models with alternative schedule selection constraints provide promising results in terms of solution quality and average computation times.
Benzer Tezler
- Turkish-British economic relations 2002-2012: An intensely political relationship
Türk-İngiliz ekonomik ilişkileri 2002-2012: Yoğun derecede siyasi bir ilişki
JOHN ANGLISS
Yüksek Lisans
İngilizce
2012
Uluslararası İlişkilerOrta Doğu Teknik ÜniversitesiUluslararası İlişkiler Ana Bilim Dalı
DOÇ. DR. EBRU BOYAR
- Core network anomaly detection using the LSTM model and comparison with various unsupervised learning methods
Telekomünikasyon merkezi şebekelerinde LSTM model ile anomali tespiti ve bazı denetimsiz öğrenme metotları ile kıyaslanması
SAMED ÇALIK
Yüksek Lisans
İngilizce
2025
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiBüyük Veri ve İş Analitiği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MEHMET ALİ ERGÜN
- 20. yüzyıl New Age akımı üzerine karşılaştırmalı bir analiz
A comparative analysis on New Age movement in the 20th century
EMRE UYSAL
Yüksek Lisans
Türkçe
2015
DinÇukurova ÜniversitesiFelsefe ve Din Bilimleri Ana Bilim Dalı
PROF. DR. MÜNİR YILDIRIM
- Türkiye'de katılım bankaları ile geleneksel bankaların çalışma prensipleri ve finansal performansları üzerine karşılaştırmalı bir analiz
A comparative analysis on working principles and financial performances of participation banks and conventional banks in Türkiye
YASİN YÜKSEL
Yüksek Lisans
Türkçe
2024
BankacılıkNecmettin Erbakan Üniversitesiİktisat Ana Bilim Dalı
PROF. DR. MUSTAFA ACAR
- Bazı gelişmiş ülkeler ile Nijer'de sınıf öğretmenlerinin eğitimi ve istihdamı konusunda karşılaştırmalı bir analiz
A comparative analysis on primary school teachers' training and employment of some developed countries and Niger
MAHAMADOU YAHAYA
Doktora
Türkçe
2018
Eğitim ve ÖğretimHacettepe ÜniversitesiEğitim Bilimleri Ana Bilim Dalı
PROF. DR. ŞADUMAN KAPUSUZOĞLU