文档介绍：基于遗传算法的公交智能排班系统的设计与实现
王宁1,2,宫生文3
(1中国海洋大学 2国家海洋局北海预报中心 3 青岛科技大学信息学院)
摘要:运营车辆智能排班问题是公交车辆智能调度需要解决的典型问题之一。它可以描述为:通过某种智能化的算法,在有限的算法步骤内,找出所有满足约束条件的排班方案中的最优方案或者接近最优的方案。本文应用己有的客流信息,并兼顾到乘客和公交公司的双重利益,引入了遗传算法(GA),针对公交智能排班问题,构造了符合行车规律的编码方式、遗传算子,并给出了系统设计,完成了程序的编码工作。
关键词:公交智能排班;遗传算法;适应度函数;车辆调度;排班优化
0 引言
公交车排班问题是一类典型的运输排班优化问题[1]。组合优化问题就是在一定约束条件下,怎样合理、有效地安排其组成部分或操作所占用资源、运行时间及先后顺序,以获得时间或成本的最优化。
人工智能 AI (Artificial Intelligence)的快速发展,为问题研究开辟了一条道路。AI研究方法在排班问题中的应用越来越广泛,并取得了一些重要的研究成果。如运用非数值并行搜索方法[2],禁忌搜索等进行排班优化问题研究。
对于城市公共交通运输问题而言,公交车辆运营排班管理通常分为三个阶段实施:计划、排班和控制。排班是其关键的中间环节,车辆运营排班问题就是针对一项可分解的运输任务,在一定的约束条件下,如何合理安排其组织部分(操作)所占有资源、运作时间及先后顺序,以获得运输成本或时间最优化。公交车辆运营排班通常包括两层含义:
(1)原始排班,车辆计划安排,称为静态排班;
(2)由于某种路况信息或突发事件,使得原始排班必须做修改、更新,称为动态排班或者重排班。
本文是根据客流资料进行车辆静态排班的研究;根据对公交车辆排班问题的描述和分析,建立起函数模型,并运用遗传算法对问题进行最后的求解。
问题描述
所谓排班问题就是为了某一目的面对共同使用的资源实行时间分配,通常可表示为在等式或者不等式的约束下,求解目标函数的优化。城市公交车辆运输系统是定时、定线行驶,并按客流量、流向时一空分布的变化而不断调节的随机服务系统。该排班问题有如下特点:
M为公交车辆集,每辆车在运输运行中只从事一种运输方式。
每辆车应按时发车,根据不同的运行时段,准时完成运输任务。
公交车辆运输排班问题就是指在固定行驶线路上,根据不同时段、依照一定的次序关系,合理的编排运输车辆运行作业形式,以达到供需平衡,满足系统的性能指标。本文在这里采用的优化指标为:在不影响乘客出行的前提下,使得乘客的等待时间和公司发车次数最少,并避免出现“大间隔”。
由于车辆运输排班问题本身是难点问题。虽然己经有一些人采用随机搜索法、人工神经网络致力于车辆排班问题的研究,但其研究问题基本上都是货车排班问题。针对公交车辆这种特殊的运输排班问题,本文将采用遗传算法优化公交车辆运营排班问题。
2 遗传算法简介
遗传算法是一种迭代算法,它从某一随机产生的或是特定的初始解集出发,按照一定的操作规则,如选择、复制、交叉、变异等,不断地迭代计算以得到新一代解集,并根据个体的适应度,按照适者生存和优胜劣汰的原则,引导搜索过程向
“最适应环境”的个体(最优解)逼近,逐代演化出越来越好的近似解,最终收