公交网络设计问题及其遗传算法

摘要

公交网络设计问题(Bus Network Design Problem)是为应对都市日益增加的出行需求而进行的交通网络优化问题,是运筹学中经典的优化问题。
　　遗传算法是一种模拟自然界生物进化的搜索算法,由于它具有很强的全局搜索能力和较好的鲁棒性而成为求解公交网络设计问题的有效方法。本文介绍了遗传算法的基本理论,基于接运公交网络和干线公交网络设计问题的特点提出了改进的混合遗传算法。为了自由应用两点间的可行路径和最短路径,又设计了一种能够给出全部可行路径的最短路径算法。
　　本文将遗传算法和公交网络设计问题结合起来,建立了基于最小花费的公交网络问题的数学模型,根据问题可行解的结构,提出相应的混合遗传算法,该算法采用优先权编码通过解码得到可行解,再通过改进的交叉、变异方法得到较优解,从而实现该问题的求解。最后,实证分析验证了应用改进的遗传算法求解公交网络设计问题的有效性和可行性。
　　全文共分五章:
　　第一章,介绍了公共交通的发展历程,接运公交网络和干线公交网络设计问题的背景及目前的研宄现状。另外,还简单介绍了遗传算法的理论知识。
　　第二章,提出了基于可行路径的最短路径算法及算法的详细步骤。与传统的Dijkstra算法和Hoyd算法相比,本算法不仅能够给出任意两点间的最短路径及距离,而且能够给出任意两点间的所有可行路径及其距离。因而在处理突发道路事故等交通实际问题中更具有应用价值。
　　第三章,研宄接运公交网络设计问题。基于最短路径和中垂线分区两种聚类方法,以乘客、公交公司和轨道交通运营者三方的总花费最小为目标函数,通过改进的染色体编码和遗传操作策略方法,成功解决了多对一模式下的接运公交网络设计问题,有效化解了公交线路重叠和服务交叉问题。另外,还考察了线路长度和乘客需求对公交线路条数、发车频率和总花费等网络性能指标的影响。实例说明,基于分区聚类方法的接运公交网络设计方案不仅能够完全覆盖服务区域,而且有助于消除线路冗余,降低总花费。
　　第四章,研宄干线公交网络设计问题,同时结合线路设计和频率设置,通过可行路径算法和混合遗传算法,以乘客的总运行时间和换乘次数的加权和最小为目标函数,分析研宄了城市外围居民区的干线公交网络设计问题。通过实例的计算验证了算法的可行性和有效性。
　　第五章,总结。

目录

封面

声明

目录

中文摘要

英文摘要

第 I 章 绪 论

1 .1城市公共交通发展历程及研究意义

1.2 接运公交网络设计问题

1.3 干线公交网络设计问题

1 .4遗传算法的基本理论

1 .5本文主要工作

第 2 章可行路径算法

2 .1预备知识

2 .2算法步骤

2 .3实例分析

第 3 章基于分区聚类方法求解接运公交网络设计问题

3 .1问题及假设

3 .2数学模型及其意义

3 .3分区聚类方法

3 .4遗传算法设计

3 .5实证分析

3 .6结论

第 4 章干线公交网络设计问题及其遗传算法

4 .1数学模型的建立

4 .2混合遗传算法的一般方案

4 .3初始化方法及遗传操作

4.4 实证分析

4 .5结论

第 5 章总结

参考文献

攻读硕士学位期间发表的论文

致谢