Search strategies for the feeder bus network design problem

This paper reports on computing solutions for a specific problem arising in public transport systems – the Feeder Bus Network Design Problem (FBDP). The problem requires the design of a set of feeder bus routes and the definition of their service frequencies to satisfy both the resource constraints and the demand for transportation: passengers located at any of the bus stops wish to go to any of the stations of a rail transit line in order to access a common destination identified as the central station. The objective is to minimize a cost function, where both passenger and operator interests are considered. This problem may be formulated as a difficult, nonlinear and nonconvex mixed integer problem classified as NP-hard. The study focuses on a combined building plus improving heuristic procedure, partially taken from literature. The starting module builds up a solution through a sequential savings or a two-phase method and for the last module the method includes local search as well as tabu search heuristics with different strategies. Additionally, computational results from a set of problems simulating real life situations are given. Through this experiment the authors conclude that the simplest short-term version of tabu search is one of most promising heuristics.