详情

原文传递城市轨道交通乘务排班优化方法

论文题名：	城市轨道交通乘务排班优化方法
关键词：	轨道交通;乘务员排班优化;遗传算法;局部搜索;隐式基因
摘要：	乘务员排班优化问题广泛存在于航空、铁路及城市交通等多个领域，如何合理地进行乘务排班以减少运营中乘务费用支出和提高运营效益一直是交通运输公司面临的重要问题。对我国快速发展的城市轨道交通系统，在给定行车计划表和乘务任务约束条件的基础上，制定适合我国城市轨道交通运输系统的乘务员排班方案，具有很大的应用价值。　　本文提出满足乘务任务约束条件的任务树生成算法，保证乘务员同站点换乘、换乘休息时间、连续工作时间、总休息次数满足乘务任务约束条件。提出一种基于遗传算法的混合启发式算法：设计一种初始种群生成方法，使用迭代启发式搜索策略保证初始种群的优良性，随机生成策略保证初始种群的多样性；选择算子基于轮盘赌策略挑选出不同的双亲个体；交叉算子依据贪婪和随机思想，迭代地构造子代染色体；变异算子应用扰动策略，提高种群多样性。引入隐式基因扩大算法搜索空间、避免算法“早熟”，基因参与进化但在解码时不表达，有效地保存父代的优良基因。采用基于换入换出的邻域变换局部搜索策略提高算法收敛速度，使用多种评价指标和惩罚函数来引导搜索路径和加速种群中个体的进化，提高算法获取全局最优解的能力。　　将所提出算法与目前最好的两个算法（BeCh和Meta_ RaPS）进行比较，实验结果表明：所提出算法在解的质量（ARPD）、算法稳定性（STD）、最优解获取能力（OPT）三个指标上都好于另外两种算法；在运行时间上比Meta_ RaPS少得多，但比BeCh多。因此，所提出的算法可以在离线情况有效地解决城市轨道交通乘务排班优化问题。
作者：	刘帅
专业：	计算机应用技术
导师：	李小平
授予学位：	硕士
授予学位单位：	东南大学
学位年度：	2010
正文语种：	中文