变邻域搜索求解公共交通乘务调度问题

摘要

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 daring 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.%公共交通乘务调度问题是一个将车辆工作切分为一组合法班次的过程,它是NP难问题,许多求解方法的效率都与班次评价密不可分,本文通过裁剪TOPSIS方法(Technique for Order Preference by Similarity to an Ideal Solution)设计了TOPSIS班次评价方法.此外,通过裁剪变邻域搜索算法使之适合求解乘务调度问题,提出了基于变邻域搜索的乘务调度方法(Crew Scheduling Approach Based on Variable Neighbourhood Search,VNS),其中,并入了TOPSIS班次评价方法在调度过程中进行班次评价,设计了两种带概率的复合邻域结构以增加搜索的多样性,帮助跳出局部最优,在VNS中利用模拟退火算法进行局部搜索.利用中国公共交通中的11组实例进行了测试,测试结果表明,VNS优于两种新近提出的乘务调度方法,且其结果关于班次数接近于下界.