Dinamik okul servisi rotalama probleminin sezgisel yöntemler ve kümeleme teknikleri kullanılarak gerçek zamanlı optimizasyonu
The real-time optimization of dynamic school bus routing problem by using heuristic methods and clustering techniques
Yazar: ÖZKAN ÜNSAL
Danışman: PROF. DR. TUNCAY YİĞİT
Süleyman Demirel Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2017
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Araç yönlendirme problemi = Vehicle routing problem ; Dinamik optimizasyon = Dynamic optimization ; Metasezgiseller = Metaheuristics ; Yapay zeka = Artificial intelligence

Özet:
Ulaşım ve dağıtım sistemleri teknolojinin ilerlemesi ile hayatın her alanında oldukça yoğun bir kullanıma sahiptir. Bu sistemlerin giderek artan karmaşık yapısı ve yoğun kullanımından kaynaklanan maliyet, iş gücü, çevre kirliliği, trafik vb. problemler nedeni ile profesyonelce yönetilmesi kaçınılmaz hale gelmiştir. Araç rotalama problemleri (ARP) birçok farklı uygulama alanı bulunan ve çözümü klasik yöntemlerle mümkün olmayan karmaşık problemlerdir. 
Günümüzde okul servis taşımacılığı, okula başlama yaşının düşmesi, okul ile ev arasındaki mesafelerin artması, güvenli ve hızlı ulaşım gibi özellikleri sayesinde veliler tarafından diğer ulaşım araçlarına göre özellikle de trafiğin yoğun olduğu büyük şehirlerde daha yoğun bir şekilde tercih edilmektedir. ARP'nin bir alt türü olan Okul Servis Rotalama Problemi (OSRP) durakların araçlara dağıtımı ve araçların izleyecekleri yolun belirlenmesi şeklinde iki aşamadan oluşmaktadır. OSRP, bir servis aracının en uygun sürede, en kısa rotayı izleyerek listesinde bulunan duraklardan öğrencileri toplayıp okula götürmesini ve okulda toplanan öğrencileri evlerine bırakmasını amaçlar. Servis araçlarının rota seçimlerini optimum bir şekilde gerçekleştirmeleri önemli yakıt ve zaman tasarrufu sağlamaktadır. Karmaşık yapısı nedeniyle OSRP'nin çözümünde metasezgisel yöntemlere ihtiyaç duyulmaktadır. Küresel konumlama sistemi (GPS), coğrafi bilgi sistemleri (GIS), mobil iletişim ağları, trafik sensörleri gibi alanlarda yaşanan teknolojik gelişmeler sayesinde bu problemlerin gerçek zamanlı olarak dinamik bir şekilde çözülmesi mümkün olmuştur.
Bu tez çalışmasında, OSRP'nin optimizasyonu amaçlanmıştır. Çalışmanın bölümlerinde ARP ve OSRP detaylı bir şekilde incelenmiş, problemler ve geliştirilen çözüm yöntemleri ile ilgili literatüre yer verilmiştir. OSRP'nin dinamik bir şekilde çözümü için kümeleme teknikleri ve metasezgisel yöntemler kullanılarak, GPS, GIS araçları ve mobil uygulama desteği ile bir yazılım geliştirilmiştir. Geliştirilen yazılım Ankara ilinde hizmet veren servis firmalarından toplanan rota verileri üzerinde uygulanmıştır. Elde edilen deneysel sonuçlar, geliştirilen yöntemin, mesafe, zaman ve rakım değişimi parametreleri açısından rotaları başarılı bir şekilde iyileştirilebileceğini göstermiştir. Çalışmanın trafik, hava kirliliği sorunlarının çözümü ile araç bakım giderleri ve yakıt tüketim maliyetlerinin azaltılmasında ülke ekonomisine yarar sağlayacağı düşünülmektedir.

Abstract:
Transportation and distribution systems have quite a common use in all fields of life thanks to the advancements in technology, as well. Due to the problems that resulted from the intensive use and the structure of these systems that increasingly become more complex, such as the cost of the labor force, environmental pollution, and traffic, their professional management has become unavoidable. Vehicle routing problems (VRP) are complicated problems, which can be encountered in a variety of different fields and are not possible to solve using classical methods.
Today, school bus transportation is widely preferred by parents due to reasons such as lower schooling age, increase in the distance between the school and home, and safe and fast transportation compared to other means of transport especially in greater cities with high density of traffic. The school bus routing problem (SBRP), which is a sub-branch of VRPs, consists of two phases in the form of distribution of bus stops to the vehicles and routing. The SBRP aims to determine the shortest route in optimal time for a school bus to pick up all the students and to take them to school, and to pick the students up from school and leave them at their houses. Optimized route selection for school bus vehicles provides significant fuel and time savings. Metaheuristic methods are needed for the solution to SBRP because of the complex structure of the problem. Thanks to the technological advancements in areas such as the global positioning system (GPS), geographical information systems (GIS), mobile communication networks, and traffic sensors, it is now possible to solve the SBRP in a dynamic and real-time manner.
In this thesis study, optimization of SBRP is aimed. In the sections of the study, VRP and SBRP have been studied in detail, and the literature on the problems and developed solution methods have been given. Using clustering techniques and metaheuristic methods a software has been developed with the support of GPS, GIS tools and mobile application for the solution of SBRP dynamically. The developed software has been applied on the route data collected from school service companies which are in the province of Ankara. The obtained experimental results have showed that the developed method can successfully optimize the school bus routes in terms of distance, time and altitude change parameters. It is thought that the study will provide benefit on the country's economy in reducing traffic, air pollution problems, costs of vehicle maintenance and fuel consumption.