Zaman-bağımlı hiyerarşik Çinli postacı problemi ve çözüm önerileri
A time-dependent hierarchical Chinese postman problem and solution proposals
Yazar: MERVE KAYACI ÇODUR
Danışman: DR. ÖĞR. ÜYESİ MUSTAFA YILMAZ
Atatürk Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Doktora, 2018
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Hiyerarşik Çinli Postacı Problemi (HÇPP), ayrıt rotalama problemlerinden biri olan Çinli Postacı Probleminin (ÇPP) bir türüdür. NP-zor problem olan HÇPP ile ilgili yapılan çalışmalarda düğümler arası mesafelerin dikkate alındığı ve seyahat sürelerinin göz ardı edildiği görülmektedir. Ancak, hemen hemen tüm metropol kentlerde seyahat eden araçların hızı ve buna bağlı olarak da ulaşım süreleri trafik yoğunluğu, trafik kazaları ve hava durumu gibi çeşitli faktörlerden dolayı katedilen mesafe ile birlikte gün boyunca değişmektedir. Dolayısıyla, sokaklarda minimum zaman harcayarak seyahat etmek, özelikle kar küreme, çöp toplama ve devriye gezen güvenlik araçlarının rotalanması gibi HÇPP'nin pratikteki birçok uygulama alanında yol güvenliğinin ve trafik akışının sağlanması açısından büyük önem arz etmektedir. Bu çalışmada Zaman-Bağımlı Hiyerarşik Çinli Postacı Problemi (ZB-HÇPP) olarak adlandırılan ve toplam seyahat süresini en aza indirmeyi amaçlayan yeni bir problem türü ele alınmıştır. Problemin çözümüne yönelik ilk olarak, toplam katedilen mesafe ve toplam harcanan seyahat süresinin en küçüklenmesini amaçlayan karma tamsayılı matematiksel programlama modelleri geliştirilmiştir. Ayrıca tanımlanan problemin büyük boyutlu problemlerde çözülebilmesi için iki meta-sezgisel algoritma önerilmiştir. Bunlar: Genetik Algoritma (GA) ve hibrit Tavlama Benzetimidir (hTB). Önerilen matematiksel modeller ve meta-sezgisel algoritmalar rasgele oluşturulmuş test problemleri üzerinde incelenerek etkinlikleri gösterilmiştir. Bu çalışma kapsamında matematiksel modeller GAMS 24.2.3'te Cplex 12 karma tam sayılı programlama çözücüsü kullanılarak çözülmüş, meta-sezgisel algoritmalar ise Matlab 2016a programlama dili kullanılarak kodlanmış ve sonuçları raporlanmıştır.

Abstract:
The Hierarchical Chinese Postman Problem (HCPP) is a type of the Chinese Postman Problem (CPP) which is one of the arc routing problems. It is seen that the distances between the nodes are taken into consideration and the travel times are ignored in the studies about HCPP which is NP-hard problem. However the speed (and time) of the vehicles traversing in almost all metropolitan areas changes during the day due to a variety of different factors such as peak traffic hours, traffic accidents and weather condition along with the distance. For this reason, travelling on the streets by spending minimum time is of great importance in terms of ensuring road safety and traffic flow particularly in many practical implementation areas of HCPP, such as routing of snow plowing, garbage collection and security patrol vehicles. In this study, a new problem type called the Time-Dependent Hierarchical Chinese Postman Problem (TD-HCPP) that aims to minimize the total travel time is introduced. Firstly, mixed integer mathematical models have been developed to minimize total traveled distance and total traveled time. For the large scale problems two meta-heuristics were proposed. These are: Genetic Algorithm (GA) and hybrid Simulated Annealing (hSA). The proposed models and meta-heuristics were tested on randomly generated problem instances and the effectiveness of these models and algorithms were shown. In this study, mathematical models are solved by Cplex 12 mixed integer programming solver in GAMS 24.2.3, meta-heuristic algorithms are coded in Matlab 2016a programming language and results are reported.