Research On Modeling And Algorithm For Track Geometry Car Routing Problem On The Urban Subway With Network Operation Condition

Subway makes great contributions to relieving urban traffic congestion with its advantages of low cost,large capacity and high speed.The operating mileage of subway in our country is continuously increasing and some metropolises have entered the era of subway network operation.The rapid development of urban subway has put forward higher requirement for the safe operation of subway train.However,the tracks with defect would bring hidden dangers to the driving safety.Therefore,track condition measurement,which aims at obtaining the information of track condition and arranging maintenance plans timely,is an important task for the subway maintenance-of-way departments.The track geometry car is used to measure track geometry parameters.This paper studies the track geometry car routing problem(hereinafter referred to as TGCRP).The inspection cost and inspection date interval consistency of each line during a planning horizon are two objectives when routing a track geometry car.On the basis of fully investigating the operating conditions of the subway track geometry car,a specific problem description of TGCRP is given: searching for a suboptimal inspection schedule with minimal total mileage on condition that starting and ending constraint,track window constraint,garage constraint,connectivity constraint,integrity constraint,and temporal consistency constraint are satisfied.Then a mathematical model for TGCRP is built.The capacitated arc routing problem(CARP)and its variant,periodic capacitated arc routing problem(PCARP),are introduced as the basic theories of TGCRP,which indicates TGCRP is a NP-hard problem and a distinguishable problem at the same time.This paper adopts a two-stage solving strategy.In the first stage,the genetic and simulated annealing hybrid heuristic algorithm is used to search the single objective optimal solutions,and some suboptimal solutions with optimal mileage and optimal temporal consistency level are obtained respectively.In the second stage,NSGA-? algorithm is used to search for the Pareto frontier of TGCRP model.A more satisfactory Pareto frontier can be found by adding the suboptimal solutions in the first stage to the initial population of NSGA-? algorithm.The proposed algorithm is applied to Beijing Subway network having for two months the total track mileage of 877.260 km inspected through one track geometry car.The schedule currently adopted in practice instructs Beijing Subway's track geometry car to run a dead mileage of 601.180 km and to inspect tracks at inconsistent time intervals for 38 days.The schedule attained via the proposed algorithm can save a dead mileage of 281.816 km(46.7%)and 6 days,and the inspection temporal consistency level can be reduced by 77.8%(0.14).Figure 27,table 11,reference 69.