A variable neighbourhood search algorithm for a demand-responsive bus system with capacitated vehicles

Abstract

In this study, we design a metaheuristic algorithm for a demand-responsive public bus system operating during peak hours with capacitated vehicles. Morning peak hours are considered where the passenger flows towards a city center are typically much larger than the flows in the opposite direction. A single-line system with express services away from the city center is optimized. Based on the expected demand, it is decided whether a bus should visit all the stops ahead or take the express route away from the city center to increase the frequency of the service towards the city center. Due to problem complexity, only small-sized instances can be solved optimally. Therefore, a metaheuristic algorithm is proposed based on Variable Neighborhood Search. The results show that the demand-responsive system can improve the average passenger travel time up to 25% compared to the conventional system especially if limited vehicle capacities need to be considered.