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
- Çin Tömür Batur Destanı üzerine mukayeseli bir inceleme
A Comparative analysis on the epic of Çin Tömür Batur
ABDULHAKİM MEHMET
Yüksek Lisans
Türkçe
1999
Halk Bilimi (Folklor)Ege ÜniversitesiHalk Bilimi Ana Bilim Dalı
YRD. DOÇ. DR. ALİMCAN İNAYET
- A comparative analysis on the perception of consumers about marketing and marketers: The case of Türkiye and Guinea
Tüketicilerin pazarlama ve pazarlamacı kavramı algılarına ilışkin karşılaştırmalı bir analiz: Türkiye ve Gine örneği
JEAN CLAUDE LAMAH
Yüksek Lisans
İngilizce
2022
İşletmeTokat Gaziosmanpaşa Üniversitesiİşletme (İngilizce) Ana Bilim Dalı
DOÇ. DR. ELİF BOYRAZ
- X, Y ve Z kuşaklarının gelinliğe bakış açılarının karşılaştırılmalı olarak incelenmesi
A comparative analysis on the perspectives of the generations X, Y and Z on wedding dress
MEDİNE KAYNAK
Doktora
Türkçe
2022
Giyim EndüstrisiGazi ÜniversitesiGiyim Endüstrisi ve Moda Tasarımı Ana Bilim Dalı
PROF. FATMA ÖZTÜRK
- A comparative analysis on modification of social networks over links with mechanism combinations
Mekanizma kombinasyonları ile linkler üzerinden sosyal ağların modifikasyonu üzerine karşılaştırmalı bir analiz
MERVE ÜNAL
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÖNENÇ YÜCEL