公交资源优化配置

公交车辆调度问题是指针对一项可分解的运输任务，在一定的约束条件下，如何合理安排其组织部分占用资源、运作时间及先后顺序，以获得运输成本或时间最优化。包含两层含义：1.编制行车时刻表，称为静态调度；2.由于某种路况信息或突发事件，使静态调度做出修改、更新，称为动态调度。

传统的调度理论方法多采用数学解析法、运筹学方法和经验模型等。随着调度问题计算复杂性及问题规模的扩大，传统方法遇到了很大的困难。人工智能为调度问题研究开辟了新的道路。现有的研究方法有：1.应用标准遗传算法进行公交静态调度优化；2.蚁群算法思想解决车辆优化调度问题；3.基于公交运营效益最大化的BRT调度问题的数学模型，并设计了优化该问题的禁忌算法；4.粒子群算法解决带时间窗的公交路径优化问题。

基于改进遗传算法在静态调度中的应用，以公交营运商和乘客费用（包括乘客等车时间费用和车上等待时间费用）最小为目标，建立公交调度优化的数学模型，在遗传算法中引入模拟退火算法的思想，研究改进的遗传算法在公交调度中应用的基本方法和基本理论。 公交调度优化问题表现为两个方面的利益最大化：1.企业的收益；2.乘客利益。且乘客利益优先于企业利益。该问题的研究对象有公交公司和乘客两部分组成。 1.

公交公司希望提供尽量大的发车间隔，发车次数尽量少，单位车辆上座率尽量高，以减少其可变成本，增加运营收入；

2. 3.

乘客则要求获得更快捷的服务，减低等车、车上和换乘费用； 减少公交公司费用意味着增加乘客费用，反之亦然。

因此，需要从公交乘客和公交公司双方利益最大化出发，根据公交车辆实际运营时乘客流量在时间上的不均衡规律，以极小化公交公司和乘客费用总和为目标，对发车间隔采用分时段多目标组合优化处理的思想，在合理假设的前提下建立优化模型。

1. 营运成本C0=(μ0/K )∑kk−1(Tk/Hk)

K 为时段总数，将一天划分为K个时段；Tk为第k时段公交车营运时间；Hk为第k时段的发车间隔；μ0为公交车的单车营运成本

2. 出行者费用Cu由乘客候车耗时费用Cub与不下车乘客由于公交站点停车所消耗的时间费用Ccb组成：Cu=Cub+Ccb Cub=(μ1/K)∑kk=1∑j=1(UkjHk)

21

J

μ1为乘客单位时间价值；Ukj为k时段、第j站的乘客到站密度，假设服从均匀分布；J为公交站点数 Ccb=(1)∑kk=1∑j=1Dkj∗[(2q)+(2q)]Hk K

1

2

μ

J

pkj1pkj2

pkj1pkj2为k时段j站点上下车乘客需求；q1q2为上下车平均速率；Dkj为k时段j站点的不下车乘客数

j−1

Dkj=∑(Bkm−Akm)

m=1

Bkm为k时段j站点的上课乘客数；Akm为k时段j站点的下车乘客数。

3. 优化模型：选取权重和方法作为多目标函数优化算法，得到目标函数f，待求变量为发车间隔Hk min f=αC0+βCu 约束条件为：

Hmin≤Hk≤Hmax,k=1,2,…,K

Jkk∑∑(∑kD)/(QJ())>70% kjdk=1j=1k=1

HkT

αβ为权重系数，取正数；Hmin为最小发车间隔；Hmax为最大发车间隔；Qd为公交车额定载客量；Nk为时段k所需车辆数；T0为车辆的周转时间；fk为时段k的发车频率；ηk为第k时段车辆的周转系数ηk=Tk/T0

遗传算法应用于公交车调度能够在排班优化问题的巨大搜索空间中可靠地找到近似最优解。在具体运算过程中，对乘客流量时间分布的设置具有很大的假设性，同时认为公交车匀速行驶也不符合实际情况。但是遗传算法的收敛性并不依赖于乘客的分布形式或道路的通行状况。

改进遗传算法比遗传算法在迭代全程表现出更好的收敛速度性能。尤其在进化末期，改进遗传算法也保持着相当的适值下降趋势。改进遗传算法的收敛效果随种群的增大而增大。在引入适值模拟退火拉伸思想后的改进遗传算法，能较好地克服遗传算法前期进化早熟和后期进化速度缓慢等问题。

二

车辆路径问题( vehicle routing problem, VRP)是指对一系列发货点或收货点，组成适当的行车路径，使车辆有序通过它们，在满足一定约束条件的情况下，达到一定的目标（如路程最短、费用最小、耗费时间尽量少等），属于完全NP问题。带时间窗的车辆路径问题(vehicle routing problem with time windows, VRPTW)是在VRP问题上加了客户要求访问的时间窗口（如邮政投递、火车及公共汽车的调度等）。先后有一般启发式算法和神经网络、遗传算法、禁忌搜索和模拟退火等智能化启发式算法。还有仿生算法，如模拟鸟群飞行的粒子群算法，有着个体数目少、计算简单、鲁棒性好等优点，在各类连续空间优化问题上均取得非常好的效果。以及蚁群算法。 有时间窗车辆路径问题的描述及数学模型：

有L项运输任务（以i表示），i=1,2…L，已知任务i的客运量为g，配送中心有m辆相同型号的车辆，车辆容量为q，对每辆车执行的任务点有∑gi≤q;同时，每项任务都要在规定时间内完成，完成任务i需要的时间为Ti，任务i的开始时间si要在一定的时间范围[ETi,LTi]内，边界分别为任务i的最早开始时间和最晚开始时间；若在车辆行驶线路上任务i为任务j的前驱，车辆由i行驶到j需要时间tij,则有sj=(si+Ti+tij)成立；问题的优化目标为求解满足客运量要求的费用（所需车辆或时间、距离等产生的运输成本）最小的车辆调度方案。 定义变量：

xijk

1 车辆k从点i行驶到点j={

0 否则

1 点i的任务由车辆k完成yki={

0 否则

cij：从点i到点j的运输成本 rk：车辆的最长工作时间

数学模型如下：

LL

minZ=∑Li=0∑j=0∑k=1cijxijk Ls.t. ∑mk=1∑j=1x0jk≤m

L

∑mk=1∑i=0xijk=1 j=1…L L∑m∑K=1j=0xijk=1 i=1…L LmL∑mk=1∑i=1x0jk−∑k=1∑j=1xj0k=0

∑LI=1giyki≤q S0=T0=0

L∑mK=1∑i=0xijk(si+Ti+tij)=sj j=1…L L∑Li=0∑j=0xijk(tij)≤rk k=1…m

蚁群算法的基本规则按照固定的模式更新信息量和确定路径选择

概率，忽略算法搜索的实际状态，往往产生加速收敛和防止早熟、停滞现象的矛盾。因此采用根据搜索状态动态调整算法路径选择策略和信息量更新策略，以求在加速收敛和防止停滞之间取得平衡甚为重要。

粒子群算法中，每个备选解被称为一个粒子，多个粒子共存、合

作寻优，每个粒子根据它自身的经验和相邻粒子群的最佳经验在问题

空间中向更好的位置飞行，搜索最优解。在对典型连续非线性函数使用粒子群算法寻优的经验研究中，发现粒子数与寻优结果的相关性不大；通过自适应修改惯量的方法，可以克服在非常复杂空间寻优时收敛于局部最优解的问题。单VRPTW属于整数规划问题，试验中采用自适应修改惯量的方法，并未能解决收敛于局部最优解的问题。

粒子群算法与遗传算法等其他演化算法的最大不同在于：1.迭代

运算中只涉及初等运算，且运算量非常少；2.每个粒子能直接获取群体历史经验和个体历史经验，比其他方法中使用精英集的方法更有效；3.整个粒子群被分为几个的子群，且子群之间有一定重叠，从而使收敛于局部最优解的几率大大减少。