成都市公交系统优化问题探索研究

胡泓鑫

摘要：本文要解决的问题是以2013年6月6日至8日在四川省成都市举行的财富全球论坛为背景而提出的。作为一个现代化国际大都市，通畅、便利的公交系统是畅行于成都市的基本保障。公交系统不但包括乘车人和公交公司，公交车生产厂商也是参与公交系统构建的重要部分。一方面，越来越多的居民选择公交出行，必然会面对出行方式与路线选择的问题。如何快速、高效地从众多的可行路线中选出最优路线成为了解决居民出行问题的关键。为满足公众查询公交线路的选择问题，本文旨在研究开发一个解决公交线路选择问题的自主查询计算机系统，其系统的核心是线路选择的模型与算法。另一方面，作为提供公交车的生产商，假设其存在三个生产部门，分别生产新能源公交车、天然气动力公交车和汽油动力公交车。其在选择生产何种公交车时也面临诸多约束，如何选择产量与降低成本的研发活动使得总体利润最大化也是本文的研究重点之一。

关键词：转乘次数 广度优先算法 利润最大化 遗传算法

一、论文思路

本文旨在研究乘车人和公交车生产厂商的利益最大化行为，以此为基础建立了两个模型分别模拟两者的最优化解。首先考虑乘车人终端，根据公交公司提供的既有公交路线，建立模型和算法计算其出行的时间和距离最优路径。其次考虑公交车生产厂商终端，根据政府提供的既有税收和补贴政策，建立数学模型并运用遗传算法计算出厂商最优的生产配置，以最大化其利润。

二、模型一：路径寻找模型

在传统的寻求路径的方法，一般是先将各个公交路线的站点全部抽取出来，然后建立一个图模型。根据这个有向图，来求取连通分量，从连通分量中找到来包含AB站点的值。

对于成都市来说，可能包含两种情况：一种情况是A，B都在一条公交路线上，另一种是A，B两站不在同一条公交路线上，从A到B需要经过转车。

如果按照传统的算法来做：首先要建立连通分量（可以通过深度优先搜寻算法来寻找连通分量），找到包含A，B站点的连通分量，并进行标记。然后查找连通分量上存在的公交路线。

这种算法能够达到效果，但是不是最优化的效果，因为存在一些问题：由于公交站点基本上全部连通，因此时间复杂度高。还有就是效率低，因为可能返回太多的连通分量。

我们再求解过程中，并不将其转会为图模型，而是直接利用公交路线的本身信息进行求解。

下图就是公交路线信息数据的格式：

图1.1 公交路线信息

因为公交路线信息中包含了所有的站点名称，可以直接就查看某点是否包含在某路公交路线中。

程序运行结果：

图1.2 S0012到S1729站点的直达路线

对第二种情况，需要进行转车，此时如果用传统的算法，更加复杂。我们的优化算法是：先求包含A，B站点的所有公交路线，然后求包含A公交站点的路线L1和包含B公交站点路线的L2之间的公共站点C，如果存在公共站点C，则说明可以先乘坐L1到站点C，然后乘坐L2从C站点到底B站点；

对于运行结果可能包含多条路径，对于不熟悉成都地图的用户来说，不知道选择坐那一路线，因此，我们再求解的同时，也要求出每个条路线经过的总站数，然后选出最短的路径推荐给用户，对应的方法为

其运行结果如下：

图 1.3 求S2636到S0515站点的路线图，并得到最短路径

三、模型二：公交车生产厂商优化生产线模型

本文构建了一个基于内生成本和税收差异的公交车厂商生产模型。

首先，假设一个公交车厂商存在着三种类型的生产部门。部门0是以其自身利润最大化为目标的生产新能源公交车的部门，政府不对部门0征税。部门1是以其自身利润最大化为目标的生产天然气动力公交车的部门，政府对部门1征收税率为的从量税。部门2是以其自身利润最大化为目标的生产普通汽油动力公交车的部门，政府对部门2征收税率为的从量税。其中，政府为鼓励新能源公交车和天然气动力公交车，对部门1征税税率小于对部门2征税税率，。

其次，令这三个部门的单位生产成本分别为，依赖于部门成本降低活动的投入（如用来降低成本的研发R&D花费），为了保证从事成本降低活动的投入是规模报酬递减（DRS）的，本文令，其中是部门不参与任何降低成本活动的初始的单位生产成本。

最后，为保证最大化的二阶条件成立，得到内点解，并且使得（）成立，我们假设。

公交车厂商存在着三种不同类型生产部门，各部门生产活动分为以下两个阶段。在第一阶段，各部门同时选择从事成本降低活动（即选择），从而决定了下一期生产时的不同的单位成本，部门需为此付出的花费为。在此基础上，第二阶段，各部门同时选择自己的产出水平。令、、分别表示部门0、部门1和部门2的产量，Q是总产量，。市场上的反需求函数为，其中，是市场上的价格，。

三种类型部门的利润分别表示为（），其中

而对于公交车生产厂商来说，其目标是最大化三个部门的利润之和。厂商的决策变量是

为求解这个最优化问题，我们应用遗传算法解决。我们对参数赋予特定的数值，其中，，，，，，。求得收敛序列结果如下图，得到公交生产厂商部门1生产新能源公交车498辆，部门1生产天然气公交车491辆，部门1生产汽油公交车486辆，获得最大利润2846万元。

遗传算法求解流程如下图，我们选取了6维空间中的60个初始点，进行了50次迭代过程，共得到了3000个样本点，得到了收敛的序列、模型要求解的利润最大化值以及厂商对于产量和成本的选择。

第一步：随机初始化60个样本

第二步：对样本进行基因交叉操作，产生新的解

第三步：对新产生的基因进行基因变异

第四步：根据适应度函数，对新的变异基因进行选择，对于那些不满足适应度函数的解要淘汰调，对于满足的则保留下来，作为下一次迭代的初始化解。对于本次的选择的函数，采用的是随机遍历抽样法，这是一种基于轮盘赌的选择方法，不过比轮盘赌选择方法更加容易选择出最优值的算法。

第五步：重复1-4步操作，直到收敛为止。

图2.1 遗传算法收敛序列

表2.1 最优化求解结果

本文研究发现在我们的模型假设下，新能源生产部门由于受到政府税收政策的保护和支持，更有激励去从事成本降低活动，投入更多资金开展科技研发，使自身生产成本低，在市场竞争中有了优势，提高了产量，获得了更高的市场份额和利润。天然气动力生产部门在开展科技创新的同时降低了一定的生产成本，但由于从事成本降低活动的投入很大，加上受到税收等因素的影响，成本降低活动受到一定制约，使得生产成本相对较高，产量下降。而传统的汽油动力生产部门虽然税收负担重，但是由于科技含量偏低，从事研发活动的成本低，企业也会选择降低此部门的成本，提高利润。

参考文献：

[1]李丹，曲玉萍，王晓燕.城市公交出行系统中最优路径算法研究[J]. 交通标准化，2005；11

[2]李曙光，苏彦民.基于GIS的城市公交路网最优路线算法研究[J]. 中国公路学报，2003；7

[3]肖文翀.最优公交线路查询系统设计[J].软件导刊，2012；6

[4]姚春龙，李旭，沈岚. 公交查询最优路径搜索的有向赋权图模型[J]. 计算机应用研究，2013；4

[5]Anez， J. and Barra， T， Dual Graph Representation of Transport Networks. Transportation Research， Vol.30 （3）， 1996， pp.209-595

[6]Brander J.A. and Spencer B.J. Tariff Protection and Imperfect Competition [M]. Monopolistic Competition and International Trade， Oxford University Press， 1984

[7]Collie D.R. Optimum Welfare and Maximum Revenue Tariffs under Oligopoly [J]. Scottish Journal of Political Economy， 1991

[8]Keechoo， Choi and Wonjae， Jang， Development of a Transit Network from a Street Map Database with Spatial Analysis and Dynamic Segmentation， Vol.8（1-6）， 2000， pp.129-146

[9]Wang L.F.S.， Wang J. and Lee J.Y. Optimum-welfare and Maximum-revenue Tariffs in Mixed Oligopoly with Foreign Competitors [J]. Australian Economic Papers， 2010

[10]Wang L.F.S.， Wang， Y.C. and Zhao L. Privatization and Efficiency Gain in an International Mixed Oligopoly with Asymmetric Costs [J]. Japanese Economic Review， 2009