详情

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

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