Recursive Hybrid Heuristic Algorithm for Routing a Track-Geometry Car through a Large-Scale Urban Subway Network

Abstract

Rail track inspection is essential to urban rail infrastructure management in terms of safety. The track geometry car is one of the important inspection vehicles for track condition measurement. Routing a track geometry car on a large-scale subway network has two objectives: inspection cost and inspection time interval consistency of each line during one planning horizon. An optimization model is developed to route a track geometry car on a large-scale subway network. Because of the model’s nondeterministic polynomial time (NP)-hardness, a recursive hybrid heuristic algorithm using a novel double-layer chromosome genetic algorithm as the global search strategy and a simulated annealing algorithm as the local search strategy are proposed to attain suboptimal inspection schedules. The proposed algorithm is applied to the Beijing subway network for two months, and the 877.260-km track mileage was inspected through one track geometry car. The schedule currently adopted in practice instructs Beijing subway’s track geometry car to complete all prescribed inspections at inconsistent time intervals in 23 days with a dead mileage of 601.180 km. The schedule attained via the proposed algorithm routes the track geometry car to inspect all tracks at consistent time intervals and saves 301.806-km of dead mileage (50.2%) and five days.