Integer programming models for school bus routing problem

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.