详情

原文传递基于智能优化的乘务调度与轮班问题研究

论文题名：	基于智能优化的乘务调度与轮班问题研究
关键词：	公共交通;乘务调度;乘务轮班;智能优化方法;班次评价;多属性决策方法
摘要：	随着我国城市化和机动化进程迅猛发展，道路拥堵等问题日益严重，城市交通面临严峻挑战，优先发展公共交通势在必行，如何建设和管理现代化的公共交通系统已成为我国经济社会发展中亟待解决的重大理论和现实问题。在公共交通规划与运营中，乘务调度与轮班问题是关键问题，决定了乘务员的工作方案，有效方案可以提高公共交通运营效率，降低运营成本，保障乘务员真正享受国家劳动法赋予的权益。它包含两个顺序执行的子问题：乘务调度问题和乘务轮班问题，其中前者是后者的基础，它们是 NP难问题，其复杂性主要在于大规模、多目标、特别是有一系列复杂多样的劳动法规约束。因此，研制高效的求解算法具有十分重要的现实意义和理论意义。目前，智能优化方法是主要求解方法类别之一，但是问题的高度复杂性使得对该类算法的研究仍有很大发展空间，其中，深刻理解问题的领域知识并将其融入算法设计中是算法设计的关键和难点，需要深入研究。此外，乘务调度问题中的班次评价是一个复杂多属性决策问题，是很多乘务调度方法的基础，然而现有的多属性决策班次评价方法研究很少。　　针对以上问题，本文首先从不同角度研制了四种乘务调度方法，其中，研制了两种多属性决策班次评价方法，随后研制了两种多目标乘务轮班方法，具体如下：　　提出了一种自适应演化乘务调度方法，它定义了一个新的染色体表示方法，具有直观、短小，允许表达非可行乘务方案的特点，其初始长度是专门设计为最优班次总数的下界，有助于保证和分析解的质量，设计了带增补和删除策略的交叉和变异操作，使得染色体长度能够在算法迭代过程中自适应地增大或减小，实验表明算法的计算速度快、求解质量高。　　提出了灰关联分析（Grey Relational Analysis，GRA）班次评价方法。为了确定GRA班次评价方法中的最优参数，进一步提出了一种基于GRA的演化乘务调度算法（Evolutionary crew scheduling algorithm based on GRA，EGRA），最优调度方案会随着这些参数相应得到。EGRA是一种专门设计的嵌入快速局部搜索的混合遗传算法，其中的局部搜索是精致设计的，用以提升算法的集中性，实验测试说明了EGRA的优越性。　　提出了基于 GRA的变迭代贪婪乘务调度方法（Variable Iterated Greedy crew scheduling approach based on GRA，GRAVIG），GRAVIG裁剪了变迭代贪婪算法（Variable Iterated Greedy，VIG）求解乘务调度问题，其中嵌入了GRA班次评价方法作为调度过程中班次评价的求解器，较大地提升了VIG的搜索能力，此外，还精心设计了一种基于偏向概率的破坏阶段，它能够使得“好的”班次可以保留在方案中，同时又不丢失随机性。实验测试结果表明该方法是有效的。　　提出了逼近理想解排序（TOPSIS）班次评价方法。同时设计了变邻域搜索乘务调度方法（Variable Neighbourhood Search crew scheduling approach，VNS），VNS裁剪了变邻域搜索算法求解乘务调度问题，其中，设计了两种带概率的复合邻域结构，极大地增大了搜索空间的多样性。在VNS中嵌入了TOPSIS方法以作为调度过程中班次评价的求解器，较大地提升了VNS的搜索能力，在VNS中还嵌入了模拟退火算法（Simulated Annealing，SA）以进行有效的局部探索，最后实验测试结果表明方法的有效性。　　提出了两种多目标乘务轮班方法，即模拟退火乘务轮班方法（Multi-Objective SA crew rostering approach，MOSA）和变邻域搜索乘务轮班方法（multi-objective Variable Neighbourhood Search crew rostering approach，VNS），它们使用了两种评价接受函数来更好地处理用户偏好。在MOSA中，首先设计了一个启发式来构建初始解，接着设计了一个基于SA的可行性修复算法来使该解可行，最后，设计了一个基于SA的非支配解生成算法来获得非支配解。其中，设计了增量评价策略，邻域切割技术和偏向精英解重启策略以分别提升计算速度和搜索能力；在VNS中设计了两种复合邻域结构，每一个分别对应一个目标，它们在VNS中依次执行，在每个邻域结构中以 SA作为局部搜索的求解器，此外，还专门设计了一种解的改进接受准则以提升VNS的搜索能力。最后实验结果说明了这些方法的有效性。
作者：	彭琨琨
专业：	控制科学与工程
导师：	沈吟东
授予学位：	博士
授予学位单位：	华中科技大学
学位年度：	2016
正文语种：	中文