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

来源：交通运输系统工程与信息杂志2017年第1期北京时间：

作者：彭琨琨，沈吟东

单位：华中科技大学自动化学院，武汉430074

摘要：公共交通乘务调度问题是一个将车辆工作切分为一组合法班次的过程，它是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优于两种新近提出的乘务调度方法，且其结果关于班次数接近于下界.

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

基金资助：国家自然科学基金/National Natural Science Foundation of China（70971044，71171087，71571076）.