Belirsizlik altında hiyerarşik çinli postacı problemi ve çözüm yaklaşımları
Hierarchical chinese postman problem under uncertainty and solution approaches
Yazar: ÖZLEM ÇOMAKLI SÖKMEN
Danışman: DOÇ. DR. MUSTAFA YILMAZ
Atatürk Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2021
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Amaç: Gerçek hayatta merkezler arasındaki ulaşım süresi öngörülemeyen hava şartları, trafik yoğunluğu gibi unsurlardan ötürü değişkenlik gösterebilmektedir. Bu nedenle çalışmada, seyahat süreleri belirsiz değişkenler olarak ele alınmış, Bulanık Seyahat Zamanlı Hiyerarşik Çinli Postacı Problemi (BSZ-HÇPP) ve Stokastik Seyahat Zamanlı Hiyerarşik Çinli Postacı Problemi (SSZ-HÇPP) olarak isimlendirilen yeni problem türleri tanıtılmıştır. Çöp toplama, sokak temizleme gibi uygulama alanı yaygın olan bu problemler için matematiksel modeller önerilmiş, büyük boyutlu problemlerin çözümüne yönelik yeni yaklaşımlar sunulmuştur. Bu çalışmada geliştirilen problem türlerinin ve çözüm yaklaşımlarının gerçek hayat problemlerine uygulanabilirliğinin artırılması, önerilen algoritmaların performanslarının karşılaştırılması amaçlanmaktadır
Yöntem: Bu çalışmada HÇPP bulanık mantık ve şans kısıtlı stokastik programlama yaklaşımı ile ele alınmıştır. Problemin NP-zor yapısından dolayı önerilen modeller yalnızca küçük boyutlu problemlere çözüm bulabilmiştir. Büyük boyutlu test problemlerine makul sürede çözüm bulabilmek amacıyla Matlab-2019b programlama dili kullanılarak biri açgözlü arama, diğeri karınca kolonisi algoritması tabanlı iki çözüm yaklaşımı önerilmiştir. 
Bulgular: Elde edilen verilere göre önerilen algoritmalar çeşitli boyuttaki problemlerde kısa sürede uygun çözümler sunmaktadır. Çalışma kapsamındaki tüm örneklerde önerilen meta-sezgisel, sezgiselden ortalama amaç fonksiyonu değeri açısından daha iyi sonuçlar bulsa da önerilen sezgisel algoritmanın kullandığı ortalama bilgisayar çözüm zamanı meta-sezgiselden daha kısadır. Dolayısıyla yöntemlerin ikisinin de bu test problemleri üzerinde belli oranlarda başarılı olduğu söylenebilir.
Sonuç: Bu çalışmada literatürde görülen eksiklikler dikkate alınarak amaç fonksiyonunda düğümler arasındaki mesafe değerleri yerine bulanık ve stokastik seyahat sürelerinin kullanılmasıyla rota ve maliyetin büyük ölçüde değişebildiği gözlemlenmiştir. Ayrıca önerilen algoritmaların etkinlikleri karşılaştırılmıştır. Meta-sezgiseller çözüm bölgesinde derin bir araştırma yaparken; sezgiseller yalnızca yerel olarak arama yaptığı için bu sonuçlara varıldığı söylenebilir.

Abstract:
Purpose: In real life, the transportation period between the centers can change due to unpredictable weather conditions and rush hours on traffic. Therefore, in the study, travel times were accepted as uncertain variables, and new types of problems, namely, Fuzzy Travel Times Hierarchical Chinese Postman Problem (FTT-HCPP) and Stochastic Travel Time Hierarchical Chinese Postman Problem (STT-HCPP) were introduced. Mathematical models for problems with a wide range of applications, such as garbage collection and street sweeping, have been proposed, as well as new methods for solving large-scale problems. This study aims to increase the applicability degree of these problem types and their solutions to real-world problems, as well as compare the performance of the proposed algorithms.
Method: In this study, HCPP fuzzy logic and the chance-constrained stochastic programming approach have been administered. Due to the NP-hard nature of the problem, the proposed models could only find solutions to the small-size problems. Two solution methods, one is based on the greedy algorithm and the other on ant colony optimization, were proposed using the Matlab-2019b programming language to find solutions to large-scale test problems in a reasonable amount of time. 
Findings: The algorithms proposed based on obtained data provide appropriate solutions to the problems of various scales in a brief time. Although the proposed meta-heuristic found better results than the heuristic in all the examples included in the study when looking at the mean objective function value, the mean computer solution time used by the proposed heuristic algorithm is shorter than the meta-heuristic. Therefore, one can say that both methods are successful on these test problems to a certain extent.
Results: Given the shortcomings of the literature, the study's results indicate that by using fuzzy and stochastic travel times rather than distance values between nodes in the objective function, the route and cost can change significantly. Besides, the efficiencies of the proposed algorithms were compared. It is possible to state that while meta-heuristics perform deep research in the solution area, heuristics reached these results because they only perform a local search.
Keywords:  arc routing problem, hierarchical Chinese postman problem, chance-constrained stochastic programming, fuzzy arc routing problem, stochastic arc routing problem, meta-heuristic algorithms