Bus rapid transit (BRT) is a cost-efficient, traffic-free bus-based transportation system competing with subways. There are 205 municipalities around the world that implemented their own BRT systems. Istanbul, having the sixth-most congested traffic in the world, built its own BRT system (Metrobus), which serves more than 830,000 people (6.45% of all public transportation usage) in a day with 6254 trips covered by its current fleet of 496 vehicles. In this study, we model the vehicle scheduling problem of Metrobus as a multiple depot vehicle scheduling problem. The model aims to minimize the fleet size and total deadhead kilometers while covering all timetabled trips. We propose a new heuristic, trips merger (TM), to solve the model and show that there exists cost reduction opportunities in terms of both fleet size and deadhead kilometers. The proposed heuristic is a member of the state-space reduction heuristics family, which first reduces the problem size, then solves the reduced problem. Computational study reveals that TM performed better than the existing state-space reduction heuristics for the Metrobus case.