Zaman pencereli tamirci problemi ve uzantılarının yeni matematiksel modelleri
New mathematical models for the traveling repairman problem with time windows and its extensions
- Tez No: 686909
- Danışmanlar: PROF. DR. İMDAT KARA
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: Türkçe
- Üniversite: Başkent Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 193
Özet
Tamirci Problemi (TP) rotalama problemlerinin temelini oluşturan Gezgin Satıcı Probleminin (GSP) bir türüdür. TP müşteri memnuniyetini esas alıp, tüm müşterilerin toplam gecikme zamanını enküçük yapmayı amaçlar. TP, başlangıç düğümünden yola çıkan bir tamircinin, tüm müşterilere hizmet verdikten sonra başlangıç noktasında veya verilen bir düğümde sona eren, toplam gecikmeyi enküçükleyen Hamilton turunu veya yolunu bulmaktır. Tez kapsamında, TP'nin gerçek hayat uygulamalarında en çok karşılaşılan, zaman pencereli TP (ZPTP), çok gezginli zaman pencereli TP (ÇZPTP) ve çok depolu zaman pencereli TP (DZPTP) uzantıları ele alınmıştır. Öncelikle, ZPTP için kaynaklarda var olan iki matematiksel model incelenerek, ZPTP için polinom sayıda kısıta ve karar değişkenine sahip dört yeni matematiksel model geliştirilmiştir. Yapılan sayısal analizler sonucunda, geliştirilen matematiksel modellerden iki tanesinin performansının, CPU süreleri ve sapma oranları yönüyle, diğerlerine göre çok üstün olduğu görülmüştür. Ardından, ÇZPTP ele alınarak, yapılan kaynak araştırması sonucunda homojen ve heterojen durum için toplam iki matematiksel model bulunmuştur. Tez kapsamında homojen ÇZPTP için düğüm tabanlı ve ayrıt tabanlı olmak üzere iki adet ve heterojen ÇZPTP için düğüm tabanlı ve ayrıt tabanlı olmak üzere iki adet, polinom sayıda kısıta ve karar değişkenine sahip matematiksel model geliştirilmiştir. Kaynaklarda var olan modeller ve geliştirilen yeni modeller farklı tamirci sayıları ele alınarak, karşılaştırma problemlerinin çözüm için gerekli CPU süreleri ve sapma oranları yönüyle incelenmiştir. Sayısal analizler sonucunda, düğüm tabanlı modellerin hem homojen hem heterojen durum için üstün performans gösterdiği görülmüştür. Çalışmanın bu aşamasından sonra DZPTP üzerine odaklanılmış ve kaynak araştırması yapıldığında bu alanda hiçbir çalışma olmadığı anlaşılmıştır. DZPTP için gerçek hayatta karşılaşılabilecek beş farklı duruma yönelik matematiksel modeller geliştirilmiştir. Kaynaklardaki test problemleri çözülerek yapılan sayısal analizlerde, bazı problemler için tamirci sayılarında artış yapılarak eniyi çözümler elde edilebilmiştir ve modellerin performansları problemlerin çözümleri için geçerli olan CPU süreleri ve sapma oranları yönüyle değerlendirilmiştir. Büyük boyutlu problemlerin az tamirci sayısı ile süre sınırı içerisinde eniyi çözümlerine erişilemediğinden dolayı metasezgisel bir algoritma olan Biyocoğrafya Tabanlı Eniyileme (BTE) algoritması geliştirilmiştir. BTE algoritmasının parametre değerleri deney tasarımı yapılarak belirlenmiştir. Sayısal analizler ile algoritmanın etkinliği incelenmiş ve bu aşamada eniyi değerden sapma oranı, değişim katsayısı ve çözüm zamanı ölçütleri temel alınmıştır. BTE algoritması ile büyük boyutlu problemler için kabul edilebilir zamanda yüksek kaliteli çözümler elde edilmiş ve algoritmanın üstün başarı gösterdiği görülmüştür. Bu çalışmanın en önemli sonuçları ZPTP, ÇZPTP ve DZPTP için önerilen yeni matematiksel modellerin ve DZPTP için geliştirilen metasezgisel algoritmanın bilime katkı olarak sunulmasıdır.
Özet (Çeviri)
The Traveling Repairman Problem (TRP) is a variant of the Traveling Salesman Problem (TSP) which is the basis of the routing problems. TRP is based on customer satisfaction and aims to minimize total delay time of customers. TRP involves finding a Hamiltonian tour or path starting from an initial node, after visiting all customers, it ends at the starting or any given node in such a way that, total delay time is minimized. In this study, TRP with time windows (TRPTW), multiple traveler TRPTW (kTRPTW) and multi depot TRPTW (DTRPTW) are considered. Firstly, we observe that there exist only two mathematical models for TRPTW and four new mathematical models with polynomial number of constraints and decision variables are developed. Benchmark problems are solved by existing and new models for TRPTW and CPU times and deviation rates are analyzed. We conclude that two of the new mathematical models are superior to the others. Then, for kTRPTW, two mathematical models are found for homogeneous and heterogeneous case in the literature. Two new mathematical models which are node-based and arc-based with polynomial number of constraints and decision variables are developed for homogeneous and heterogeneous kTRPTW. The performances of the existing and new models for kTRPTW are compared by using benchmark problems in terms of CPU times and deviation rates with different number of repairmen. As a result of computational analysis, we observe that, the node-based models show superior performance for both cases. Lastly, it is focused on DTRPTW and we could not find any study for DTRPTW in the literature. Five mathematical models with polynomial number of constraints and decision variables are proposed for various types of the DTRPTW. The performances of new formulations are analyzed in terms of CPU times and deviation rates for solving problems. Since the optimal solutions cannot be reached with mathematical formulation by using small number of repairmen for some large-sized problems in a reasonable time, a metaheuristic algorithm named as Biogeography-Based Optimization (BBO) is developed to solve them approximately. The parameter values of BBO algorithm are estimated by experimental design. The efficiency of the algorithm is evaluated by using deviation rate from the optimal value, coefficient of variation and solution time. The proposed metaheuristic algorithm represents a high performance to find good quality solutions within acceptable CPU times for large-size problems. The main contribution of this study is to present new mathematical models for TRPTW, kTRPTW, DTRPTW and the metaheuristic algorithm for DTRPTW.
Benzer Tezler
- Müşteri odaklı bakım onarım faaliyetleri performansının dinamik tamirci rotalama problemi ile modellemesi ve optimizasyonu
Modeling and optimisation of maintenance and repair activities performance by dunamic repairman problem
ARZUM ÖZGEN
Doktora
Türkçe
2008
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. HAYRİ BARAÇLI
- Zaman pencereli ve bulanık talepli evde bakım/beslenme hizmeti yönlendirme problemi için karınca koloni algoritması
Ant colony algorithm for household care / nutrition service direction problem with time window and fuzzy demand
BURAK CAN
Yüksek Lisans
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMersin ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. HAMZA EROL
- A solution approach for the distributed no-idle flowshop scheduling problem with due windows
Zaman pencereli dağıtık beklemesiz akış tipi çizelgeleme problemi için bir çözüm yaklaşımı
KASRA MOUSIGHICHI
Yüksek Lisans
İngilizce
2023
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUALLA GONCA AVCI
- Zaman pencereli araç rotalama probleminin geliştirilmiş yapay arı kolonisi ve ateş böceği algoritmaları ile çözümü
Solving the time window vehicle routing problem with improved artificial bee colony and firefly algorithms
NAZİFE ŞAHİN MACİT
Doktora
Türkçe
2022
İşletmeBurdur Mehmet Akif Ersoy Üniversitesiİşletme Ana Bilim Dalı
DOÇ. DR. YUSUF ŞAHİN
- Zaman pencereli araç rotalama probleminin genetik algoritma ile modellenmesi
Modeling vehicle routing problem with time windows with genetic algorithm
PINAR DURSUN
Yüksek Lisans
Türkçe
2009
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. Y. İLKER TOPÇU