A tabu search approach to an urban transport problem in northern Spain

In this work we analyze an urban transport problem that the City Council of Burgos, a city in northern Spain, has posed to the authors. Given a fleet of buses and drivers, the problem consists in designing routes and assigning buses to the routes such that the service level is optimized. The optimality of the service level is measured in terms of the waiting time at the bus stops and the duration of the trip. Thus, the problem comprises two decision levels (route design and bus assignment) and differs from other urban transport models found in the literature. In order to solve the problem, we propose two algorithms: one with a local search strategy and another with a tabu search strategy. In both cases, the solutions of the two decision levels are modified in alternating steps. The proposed algorithms obtained significantly better results than the tools currently applied by the transport authorities. In addition, the solutions obtained are very robust with respect to variations on demand, as shown by the experiments.