赵厚宝1 苏勇
（江苏科技大学 计算机科学与工程学院 江苏 镇江 212003）
摘要：城市公交系统是一个巨系统，其相关的模型和方法都非常复杂，为此，本文引入了高性能计算来提高智能算法的优化质量和收敛速度。有机结合遗传算法GA（Genetic Algorithm）和禁忌搜索法TS（Tabu Search）两者优点，构成混合遗传算法HGA（Hybrid Genetic Algorithm）。针对公交车辆调度现状及所处的运营环境，运用HGA的智能化特征，进行了公交车辆智能调度研究。研究表明，基于GA-TS的混合遗传算法优化公交车辆运营调度，能够有效地改善原有公交车辆运营调度的不足，提高动态运营决策效率和服务质量。 关键词：遗传算法；禁忌搜索算法；混合遗传算法；城市公共交通
中图分类号：TP311 文献标识码： B
Optimizing Dispatching of Public Traffic Vehicles in Intelligent Transport
ERP系统设计与开发Systems
Zhao Hou-bao Su Yong
(School of Computer Science and Engineering,Jiangsu University of Science and Technology,Zhenjiang Jiangsu 212003)
Abstract: Urban public transport system is a giant system and its related models and methods are very complicated, this paper, the introduction of high-performance computing to improve the intelligent algorithm to optimize the quality and the convergence rate. The basic principles of Genetic Algorithm (GA) and Tabu Search (TS) are expatiated on. Both of optimizing algorithms are availably integrated into Hybrid Genetic Algorithm (HGA). With regard to actual status and operation environment of Public Traffic Vehicles (PTV), intelligent dispatching of PTV is studied with HGA. The simulation results are demonstrated that intelligent dispatching of PTV could be realized to decision-making and the shortcoming cab be effectively overcome based on GA-TS Hybrid Genetic Algorithm. In the way operation efficiency, traveling safety and service level of PTV are enhanced, the reasonable and viable means are provided for intelligent dispatching of urban PTV.
Key words: Genetic Algorithm; Tabu Search; Hybrid Genetic Algorithm; Urban Public transportation;
1.引言
随着城市社会经济的快速发展，城市交通需求增长迅猛，现有城市交通基础设施已不能适应机动化增长需求，城市交通问题成为城市社会经济发展的重要制约因素。。因此公交车辆的合理运营调度就显得尤为重要。将人工智能方法引入公交车辆运营调度管理中，利用智能算法、调度经验以及专家知识来缩小搜索空间，可以尽快到满意解，形成合理、可行的调度方案。本文采将混合遗传算法HGA（Hybrid Genetic Algorithm）用于公交车辆优化调度研究，以合理解决公交车辆供需矛盾。
2.公交车辆运营调度的GA-TS混合遗传算法设计
遗传算法是一类借鉴生物界的进化规律－适者生存、优胜劣汰遗传机制演化而来的随机搜索算法[1]。公交运营优化问题多参数，多变量，无法通过解析过程求出最优解，我们可以从众多的解中选出最优的解。这也恰好模拟了生物进化的适者生存规律，使得最具有生存能力的染体最大可能地生存下来，这个最具有生存能力的染体就对应于公交运营优化问题_______________________
作者简介：赵厚宝(1978-)，男，汉，安徽六安人，计算机应用技术硕士研究生。苏勇(1961-)，男，汉，江苏镇江，副教授，硕导，主要研究方向，数据挖掘，数据库等。Email: zhaohoubao_01@163
的一个最优解。禁忌搜索算法是一种局部搜索修正算法，模拟人类具有记忆功能的寻优特征。禁忌搜索算法通过局部邻域搜索机制和相应的禁忌准则，来避免重复迂回搜索，并通过期望标准来释放一些机械复制时代的艺术作品
被禁忌的优良个体，进而保证多样化的有效搜索，以此来最终实现全局优化[2]。研究发现，GA是一个渐近的收敛过程，可以极快地达到最优解的90％，但要真正达到最优解却要花很长时间[3]。解决这一问题的一种方法是对简单GA进行适当的改进，如简单GA中增加交叉约束算子，使交叉操作限制在基因型（编码串）相似的染体之间，就能在一定程度上改善GA的局部搜索能力；另一种方法是将GA与传统的、基于问题知识的启发式搜索技术相结合构成HGA框架，从而改善简单GA的局部搜索能力，提高优化质量和搜索效率，以弥补单一优化方法的不足。GA-TS混合遗传算法程序流程框图如图1所示[4]
图1.1GA-TS流程
Fig1.1 The Flowchart Hybrid Genetic Algorithm
3.模型求解
公交车辆调度既要考虑公交公司的利益也要充分考虑乘客的利益，因此设定公交车辆调度问题的目标函数时从以下两个方面考虑：a)从公交公司的角度出发，使公交公司的发车次数最少来保证公司的利益，也即公交公司的运营成本最低。b)从乘客的角度出发，使得全天所有乘客的等车时间最小来保证乘客的利益，也即乘客等车所损失的费用最低[5]。
公交公司的运营成本V是一天的发车次数
1
(/)
k
i k
k
T t
=
功率自行车∑V与此线路的里程L以及每辆车每
公里消耗的单位成本
1
C的乘积：
1/
1
k
K k
K
v C L t t
=
=∑V (3-1)
乘客等车所损失的费用P 是所有乘客的等车时间2kj
111(/2)k m K J k k i j t ===ρ∑∑∑V 与每一个乘客每等待
一个单位时间所相当的损失费用2C 的乘积：
22kj 111(/2)k m K J
k k i j P C t ====ρ∑∑∑V (3-2) 但这两类目标是相互冲突的，两个目标函数就存在一个权值的问题，这体现在目标函数种两项的加权系数的大小。如果希望乘客等车时间比较短，这个时候乘客等车时间的加权系数要大些；反之亦然。于是目标函数为
21/2kj 1111min ()(/2)k m k K J
K k k K k i j f C L t
t C t =====α+βρ∑∑∑∑V V (3-3) 模型的约束条件主要考虑两个方面：a)发车的最小间隔和最大的时间间隔要满足有关部门的规定;b)公交公司要盈利，必须使公交公司所收得的票钱总和要大于公交公司最低的消耗成本，也就是要满足下式：
111/(/)J K ki
k k j K n u T t C L κΚ=1==×>∑∑∑V (3-4)
3.1 符号说明
k 为时段集，{1,...,,...,}k k K =，k 表示第k 个时段；J 为车站集，{1,...,,...,}J j J =，j 表示第j 个车站；k T 表示第k 时段的时间长度；m 表示一天中总的发车车次；kj u 表示第k 时段第j 站上车乘客数；kj ρ表示第k 站的乘客到达率；k ij Φ表示在第j 站上乘坐上第k 时段发的第i 次车的乘客的总等车时间；1C 为每公里每辆公交车消耗的费用；2C 为每个乘客每等待一个单位时间相当的损失费用；α表示公交公司消耗费用的加权系数；β表示乘客等待时间所损失费用的加权系数，加权系数的关系为α+β=1；n 为全程公交票价；L 为线路的总公里数；/k k k m T t =V 表示第k 时段的总发车车次于该时段的时段长度与发车间隔的比值；K k k=1m
m =∑总表示一天中总发车车次为各时段的发车车次之和；kj kj k u /T ρ=表示第k
时段第j 站的上车乘客数与该时段的时段长度的比值；2kj 2k t ρ×⁄V 。其中kj k T ρ×V 为第k 时
段从第j 站上了同一车次的乘客数，因为乘客到站服从均匀分布，则k t 2⁄V 为第k 时段乘客的平均等待时间。
4.仿真研究
根据3建立的目标函数。运用智能算法GA-TS进行公交车辆运营调度方案(公交车辆不同的发车间隔及类型反映着不同的调度方案)的研究.为了使仿真研究尽可能接近实际情况，这里通过性能指标函数式中的惩罚项的不同取值，来反映公交车辆在不同时段的实际运行环境. GA-TS体规模取为60，单点交叉概率为Pc=0.75，变异概率为Pm=0.005，这里采用自然编码方式，全程车为0，快车为1，区间车为2[6-7].经仿真实验研究，结果如图4.1。
图4.1 混合遗传算法
Fig 4.1 Hybrid Genetic Algorithm
以镇江市公交公司某车队4路运营线路为研究对象, 其运营参数设定为：运营车辆发车间隔为8min，每站停靠时间为0.25min，每站间行驶时间为2.9min，为了便于运营调度的研究，本文在平峰时段进行仿真实验研究，这里仅取全程车、快车、区间车等3种类型构成36车次运营车辆，其中36车次中全程车占2/3、快车占1/6、区间车占1/6[8]。经仿真实验研究。最终得到36车次运营车辆编排结果(即调度方案)为000010021001002002001000020000100122。
以上仿真结果可以看出，在采用8min发车间隔时，只需要13辆运营车辆就能够满足一次周转，计算出其周转时间为366.2998min。若投入18辆车，投入该运营调度方案编排，发车间隔只须5.5min即可满足要求。与原来通过经验采用的调度方案(使用18辆车，发车间隔8min，周转时间为385.4min)相比，现在采用的GA-TS中，周转时间节省了19.1min，减少了6辆车。结合3.3.2公式，求的总费用为3697.62元。因此，采用HGA优化算法能够合理分配公交车辆资源，有效调整供需平衡，极大地提高了运输效率[9]。
5.结论
人类工效学
采用最小费用作为目标函数，考虑了车辆配置、时间、运营效率及资源利用等方面因素，通过选择、交叉及变异等遗传操作，得到了最优的调度排序方案，仿真结果表明，利用GA-TS 解决车辆调度问题具有可行性、先进性和快速性。
本文创新点：本文将HGA引入到公交车辆运营调度管理中，利用HGA的智能化特征缩小搜索空间，尽快到满意解，形成合理有效的调度方案。
参考文献
[1] Luc B. and Stefan S. Genetic Algorithms：theory and application[J]. Journal A，1997，38
（2）：13-23.
[2] Barbarrosoglu，Gulay，Ozgur. Tabu Search Algorithm for the Vehicle Routing Problem. Computers
& Operations Research，1999，26（3）：255-270.
[3] Zhang Defu,Deng Ansheng,An effective hybrid algorithm for the problem of packing circles into
a larger containing circle,Computer and Operations Rearch,2005, 32(8):1974-1951.
[4] 蔡延光，钱积新，孙优贤. 智能运输调度系统的设计与实现[J]. 决策与决策系统支持，1996，6（4）：
108-114.教书育人期刊
[5] 石爱菊，周林．公交车优化调度中的几个问题的研究数学的实践与认识2002.3.
[6] 蔡延光，钱积新，孙优贤. 智能运输调度系统的设计与实现[J]. 决策与决策系统支持，1996，6（4）：
108-114.
[7] Glover Fred，Kelly James P. et al. Genetic algorithms and tabu search: Hybrids for
optimization[J]. Computers & Operations Research，1994，22（1）：111-134.
[8] 孙芙灵.公交调度中发车间隔的确定方法的探讨[J].西安公路交通大学学报.1997，17(2B):44-48.
[9] 黄胜忠. 遗传算法在企业车间生产调度中的应用[J].微计算机信息.2008，7-3:266-267.
第一作者简介：赵厚宝（1978－），男，安徽六安人，汉，硕士研究生，计算机应用技术，主要研究
蓝血人作品
方向：数据库系统。
Biography: ZhaoHoubao (1978-),male,Anhui liu’an,the Han nationnality,raduate student,computer application technology,major in:database systems.
导师简介：苏勇（1961-），男，汉，硕导，研究方向：数据库系统，数据挖掘。
Biography:Suyong(1961-),male, the Han nationnality,a tutor of masters degree candidate, major in:database systems,data mining.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议