关键词: 城市交通, 乘务调度, 变邻域搜索, 复合邻域结构, 班次评价

Abstract:

Public transport crew scheduling is a process of partitioning blocks of vehicle work into a set of legal shifts, which is NP hard. The efficiency of many solving approaches is closely related to shift evaluation. In this paper, a TOPSIS shift evaluation method is proposed by tailoring TOPSIS (Technique for Order Preference by Similarity to an Ideal Solution). Moreover, a crew scheduling approach based on Variable Neighbourhood Search (VNS) is presented, which tailors Variable Neighbourhood Search to sovle crew scheduling problem. In the VNS, the TOPSIS shift evaluation method is embedded to serve for shift evaluation during the scheduling process, and two compound neighbourhood structures with probability are designed, which considerably enhances search diversification and helps to escape from local minima. In addition, Simulated Annealing is employed for local search in the VNS. Computational experiments bases on 11 real- world crew scheduling problems in China show that the VNS outperforms two recently proposed solving approaches, and achieves results close to the lower bounds in terms of shift number.

Key words: urban traffic, crew scheduling, variable neighbourhood search, compound neighbourhood structure, shift evaluation