城轨线路全日车底空驶出入场路径及时刻表综合优化

Integrated optimization of daily depot deadhead routes and timetables for rolling stocks in an urban rail transit line

城轨线路车底在出入场时需在其车场与其担当车底交路始发/终到站间空驶,优化全日车底空驶出入场方案(含始发和终到车场,出入场路径和时刻表)对降低车底空驶距离和时间,节省运营成本具有重要作用.本文针对具有多车场和多折返站的城轨线路,基于广义集合划分构建大规模0-1线性规划模型,综合优化担当给定车底交路所需车底的空驶出入场方案.结合模型特点,设计行列生成算法高效求解模型.对某布置复杂且繁忙城轨线路开展实例分析,验证算法有效性和实用性.结果表明,所提出算法可在合理时间(2小时)内获得紧致下界和接近最优解(相对误差小于1%),且在求解质量和计算时间上均优于现场经验方法.

Rolling stocks in an urban rail transit line should cover the deadhead distance between depots and the origin and destination stations of their served rolling stock routes,during their depot deadhead exiting and entering operations.Optimizing the rolling stock depot deadhead plan(including origin and destination depots,depot deadhead exiting and entering routes and timetables)is of great significance to reduce the deadhead distance and running time of rolling stocks,and to save operation cost.By means of generalized set partitioning,the studied problem,derived from an urban rail transit line with multiple depots and turn-back stations,is formulated as a large-scale 0-1 integer linear programming model.By exploiting the characteristics of the model,a row and column generation-based algorithm is developed to solve the model efficiently,respectively.A real-world case study from a complicated and busy urban rail transit line is conducted to verify the effectiveness and practicability of the proposed algorithm.Computational results demonstrate that our algorithm can compute a tight lower bound and a near-optimal solution(with a relative gap less than 1%)within a reasonable computation time(less than 2 h),and it is superior to the empirical method in practice in terms of both solution quality and computation time.