公交智能调度系统中运营车辆自动排班的遗传算法

点击蓝字，一键关注 

走进《公共交通资讯》，及时掌握公交领域的行业政策、管理理论、科技信息、专家观点和先进经验...

遗传算法在智能调度系统中的应用

      运营车辆的自动排班是智能调度系统需要解决的问题之一，将车辆、客流、服务、运营、客流等因素考虑到公交调度方案中，以此建立多目标优化模型。针对给出的条件和数据，将遗传算法应用到公交智能调度系统中，制定合理最优的排班方案。

1

遗传算法的基本理论

      遗传算法（Genetic Algorithms）是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,是一种有效解决最优化问题的方法。遗传算法是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法包括编码、初始群体、适合度函数、遗传操作和控制参数。算法的基本原理如下图：

2

基于遗传算法的排班调度模型

      首先建立目标函数对模型进行设计：公交运营最优，即运营车辆最少；服务最优，即乘客候车时间最短。首先通过二进制编码形式进行初始化，然后计算适度值并选择新的临界种群，根据交叉、变异对其进行适度值计算，最后根据适度值筛选出最优结果。遗传算法步骤如下：

      根据算法步骤合理解决公交排班系统问题，需要将人、车、路等因素考虑进去，运用科学算法解决公交调度问题。公交车排班是调度系统的核心内容，合理的发车时刻表可以提高车辆利用率，降低运营成本，减少乘客候车时间。

3

济南公交调度排班

      通过一系列算法生成一份合理的行车时刻表是一项非常重要而且复杂的工作，行车时刻表决定了某条线路一天发出的班次总数，给出了每个班次的到离站时间，决定了主站发车的时间间隔，因此也就决定了乘客的平均候车时间，对乘客的服务质量有着很大的影响。

      济南公交自动排班模式分为单向自动排班和双向自动排班，同时根据需要把车辆分为多个班制，单班制、双班制和高峰车。按照车辆班序，根据班次数量进行运营。双班车定在早班和晚班发车，对于早高峰和晚高峰班次，优先使用高峰车来进行排班，再使用双班车和单班车相互穿插排班；单班车则以班次任务量多的优先排班，任务量少的依次再排，一直穿插到平峰。优化了发车间隔，提高了车辆运行效率，提升了公交服务管理水平。

4

结论

      随着交通拥堵、人口增加等问题的出现，使得公交车调度难度越来越大，基于遗传算法的调度排班，能够提高公交车运行效率和资源利用率，合理确定发车时间和车次，优化发车密度，最大化满足乘客出行需求。

参考文献：百度百科

丁勇 姜枫 武玉艳 遗传算法在公交调度中的应用 计算机科学 2016年第11A期

来源：济南市城市交通研究中心有限公司

---

更多阅读：