基于遗传算法GIS公交线路网优化模型研究

摘要：本文主要研究了城市公交线路网优化策略。城市公交交通问题一直困扰城市一大难题，是为了解决城市公共交通运行问题，改善城市交通运行效率，提高公共交通车辆调度效率，本文提出了基于遗传算法GIS公交线路网优化策略。该策略以地理信息系统（GIS）为平台，遗传算法为空间布局优化模型的公交车交通网优化布局算法。

关键字：遗传算法；地理信息系统；公交线路网

中图分类号：TP183 文献标识码：A文章编号：1007-9599 (2010) 15-0000-02

GIS Bus Line Network Optimization Model Based on Genetic Algorithm

Yuan Hua1,Yu Xinshui2,Tang Weidong3

(1.Southwest Forestry University,Kunming650224,China;2.Forest Resources Management Station of Baoshan,Baoshan678000,China;

3.Forestry Administration Office of Nujiang,Nujiang673100,China)

Abstract: This paper studies the optimization strategy for the city bus lines.Traffic problems in urban public transport the city has been plagued,a difficult problem to solve the problem of urban public transport operation and improve the efficiency of urban transport,vehicle scheduling to improve the efficiency of public transport,this paper presents a genetic algorithm based optimization strategy for GIS bus lines. The strategy for geographic information system (GIS) as a platform,the genetic algorithm optimization model for the spatial layout of the bus transport network optimized layout algorithm.

Keywords:Genetic algorithms;Geographic information system;Bus lines network

随着社会的快速发展，公共交通工具已逐渐成为人们日常出行的主要交通工具，我国各城市的公交系统也迅速发展，公众出行较为通畅、便利。但与此同时，搭乘公交时，乘客也面临着多条线路的选择问题。在这种情况下，研制开发出一个解决公交线路选择问题的自主查询计算机系统，已成为一个非常值得研究与探讨的问题。公交线路选择问题的研究，涉及乘客心理、路段流量、公交容量、换乘耗时、及站点分配等诸多因素。这些因素彼此约束，内在联系较为细微，各种因素难以精确分析并予以量化，处理起来较为复杂。而由于大中型城市的公交线路数、站点数都已达到百、千数量级，数据处理的繁琐性进一步增大了问题本身的难度。

地理信息系统（GIS）是以计算机技术为基础的信息管理技术，它主要是完成空间数据的采集、维护、存储、分析、输出和等功能。GIS和空间分析一方面通过记录地物的坐标值定量化了空间位置，另一方面又通过存储这些地物的属性表格描述了地物特性。它能够全面的分析这些地物的空间关系和相互影响，并能够直观和灵活的显示空间数据和空间分析结果。因此，GIS已经成为解决涉及空间相关问题的唯一方案。目前GIS已经被广泛的应用到各个领域。本文针对城市公交交通问题一直困扰城市一大难题，是为了解决城市公共交通运行问题，改善城市交通运行效率，提高公共交通车辆调度效率，本文提出了基于遗传算法GIS公交线路网优化策略。该策略以地理信息系统（GIS）为平台，遗传算法为空间布局优化模型的公交车交通网优化布局算法。

一、遗传算法

遗传算法（GA）提供了一种受生物进化启发的学习方法。它不再是从一般到特殊或从简单到复杂地搜索假设，而是通过变异和重组当前已知的最好假设来生成后续的假设。在每一步，被称为当前群体（population）的一组假设被更新，方法是通过使用目前适应度最高的假设的后代替代群体的某个部分。这个过程形成了对假设的生成并测试（generate-and-test）柱状搜索（beam-search），其中若干个最佳当前假设的变体最有可能。采用遗传算法主要有以下几个优点：

（一）将搜索过程作用在编码后的字符串上，不直接作用在优化问题的具体变量上，在搜索中用到的是随机的变换规则，而不是确定的规则。它在搜索时采用启发式的搜索，而不是盲目的穷举，因而具有更高所搜索效率。

（二）现行的大多数优化算法都是基于线性、凸性、可微性等要求，而遗传算法只需要适合度信息，不需要导数等其他辅助信息，对问题的依赖性较小，因而具有高度的非线性，适用范围更广。此外还可以写出一个通用算法，以求解许多不同的优化问题。

（三）遗传算法从一组初始点开始搜索，而不是从某一个单一的初始点开始搜索。而且给出的是一组优化解 ，而不是一个优化解，这样可以给设计者更大的选择余地。它能在解空间内充分搜索，具有全局优化能力。

（四）遗传算法具有很强的易修改性。即使对原问题进行很小的改动 （ 比如目标函数的改进 ），现行的大多数算法就有可能完全不能使用 ，而遗传算法则只需作很小的修改就完全可以适应新的问题。

（五）遗传算法具有很强的可并行性，可通过并行计算来提高计算速度， 因而更适用于大规模复杂问题的优化。

二、遗传算法GIS公交线路网优化模型

（一）模型的建立

设城市公交系统共有 个站点，（本问题中 ）， 条公交线路，设站点和线路通过一个3维的0-1矩阵来表达。设

这样该城市的公交网络通过该0-1矩阵能完全表达。

设决策变量为 ，意义为：

则当站点i和j之间无第k条线路时，i和j之间则不能通过第k条线路到达，因此有：

（1）

设起始点为a，目标点为b，我们目的是在在a和b之间插入r个站点 ，使得a， ，b构成一个可到达的线路。即：

（2）

目标函数我们考虑费用最小，时间最小和换乘次数最小三个目标。

设 ，表示线路 是否需要通过 换乘。当 则线路 不换乘；当 则线路 换乘。

则换乘次数最少的目标为

要求时间最小，则有：

其中 为经过站点数， 为坐车时间； 表示换乘时间.二者之和为总时间。设线路a， ，b计算得到费用为Cost，计算方法根据一元制和分段计价制度的规则进行计算总费用最小的目标函数为：

最后得到的总模型为：换乘次数最少

时间最少

费用最小

（3）

对该模型的求解，我们可以根据换乘次数最少得到最优结果，也可以根据时间最少得到最优结果，还也可以根据费用最少得到最优结果。把三种情况下的最好结果都可以提供给顾客考虑，由顾客根据自己的需要选择。当然有的结果会是两种或三种目标最小情况下的解，这样就更好。

（二）模型求解

基于本文前面所提到的遗传算法GIS公交线路网优化模型，设计出公交线路网的求解的流程图如图1所示，同时以地理信息系统（GIS）平台，选取了苏州市公交网络作为实验数据。

三、结束语

为了解决城市公共交通运行拥挤问题，改善城市交通运行效率，提高公共交通车辆调度效率，本文提出了基于遗传算法GIS公交线路网优化策略。构建了公交系统的数学模型，并提出了采用遗传算法求解该模型，该策略以地理信息系统（GIS）为平台，遗传算法为空间布局优化模型的公交车交通网优化布局算法。

参考文献：

[1]徐士伟.等.GIS技术在公共交通规划中的应用[D].同济大学道路与交通工程系硕士学位论文,2000

[2]刘光明,蔡先华.一种城市公交查询的算法及其应用[J].交通运输工程与信息学报,2005,3(2):87-91

[3]曹桂发,傅俏梅.城市交通信息系统的设计研制[J].系统工程理论与实践,1997,(1):105-109

[4]时敬梁,田世峰.遗传算法在公交车辆智能排班系统中的应用研究.人工智能与识别技术,2007(5):1679-1681

资助项目：西南林业大学森林经理学国家林业局重点学科资助（XKZ200901），云南省省级重点建设专业西南林业大学林学专业资助。

第一作者简介

袁华（1978），男，汉族，湖北人，硕士，研究方向：地理信息系统开发。