含时间窗的司售员调度模型及多邻域结构设计

Model for crew scheduling with time windows and multi-neighborhood structures

形式化定义了司售员调度中的关键因素:车辆运营工作、调度方案、劳动法规和调度目标,建立了一个能够准确反映实际问题的模型.设计出能够有效处理时间窗的多邻域结构,为应用基于邻域搜索的各种算法求解该模型奠定了基础.最后将其应用于基于禁忌搜索的构造式方法——启发式自动司售员调度(HACS)中.实验表明:应用该模型及多领域结构改进了HACS,有效解决了含时间窗的司售员调度问题并得到更优解,对大规模问题,解的改进更加明显.

A model which can accurately reflect the real crew scheduling problem was established by defining exactly the following key factors, vehicle work, crew schedule, labor agreement rules and objectives. Based on the model, multi-neighborhood structures were designed, which could be applied by various neighborhood search approaches to solve the crew scheduling problem with time-windows. Applying them to the heuristics for automatic crew scheduling （HACS）, an enhanced tabu search based approach was developed. Experiments showed that the enhanced approach can handle time-win- dows, and its results better than HACS. For large problem instances, the improvement is more obvious by taking the advantages of time-windows.