公交驾驶员调度问题的改进模型及其算法研究.docVIP

公交驾驶员调度问题的改进模型及其算法研究 (东北大学 信息科学与工程学院，辽宁省 沈阳市 邮编：110819) 摘 要：驾驶员调度问题是智能公共交通调度系统的一个重要组成部分。绝大多数驾驶员调度研究忽视了人员有效工作时间的均衡性，可能会影响人员的工作热情，从而降低工作效率和服务质量。因此本文给出了基于均衡性的驾驶员调度问题的改进模型，模型的目标是在满足相关约束的条件下，使驾驶员完成车辆运营任务的班次数最少，运营成本最小，班次有效工作时间标准差最小。同时针对目前普遍采用“生成与选择”模式的方法求解驾驶员调度问题存在的局限性及其不足，提出了改进的蚁群算法，在班次的构造阶段就考虑目标函数。通过实验,对模型的正确性进行了验证，证明了改进蚁群算法解决驾驶员调度问题的高效性和较强的适用性。 关键词：驾驶员调度；公共交通；蚁群算法 An Improved Model and Algorithm for Bus Driver Scheduling Problem (College?of?Information?Science?and?Engineering,?Northeastern?University Shenyang?110819,?China) Abstract: Driver scheduling problem is an important part of the intelligent dispatching system in public transit. Most of the research related to driver scheduling ignored the balance of effective working time of the staff, which may affect the staff’s enthusiasm, reduce the efficiency and the quality of service. In this paper, an improved model is established with the objective of minimizing the number of duties, operating costs and the standard deviation of effective working time. To overcome the existing shortcomings of the generate-and-select approach widely used in driver scheduling, an improved ant colony algorithm (IACA) is proposed and the objective function is considered in the duties’ construction phase. An example is applied to demonstrate the feasibility of this improved model. It is proved that the proposed IACA is efficient and robust in solving driver scheduling problem. Key words：driver scheduling; public?transport; ant colony algorithm 驾驶员调度问题是智能公共交通系统中一个重要的组成部分，直接关系到公交公司的运营成本和服务质量。对公共交通驾驶员调度问题的研究可以帮助大幅度提高驾驶员利用效率,进而给公共交通企业带来良好的经济效益因此吸引了人们广泛的关注与兴趣。 国内外学者和专家针对驾驶员调度问题的研究取得[1]。Simth采用集合覆盖模型描述驾驶员调度问题，并采整数规划求解[2]。Desrochers和Soumis等采用列生成法求解大规模驾驶员调度问题[3]。Wren将遗传算法引用到求解司售人员排班的问题中来[4]。Beasley等建立0-1整数规划数学模型，并采用拉格朗日松弛法确定下界，树形有哪些信誉好的足球投注网站算法求得最后的最优解[5]。Lourenco等了一种多目标的驾驶员调度问题模型,它的思想来源是在实际工作中决定驾驶员工作班次时需要综合考虑多个相互冲突的目标，因此该模型综合利用元启发式算法，禁忌有哪些信誉好的足球投注网站算法和遗传算法来对多目标问题进行计算处理[6]。沈吟东对TRACS的整数规划模型和求解方法进行分析，并指出其局限性以及进一步研究公交驾驶员调度问题的方向[7]。张斐斐对公共交通司售人员排班问题进行了研究，综述了排班问题常用的研究方法，