胡泓鑫

摘要：本文要解決的問(wèn)題是以2013年6月6日至8日在四川省成都市舉行的財(cái)富全球論壇為背景而提出的。作為一個(gè)現(xiàn)代化國(guó)際大都市，通暢、便利的公交系統(tǒng)是暢行于成都市的基本保障。公交系統(tǒng)不但包括乘車人和公交公司，公交車生產(chǎn)廠商也是參與公交系統(tǒng)構(gòu)建的重要部分。一方面，越來(lái)越多的居民選擇公交出行，必然會(huì)面對(duì)出行方式與路線選擇的問(wèn)題。如何快速、高效地從眾多的可行路線中選出最優(yōu)路線成為了解決居民出行問(wèn)題的關(guān)鍵。為滿足公眾查詢公交線路的選擇問(wèn)題，本文旨在研究開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)，其系統(tǒng)的核心是線路選擇的模型與算法。另一方面，作為提供公交車的生產(chǎn)商，假設(shè)其存在三個(gè)生產(chǎn)部門，分別生產(chǎn)新能源公交車、天然氣動(dòng)力公交車和汽油動(dòng)力公交車。其在選擇生產(chǎn)何種公交車時(shí)也面臨諸多約束，如何選擇產(chǎn)量與降低成本的研發(fā)活動(dòng)使得總體利潤(rùn)最大化也是本文的研究重點(diǎn)之一。

關(guān)鍵詞：轉(zhuǎn)乘次數(shù) 廣度優(yōu)先算法 利潤(rùn)最大化 遺傳算法

一、論文思路

本文旨在研究乘車人和公交車生產(chǎn)廠商的利益最大化行為，以此為基礎(chǔ)建立了兩個(gè)模型分別模擬兩者的最優(yōu)化解。首先考慮乘車人終端，根據(jù)公交公司提供的既有公交路線，建立模型和算法計(jì)算其出行的時(shí)間和距離最優(yōu)路徑。其次考慮公交車生產(chǎn)廠商終端，根據(jù)政府提供的既有稅收和補(bǔ)貼政策，建立數(shù)學(xué)模型并運(yùn)用遺傳算法計(jì)算出廠商最優(yōu)的生產(chǎn)配置，以最大化其利潤(rùn)。

二、模型一：路徑尋找模型

在傳統(tǒng)的尋求路徑的方法，一般是先將各個(gè)公交路線的站點(diǎn)全部抽取出來(lái)，然后建立一個(gè)圖模型。根據(jù)這個(gè)有向圖，來(lái)求取連通分量，從連通分量中找到來(lái)包含AB站點(diǎn)的值。

對(duì)于成都市來(lái)說(shuō)，可能包含兩種情況：一種情況是A，B都在一條公交路線上，另一種是A，B兩站不在同一條公交路線上，從A到B需要經(jīng)過(guò)轉(zhuǎn)車。

如果按照傳統(tǒng)的算法來(lái)做：首先要建立連通分量（可以通過(guò)深度優(yōu)先搜尋算法來(lái)尋找連通分量），找到包含A，B站點(diǎn)的連通分量，并進(jìn)行標(biāo)記。然后查找連通分量上存在的公交路線。

這種算法能夠達(dá)到效果，但是不是最優(yōu)化的效果，因?yàn)榇嬖谝恍﹩?wèn)題：由于公交站點(diǎn)基本上全部連通，因此時(shí)間復(fù)雜度高。還有就是效率低，因?yàn)榭赡芊祷靥嗟倪B通分量。

我們?cè)偾蠼膺^(guò)程中，并不將其轉(zhuǎn)會(huì)為圖模型，而是直接利用公交路線的本身信息進(jìn)行求解。

下圖就是公交路線信息數(shù)據(jù)的格式：

圖1.1 公交路線信息

因?yàn)楣宦肪€信息中包含了所有的站點(diǎn)名稱，可以直接就查看某點(diǎn)是否包含在某路公交路線中。

程序運(yùn)行結(jié)果：

圖1.2 S0012到S1729站點(diǎn)的直達(dá)路線

對(duì)第二種情況，需要進(jìn)行轉(zhuǎn)車，此時(shí)如果用傳統(tǒng)的算法，更加復(fù)雜。我們的優(yōu)化算法是：先求包含A，B站點(diǎn)的所有公交路線，然后求包含A公交站點(diǎn)的路線L1和包含B公交站點(diǎn)路線的L2之間的公共站點(diǎn)C，如果存在公共站點(diǎn)C，則說(shuō)明可以先乘坐L1到站點(diǎn)C，然后乘坐L2從C站點(diǎn)到底B站點(diǎn)；

對(duì)于運(yùn)行結(jié)果可能包含多條路徑，對(duì)于不熟悉成都地圖的用戶來(lái)說(shuō)，不知道選擇坐那一路線，因此，我們?cè)偾蠼獾耐瑫r(shí)，也要求出每個(gè)條路線經(jīng)過(guò)的總站數(shù)，然后選出最短的路徑推薦給用戶，對(duì)應(yīng)的方法為

其運(yùn)行結(jié)果如下：

圖 1.3 求S2636到S0515站點(diǎn)的路線圖，并得到最短路徑

三、模型二：公交車生產(chǎn)廠商優(yōu)化生產(chǎn)線模型

本文構(gòu)建了一個(gè)基于內(nèi)生成本和稅收差異的公交車廠商生產(chǎn)模型。

首先，假設(shè)一個(gè)公交車廠商存在著三種類型的生產(chǎn)部門。部門0是以其自身利潤(rùn)最大化為目標(biāo)的生產(chǎn)新能源公交車的部門，政府不對(duì)部門0征稅。部門1是以其自身利潤(rùn)最大化為目標(biāo)的生產(chǎn)天然氣動(dòng)力公交車的部門，政府對(duì)部門1征收稅率為的從量稅。部門2是以其自身利潤(rùn)最大化為目標(biāo)的生產(chǎn)普通汽油動(dòng)力公交車的部門，政府對(duì)部門2征收稅率為的從量稅。其中，政府為鼓勵(lì)新能源公交車和天然氣動(dòng)力公交車，對(duì)部門1征稅稅率小于對(duì)部門2征稅稅率，。

其次，令這三個(gè)部門的單位生產(chǎn)成本分別為，依賴于部門成本降低活動(dòng)的投入（如用來(lái)降低成本的研發(fā)R&D花費(fèi)），為了保證從事成本降低活動(dòng)的投入是規(guī)模報(bào)酬遞減（DRS）的，本文令，其中是部門不參與任何降低成本活動(dòng)的初始的單位生產(chǎn)成本。

最后，為保證最大化的二階條件成立，得到內(nèi)點(diǎn)解，并且使得（）成立，我們假設(shè)。

公交車廠商存在著三種不同類型生產(chǎn)部門，各部門生產(chǎn)活動(dòng)分為以下兩個(gè)階段。在第一階段，各部門同時(shí)選擇從事成本降低活動(dòng)（即選擇），從而決定了下一期生產(chǎn)時(shí)的不同的單位成本，部門需為此付出的花費(fèi)為。在此基礎(chǔ)上，第二階段，各部門同時(shí)選擇自己的產(chǎn)出水平。令、、分別表示部門0、部門1和部門2的產(chǎn)量，Q是總產(chǎn)量，。市場(chǎng)上的反需求函數(shù)為，其中，是市場(chǎng)上的價(jià)格，。

三種類型部門的利潤(rùn)分別表示為（），其中

而對(duì)于公交車生產(chǎn)廠商來(lái)說(shuō)，其目標(biāo)是最大化三個(gè)部門的利潤(rùn)之和。廠商的決策變量是

為求解這個(gè)最優(yōu)化問(wèn)題，我們應(yīng)用遺傳算法解決。我們對(duì)參數(shù)賦予特定的數(shù)值，其中，，，，，，。求得收斂序列結(jié)果如下圖，得到公交生產(chǎn)廠商部門1生產(chǎn)新能源公交車498輛，部門1生產(chǎn)天然氣公交車491輛，部門1生產(chǎn)汽油公交車486輛，獲得最大利潤(rùn)2846萬(wàn)元。

遺傳算法求解流程如下圖，我們選取了6維空間中的60個(gè)初始點(diǎn)，進(jìn)行了50次迭代過(guò)程，共得到了3000個(gè)樣本點(diǎn)，得到了收斂的序列、模型要求解的利潤(rùn)最大化值以及廠商對(duì)于產(chǎn)量和成本的選擇。

第一步：隨機(jī)初始化60個(gè)樣本

第二步：對(duì)樣本進(jìn)行基因交叉操作，產(chǎn)生新的解

第三步：對(duì)新產(chǎn)生的基因進(jìn)行基因變異

第四步：根據(jù)適應(yīng)度函數(shù)，對(duì)新的變異基因進(jìn)行選擇，對(duì)于那些不滿足適應(yīng)度函數(shù)的解要淘汰調(diào)，對(duì)于滿足的則保留下來(lái)，作為下一次迭代的初始化解。對(duì)于本次的選擇的函數(shù)，采用的是隨機(jī)遍歷抽樣法，這是一種基于輪盤賭的選擇方法，不過(guò)比輪盤賭選擇方法更加容易選擇出最優(yōu)值的算法。

第五步：重復(fù)1-4步操作，直到收斂為止。

圖2.1 遺傳算法收斂序列

表2.1 最優(yōu)化求解結(jié)果

本文研究發(fā)現(xiàn)在我們的模型假設(shè)下，新能源生產(chǎn)部門由于受到政府稅收政策的保護(hù)和支持，更有激勵(lì)去從事成本降低活動(dòng)，投入更多資金開(kāi)展科技研發(fā)，使自身生產(chǎn)成本低，在市場(chǎng)競(jìng)爭(zhēng)中有了優(yōu)勢(shì)，提高了產(chǎn)量，獲得了更高的市場(chǎng)份額和利潤(rùn)。天然氣動(dòng)力生產(chǎn)部門在開(kāi)展科技創(chuàng)新的同時(shí)降低了一定的生產(chǎn)成本，但由于從事成本降低活動(dòng)的投入很大，加上受到稅收等因素的影響，成本降低活動(dòng)受到一定制約，使得生產(chǎn)成本相對(duì)較高，產(chǎn)量下降。而傳統(tǒng)的汽油動(dòng)力生產(chǎn)部門雖然稅收負(fù)擔(dān)重，但是由于科技含量偏低，從事研發(fā)活動(dòng)的成本低，企業(yè)也會(huì)選擇降低此部門的成本，提高利潤(rùn)。

參考文獻(xiàn)：

[1]李丹，曲玉萍，王曉燕.城市公交出行系統(tǒng)中最優(yōu)路徑算法研究[J]. 交通標(biāo)準(zhǔn)化，2005；11

[2]李曙光，蘇彥民.基于GIS的城市公交路網(wǎng)最優(yōu)路線算法研究[J]. 中國(guó)公路學(xué)報(bào)，2003；7

[3]肖文翀.最優(yōu)公交線路查詢系統(tǒng)設(shè)計(jì)[J].軟件導(dǎo)刊，2012；6

[4]姚春龍，李旭，沈嵐. 公交查詢最優(yōu)路徑搜索的有向賦權(quán)圖模型[J]. 計(jì)算機(jī)應(yīng)用研究，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