Meta-heuristics for a class of demand-responsive transit systems

The demand-adaptive systems studied in this paper attempt to offer demand-responsive services within the framework of traditional scheduled bus transportation: Users call to request service between two given points and, in so doing, induce detours in the vehicle routes; at the same time, though, a given set of compulsory stops is always served according to a predefined schedule, regardless of the current set of active requests. The model developed to select requests and determine the routing of the vehicle yields a difficult formulation but with a special structure that may be used to develop efficient algorithms. In this paper, we develop, test, and compare several solution strategies for the single line–single vehicle problem that belong to two general metaheuristic classes, memory-enhanced greedy randomized multistart constructive procedures, and tabu search methods. Hybrid meta-heuristics combining the two methods are also analyzed.