CAJ | 학술논문

针对我国城市轨道交通(以下简称城轨)乘务计划编制效率较低的现状，结合城轨乘务劳动作业规定，建立城轨乘务任务划分的RTSCP模型。提出基于列生成思想的乘务任务划分优化算法(CGLR算法)，采用该思想获取小规模较优乘务任务子集合，降低任务划分问题的求解复杂度；采用以最优拉格朗日乘子为启发信息的LR_Heuristic算法取代单纯形算法求解 RTSCP松弛问题，提高算法效率；结合获取的拉格朗日乘子，引入随机列修补技术获取 RTSCP问题的可行解，提高解质量。最后以某地铁线路为背景进行验证。结果表明，模型及算法能有效求解乘务任务划分问题并获得较优的划分方案。
침대아국성시궤도교통(이하간칭성궤)승무계화편제효솔교저적현상，결합성궤승무노동작업규정，건립성궤승무임무화분적RTSCP모형。제출기우렬생성사상적승무임무화분우화산법(CGLR산법)，채용해사상획취소규모교우승무임무자집합，강저임무화분문제적구해복잡도；채용이최우랍격랑일승자위계발신식적LR_Heuristic산법취대단순형산법구해 RTSCP송이문제，제고산법효솔；결합획취적랍격랑일승자，인입수궤렬수보기술획취 RTSCP문제적가행해，제고해질량。최후이모지철선로위배경진행험증。결과표명，모형급산법능유효구해승무임무화분문제병획득교우적화분방안。
In view of the low efficiency of crew scheduling in urban rail traffic in our country and in accordance with the current urban rail transit crew operation rules & regulations,the urban rail transit set covering prob-lem (RTSCP)model was established.On the basis of the idea of column-generation,the column generation and Lagrange-relaxation (CGLR)algorithm was put forward,by which a smaller better-solved sub-set of crew tasks was generated and the complexity of calculation was reduced.In order to enhance the efficiency of solving RTSCP relaxation problems,the LR-Heuristic algorithm using the optimal Lagrange Multiplier as the heuristic information was adopted to replace the generally-used simplex algorithm.With the acquired Lagrange Multipli-er,the stochastic column fixing method was introduced to obtain feasible improved solutions to RTSCP prob-lems.Case study of a certain URT line was made.The results show that the model and algorithm are effective to solve crew pairing problems and to formulate good set covering schemes.