Özet: Kombinatoryal eniyileme problemleri, yöneylem araştırması alanında en çok çalışılan problem tipidir ve büyük bir kısmı NP-Zor'dur. Araç Rotalama Problemi (ARP) de kombinatoryal eniyileme problemi grubuna girmektedir. Problemin gerçek hayattaki uzantılarından biri "Okul Taşıtları Rotalama Problemi (OTRP)"dir. OTRP; enküçük toplam işletim maliyetiyle, öğrencilerin belirli toplama noktalarından alınması ve okula bırakılması veya öğrencilerin okuldan alınarak, alındıkları yerlere bırakılması problemidir. Uygulamada farklı durumların ortaya çıkması, problemin çok boyutlu düşünülmesini gerekli kılmıştır. Bu tez kapsamında gerçek hayatta en çok karşılaşılan durum belirlenmiş ve onun üzerinde çalışılmıştır. Bilgisayar teknolojisindeki hızlı gelişme, matematiksel modellerin garanti ettiği kesin çözümlerin kolay ve etkin bir şekilde bulunabileceği izlenimini vermiştir. Bundan dolayı problemin çözümü için matematiksel karar modelleri üzerinde çalışılmıştır. Tez kapsamında, probleme karsı gelen serimin simetrik olamayacağı göz önüne alınmıştır ve modelleme sabah (toplama) ve öğlen (dağıtım) olmak üzere iki alt baslıkta incelenmiştir. Çalışmada OTRP için polinom boyutta yeni geliştirilen ikisi düğüm tabanlı, ikisi akış tabanlı dört tamsayılı karar modeli tanıtılmıştır. İlgili kütüphanelerde yer alan OTRP problemleri ve rassal olarak üretilen problemler dört modelle de çözdürülerek, çözüm süreleri ve doğrusal programlama gevşetilmiş değerleri üzerinden karsılaştırmalı analizler yapılmıştır. Yapılan analizler sonucunda, gelişen teknolojik ilerlemeye bağlı olarak modelleme üzerine çalışmayı destekleyebilecek sonuçlara varılmıştır.

Abstract: Combinatorial optimization problems are the most widely studied problems in Operations Research literature and generally they are NP-Hard. Vehicle Routing Problems (VRP) are also classified in Combinatorial Optimization Problems. School Bus Routing Problem is a special type of Vehicle Routing Problems and also an NP-Hard problem. School Bus Routing Problem (SBRP) is the problem of picking students from defined points and taking them to school and/or vice versa with minimum transportation costs. Several approaches are used in solving SBRP depending on the situation which is being observed. In this study, the situation which researchers can most likely come across in real life is identified and/or examined. Rapid improvement in computing technology has showed that exact solutions for mathematical models can be found. As a matter of this fact, mathematical decision models have been examined in order to solve problems. In this study, the network is assumed as an asymmetric. Two node based decision models and two flow based decision models are introduced. Formulations have been made by considering two situations which are named as "Morning" and "Noon". Test problems were taken from the literature as well as generated randomly. Thereafter, these problems were solved by using four models which are introduced in this study. All solutions are then analyzed comparatively in terms of computation times and LP relaxation values. Finally, conclusions are made to guide future studies.