关键词: 城市交通, 乘务资源共享, 列生成法, 乘务排班计划, 网络图模型

Abstract:

This study aims to address a crew scheduling problem with shared crew members and bases among different lines without considering cross- line trains. Through the analysis on crew resources sharing, a new set covering model for the crew scheduling problem is proposed. Three crucial elements are covered in this model, including the across- line duties, proportion of shifts with different starting and ending locations, and robustness optimization. However, the scale of problem increases dramatically due to the collaborative optimization of shifts among different lines. A network model is developed where consecutive tasks executed by the same train are served as the minimum duty unit. Several improvements are made to satisfy the feasibility constraints of shifts including employing multilayer structure, multilevel source and sink nodes as well as cross-line meal and rest arcs. Furthermore, networks are generated into some sets corresponding to different starting and ending locations. A column generation algorithm is then designed in which the pricing problem is converted into the shortest path problems base on each network set. The experimental results indicate that the crew resources sharing can provide more choice for drivers to select a preferred location when they start and end their daily work. It also significantly reduces the commuting time. Besides, crew resources sharing is able to decrease the shift number by a little and improve the efficiency of crew scheduling.

Key words: urban traffic, crew resources sharing, column generation, crew scheduling, network model