复杂约束下公交车辆与乘务员集成调度模型与方法研究

In public transit of China, vehicle and crew scheduling are usually compiled manually or sequentially, i.e. vehicle scheduling is firstly compiled and then crew scheduling is compiled according to the results of vehicle scheduling. However, it’s hard to achieve the optimal scheduling solutions since vehicles and crews are restricted mutually. Moreover, a serial of Chinese complex constraints can’t be dealt with in traditional scheduling approach. This project is to study an integrated vehicle and crew scheduling approach with considering Chinese complex constraints. The research consists of the following two main parts: The first is to analyze and extract the essential characteristics of Chinese complex constraints such as crews bundled with vehicles, Chinese meal break, multiple vehicle types, restriction on number of relief, time windows of relief, etc. Based on exploration of coupling relationship of vehicles and crews, we then define the scientific problem of integrated vehicle and crew scheduling problem with complex constraints, and establish appropriate mathematical formulation. The second is to solve the integrated formulation by combing math programming approaches with metaheuristic algorithms such as tabu search, variable neighbourhood search. This project is proposed to be helpful for bus companies to increase the utilization of resources and managerial levels. And the research fruits would also be helpful to solve other similar resource scheduling problems such as machine scheduling, vehicle routing.

针对我国公交调度中普遍采用人工经验或顺序调度方法（即先进行车辆调度，再进行乘务员调度），难以达到运营资源的全局优化配置，以及一系列复杂特色约束难以处理等问题，本项目拟围绕复杂约束下公交车辆与乘务员集成调度模型与方法展开研究。主要内容包括两个方面：1）分析和提炼诸如人车捆绑、中式用餐、多车型、换班次数限制、换班时间窗等具我国特色约束的本质特征及其对公交车辆调度和乘务员调度的影响因素，研究集成调度模式下车辆与乘务员资源间的耦合关系，定义复杂约束下公交车辆与乘务员的集成调度科学问题，并建立复杂约束下公交车辆和乘务员的集成调度数学模型；2）基于大规模整数规划分解理论与方法，融合禁忌搜索、变邻域搜索等元启发式方法，研究公交集成调度模型的高效混合优化求解方法。此项研究将能够帮助公交运营企业大幅降低运营成本、提高资源利用效益和服务水平，同时对求解如机器排序、车辆路径等资源调度问题也具重要借鉴意义。

在我国公交运营中，传统“先求解车辆调度，再求解乘务员调度”的顺序调度模式存在资源利用率低的缺点。而在考虑集成调度时，存在“人车捆绑”、“换班次数限制”等难以处理的复杂约束。本项目分析车辆调度和乘务员调度的相互制约关系，充分挖掘复杂约束特征，研究集成车辆与乘务员调度的数学建模和求解方法。首先，分析车辆调度与乘务调度的共性元素和特征，构造出能融入“人车捆绑”、“换班次数限制”等复杂约束的有向网络流图，建立基于双网络流的集成调度模型，保证了模型的全局最优性。其次，针对集成公交调度模型，设计了基于数学模型分解的求解方法。针对集成调度模型求解中的最难子问题乘务调度问题，研究出基于乘务换班机会特征的快速列生成方法，用实际案例测试，表明其比传统列生成方法更具优势。再次，对整数规划建模和元启发式求解方法做了一系列研究。针对围堵嫌犯问题，建立了易于求解的整数规划模型。针对贴片机贴装路径优化问题，建立数学模型并研究出了高效的免疫优化算法，案例计算表明其优于一般遗传算法。针对一维下料问题，设计了基于改进模拟退火的混合优化求解方法。最后，在数值计算稳定性和算法效率等方面，做了一些拓展研究。针对非线性空间分数阶Schrödinger方程，设计了基于指数时间差分的数值求解算法，从理论分析和案例计算两方面，证实了算法的准确性、高效率和可靠性。针对大型稀疏线性方程组的求解，将Java多线程技术与SSOR-PCG算法相结合,设计并实现了一个运算效率更高的并行求解方法。本项目研究的集成车辆与乘务员调度建模方法、列生成方法、元启发式方法、算法稳定性和效率分析等，为城市公交实施优化调度提供了理论和方法基础，对公交运营企业降低运营成本、提高公交资源利用效益、增强公交竞争力具有重要实际意义。相关研究成果加以改进也可用于解决其他经济管理、工业工程领域的资源调度问题。