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: Araç yönlendirme problemi, Karma tamsayılı programlama, Çizelgeleme, Vehicle routing problem, Mixed integer programming, Scheduling
- 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ı: Belirtilmemiş.
Ö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
- Almanya Parlamentosu ve TBMM'de 2015 ve 2016 yıllarında göç hareketliliği üzerine yapılan tartışmaların analizi
An analysis of the debates on migration mobility in the German Parliament and TBMM in 2015 and 2016
SELİM YILDIRIM
Doktora
Türkçe
2024
Siyasal BilimlerGalatasaray ÜniversitesiSiyaset Bilimi Ana Bilim Dalı
DOÇ. DR. ASLI DİDEM DANIŞ ŞENYÜZ
- Türk ve İtalyan Ceza Hukukunda güvenlik tedbiri kuramı ve kişi hürriyetini sınırlandıran güvenlik tedbirleri
The theory of security measure and personal security measures limiting personal freedom in Turkish and Italian Criminal Law
BATUHAN AKTAŞ
- Küreselleşme sürecinde güvenliği yeniden düşünmek
Rethinking security in the globalisation process
BİLAL KARABULUT
Doktora
Türkçe
2009
Uluslararası İlişkilerGazi ÜniversitesiUluslararası İlişkiler Bölümü
PROF. DR. HAYDAR ÇAKMAK
- Türk Ceza Hukukunda yetkili merciin emrini ifa (TCK m. 24)
Execution of the order of the competent authority in Turkish Criminal Law (TPC art. 24)
MELİKE EZGİ YETİMOĞLU