《基于蚂蚁算法的公交驾驶员调度问题研究》由会员分享，可在线阅读，更多相关《基于蚂蚁算法的公交驾驶员调度问题研究（69页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 硕士学位论文 基于蚂蚁算法的公交驾驶员调度问题研究 姓名：杨尚 申请学位级别：硕士 专业：系统工程 指导教师：陈学广 20090528 华 中 科 技 大 学 硕 士 学 位 论 文 I 摘 要 摘 要 公共交通在城市交通中占据主体地位，而驾驶员调度问题则是公共交通系统运 营管理中的一个重要的问题，直接影响到公交公司的运营成本和服务质量。在国外， 已经有比较成熟的驾驶员调度软件系统，而国内公交系统的特殊性，使得国外的研 究成果和应用技术很难直接套用。因此驾驶员调度问题正在得到越来越多的国内研 究者的关注。另一方面，驾驶员调度问题本身还有一些问题没有得到很好的解决， 比如时间窗问题
2、、用餐时间问题等，值得进行进一步研究。 本文研究利用蚂蚁算法来解决公共交通中公共汽车驾驶员调度的问题。蚂蚁算 法是一种带有正反馈机制的启发式算法，并具有贪婪的特性，在解决路径优化、调 度排班这类利用传统数学规划方法很难解决的问题上具有很大的潜力。本文对驾驶 员调度问题的数学模型进行了详细分析，根据驾驶员调度问题的特点和其特殊的约 束，对蚂蚁算法做了改进，包括：将驾驶员调度特有的规则加入到算法当中，为可 设置的参数；采用多只蚂蚁分工进行一个解的搜索；对启发信息进行重新设置等， 并通过控制蚂蚁算法中蚂蚁移动的方式解决了驾驶员调度问题的时间窗问题。同时， 蚂蚁算法可以直接在行车计划的基础上进行解的搜
3、索，实现了贪婪式的要求。最后 利用 C#语言实现了蚂蚁算法，并进行了仿真试验，分析了蚂蚁算法的参数对算法性 能的影响，得出了经验式的参数优化设置方法，并可以在较短的时间内获得满意解。 与禁忌搜索算法的对比表明，对同一原始数据可得出相似的优化结果。 关键字：驾驶员调度，换班机会窗，蚂蚁算法 华 中 科 技 大 学 硕 士 学 位 论 文 II Abstract Public Transport System is an indivisible part of the cities transport, and Bus Driver Scheduling which strongly relate
4、s 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 dr
5、iver 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 po
6、sitive 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 syst
7、em 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 searche
8、s 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 t
9、ime. 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. Keywords: bus driver scheduling, window of relief opportunity, ant system 华 中 科 技 大 学 硕 士 学 位 论 文 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取
10、得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_
11、年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 绪论 1.1 课题来源 公共交通在人们的日常生活中占有非常重要的地位，公交公司运营过程中普遍 存在如下问题：信息化程度低，运营费用昂贵，缺乏整体规划。目前全国各大城市 开始逐步建立智能公共交通系统，将极大的转变以往的工作管理方式，大量的手工 操作改由计算机完成。 项目组对上海杭州，上海，广州，深圳和武汉的公交系统的进行了调研。目前 各公交公司都在积极发展智能公共交通系统，采用信息化、智能化的
12、工具，转变管 理模式、改变调度方式，以提高效率、降低成本和提高服务质量。但是在建设发展 过程中仍然存在一些亟待解决的问题，比如在建立智能公交系统时，有海量数据的 传输、存储和利用，调度工作的自动化程度并不高，因此提出了基于网格的公共交 通信息管理与调度决策支持系统。在项目实施过程中，作者根据参与的调度子模块 的研究工作，提出了本文所讨论的驾驶员调度问题。 1.2 研究目的及意义 公共交通公共汽车驾驶员调度（Bus Driver Scheduling，BDS）专指在公共交通 中公交巴士的驾驶员的调度，以下简称驾驶员调度问题，它是智能公共交通系统 （Intelligent Transport Sy
13、stem，ITS）中一个重要的组成部分，并直接关系到公交公 司的运营成本和服务质量。驾驶员调度问题主要是指在已有行车时刻表和车辆调度 的前提下，为驾驶员分配驾驶的时间和路线区间1。它以行车时刻表位依托，又是行 车时刻表的实施。 公交驾驶员调度工作中，目前人工干预的部分还比较大，而驾驶员调度的自动 化系统尚处于研究开发阶段。以现有的方式进行驾驶员调度，既费力费时，又无法 验证排班结果是以一种比较优化的方式；而且在排班过程中，调度人员需要大量的 经验才能进行。而在公共交通这样的大型公共项目中，只要效率提高一点，都可以 华 中 科 技 大 学 硕 士 学 位 论 文 2 为公交公司和相关部门节省大量
14、的时间和资金。有很多的研究人员尝试着用各种方 式解决驾驶员调度问题，虽然有一些方法在商业应用中取得了巨大的成功，但驾驶 员问题本身的还有很多值得研究的地方。现有的软件系统虽说在国外取得了很大的 成功，但这些解决方法并不通用，需要根据不同的情况做出调整，是否适合国内的 环境还有待进一步研究。另外，比较成功的软件系统采用的方法大都为“生成加选 择”模式2，其中“生成”阶段并非贪婪式的，而又占据了整个算法的大部分时间， 因而很难在较短的时间内求得满意解。因此，有必要对驾驶员调度问题进行更多更 深入的研究。 根据文献2指出的研究方向，本文将尝试将蚂蚁算法引入到驾驶员调度问题中。 本文在分析了驾驶员调度
15、问题的特性后，对蚂蚁算法进行了改进，并将其引入到驾 驶员调度问题中，解决带时间窗的驾驶员调度问题，并实现贪婪式的要求，以期在 容许的时间内获得问题的满意解。 1.3 驾驶员调度问题的国内外研究现状 驾驶员调度问题是世界公认的 NP 难问题， 单单采用传统的数学规划方法并不能 在有效的时间内求的问题的最优解。研究者在很早就关注到驾驶员调度问题，对其 进行了研究，并取得了很多成果，目前已经有成功的商业应用。但是，目前能在商 业中应用的系统所采用的方法主要还是采用“生成加选择”模式进行，即先利用线 路信息、班次类型等信息缩小问题的规模，再利用数学规划方法进行筛选，最终生 成满意解。在这种方法取得了巨
16、大成功后，有较多研究者研究如何改进这种模式。 这种“生成加选择”模式对问题的规模具有较为严格的限制，并且在方法初期并不 能实现贪婪式的要求，不易在短时间内生成可以接受的满意解。目前，研究者多考 虑如何将各种启发式方法进行改进和融合，以减小对驾驶员调度问题规模的限制， 并跳出“生成加选择”的模式，设计具有贪婪特性的方法，以提高问题的求解速度。 公共交通系统最早可以追述到 1819-1854 年， 在法国巴黎出现的公共马车和有轨 马车逐步替代了出租马车，形成了城市中的公共交通系统的雏形3。 当时系统并不复 杂，并没有体现对驾驶员调度这方面的要求。直到公共交通系统越来越具有规模， 华 中 科 技 大 学 硕 士 学 位 论 文 3 调度问题渐渐凸显，驾驶员调度问题也在其中占据着重要的地位。 在二十世纪七十年代之前，启发式算法还不成熟，将驾驶员调度问题主要被归 结为整数现行规划问题，但是在规模不大的时候，就需要非常不合理的时间来获取 最优解，这种方式并没有得到实际应用。 七十年代初期，在一些启发式算法的理论和技术开始成
