School Bus Routing and Scheduling Based on Branch and Bound Approach

Abstract

The congestion in the traffic is the most basic problem that most of the cities facing now a days because more and more people are moving towards urban areas. As more and more people are moving toward urban areas so the number of schools are increasing and thus number of students travelling through school buses it is required to route and schedule school buses in an optimized manner. This problem is arising in most of the schools in urban cities, most of the parents are complaining about the travelling time and distance student has to travel because of no proper routing and scheduling. Hence, there is a need to find a way of minimizing the students travelling time. If the school buses are not routed and scheduled in an optimized manner it will result in loss of time, resources and money. So from there comes the concept of School Bus Routing and Scheduling Problem (SBRSP). It is a special case of Vehicle Routing Problem and is an NP-Complete problem. So, it is unlikely to get result in polynomial time. So for smaller problems we have given this approach. In this proposed work we have proposed Branch and Bound approach with combination of Hungarian algorithm on Homogenous Bus Fleet. The Branch and bound algorithm provide optimal solution for the smaller problems in polynomial time. In this proposed work we have taken care of several constraints like time window of schools, capacity of buses etc. For a group of schools it will provide an optimal solution that will help those schools to optimize the bus routes, number of buses used and thus optimizing cost. This will also help in reducing pollution as the distance travelled by buses is optimized. The proposed approach has been applied on the input set of data obtained from simulated using our proposed algorithm.