过站保障车辆集中式调度的单亲遗传算法
Centralized Scheduling of Service Vehicles for Aircraft Turnaround Based on Partheno-Genetic Algorithm

针对飞机过站保障车辆集中式调度问题，提出递阶式编码结构单亲遗传算法.该算法采用保障作业编号构成控制基因染色体、车辆编号构成参数基因染色体，分别体现过站保障作业时序约束和车辆指派规则约束，使算法对问题具有良好的适用性；设计控制基因染色体片段段内换位变异和参数基因染色体片段段间换位变异相结合的遗传算子，并引入车辆可调度能力空间概念提出解码算法，实现对解空间搜索能力优化；以过站保障造成的航班延误惩罚费用和车辆行驶费用之和最小为优化目标，建立算法适应度函数，可衡量过站保障和车辆使用综合效率.采集某机场过站航班数据验证所给算法有效性并对比分析车辆就近指派和使用率均衡两种调度策略，结果表明，算法收敛性良好，且就近指派策略相对于使用率均衡策略，在过站保障延误方面改进较小，但在车辆行驶时间方面改进达40%.
：In order to solve the centralized scheduling problem of service vehicles for aircraft turnaround, a partheno-genetic algorithm with hierarchical encoding structure was proposed. The service activity number and vehicle number were employed to encode the control and parametric genes chromosome, respectively, which characterized the temporal and vehicle scheduling rules in turnaround service, ensuring the applicability of algorithm. The crossover and mutation operators were designed, which acted on each control genes chromosome segment and between different parametric genes chromosome segments. The schedulable capacity concept for service vehicle was introduced in chromosome decoding process to optimize search ability of algorithm. The fitness function was established to minimize the penalty of flight delay due to turnaround service and driving distance cost of vehicle, which measured the overall efficiency of turnaround service and vehicle scheduling. The data of aircraft turnaround was used to validate the proposed algorithm, and also the nearest vehicle scheduling strategy and workload balance scheduling strategy were compared. The results indicate that, the convergence of the proposed algorithm is acceptable, and flight delays in these two scheduling strategies are close, while the vehicle driving time is 40% shorter in the nearest vehicle scheduling strategy