• 一种基于混合启发式算法的智能公交调度方法

    • 摘要:

      本发明公开了一种基于混合启发式算法的智能公交调度方法.本发明将模拟退火算法和遗传算法结合在一起,并且加入精英保留策略和适应度拉伸函数.将每一代种群中适应度最大的个体直接保留到下一代,避免它被交叉和变异操作破坏.适应度拉伸函数在算法的初期阶段,削减个体之间的差异,从而增加种群的多样性,避免遗传算法陷入局部最优解;在算法的后期阶段,增大个体间的差异,从而增加优秀个体被选择的概率,加快收敛速度.本发明运算速度快,能在较短时间内在给定发车时间频率条件下,得到优化后的调度计划,使乘客的等待时间大幅度减少;能动态调整发车频率,使发车频率符合客流总量的变化规律;能动态调整发车间隔,大幅度减少乘客的等待时间.

    • 专利类型:

      发明专利

    • 申请/专利号:

      CN201410481840.4

    • 申请日期:

      2014.09.19

    • 公开/公告号:

      CN104504229A

    • 公开/公告日:

      2015-04-08

    • 发明人:

      郑宁 陈涛 徐海涛 林菲

    • 申请人:

      杭州电子科技大学

    • 主分类号:

      G06F19/00(2011.01)I,G,G06,G06F,G06F19

    • 分类号:

      G06F19/00(2011.01)I,G08G1/00(2006.01)I,G,G06,G08,G06F,G08G,G06F19,G08G1,G06F19/00,G08G1/00

    • 主权项:

      一种基于混合启发式算法的智能公交调度方法,其特征在于包括如下步骤:步骤(1)读取乘客的刷卡记录,统计每天乘车总人数和每个时间段I内的人数,获取每天的历史天气状况和节假日情况;使用层次聚类方法,对获取的历史数据进行聚类分析;即将一天当中的乘车总人数、不同时间段内的乘车人数、天气情况和节假日情况组合成一个向量,然后对该向量进行归一化操作,使用系统聚类算法中的Ward法进行聚类操作,根据聚类的结果提取每个类别的特征;所述的刷卡记录包括上车刷卡时间、上车站点、下车刷卡时间和下车站点;所述的获取的历史数据包括乘客的刷卡记录、历史天气状况和节假日情况;步骤(2)根据第二天的天气预报信息和节假日情况,从步骤1的聚类结果中匹配到一个类,并从该类中抽取一个向量作为预测值;步骤(3)根据预测值,结合公交企业期望的满载率,两者相除,得到第二天的总发车班次;步骤(4)随机生成N个向量,向量的维度与总发车班次相等;每个分量代表对应班次的发车时间,发车时间以分钟为单位,设定第一个分量等于0,最后一个分量等于末班车发车时间与首班车发车时间之间的分钟数;向量中的分量按从小到大的顺序排列,这N个向量组成初始解的集合P0,并设定迭代次数g为0;其中N为偶数;步骤(5)建立公交调度的数学模型,以乘客的等待时间最短为目标设定适应度函数,计算每个初始解的适应度,然后通过混合启发式算法进行求解;5‑1.使用适应度拉伸函数进行适应度拉伸操作,用拉伸后的值替换掉原来的适应度;5‑2.按照轮盘赌选择策略从集合Pg中选择任意两个解,按照设定的交叉概率进行交叉操作,即随机选择一个交叉位置,交换两个解交叉点前后的部分,得到两个交叉后的解;然后对两个交叉后解进行模拟退火操作:计算交叉后的解的适应度,如果适应度增大,接受新的解,否则以当前的接受概率接受新的解;从而获取两个新的解;5‑3.按照设定的变异概率,对步骤5‑2中获取的两个新解的每一个分量进行变异操作,即随机生成一个大小位于前后两个分量之间的自然数,替换掉原来的值,得到两个变异后的解;然后进行模拟退火操作:计算变异后的解的适应度,如果适应度增大,接受新的解,否则以当前的接受概率接受新的解;从而获取两个新的解,并将获取的两个新的解放入解集Pg+1;5‑4.重复步骤5‑2和5‑3,直至解集Pg+1中解的个数与N相等;步骤(6)更新迭代次数g=g+1,若已经达到最大的迭代次数Gmax,则输出解集Pg中适应度最高的解,即为优化后的发车时刻表;否则,转到步骤5‑1;所述的迭代次数Gmax为正整数.