公交车辆优化调度问题及其单亲遗传算法

《公交车辆优化调度问题及其单亲遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ＣＮ４３－１２５８／ＴＰ计算机工程与科学２０１１年第３３卷第１１期ＩＳＳＮ１００７－１３０ＸＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩＥＮＣＥＶｏｌ．３３，Ｎｏ．１１，２０１１文章编号：１００７－１３０Ｘ（２０１１）１１－００７５－０５＊公交车辆优化调度问题及其单亲遗传算法ＴｈｅＰｕｂｌｉｃＴｒａｎｓｐｏｒｔＤｉｓｐａｔｃｈｉｎｇＰｒｏｂｌｅｍａｎｄＩｔｓＰａｒｔｈｅｎｏ－ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ姚纯，李茂军ＹＡＯＣｈｕｎ，ＬＩＭａ

2、ｏ－ｊｕｎ（长沙理工大学电气与信息工程学院，湖南长沙４１０１１４）（ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｉｃａｌａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＣｈａｎｇｓｈａＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１０１１４，Ｃｈｉｎａ）摘要：公交调度问题是一个典型的组合优化问题。本文结合我国城市公交常用调度模式，兼顾企业利益和乘客利益，建立了以企业收益满意度、乘客候车满意度为目标的公交线路发车频率优化模型，同时设计了一种求解该模型的单亲遗传算法。该算法在个体繁殖过程中引入随机变异步长并且增加中间子

3、群体的迁移、重插入等操作。最后通过具体实例进行验证，仿真结果证实了算法的有效性。Ａｂｓｔｒａｃｔ：Ｔｈｅｂｕｓｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｉｓａｔｙｐｉｃａｌｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ．Ｉｎｔｈｉｓｐａｐｅｒ，ｃｏｍｂｉｎｉｎｇｗｉｔｈＣｈｉｎａ’ｓｕｒｂａｎｐｕｂｌｉｃｔｒａｎｓｐｏｒｔｓｃｈｅｄｕｌｉｎｇｍｏｄｅｌａｎｄｃｏｎｓｉｄｅｒｉｎｇｂｏｔｈｔｈｅｉｎｔｅｒｅｓｔｓｏｆｃｏｍｐａｎｙａｎｄｐａｓｓｅｎｇｅｒｓ，ｔｈｅｂｕｓｓｅｒｖｉｃｅｆｒｅｑｕｅｎｃｙｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅ

4、ｌｉｓｅｓｔａｂｌｉｓｈｅｄｗｉｔｈｃｏｍｐａｎｙｉｎ－ｃｏｍｅｓａｔｉｓｆａｃｔｉｏｎａｎｄｐａｓｓｅｎｇｅｒｗａｉｔｉｎｇｓａｔｉｓｆａｃｔｉｏｎａｓｔｈｅｇｏａｌｓ．Ａｌｓｏａｐａｒｔｈｅｎｏ－ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｔｈｉｓｍｏｄｅｌｉｓｄｅｓｉｇｎｅｄ．Ｉｔｉｎｔｒｏｄｕｃｅｓｔｈｅｒａｎｄｏｍｍｕｔａｔｉｏｎｓｔｅｐｉｎｉｎｄｉｖｉｄｕａｌｒｅｐｒｏｄｕｃｔｉｏｎ，ａｄｄｉｎｇｍｉｇｒａ－ｔｉｏｎ，ｒｅｉｎｓｅｒｔｉｏｎａｎｄｏｔｈｅｒｏｐｅｒａｔｉｏｎｓｉｎｉｎｔｅｒｍｅｄｉａｔｅｓｕｂ－ｇｒｏｕｐｓ．Ｆｉｎａｌ

5、ｌｙ，ｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｖｅｒｉｆｉｅｄｂｙａｃｏｎｃｒｅｔｅｅｘａｍｐｌｅｓ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈｅｓｕｐｅｒｉｏｒｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．关键词：单亲遗传算法；公交车调度；数学模型；变异步长；中间群体Ｋｅｙｗｏｒｄｓ：ｐａｒｔｈｅｎｏ－ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｐｕｂｌｉｃｔｒａｎｓｐｏｒｔｄｉｓｐａｔｃｈｉｎｇ；ｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌ；ｍｕｔａｔｉｏｎｓｔｅｐ；ｉｎｔｅｒｍｅｄｉａｔｅｇｒｏｕｐｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７－１３０Ｘ．２０１１

6、．１１．０１４中图分类号：Ｕ４９２．２；ＴＰ１８文献标识码：Ａ们一直在积极地研究，并提出了各式各样的方法。１引言例如，直接用标准遗传算法、模拟退火算法、粒子群算法求解；贾以霞等针对公交车优化调度提出了改［２～４］公交运营调度是整个公交企业管理业务的核进的遗传算法；谢燕琴等通过自适应调整交叉［５］心，提高我国城市公交的运营调度水平，对于解决和变异概率，提出了自适应遗传算法；张飞舟等大、中城市存在的交通拥挤和环境污染问题具有非通过遗传算法与禁忌搜索法、模拟退火算法、蚁群［１］常重要的意义。随着人工智能算法的发展，学者算法、人工免疫算法等的结合，

7、提出了混合算＊收稿日期：２０１１－０４－１８；修订日期：２０１１－０７－１２通讯地址：４１０１１４湖南省长沙市长沙理工大学云塘校区电气与信息工程学院研究生信箱Ａｄｄｒｅｓｓ：ＭＳＭａｉｌｂｏｘ，ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｉｃａｌａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＹｕｎｔａｎｇＣａｍｐｕｓ，ＣｈａｎｇｓｈａＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈ－ｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ４１０１１４，Ｐ．Ｒ．Ｃｈｉｎａ７５［６～９］法。但是，由于公交车调度这一问题实验数据第ｉ时段的发车间隔；ｗｉｊ表示第ｉ时段

8、第ｊ车站乘难以获取、数学模型难以建立、约束条件较多，至今客到达率（人／分钟）；ｓ表示某公交线路总公里数；没有得到很好的解决。文献［１０］提出的单亲遗传α、β分别为公交公司和乘客消