遗传算法在公交车调度问题中的应用

　　摘要随着社会经济的迅速发展，城市交通的拥堵问题变得越来越严重，甚至成为制约部分城市可持续发展的瓶颈。因此如何最大程度地利用公共交通工具减轻出行压力成为了城市化建设的重要目的。本文基于人流量，提出智能调度的概念，结合改进的遗传算法设计了公交车调度模型，并使用前后端分离模式、vue框架、SpringBoot实现了智能公交调度平台。本平台能帮助公交公司提高运营效益和服务质量，同时提高乘客的出行体验。

　　关键词人流量;遗传算法;智能公交调度平台

　　1引言

　　公交车是人们日常出行的主要交通工具，目前城市公共交通运输中存在公交车运行效率低、城市拥堵严重等问题。如何优化调度方案来解决这一系列问题，是很多科研人员关注的重点。传统的数学解析法往往只能解决单一问题，而公交车调度是一个多目标优化问题。遗传算法通过迭代的方式，对随机生成的一组候选解进行选择、交叉、变异三种基本运算，直到得到最大适应度的最优解。这是解决多目标搜索问题的一种常用方法。公交车调度主要是选择一种算法来生成公交车调度时间表，从而达到公交运行效率和乘客出行体验的最优解。

　　本文考虑乘客人流量因素，通过对遗传算法和禁忌搜索算法进行分析和改进，结合两种算法的优点并将其应用在公交调度问题中，得到公交发车时间的最优解。在公交车运行时，该公交调度平台可根据乘客人流量的不均衡性来调整公交车的发车频率和数量，生成合理有效的发车时刻表，指导公交车出行线路，平衡公交公司和乘客双方的利益，提高公共交通的服务水平。

　　2系统建模

　　公交公司希望发车时间间隔大，公车座位利用率高，以节省成本;乘客则希望等车时间短，提供更便捷的乘车服务。要兼顾这两者的利益最大化，需要考虑的基础数据是人流量。

　　本公交调度方案就是根据人流量划分的时间段来平衡公交公司和乘客两者的利益。在分析了乘客满意度在高峰时段和非高峰时段与等车时间的关系后，选择了直线和插值法中的牛顿插值法来拟合上述两类关系，从而得到乘客的满意度函数[1]。遗传算法是基于达尔文生物进化论的自然选择和遗传学理论而提出来的计算模型。本文将遗传算法应用在智能公交的调度问题中。主要过程分以下几步：(1)编码：要应用遗传算法首先要解决编码问题，本系统采用二进制编码法，并通过计算得到初始种群数量。在公交调度平台的应用中，公交车发车总次数对应于总群规模[2]。

　　(2)选择操作：选择操作是为了确定交叉、变异的个体，本系统采用了截断选择的方法对种群进行选择。将每个遗传算子通过数学模型计算出符合该数学模型的最优解，通过选择出计算结果最好的算子进行复制n次，创建出新的种群。(3)交叉操作：设置一个随机数，当选择的随机数满足算法参数中的交叉概率时，则在新的种群选择两个算子，再对这两个算子进行随机选择一个时间段进行交换，从而生成新的算子。

　　(4)变异操作：设置一个随机数，当该随机数满足遗传算法中的变异概率时，在通过前两次步骤得到的新种群中选择一个算子，随机选择该算子中的一个时间段进行变异操作，变成新的算子[3]。遗传算法比较适合解决公交调度的问题，但存在的缺陷是不同时间段的发车频率比较相似，无法满足乘客在上下班高峰期对公交车的高需求，也造成低峰期空车率高。针对遗传算法应用到公交调度模型会导致局部寻优能力较差和运行效率低等问题，本文结合了禁忌搜索算法和遗传算法的优势，并对其进行了改进和应用[4]。

　　3系统设计

　　智能公交调度平台的设计采用目前广泛应用的B/S架构和流行的Web开发技术。本系统使用前后端分离架构，前端基于Vue框架开发，Vue起到连接视图与数据中间件的作用，并负责界面交互。后端服务使用的框架是基于java的SpringBoot，后端系统负责数据持久化。

　　数据库选用MongoDB来存储较复杂的数据类型，有利于系统字段的扩展。前后端分离是目前Web开发中流行的架构，通过Nginx+Tomcat(NodeJS)的方式有效地对前端和后端的开发进行解耦。本系统使用Vue框架中的VantUi库构建系统界面，提高了开发效率。Nuxt作为Vue的SSR(服务端渲染)代表，解决了Vue的首屏加载慢和SEO问题。

　　本系统也将其应用于用户使用界面。SpringBoot是spring应用的快速开发框架，内嵌了tomcat和jetty容器，可直接生成jar包来发布web服务。其基于注解无需配置模式，便于和SpringWebMVC、Mybatis、SpringCloud等各种流行框架无缝整合[5]。MongoDB是基于分布式文件存储的NoSQL数据库，支持bson格式的松散数据结构，适合存储相对mysql而言较复杂的数据类型。

　　4系统实现

　　智能公交调度平台包括公交管理、客流信息、公交调度和系统管理四个模块。该系统的核心功能是通过分析客流量信息，利用改进的遗传算法为公交公司提供合理有效的发车时间表。本文主要围绕公交调度模块功能点进行分析设计。

　　4.1公交信息设置

　　公交公司管理员登陆系统后，可以在公交管理页面新增公交信息，并设置公交车次的发车时间、末班车时间、车站数和发车总班次。该公交信息构成遗传-禁忌算法中生成公交调度时刻表的基础数据。公交调度时刻表的发车时段的起始时间由首班时间和末班时间确定，总共发车的数量由发车总班次决定。

　　4.2算法参数设置

　　调度参数设置页面，主要用来设置遗传-禁忌算法中相关的影响因子。其中种群数、交叉频率、变异频率是遗传算法的三个基本参数。进化代数是遗传算法在运行过程中的迭代次数，也是遗传算法的停止机制，一般可以人为依据经验设置，或通过测试比较连续迭代相同次数后结果没有变化，则可以认为该遗传算法已经收敛，此时为最优解。乘客权重系数和公交权重系数表示乘客与公交公司的满意度，两者之和等于1。

　　禁忌搜索次数和搜索变异次数是禁忌搜索算法中用来设置特定方向搜索次数的参数。本算法基于的人流量是指乘车人数和乘客数量，在“乘客人数”和“乘客数量”tab页可以管理不同时间段和站点的人流信息。根据不同时间段的人流量，可以将公交车的发车时间分成五个时间段：早上的低峰时段、上班高峰时段、普通时段、下班高峰时段、晚上的低峰时段。本公交调度方案就是根据人流量划分的时间段来平衡公交公司和乘客两者的利益。

　　4.3生成公交调度表

　　系统设置完公交信息和算法参数后，管理员点击“生成调度表”按钮，可得到该公交车的最佳发车时刻表。在上下班的高峰时段，该调度表安排的车次多;而在早晚客流量较少的低峰时段，发车次数就较少。由此可见，本智能公交平台生成的公交调度表，能满足乘客在不同时间段对公交车的需求，同时降低公交公司的成本。

　　公交论文投稿刊物：计算机时代杂志本刊1983年创刊，所刊文章内容主要是电脑信息领域新技术、成果和趋势。

　　5结束语

　　本平台在现有的技术和模式下，基于人流量，使用改进的遗传-禁忌算法解决公交排班问题。通过实际调研分析，符合现实情况的公交车发车时间表，能够帮助公交企业提高运营效益和服务质量。本系统下一步的优化有：(1)开发移动端应用，实时获取公交车运行过程中各站点的客流量，达到动态调整公交车发车时刻表的目的。(2)定位乘客所在站点。根据公交调度时刻表，提醒乘客时间，同时通过谷歌地图插件接口提供的拥挤路段信息，使用算法计算出较准确的乘车时间。

　　参考文献

　　[1]姚艳君.智能公交车辆调度系统的设计与优化[硕士学位论文].沈阳工业大学,沈阳,2010

　　[2]张超群.遗传算法编码方案比较.计算机应用研究,2011(03):25-28

　　[3]谭华.基于遗传算法的公交车调度优化研究.科学技术与创新,2020(32):50-52

　　[4]李志.基于遗传和禁忌搜索混合算法的预制生产调度的研究.计算机测量与控制,2020,28(10):211-215

　　[5]闫四洋.基于SpringBoot+MongoDB的微服务日志系统的实现.计算机时代,2020(08):69-74

　　作者：刘莉