单线公交司机排班计划网络流模型与求解算法

摘要：

随着公共交通的快速发展,公交运营规划的相关研究对于城市交通系统的运行具有重要意义.司机调度问题是公交运营规划研究的重要组成部分,该问题因满足相关劳动法规约束而被视为N P-hard问题.我国公交存在的早晚班制和司机用餐时间窗使公交司机排班问题更加复杂,一些主流调度方法并不能很好解决这一问题.针对该问题,以最小化司机排班计划总成本为目标,考虑早晚班制、司机相关工作法规及用餐时间窗的单线公交司机排班计划来构建网络流模型,并提出一种基于离散事件模型和变邻域搜索算法(VNS)对问题进行求解.最后,设置11组算例,验证所提出的网络流模型和基于离散事件模型的变邻域搜索算法有效性.算例结果显示,在小规模算例中VNS算法能快速得到与CPLEX相近的解,在大规模算例中可快速获得问题的可行解.

关键词：城市交通、公交车司机调度、变邻域搜索、时空网络、离散事件

所属期刊栏目：24

分类号：U121(城市交通运输)

资助基金：国家自然科学基金;中国博士后科学基金资助项目

在线出版日期：2022-09-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：8-15