基于惩罚费用的城市轨道交通乘务排班优化模型与算法

Urban Rail Transit Crew Scheduling Model and Algorithm Based on Punishment Costs

乘务排班计划是城市轨道交通运营的核心问题之一.本文首先分析了乘务排班问题,接着基于惩罚费用构建了乘务排班优化模型,并提出了相应惩罚费用计算方法.根据乘务排班计划步骤可知,模型分为乘务作业段生成模型和乘务工作班生成模型,其中乘务作业段生成模型为乘务工作班生成模型的下层,乘务作业段生成模型的解为乘务工作班生成模型的输入条件.随后针对建立的双层模型,分别设计了改进的Dijkstra算法和离散粒子群算法.最后,采用某地铁线路的运行数据对模型和算法进行了验证.结果表明,间休时间的均值为37分,工作时间的均值为6小时41分,并且所有的乘务工作班分布均匀,证明了模型与算法的有效性.

Crew scheduling is one of the core issues of urban rail transit operations.This paper develops an optimization model of crew scheduling based on punishment costs,and proposes corresponding punishment cost calculation method.From the process of crew scheduling,it is found that the models include a crew operating segment generation model and a crew work shift generation model.The crew operating segment generation model is the lower model,and its results are the inputs of crew work shift generation model.Then,for the double-layer model,the paper formulates the improved Dijkstra algorithm and discrete particle swarm optimization.Finally,a subway line＇ s operational data are used to validate the model and algorithms.The results show that the average rest time is 37 minutes,the average working time is 6 hours 41 minutes,and the crew work shifts are uniformly distributed.All of these demonstrate the effectiveness of the models and its algorithms.