基于时间耗费的城市轨道交通乘务排班优化

Optimization of Crew Scheduling for Urban Rail Transportation Based on Time Costs

乘务排班问题一直是城市轨道交通运营部门面临的既关键又具体的问题之一,合理的排班对于减少运营中乘务费用支出,提高运营效益有着极其重要的意义。文中以上海城市轨道交通为背景,研究了城市轨道交通乘务排班软件中的优化方法。在以总时间耗费最小实现多目标优化的基础上,将优化过程分为两步,首先对列车运行线在乘务换乘点上划分为乘务作业段,这个过程归结为一个径路选择问题,通过最短路算法实现。然后将划分好的乘务作业段组合成乘务任务,这个过程是一个匹配问题,通过最小费用最大流算法来实现。本文对乘务作业段的定义与划分、时间耗费的计算及整个排班计算的实现过程进行了详细阐述。

Crew scheduling is one of the important and concrete problems facing the management of urban rail transportation. Reasonable crew scheduling is significant in reducing crew expenses and raising operation profits. This paper studies optimization of the crew scheduling software against the background of Shanghai urban rail transit. The optimizing course is decomposed into two stages on the basis of minimizing the total time cost and realizing multiple optimization objectives. First, cutting the runs into segments which are referred to as pieces, one segment assigned to one single driver. This stage is formulated as a pathing problem simplified with the shortest paths computations. Second, integrating the pieces to form duties. This stage is formulated as a matching problem solved by the min-cost max-flow algorithm. Defining and cutting of work-pieces, calculation of time costs and the process of total scheduling are detailed.