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

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

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

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-windows,and its results better than HACS.For large problem instances,the improvement is more obvious by taking the advantages of time-windows.