【作者】 杨尚；

【导师】 陈学广；

【作者基本信息】 华中科技大学 ， 系统工程， 2009， 硕士

【摘要】 公共交通在城市交通中占据主体地位,而驾驶员调度问题则是公共交通系统运营管理中的一个重要的问题,直接影响到公交公司的运营成本和服务质量。在国外,已经有比较成熟的驾驶员调度软件系统,而国内公交系统的特殊性,使得国外的研究成果和应用技术很难直接套用。因此驾驶员调度问题正在得到越来越多的国内研究者的关注。另一方面,驾驶员调度问题本身还有一些问题没有得到很好的解决,比如时间窗问题、用餐时间问题等,值得进行进一步研究。本文研究利用蚂蚁算法来解决公共交通中公共汽车驾驶员调度的问题。蚂蚁算法是一种带有正反馈机制的启发式算法,并具有贪婪的特性,在解决路径优化、调度排班这类利用传统数学规划方法很难解决的问题上具有很大的潜力。本文对驾驶员调度问题的数学模型进行了详细分析,根据驾驶员调度问题的特点和其特殊的约束,对蚂蚁算法做了改进,包括:将驾驶员调度特有的规则加入到算法当中,为可设置的参数;采用多只蚂蚁分工进行一个解的搜索;对启发信息进行重新设置等,并通过控制蚂蚁算法中蚂蚁移动的方式解决了驾驶员调度问题的时间窗问题。同时,蚂蚁算法可以直接在行车计划的基础上进行解的搜索,实现了贪婪式的要求。最后利用C#语言实现了蚂蚁算法,并进行了仿真试验,分析了蚂蚁算法的参数对算法性能的影响,得出了经验式的参数优化设置方法,并可以在较短的时间内获得满意解。与禁忌搜索算法的对比表明,对同一原始数据可得出相似的优化结果。更多还原

【Abstract】 Public Transport System is an indivisible part of the cities’transport, and Bus Driver Scheduling which strongly relates to the costs of operations and the quality of services is an important part of the daily operations of the public transport systems. Although there are mature bus driver scheduling software systems abroad, the differences of local public transport systems make them hard to import in. So the bus driver scheduling problem is paid more and more attention to. Meanwhile the problems of window of relief opportunity and meal time are not well solved which worth more researches.This thesis discussed the Ant System bases bus driver scheduling. Ant system is a heuristic and greedy algorithm with a positive feedback, and it has a potential in some kinds of combinatorial optimization problems like path optimizations and scheduling problems which are hardly solved with integer linear programming. This thesis analyzed the mathematics model of bus driver scheduling problem, and improved the ant system within the special rules of this problem including adding the constraints in as the parameters, dividing ants for different works, and resetting the heuristic information. Meanwhile the window of relief opportunity problem was solved by controlling the movement of the ant. This ant system searches solutions directly from the route plan and realized a greed algorithm. This ant system is realized using C# language, and with simulation, the parameters’impacts to the performance were analyzed. Better parameters can be set from the analysis and a satisfactory solution can be got in appropriate time. In the simulation, this ant system was compared with the tabu search algorithm in a same problem from the real world showed they achieved similar results.更多还原