公交资源优化配置

1、公交车辆调度问题是指针对一项可分解的运输任务，在一定的约 束条件下，如何合理安排其组织部分占用资源、 运作时间及先后顺序， 以获得运输成本或时间最优化。包含两层含义：1.编制行车时刻表，称为静态调度； 2.由于某种路况信息或突发事件，使静态调度做出修 改、更新，称为动态调度。传统的调度理论方法多采用数学解析法、运筹学方法和经验模型 等。随着调度问题计算复杂性及问题规模的扩大， 传统方法遇到了很 大的困难。 人工智能为调度问题研究开辟了新的道路。 现有的研究方 法有： 1.应用标准遗传算法进行公交静态调度优化； 2.蚁群算法思想 解决车辆优化调度问题；3基于公交运营效益最大化的BRT调度问题 的

2、数学模型，并设计了优化该问题的禁忌算法；4.粒子群算法解决带时间窗的公交路径优化问题。基于改进遗传算法在静态调度中的应用，以公交营运商和乘客费 用（包括乘客等车时间费用和车上等待时间费用）最小为目标，建立 公交调度优化的数学模型，在遗传算法中引入模拟退火算法的思想， 研究改进的遗传算法在公交调度中应用的基本方法和基本理论。公交调度优化问题表现为两个方面的利益最大化： 1.企业的收益； 2.乘客利益。且乘客利益优先于企业利益。该问题的研究对象有公交 公司和乘客两部分组成。公交公司希望提供尽量大的发车间隔，发车次数尽量少，单位车辆上座率尽量高，以减少其可变成本，增加运营收入；乘客则要求获得更快捷的

3、服务，减低等车、车上和换乘费用;3. 减少公交公司费用意味着增加乘客费用，反之亦然。因此，需要从公交乘客和公交公司双方利益最大化出发，根据公交车辆实际运营时乘客流量在时间上的不均衡规律，以极小化公交公司和 乘客费用总和为目标，对发车间隔采用分时段多目标组合优化处理的 思想，在合理假设的前提下建立优化模型。营运成本 Co=/K ) J(Tk/Hk)K为时段总数，将一天划分为 K个时段；Tk为第k时段公 交车营运时间；Hk为第k时段的发车间隔；为公交车的 单车营运成本出行者费用Cu由乘客候车耗时费用Cub与不下车乘客由于 公交站点停车所消耗的时间费用Ccb组成：Cu =Cub + Ccb1JCub

4、=-( 山/K) k=i J=i (UkjHk)*为乘客单位时间价值；Ukj为k时段、第j站的乘客到站 密度，假设服从均匀分布；J为公交站点数C =上1CCb = Kk=iJ=i Dkj?；q： +:q；HkPkji Pkj2为k时段j站点上下车乘客需求；q1q2为上下车平均速率；Dkj为k时段j站点的不下车乘客数j- 1Dkj =(Bkm - Akm )m=1Bkm为k时段j站点的上课乘客数；Akm为k时段j站点的 下车乘客数。优化模型：选取权重和方法作为多目标函数优化算法，得到目标函数f,待求变量为发车间隔Hkmin f= aC0 + 约束条件为：Hmin W Hk 70%kNY Nk/7

5、* * 丁 A %N* = i 12 * * t K F(A*T. 丁oa为权重系数，取正数；Hmin为最小发车间隔；Hmax为最 大发车间隔；Qd为公交车额定载客量；Nk为时段k所需车 辆数；T。为车辆的周转时间；fk为时段k的发车频率；n为 第k时段车辆的周转系数n = Tk/T0遗传算法应用于公交车调度能够在排班优化问题的巨大搜索空间 中可靠地找到近似最优解。在具体运算过程中，对乘客流量时间分布 的设置具有很大的假设性，同时认为公交车匀速行驶也不符合实际情 况。但是遗传算法的收敛性并不依赖于乘客的分布形式或道路的通行 状况。改进遗传算法比遗传算法在迭代全程表现出更好的收敛速度性能。尤其在

6、进化末期，改进遗传算法也保持着相当的适值下降趋势。改进遗传算法的收敛效果随种群的增大而增大。 在引入适值模拟退火拉伸 思想后的改进遗传算法，能较好地克服遗传算法前期进化早熟和后期 进化速度缓慢等问题。车辆路径问题（vehicle routing problem, VRP是指对一系列发货点 或收货点，组成适当的行车路径，使车辆有序通过它们，在满足一定 约束条件的情况下，达到一定的目标（如路程最短、费用最小、耗费 时间尽量少等），属于完全NP问题。带时间窗的车辆路径问题（vehicle routing problem with time windows, VRPTW）是在 VRP问题上加了客户 要

7、求访问的时间窗口（如邮政投递、火车及公共汽车的调度等） 。先 后有一般启发式算法和神经网络、 遗传算法、 禁忌搜索和模拟退火等 智能化启发式算法。还有仿生算法，如模拟鸟群飞行的粒子群算法， 有着个体数目少、计算简单、鲁棒性好等优点，在各类多维连续空间 优化问题上均取得非常好的效果。以及蚁群算法。有时间窗车辆路径问题的描述及数学模型：有L项运输任务（以i表示），i=12L,已知任务i的客运量为g, 配送中心有m辆相同型号的车辆，车辆容量为q,对每辆车执行的任 务点有gi q；同时，每项任务都要在规定时间内完成，完成任务i需要的时间为T，任务i的开始时间si要在一定的时间范围可口内， 边界分别为任

8、务 i 的最早开始时间和最晚开始时间；若在车辆行驶线 路上任务i为任务j的前驱，车辆由i行驶到j需要时间5,则有 sj = （si + Ti + tij ）成立；问题的优化目标为求解满足客运量要求的费 用（所需车辆或时间、距离等产生的运输成本） 最小的车辆调度方案。定义变量：xijk1 车辆 k 从点 i 行驶到点 j0 否则yki =1点i的任务由车辆k完成0 否则cij ：从点 i 到点 j 的运输成本rk ：车辆的最长工作时间minZ= i=0数学模型如下：m k=1L j=1x0jk mm k=1Li=0 xijk= 1 j =1 .LmK=1Lj=0 xijk=1 i=1LmLx0j

9、kmLk=1i=1-k=1jL=1 xLI=1giyki qs.t.j0k = 0j=0k=1 cij xijkSj j = 1 LS0=T0=0Km=1iL=0 xijk si + Ti + tiji=o j=o Xijktij rk k= 1 m蚁群算法的基本规则按照固定的模式更新信息量和确定路径选择 概率，忽略算法搜索的实际状态，往往产生加速收敛和防止早熟、停 滞现象的矛盾。因此采用根据搜索状态动态调整算法路径选择策略和 信息量更新策略， 以求在加速收敛和防止停滞之间取得平衡甚为重要粒子群算法中，每个备选解被称为一个粒子，多个粒子共存、合 作寻优，每个粒子根据它自身的经验和相邻粒子群的最佳经验在问题 空间中向更好的位置飞行， 搜索最优解。 在对典型连续非线性多维函 数使用粒子群算法寻优的经验研究中， 发现粒子数与寻优结果的相关 性不大； 通过自适应修改惯量的方法， 可以克服在非常复杂空间寻优 时收敛于局部最优解的问题。单 VRPTW属于整数规划问题，试验中 采用自适应修改惯量的方法，并未能解决收敛于