一种用于计算城市公交时刻表的复合遗传算法

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

一种用于计算城市公交时刻表的复合遗传算法　

张明辉，牛惠民　

ＺＨＡＮＧ　Ｍｉｎｇｈｕｉ，ＮＩＵ　Ｈｕｉｍｉｎ　兰州交通大学交通运输学院，兰州７３００７０　

Ｓｃｈｏｏｌ　ｏｆ　Ｔｒａｆｆｉｃ　ａｎｄ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ，Ｌａｎｚｈｏｕ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ　７３００７０，Ｃｈｉｎａ　

ＺＨＡＮＧ　Ｍｉｎｇｂｕｉ，ＮＩＵ　Ｈｕｉｍｉｎ．Ｓｐｅｃｉａｌ　ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｃｏｍｐｌｅｘ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｏｎ　ｃａｌｃｕｌａｔｉｏｎ　ｏｆ　ｃｉｔｙ　ｂｕｓ　ｔｉｍｅｔａｂｌｅ．　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１１，４７（２０）：２１０－２１３．　

Ａｂｓｔｒａｃｔ：Ｃｏｎｍｄｅｆｉｎｇ　ｔｈｅ　ｃｒｏｗｄｅｄ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ｔｈｅ　ｐａｓｓｅｎｇｅｒｓ　ａｒｒｉｖａｌ，ａｎｄ　ｔｈｅ　ｎｉｎｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｏｆ　ｔｈｅ　ｂｕｓｅｓ，ｔｈｅ　ｍｏｄｅｌ　

ｏｆ　ｔｈｅ　ｂｕｓ　ｔｉｍｅｔａｂｌｅ　ｉｓ　ｅｓｔａｂｌｉｓｈｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ｔｈｅ　ｍｏｄｅｌ，ａｎ　ｏｒｄｅｒｌｙ　ｉｎｔｅｇｅｒ－ｃｏｄｅｄ　ｇｅｎｅｔｉｃ　

ａｌｇｏｒｉｔｈｍ　ｉｓ　ｄｅｓｉｇｎｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ，ａｎｄ　ｉｔ　ｉｓ　ａｌｓｏ　ｉｍｐｒｏｖｅｄ　ｂｙ　ｍｅａｎｓ　ｏｆ　ｃｏｍｂｉｎｉｎｇ　ｖａｒｉｏｕｓ　ｗａｙｓ　ｏｆ　ｓｅｌｅｃｔｉｏｎ　ｏｐｅｒａ—　

ｔｉｏｎ　ａｎｄ　ｃｏｍｐａｒｉｎｇ　ｗｉｔｈ　ｔｈｅ　ａｂｓｏｌｕｔｅ　ｖａｌｕｅ　ｏｆ　ｃｒｏｓｓｏｖｅｒ　ｏｐｅｒａｔｉｏｎ．Ｔｈｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｂｕｓ　ｎｕｍｂｅｒ　ｃａｎ　ｂｅ　ｏｂｔａｉｎｅｄ　ｔｈｒｏｕｇｈ　ａ　

ｃａｓｅ　ｓｔｕｄｙ　ｗｈｉｃｈ　ｍｅｅｔｓ　ｔｈｅ　ｄｅｍａｎｄｓ　ｏｆ　ｔｒａｎｓｉｔ　ｅｎｔｅｒｐｒｉｓｅｓ　ａｎｄ　ｐａｓｓｅｎｇｅｒｓ．Ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｂａｌａｎｃｅｄ　ｄｅｐａｒｔｕｒｅ，ｔｈｅ　ｒｅｓｕｌｔ　ｉｓ　

ｍｏｒｅ　ｒｅａｓｏｎａｂｌｅ，ａｎｄ　ｉｔ　ａｌｓｏ　ｄｅｍｏｎｓｔｒａｔｅｓ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｅｆｆｉｃｉｅｎｔ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｂｕｓ　ｔｉｍｅｔａｂｌｅ　ｐｒｏｂｌｅｍ．　

Ｋｅｙ　ｗｏｒｄｓ：ｏｒｄｅｒｌｙ　ｉｎｔｅｇｅｒ－ｃｏｄｅｄ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｂｕｓ　ｔｉｍｅｔａｂｌｅ　

摘要：针对公交时刻表设计问题，考虑客流到站的拥挤特征，结合公交车辆运行和乘客到站的时间约束，建立公交时刻表的优　

化模型。针对模型的特点，设计有序整数编码的遗传算法，对遗传操作进行改进，采用多种方式相结合的选择操作，以及绝对值　

比较法的区域交叉操作。通过实例测试，在满足公交企业和乘客需求的前提下，得到最优发车车次和车辆在起点站的发车时刻，　

并结合均衡时刻发车的结果，表明该算法能够有效地解决城市公交时刻表的优化问题。　

关键词：有序整数编码；遗传算法；公交时刻表　

ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２．８３３１．２０１１．２０．０５９　文章编号：１００２．８３３１（２０１１）２０．０２１０—０４　文献标ｉ｝ｃ码：Ａ　巾Ｉ冬１分类　：ＴＰ３０１．６　

１　引言　

在城市公共交通系统中，编制运营调度计划是运营组织　

的基础，而公交运营组织计划的核心是编制公交时刻表。公　

交时刻表是公交企业组织车辆运营的具体作业计划，指导着　

公交运营的全过程，是公交企业管理的基础，是公交企业提供　

优质服务的关键因素。公交时刻表设计的好坏直接影响到线　

路上公交车辆的调度，进而影响乘客的出行和公交企业的效　

益，是公交企业重点关注的运营环节之一。因此，在城市公交　

网络中，设计合理的公交时刻表是至关重要的。　

对于公交时刻表设计问题，国内外的学者都进行了深入　

的研究。文献【１】给出了基于均衡发车条件下，编制公交时刻　

表的离散方法。文献［２】以客车容量和费用为约束，提出了改　

进公交时刻表的离散方法，以图解法来计算发车时刻。文献　

［３】考虑了车辆成本和乘客等待时间等因素，提出了确定发车　

频率的公式，但是其给出的公式是个连续函数，与实际公交调　

度情况存在冲突，缺乏实用性。文献［４】给出的动态调度优化　

模型，考虑了车辆运行、客流变化等因素的干扰，保证了行车　

间隔和车辆的载客均匀，但不能保证公交企业效益的最大　

化。文献［５】给出了一种基于乘客满意度约束条件下的车辆运　行最短算法。文献［６】提出了一种公交　度中行车时刻表的编　排算法，是在单位时间内的行车频率确定的基础上，对行车时　

刻表进行优化。文献［７］采用遗传算法对公交车运用调度进行　

了优化，但未考虑城市公交运行中乘客的需求影响。上述研　

究都是从某个方面研究公交时刻表的没汁，而实际的公交时　

刻表设汁是多目标非线性优化问题，应充分考虑公交线路状　

况、乘客到站情况及ＯＤ需求、车辆运行时间和公交企业运营　

成本等因素，其求解较为复杂。　

本文在既有研究成果的基础上，考虑乘客到站的拥挤现　

象，结合车辆运行时间和乘客到站时问的约束，建立公交时刻　

表模型。重点是根据建立模型的特点，没计有序整数编码的　

遗传算法，并对算法进行改进，计算公交时刻表。　

２模型构建　

在城市公交运营过程中，公交企业希望投入　可能少的　

车辆，减少运营成本，又希望运行车辆有尽可能大的满载率，　

以提高效益；同时乘客则希望公交企业提供方便舒适的条件，　

满足自身出行的需要，这两个方面既存在矛盾而又相互联系。　

最小化乘客的车站等待时问，既是满足乘客出行需求的　

基金项日：国家自然科学基金（ｔｈｅ　Ｎ￣ｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．５０９６８００９）；教育部高等学校博士点基金项目　（Ｎｏ．２００９６２０４１１０００３）。　作者简介：张明辉（１９８４一），男，硕士研究生，主要研究方向：交通规划与管理；牛惠民（１９６３一），男，教授，博士生导师。Ｅ－ｍａｉｌ：ｚｍｉｎｇｈｕｉ１２６＠１６３．ｃｏｍ　收稿日期：２０１０．０９—１４；修四日期：２０１０—１２—０３

　张明辉，牛惠民：一种用于计算城市公交时刻表的复合遗传算法　

体现，又是公交企业效益最大化的具体化。本文以调度时段　

内，乘客在站等待时间最少建立目标函数，目标函数如下：　

ｆ　’　’，Ｅ（　，　’　］　∑ｋ　ｎ∑－｜∑ｎ－ｉ　ｆ∑∑∑　Ｊ　

，　ｆ∈　，Ｅ　’　Ｄｉ，ｉ＋ｓ（ｔ）（ＤＴ／一ｔ）ｄｔ＋　

Ｄｉ，ｉ＋ｓ（ｆ）（Ｄ　一ｔ）ｄｔ　

Ｓ．ｔ．　１　Ｄ　ｉ＝以　ｉ＋ｍａｘ｛ａ・∑　・∑　”），ｉ＝２，３，…，　—Ｉ；　』＝ｌ　＝Ｉ　－，＝１，２，…，后　（１）　

＝Ｄ　＋Ｒ卜　，ｉ＝２，３，。一，ｈ一１；　＝１，２，…，ｋ　（２）　

ｆ—ｌ　＝　一∑Ｂ，１．　，ｉ＝２，３，…，ｎ一１；　＝ｌ，２，…，ｋ　（３）　ｆ＝Ｉ　

＝ｍｉｎ｛Ｒ｝＋∑【　Ｊ　ＤＩ’“　（　ｄ妇，ｃ），ｆ＿１，２，…，　。ｆ　（　，。　

一１；　＝１，２，…，尼　（４）　

＝　Ｉ　Ｄｉ’　（０ｄｔ，ｉ＝１，２，…，　一１；　＝１，２，…，　

ｔＥｔＥ　．Ｅ　１　ｎ—ｆ；　＝１，２，…，ｋ　（５）　

”　＝　：）・ｏｒ；＋【ｌ－Ｉ　

ｍａｘ｛ｈｉ∑』Ｄｉ，ｉ＋ｓ（ｔ）ｄｔ＜Ｃ－Ｒ￣｝　（６）　

ｒＥ（　，棚　

＝ｃ一　一∑　』Ｄｉ，ｉ＋ｓ（ｔ）ｄｔ　（７）　。，　！　，Ｄ　

式中，ｉ为站点；Ｊ为车辆；　为公交线路上站点的数目；ａ、　

为单个乘客平均下车和上车所花费的时间；ｋ为调度时段内　

的发车次数；Ｃ为车辆额定载客人数；，（－）为符号函数；Ｒ　为　

车辆在相邻站点间的运行时间；　为第　辆车到达ｉ站的时　

刻；Ｄ　为第　辆车离开ｉ站的时刻；Ｄｉ，ｉ＋ｓ④为动态客流需　

求，表示ｔ时刻从ｉ站前往ｉ＋ｓ站的乘客人数；Ｐ　为第．，辆车　

离开ｉ站时车上的乘客人数；Ｒ；为第，辆车上的乘客到达ｉ站　

下车后，车上剩余的乘客人数；曰ｉ，’　为第　辆车离开ｉ站时，　

前往ｉ＋ｓ站的候车乘客ｅｅ可上车的人数；Ｅ，ｉ’　为前往ｉ＋ｓ站　

能乘上第，辆车的乘客最晚到达ｉ站的时刻，早于或等于该时　

刻到达车站的乘客均能乘上当前到站辆车。　

模型的目标函数由两部分构成，第一部分统计乘上首班　

车的乘客所产生的等待时间，第二部分统计首班车以后所有　

乘客所产生的总等待时间。　

约束条件中，式（１）表示第，辆车离开ｉ站的时刻等于到　

达时刻与车辆在站停留时间之和；式（２）表示车辆到达车站的　

时刻等于车辆在前站的发车时刻与车辆在相邻站点运行时间　

之和；式（３）表示当第，辆车上的乘客到达ｉ站下车后，车上剩　

余的乘客人数等于第，辆车离开前站时车上的乘客人数减去　

在站下车的乘客人数；式（４）表示第　辆车离开ｉ站时车上的　

乘客人数，或等于车辆剩余人数与所有等待及车辆停留期间　

到站人数之和，或等于车辆的额定载客人数，即二者中的最小　

者；式（５）表示所有到达ｉ站前往ｉ＋ｓ站的乘客能够乘上第＿，　

辆车的人数；式（６）表示车辆临界时刻；式（７）为符号函数，表　示如果所有在站等待和到达的人数　Ｉ　Ｄ“　（ｔ）ｄｔ小于　－　（　！　，Ｄ　或等于Ｃ—Ｒ：，　＝１，所有乘客均可上车，ｉ站前往ｉ＋ｓ站第　

辆车的临界时刻为第，辆车离开ｉ站的时刻；如果所有在站　

等待和到达的人数　Ｉ　Ｄｉ，ｉ＋ｓ（ｔ）ｄｔ大于Ｃ—Ｒ　，　＝０，则　－　Ｊ　ｅ（　，。　只有部分乘客能乘上第，辆车，本文假定所有乘客分别到站，　

并按先到先上车的原则上车，则第，辆车的临界时刻为能够　

乘上第＿，辆车的最后一个乘客的到达ｉ站的时刻。　

３基于有序整数编码的改进遗传算法设计　

３．１遗传编码　

在遗传算法的创始人Ｈｏｌｌａｎｄ教授的工作中，采用了二进　

制字符串编码方法，其也是遗传算法中最常用的编码方法。　

但是由于Ｈａｍｍｉｎｇ悬崖的存在，二进制编码对函数优化问题　

存在严重的缺陷嘲。因此，针对本文提出的公交时刻表优化模　

型，采用整数编码方法，可以避免Ｈａｍｍｉｎｇ悬崖造成的影响，　

而且解的形式更加充实，适当扩大了可行解的范围，增加全局　

搜索的能力。　

以整数编码为基础，公交调度时段内总发车次数表示染　

色体的编码长度，染色体基因位的值由调度时段与发车最小　

间隔的比值中不重复的整数随机确定，然后将所有基因位上　

的值按从小到大顺序排序，经过解码后，每个基因位的值表示　

调度时段内，相应车辆在首站的发车时刻。例如取调度时段为　

１２０　ｍｉｎ，以０．５　ｒａｉｎ为最小发车间隔，则共有２４０个发车点。假　

定在该调度时段发车次数为３５，则分别从１，２，…，２４０中选取　３５个不重复的整数，并按从小到大排序组成一条染色体，如３，　

７，１０，１３，…，经过解码操作后，该染色体表示车辆在首站的发　

车时刻依次为第１．５　ｒａｉｎ，３．５　ｒａｉｎ，５　ｒａｉｎ，６．５　ｍｉｎ，…。