Okul taşıtları rotalama problemi için tamsayılı karar modelleri

Abstract

Okul Taşıtları Rotalama Problemi için Tamsayılı Karar ModelleriKombinatoryal 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. Problemingerçek hayattaki uzantılarından biri ?Okul Tasıtları Rotalama Problemi (OTRP)?dir.OTRP; enküçük toplam işletim maliyetiyle, öğrencilerin belirli toplamanoktaları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ındagerçek hayatta en çok karşılasılan durum belirlenmiş ve onun üzerindeçalışılmıstır.Bilgisayar teknolojisindeki hızlı gelişme, matematiksel modellerin garantiettiğ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ıstır. Tez kapsamında, probleme karşı 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 başlıkta incelenmiştir. Çalışmada OTRP için polinom boyutta yenigeliştirilen ikisi dügüm tabanlı, ikisi akış tabanlı dört tamsayılı karar modelitanı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ğrusalprogramlama gevşetilmis degerleri üzerinden karşılaştırmalı analizler yapılmıstır.Yapılan analizler sonucunda, gelişen teknolojik ilerlemeye bağlı olarak modellemeüzerine çalışmayı destekleyebilecek sonuçlara varılmıstır.

Integer Programming Models for School Bus Routing ProblemCombinatorial optimization problems are the most widely studied problems inOperations Research literature and generally they are NP-Hard. Vehicle RoutingProblems (VRP) are also classified in Combinatorial Optimization Problems.School Bus Routing Problem is a special type of Vehicle Routing Problems andalso an NP-Hard problem. School Bus Routing Problem (SBRP) is the problem ofpicking students from defined points and taking them to school and/or vice versawith minimum transportation costs. Several approaches are used in solving SBRPdepending on the situation which is being observed. In this study, the situationwhich researchers can most likely come across in real life is identified and/orexamined.Rapid improvement in computing technology has showed that exact solutions formathematical models can be found. As a matter of this fact, mathematical decisionmodels have been examined in order to solve problems. In this study, the networkis assumed as an asymmetric. Two node based decision models and two flowbased decision models are introduced. Formulations have been made byconsidering two situations which are named as ?Morning? and ?Noon?. Testproblems were taken from the literature as well as generated randomly.Thereafter, these problems were solved by using four models which areintroduced in this study. All solutions are then analyzed comparatively in terms ofcomputation times and LP relaxation values. Finally, conclusions are made toguide future studies.