The transit network design problem: An AI-based approach

Standard Operations Research optimization approaches have not been successful in the solution of practical public transport network design problems. The problem is combinatorial in nature and presents several sources of non-linearities and non-convexities which preclude guaranteed optimal solution algorithms. We define the above problem, present a typical mathematical formulation of it, and review the past approaches. A solution methodology that relies on AI heuristics and search techniques in addition to domain-specific human knowledge and expertise is presented. Such solution employs three major components: (1) an AI-based route generation design algorithm, (2) an analysis procedure that generates all necessary performance measures and descriptors, particularly on the demand side, and (3) an AI-based route improvement algorithm that suggests modifications to the already generated sets of routes. The route generation algorithm is a design algorithm that is: (1) heavily guided by the transit demand matrix, (2) allows the designer's knowledge to be implemented so as to reduce the search space, and (3) generates different sets of routes corresponding to different tradeoffs between user costs and operator resources and performance measures reflecting the quality of service of the transit network. We test the solution approach on an existing benchmark problem as well as data derived from the transit system of the city of Austin, Texas, U.S.A.