基于列生成技术的乘务调度问题研究

《基于列生成技术的乘务调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号学号D200977449学校代码10487密级博士学位论文基于列生成技术的乘务调度问题研究学位申请人：陈仕军学科专业：系统分析与集成指导教师：沈吟东教授答辩日期：2014年03月17日万方数据万方数据ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinScienceColumnGenerationBasedApproachesforSolvingCrewSch

2、edulingProblemsPh.D.Candidate：ChenShijunMajor：SystemsAnalysisandIntegrationSupervisor：Prof.ShenYindongHuazhongUniversityofScienceandTechnologyWuhan,Hubei,430074,P.R.ChinaMarch,2014万方数据万方数据独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本

3、论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在___

4、__年解密后适用本授权书。本论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日万方数据万方数据华中科技大学博士学位论文摘要乘务调度问题是指在满足各种劳动法规和实际约束的条件下，将给定的车辆任务集进行切分和组合，形成一组乘务员可执行的班次集，并使得班次总成本（总数或总工时）最小化。该问题是公交运营管理与规划的核心问题之一，有效的乘务调度方法对提高公交运营效率和降低人力资源成本具有重要意义。目前，解决乘务调度问题存在着两个方面的难题。一方面，乘务调度问

5、题是NP难问题，研究大规模乘务调度问题的求解方法一直是公交调度与组合优化领域的热点和难点之一。目前，传统整数线性规划（ILP）方法、元启发式方法（遗传算法、禁忌搜索等）和以列生成技术为主的数学规划方法是求解该问题的主要方法。传统ILP方法受变量和约束数量的限制，求解能力有限；元启发式方法相对求解速度快，但难以保证解的最优性；列生成法不受问题规模的限制，且能够求得次优解甚至最优解，但具有收敛速度慢的缺点。另一方面，常用的乘务调度模型（如集覆盖模型）过于理想化，其求解结果在实际应用时，时常不能满足运营

6、企业的实际要求和期望，具有一定的局限性。为了克服上述难题，本文对大规模乘务调度问题的快速求解方法和更一般化的乘务调度模型两方面进行了研究。首先，提出了基于问题特征与缩减问题规模的方法，以处理带“中式用餐”约束的大规模乘务调度问题；其次，从多种不同角度出发，研究了求解大规模乘务调度问题的快速列生成方法；最后，为了克服传统乘务调度模型的缺点，建立了更加一般化的乘务调度扩展模型，并提出了相应的列生成方法。主要研究内容和成果如下：（1）提出了基于缩减问题规模的ILP方法以求解带“中式用餐”约束乘务调度问题

7、。主要是利用“中式用餐”约束和乘务问题特征，提出筛选换班机会（乘务员换班的时间与地点对）集的启发式方法，再利用基于“生成与选择”的ILP方法求解，并在“生成”阶段处理“中式用餐”约束问题。最后，通过实验说明所提方法的有效性。（2）基于乘务问题特征，提出了带换班机会选择的乘务调度网络流模型，并利用Dantzig-Wolfe分解原理将网络流模型转化为带换班机会选择的集覆盖模型，设计了列生成法用于求解集覆盖模型的松弛解，从而得到所求问题的下界。最后，提出一种快速求解整数解的逐步迭代方法：即利用松弛解信息

8、，逐步确定不被使用的换班机会集，并利用列生成法求解未被确定换班机会集上的更小规模的乘务调度问题松弛解。通过I万方数据华中科技大学博士学位论文实例验证，该方法能快速得到问题的整数解，并且与下界进行比较，结果表明大多数实例取得了次优解或最优解。（3）为了克服传统列生成法求解乘务调度问题时子问题求解（利用精确的动态规划方法）太耗时的缺点，提出了集成新列选择与构造的两阶段乘务调度方法。通过分析实际乘务班次的构成特点，设计了快速构造高效班次池的启发式方法。在求解子问题时，优先从班次池中选择能