An experimental evaluation of heuristic algorithms for bus-depot matching problem of urban road transport systems

Abstract

This research is motivated by a bus-depot matching problem observed in Urban Road Transport Systems (URTS). In URTS, buses are parked overnight at depots. Starting points of routes are usually different from depot locations. A bus has to cover the distance from its depot to the starting point of its route before being engaged on regular service. Likewise, buses usually do not provide service to the depot at the end of the service period. The distance travelled by a bus in a day from a depot to a starting terminus and/or from the ending or last terminus back to the depot without carrying passengers is known as 'dead kilometers'. The dead kilometers can be reduced by efficiently allocating the buses to depots. In the literature this problem is solved using mathematical model and heuristic algorithms. However, there is no detailed computational analysis to highlight the merits and demerits of various solution methodologies, so far addressed in the literature. In this study a set of heuristic algorithms are considered to make an efficient decisions in buses-depots matching problem. A computational experiment is carried out to understand the efficiency of the heuristic algorithms considered in this study for various large size problems in comparison with exact solutions. From the computational analysis, two out of the five heuristic algorithms considered in this study, resulted very close to exact solutions in most of the problem instances. All the heuristic algorithms considered in this study takes very meager computational time in Pentium IV for the large size problem of 30 depots and 5,031 buses considered in this study. Operational Research Society of India 2011.