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

摘要

乘务调度问题是指在满足各种劳动法规和实际约束的条件下，将给定的车辆任务集进行切分和组合，形成一组乘务员可执行的班次集，并使得班次总成本（总数或总工时）最小化。该问题是公交运营管理与规划的核心问题之一，有效的乘务调度方法对提高公交运营效率和降低人力资源成本具有重要意义。目前，解决乘务调度问题存在着两个方面的难题。一方面，乘务调度问题是NP难问题，研究大规模乘务调度问题的求解方法一直是公交调度与组合优化领域的热点和难点之一。目前，传统整数线性规划（ILP）方法、元启发式方法（遗传算法、禁忌搜索等）和以列生成技术为主的数学规划方法是求解该问题的主要方法。传统ILP方法受变量和约束数量的限制，求解能力有限；元启发式方法相对求解速度快，但难以保证解的最优性；列生成法不受问题规模的限制，且能够求得次优解甚至最优解，但具有收敛速度慢的缺点。另一方面，常用的乘务调度模型（如集覆盖模型）过于理想化，其求解结果在实际应用时，时常不能满足运营企业的实际要求和期望，具有一定的局限性。
　　为了克服上述难题，本文对大规模乘务调度问题的快速求解方法和更一般化的乘务调度模型两方面进行了研究。首先，提出了基于问题特征与缩减问题规模的方法，以处理带“中式用餐”约束的大规模乘务调度问题；其次，从多种不同角度出发，研究了求解大规模乘务调度问题的快速列生成方法；最后，为了克服传统乘务调度模型的缺点，建立了更加一般化的乘务调度扩展模型，并提出了相应的列生成方法。主要研究内容和成果如下：
　　（1）提出了基于缩减问题规模的ILP方法以求解带“中式用餐”约束乘务调度问题。主要是利用“中式用餐”约束和乘务问题特征，提出筛选换班机会（乘务员换班的时间与地点对）集的启发式方法，再利用基于“生成与选择”的ILP方法求解，并在“生成”阶段处理“中式用餐”约束问题。最后，通过实验说明所提方法的有效性。
　　（2）基于乘务问题特征，提出了带换班机会选择的乘务调度网络流模型，并利用Dantzig-Wolfe分解原理将网络流模型转化为带换班机会选择的集覆盖模型，设计了列生成法用于求解集覆盖模型的松弛解，从而得到所求问题的下界。最后，提出一种快速求解整数解的逐步迭代方法：即利用松弛解信息，逐步确定不被使用的换班机会集，并利用列生成法求解未被确定换班机会集上的更小规模的乘务调度问题松弛解。通过实例验证，该方法能快速得到问题的整数解，并且与下界进行比较，结果表明大多数实例取得了次优解或最优解。
　　（3）为了克服传统列生成法求解乘务调度问题时子问题求解（利用精确的动态规划方法）太耗时的缺点，提出了集成新列选择与构造的两阶段乘务调度方法。通过分析实际乘务班次的构成特点，设计了快速构造高效班次池的启发式方法。在求解子问题时，优先从班次池中选择能改进目标值的班次；当无法找到所需班次时，调用精确的构造式方法生成新班次。通过实例，将该方法与传统方法进行比较，该方法在求解时间上能减小20％。
　　（4）根据乘务调度问题特点，从受限主问题、子问题求解以及整数求解方面提出三种针对列生成方法的新加速策略：在列生成过程中，定期移除受限主问题的部分“差”列，以减小主问题的规模；在利用多标号动态规划求解子问题时，提出一种强标号消除准则，并提出基于强标号消除准则的二阶段法以加速子问题求解；提出一种班次池策略以继承已有解信息，从而加速整数解的求解。通过实例计算和比较，结果说明这些策略能对列生成算法起到一定的加速作用。
　　（5）针对传统基于单纯集覆盖（或集分割）模型不能反映实际中乘务员与运营企业的偏好或某些特定约束的缺点，提出一种带有多种外加约束的扩展集覆盖模型。该模型能反映实际问题中的多种特定约束，更具一般性。针对该模型，设计了相应的列生成求解方法。由于外加约束的引入，使得传统的子问题求解方法无法直接使用。本文基于外加约束所限制的班次集，对潜在班次进行重新分类，并提出一个基于分解技术的子问题求解方法。最后，对实际问题中遇到的四类外加约束，利用本文方法进行实验测试，均在合理时间内得到次优解或最优解。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景与意义

1.2 乘务调度问题的国内外研究现状

1.3 存在的问题、难点以及本文的创新点

1.4 论文组织结构

2 乘务调度问题及其求解方法

2.1 乘务调度问题描述

2.2 基本的乘务调度模型

2.3 基于“生成与选择”的ILP求解方法

2.4 基于列生成技术的求解方法

2.5 小结

3 基于缩减问题规模的乘务调度方法

3.1 引言

3.2 带“中式用餐”约束的乘务调度问题

3.3 基于“生成与选择”的求解方法

3.4 换班机会集的筛选与乘务班次集的生成

3.5 实例计算

3.6 小结

4 基于逐步确定换班机会集的乘务调度列生成方法

4.1 引言

4.2 具有换班机会选择的乘务调度数学模型

4.3 乘务调度问题的列生成方法

4.4 基于逐步确定换班机会的列生成方法

4.5 实例计算与结果

4.6 小结

5 集成新列选择与构造的两阶段乘务调度列生成方法

5.1 引言

5.2 乘务调度问题与模型

5.3 求解方法

5.4 实例计算与结果

5.5 小结

6 基于新加速策略的乘务调度列生成方法

6.1 引言

6.2 乘务调度问题与模型

6.3 基于列生成法的乘务调度问题求解

6.4 实例计算与结果

6.5 小结

7 带外加约束的乘务调度扩展模型及其列生成方法

7.1 引言

7.2 乘务调度数学模型

7.3 基于列生成的求解方法

7.4 实例计算与结果

7.5 小结

8 研究总结与展望

8.1 研究总结

8.2 研究展望

致谢

参考文献

附录1 攻读博士学位期间发表学术论文

附录2 公开发表的学术论文与博士学位论文的关系

附录3 攻读博士学位期间参与的科研项目