城市公交车路线选择的 遗传算法卜 雷1 蒲 云2 尹传忠1(1.西南交通大学交通运输学院,成都610031 ;2.西南交通大学研究生院,成都610031)摘 要:针对公交车路线的特点,设计了基于变长度染色体编码的遗传算法,求解固定始发站与终 到站间的公交车路线优化选择问题,并采用了适合该编码方式的遗传算子。关键词:遗传算法 公交车 路线优化Selecting an Urban Bus Route with Genetic AlgorithmBU Lei PU Yun YIN Chuanzhong ( School of Traffic and Transport , Southwest Jiaotong University, Chengdu 610031)Abstract :Based on changing length chromosome coding , the author designs genetic algorithm aimedat the character of the bus route to select an optimal route between the f ixed begin station and end sta2tion , and uses the genetic operators suitable for this coding method.Key words :genetic algorithm , bus , route optimization公交车路径选择问题属组合最优化问题,街道 密度及需求分配复杂性的不断增大使得可行路线空 间指数倍地增大,应用传统的优化方法计算,时间也 会随之以指数倍地增多,很难发挥较高的计算效率。 遗传算法(简称GA)作为一种基于生物遗传和进化 机制的自适应概率优化技术12,同传统的优化算 法如单纯形法、 梯度法、 动态规划法、 分枝定界法以 及近年来应用的性能较好的模拟退火算法(简称SA)相比,具有运算简单、 搜索过程灵活、 搜索效率 高以及隐含并行性等特点,目前已广泛应用于函数 优化、 组合优化、 生产调度、 自动控制、 机器学习、 图 像处理以及人工生命等领域,是一类可用于复杂系 统优化计算的鲁棒搜索算法。本文针对公交车路线的特点,提出应用变长度染色体遗传算法求解固定 始发站与终到站间的公交车路线优化选择问题,以 提高计算效率。1 公交车路线优化选择问题的简 化将公交车非规则形状服务区按照街道间隔和需求分配划分为mn个矩形区域,如图1所示,实线表示可以通行公交车的实际街道,虚线表示禁止通行公交车或实际不存在的街道,区域(i , j)表示方法见图2 ,公交车的可选运行方向见图3 ,则可行的公交车路线由一系列路段和节点构成。21世纪青年学者论坛世界科技研究与发展 2004年2月第52 页 Vol. 26No. 1www . globesci. com图1 服务区划分区域示意图同时为了使研究问题简化,不考虑公交车的停 车位置。2 优化目标记符号Z表示总费用,y ij( i= 1,2, m- 1; j =1,2, n)表示垂直路段状态变量,若连接节点( i , j)和( i+ 1, j)的垂直路段位于公交车路线上 y ij= 1,否则y ij= 0;x ij( i= 1,2, m ; j= 1,2,n- 1)表示水平路段状态变量,若连接节点( i , j)和( i , j+ 1)的水平路段位于公交车路线上x ij= 1,否 则x ij= 0;ij( i= 1,2, m ; j= 1,2, n)表示节 点状态变量,若节点( i , j)位于公交车路线上ij= 1,否则ij= 0; c1表示公交车单位时间运营费用, vb 表示公交车的平均运行速度, Tij表示公交车在节点( i , j) ( i= 1,2, m ; j= 1,2, n)的延误时间,tij表示旅客从区域( i , j)出发至公交车路线的总行程时间, c2表示旅客单位行程费用, w表示区域宽 度, l表示区域长度。则固定始发站与终到站间的 公交车路线优化选择问题的优化目标:minZ=c1(m- 1i= 1nj= 1y ijw b+mi= 1n- 1j= 1x ijl b+mi= 1nj= 1ijTij)+m- 1i= 1n- 1j= 1tijc2(1)式中第一项为公交车运营费用,第二项为旅客 行程费用。3 遗传算法本文结合研究问题的具体特点,构造了适合求 解该优化问题的变长度染色体遗传算法,流程如下:step0 问题编码及参数初始化:确定最大迭代 代数G、 群体规模N、 切断概率Pc、 拼接概率Ps、 变 异概率Pm的值,令迭代代数gen : gen= 0;step1 产生初始群体:随机产生N个变长度 染色体,组成初始群体G0=( g1, g2, gN) ;step2 染色体解码;step3 计算适应函数值,并将染色体按照适应 度降序排列, g1gen为本代群体中的最优染色体编码, gNgen为本代群体中的最劣染色体编码;step4 若迭代代数gen达到最大迭代代数G , 转step10,否则转step5;step5 实施最优保留策略及删除操作:将本代 中最劣染色体编码gNgen替换为上一代中最优染色体编码g1gen- 1,并将群体中有始发节点编号而无终 到节点编号或者无始发节点编号而有终到节点编号 的染色体删除,同时对相同染色体进行 “一个保留、 其余删除” 的操作,删除染色体分别用step1随机产 生的染色体替换;step6 对染色体依概率Pgen( a)执行复制操 作;step7 对执行复制操作后得到的新染色体,根 据概率Pc执行切断操作;step8 对执行切断操作后得到的新染色体,根 据概率Ps执行拼接操作;step9 对执行拼接操作后得到的新染色体,根 据概率Pm执行变异操作,返回step2;step10 结果输出:染色体g1gen对应编码方案即为固定始发站与终到站间的公交车优化路线, Z( a)为最优目标函数值。311 问题编码方法采用变长度的染色体编码方法,每条染色体对 应一条公交车路线方案。染色体a编码为ga=( S1, S2, Sk, SK) , a= 1,2, N , Sk表示服 务区中节点处的公交车运行方向状态,且Sk=( sj1, sj2, sj3, sj4)。基因sj1代表服务区中节点的编号;基因sj2代表公交车在节点处的右行方向选择状态变 量,若选择右行方向sj2= 1,否则sj2= 0;基因sj3代 表公交车在节点处的上行方向选择状态变量,若选 择上行方向sj3= 1,否则sj3= 0;基因sj4代表公交车 在节点处的下行方向选择状态变量,若选择下行方 向sj4= 1,否则sj4= 0。 由于始发站与终到站固定,因此编码时基因S1 表示始发节点处的公交车运行方向状态, SK表示终 到节点处的公交车运行方向状态,并且对于不同的 公交车路线,其染色体长度K值不同。 3. 2 解码处理与适应度评价 将染色体基因型转换为常规遗传算法中的个体 基因型,对于过剩指定的染色体,取最左边的四元组2004年2月 世界科技研究与发展21世纪青年学者论坛www . globesci. comVol. 26No. 1 第53 页解码;对于缺省指定的染色体,基因sj2、sj3、sj4分别 取0、0、0。解码后计算染色体适应度,第gen代群 体中染色体a对应公交车路线方案的优劣通过适应 度Fgena的大小来评价:Fgena= 1/ Z( a)(2)313 遗传操作 对染色体的遗传操作包括复制操作、 切断操作、 拼接操作及变异操作。在复制操作中,采取轮盘赌 法复制N个染色体,根据个体排序决定每个染色体 复制到下一代的概率Pgen( a)。Pgen( a)=( N-a+ 1) /i= 1N= 2( N-a+1) / (1 +N) N (3) 在切断操作中,按均匀分布在(1, K)中随机产 生一个整数作为切断基因位,自该位将执行切断操 作的父染色体切断成为两染色体。例如:对于K= 8父染色体ga=( S1, S2, S3, S4,|S5, S6, S7, S8)在 “|” 处经切断操作后得到两子染色体ga1=( S1, S2, S3, S4)和ga2=( S5, S6, S7, S8)。 在拼接操作中,将首位基因为始发节点运行方 向状态而末位基因非终到节点运行方向状态的染色 体与首位基因非始发节点运行方向状态而末位基因 为终到节点运行方向状态的染色体基因连接在一起 成为一条染色体。例如:对于两染色体ga1=( S1, S2, S3, S4, S5, S6)和ga2=( S9, S10, S11, S12, S13,S14) ,经拼接操作后得到染色体ga=( S1, S2, S3,S4, S5, S6, S9, S10, S11, S12, S13, S14)。为了保持群体内个体的多样性,在完成复制操 作、 切断操作和拼接操作后需对群体内的个体根据 概率Pm执行变异操作:在(1, K)中按均匀分布随 机产生两整数最为变异基因位并互换基因值。4 实例计算与结果分析街道模式为非规则格状结构的服务区(长 宽 = 35) ,划分为60个尺寸相同的区域(lw= 015 015) ,公交车平均运行速度vb= 20 ,公交车在节 点(i , j)的延误时间Tij= 1,公交车单位时间运营费用c1= 50,旅客单位行程费用c2= 3, N= 50, Pc= 0195, Ps= 110, Pm= 0101,分别应用变长度染色体 遗传算法和动态规划方法确定相同始终点间的公交 车优化路线,在同一台计算机上分别运行30次,计 算结果比较见表1。 表1 计算结果比较变长度染色体 遗传算法动态规划方法最优目标函数15331071533107 收敛到同一最优解时的 平均计算时间(min)218611可以看出:应用变长度染色体遗传算法求解,不 仅能够得到与其他优化方法相同的最优解,而且计 算时间也大大缩短。5 结论本文结合城市公交车路线选择的特点,构造了 求解固定始发站与终到站间的公交车路线优化选择 问题的变长度染色体遗传算法,实际数值计算表明 该算法有效可行,而且很好地解决了维数灾难问题, 尤其适合于在大中城市中选择公交车路线。参考文献 1周明,孙树栋.遗传算法原理及应用M.北京:国防工业出版社,20002康立山,谢云等.非数值并行算法() 遗传算法 M.北京: 科学出版社,19983Byrne B. ,Vuchic V. Public transportation line positions and head2 way for minimum cost M. Traffic flow and transportation. Elsevi2er ,New York. 1971 : 3473604Chien S. ,Yang Z. Optimal feeder bus routes on irregular street net2work J . Journal of advanced Transportation. 2000 ,34(2) :213 2485Cndida Mouro M. , Teresa Almeida M. Lower - bounding andheuristic methodsfor a refuse collection vehicle routing problem J .European Journal of Operational Research. 2000 ,121 (45) :420