徐奔

摘要：針對(duì)城市公共自行車系統(tǒng)的現(xiàn)狀，通過逐步遍歷找到每個(gè)站點(diǎn)的最優(yōu)規(guī)劃方案，然后對(duì)站點(diǎn)分類并根據(jù)區(qū)域內(nèi)公共自行車站點(diǎn)的分布圖，將規(guī)劃路線問題擬化為TSP問題，并用普里姆算法生成最小生成樹解決該問題，對(duì)路線進(jìn)行多次優(yōu)化，得出最終結(jié)果。并用價(jià)值模型對(duì)優(yōu)化前后路線進(jìn)行比較。最后通過實(shí)例，驗(yàn)證了所設(shè)計(jì)的模型和算法取得了預(yù)期的效果，證明了所用算法符合該模型的求解，且通過該模型所求得的規(guī)劃方案是合理的。

關(guān)鍵詞：逐步遍歷；TSP問題；最小生成樹；普里姆算法；多次優(yōu)化

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）14-0098-03

Abstract：The status of the city public bicycle system， and gradually to traverse through to find the optimal planning of each site and then on the site classification and according to the regional public self station distribution map， the route planning problem simulation as traveling salesman problem （TSP）， and prim algorithm to generate the minimum spanning tree to solve the problem， the route was optimized for many times， to obtain the final results. The comparison of the route before and after optimization is made by the value model.. Finally through an example to verify the model and the algorithm designed in this paper has achieved the desired results. It is proved that the algorithm used in this paper conforms to the solution of the model and the model obtained from the planning scheme is reasonable.

Key words：Step through；TSP problem；Minimum Spanning Tree；Prim's algorithm；Several optimization

隨著城市公共自行車的普及，在一定程度上緩解了城市交通壓力，對(duì)節(jié)能減排、減少污染和可持續(xù)發(fā)展有重大意義，城市公共自行車將會(huì)是未來城市發(fā)展的重要區(qū)域。但是，目前城市公共自行車系統(tǒng)也存在著很多不足，例如無法在高峰期滿足用戶的需求。所以，對(duì)城市公共自行站點(diǎn)進(jìn)行再規(guī)劃是非常重要的，不僅能緩解部分交通壓力，還能提升整個(gè)城市公共交通系統(tǒng)的服務(wù)質(zhì)量，最大限度滿足人們對(duì)出行便利性的要求。

城市公共自行車站點(diǎn)規(guī)劃就是在盡可能節(jié)省運(yùn)營成本的前提下，研究對(duì)各個(gè)站點(diǎn)的公共自行車進(jìn)行有效調(diào)配，使之在時(shí)間和空間上達(dá)到均衡的最佳狀態(tài)（即可借還狀態(tài)）。規(guī)劃前期對(duì)站點(diǎn)信息采集可分為站點(diǎn)位置信息采集和站點(diǎn)實(shí)時(shí)數(shù)據(jù)采集，其中位置信息采集通過獲取站點(diǎn)的遍布位置并轉(zhuǎn)換為坐標(biāo)圖；實(shí)時(shí)數(shù)據(jù)采集包括站點(diǎn)當(dāng)前車輛數(shù)、停車位數(shù)量等。通過對(duì)歷史數(shù)據(jù)的計(jì)算，得到每個(gè)時(shí)間段每個(gè)站點(diǎn)所需調(diào)配的自行車數(shù)量，統(tǒng)計(jì)出每次調(diào)配所需的總數(shù)量和各個(gè)站點(diǎn)所需數(shù)量。

1 相關(guān)理論

1.1 TSP問題

旅行商問題（Traveling Salesman Problem，即TSP）：對(duì)于城市[V={v1，v2，…，vn}]的一個(gè)訪問順序?yàn)閇T={t1，t2，…，tn}]，其中[ti=Vi=1，...，n]，且[tn+1=t1]，則問題[minT∈Ωi=1ndti，ti+1]，其中[Ω]為這n個(gè)城市不重復(fù)排列的所有可能回路。求解TSP 問題的常用算法為蟻群算法，該算法是一種自適應(yīng)、正向反饋的方法，可促使整個(gè)系統(tǒng)向最優(yōu)解進(jìn)化。

1.2 普里姆算法

普里姆算法就是從一個(gè)最小的連通子網(wǎng)開始，逐步擴(kuò)大到最小生成樹。即：設(shè) G=（V，E）是連通網(wǎng)絡(luò)，[V={v0，v1，…，vn}]。不失一般性，設(shè)[v0]為起始點(diǎn)，U 是入選子網(wǎng)的頂點(diǎn)集，T 是入選子網(wǎng)的邊集。

[U ={v0}；T =Φ；while（U ≠V ）{ c（ u'， v'）=min∪v∈V U{min∪u∈Uc（u，v）}； T=T∪{（u'， v'）}； U=U∪{v'}}]

2 公共自行車站點(diǎn)規(guī)劃模型構(gòu)建

構(gòu)建公共自行車站點(diǎn)規(guī)劃模型主要分為兩部分：一是每個(gè)站點(diǎn)的規(guī)劃方案，二是整塊區(qū)域的規(guī)劃路線模型。

2.1 站點(diǎn)規(guī)劃方案

站點(diǎn)分類后，得到整塊區(qū)域所有站點(diǎn)的坐標(biāo)圖，將規(guī)劃路線擬化為TSP問題，通過構(gòu)建最小生成樹TSP方案模型來確定整個(gè)區(qū)域的規(guī)劃線路。

通過抽樣計(jì)算，發(fā)現(xiàn)站點(diǎn)之間最近路程約為站點(diǎn)直線距離的[1+32]倍，于是得到：[Dab=（1+3）xa-xb2+ya-yb22]，[Dab]表示[ab]兩點(diǎn)間的近似實(shí)際最短距離。

因?yàn)樾枰?jié)省人力成本，所以將為每個(gè)區(qū)域制定一套合理的路線方案，用最小生成樹解決來解決不重復(fù)的環(huán)形TSP問題。用普里姆算法構(gòu)造最小生成樹。在含有n（n>1）個(gè)頂點(diǎn)的完全連通無向圖中，任意選擇一個(gè)頂點(diǎn)[Vi]作為起始點(diǎn)，在與頂點(diǎn)[Vi]相關(guān)聯(lián)的n-1條邊中，選擇一條權(quán)值最小的邊[ei]，此邊可連接[Vi]及圖中另一個(gè)頂點(diǎn)[Vj]，然后在與[Vi]或[Vj]相關(guān)聯(lián)除[ei]以外的所有邊中，選擇權(quán)值最小的邊[ej]，[ej]又可連接另外一個(gè)頂點(diǎn)（邊的選則還要保證樹中沒有環(huán)的產(chǎn)生）。依次求出所有的可連接n個(gè)頂點(diǎn)的n-1條邊，因?yàn)樵诖松蓸渲械拿恳粭l邊均為不會(huì)生成環(huán)的，且權(quán)值最小的連接頂點(diǎn)的邊，因此這棵生成樹為含有n（n>1）個(gè)頂點(diǎn)的完全連通無向圖的最小生成樹。由于不同類站點(diǎn)之間可能相距很近，所以得到規(guī)劃路線后，需再對(duì)其二次優(yōu)化，即人工優(yōu)化。

通過上述方法得到每條規(guī)劃路線后，計(jì)算每條路線所需時(shí)間，要求每條規(guī)劃路線所花的時(shí)間能在規(guī)定時(shí)間內(nèi)完成，即：[6030000Dab+2N<90]，其中[N]表示每條路線上的公共自行車站點(diǎn)個(gè)數(shù)。

2.3價(jià)值模型

為了進(jìn)一步研究各個(gè)路線是否具有較大的價(jià)值，建立一個(gè)表示該站點(diǎn)不健康度的模型。因?yàn)楦鱾€(gè)站點(diǎn)無論是不能歸還狀態(tài)還是不能借出狀態(tài)都是不理想狀態(tài)，所以將站點(diǎn)剩余車輛等于該站點(diǎn)總車輛數(shù)的一半的情況視作最健康狀態(tài)，而距離這個(gè)狀態(tài)越遠(yuǎn)，表示該站點(diǎn)越不健康。得到站點(diǎn)不健康度[Hi]的關(guān)系式：[Hi=Zi'-Zi]，其中[Hi]表示第[i]點(diǎn)的不健康度；[Zi']表示第[i]點(diǎn)的實(shí)際可租自行車輛數(shù)；[Zi]：表示第[i]點(diǎn)的最佳可租自行車輛數(shù)。

然而這個(gè)不健康度就是表示需要管理的量，所以價(jià)值[Vi]可表示為：[Vi=HiLi]，其中[Vi]表示去第[i]服務(wù)點(diǎn)的價(jià)值；[Li]表示去[i]站點(diǎn)的距離。整個(gè)方案線路的總價(jià)值可以表示為：[V?=HiL?]

3 實(shí)證分析

根據(jù)上述公共自行車規(guī)劃模型，現(xiàn)以某市某小區(qū)某站點(diǎn)為例進(jìn)行規(guī)劃模型的驗(yàn)證，其中每個(gè)站點(diǎn)都編有數(shù)字代號(hào)。

1）建立公共自行車站點(diǎn)的位置坐標(biāo)圖，用不同顏色區(qū)分，如圖1所示。綠色點(diǎn)表示平淡區(qū)，代表基本能保持借還平衡，所以每天只需去規(guī)劃一次。紫色點(diǎn)表示生活區(qū)，紅色點(diǎn)表示工作區(qū)，代表每天需要規(guī)劃兩次，且時(shí)間都在早上和傍晚。

2）利用MATLAB求解，得到各區(qū)域的一個(gè)較優(yōu)的回路方案，黃色回路表示管理工作區(qū)的站點(diǎn)路線，紅色回路表示管理生活區(qū)的站點(diǎn)路線，藍(lán)色回路表示管理平淡區(qū)的站點(diǎn)路線。同時(shí)，可以發(fā)現(xiàn)每個(gè)方案的路線都會(huì)出現(xiàn)幾個(gè)其他方案的點(diǎn)，可對(duì)其進(jìn)行優(yōu)化，結(jié)果如圖2所示。

3）將各路程上的站點(diǎn)帶入公式

4 結(jié)束語

本文旨在研究公共自行車站點(diǎn)選址規(guī)劃和調(diào)度優(yōu)化方法，并將優(yōu)化結(jié)果再進(jìn)行人工優(yōu)化，通過比較得到最好的規(guī)劃模型，從而降低了規(guī)劃時(shí)間和運(yùn)行成本，使公共自行車站點(diǎn)能最大程度滿足市民的需求。通過研究，創(chuàng)新公共自行車系統(tǒng)運(yùn)營管理的體制和保障措施，就能更好地促進(jìn)公共自行車系統(tǒng)及城市公共交通的進(jìn)一步發(fā)展。

參考文獻(xiàn)：

[1] 李黎輝，陳華，孫小麗.武漢市公共自行車租賃點(diǎn)布局規(guī)劃[J].城市交通，2009，7（4）：39-44.

[2] 王劍文，戴光明，謝柏橋，等.求解TSP問題算法[J].計(jì)算機(jī)工程與科學(xué)，2008（30）：72-75.

[3] Krykewycz Gregory R，Puchalsky Christopher M，Rocks Joshua. Defining a Primary Market and Estimating Demand for Major Bicycle-Sharing Program in Philadelphia，Pennsylvania[J]. Transportation Research Record. Octobe，2010：117-124.

[4] Kalten brunner Andreas， Meza Rodrigo， Grivolla Jens. Urban cycles and mobility patterns： Exploring and predicting trends in a bicycle-based public transport system [J]. Pervasive and Mobile Computing，August，2010：455-466.

[5] Maria Bordagaray， Angel Ibeas， Luigi dellOlio*. Modeling user perception of public bicycle services [J]. Procedia - Social and Behavioral Sciences， 2012：1308-1316.

[6] 潘海嘯，湯謁，犮賢敏，等.公共自行車交通發(fā)展模式比較[J]. 城市交通，2010，11（6）：40-4.

[7] Liu Xingcai， Rui Song， Li Zhen， et al. Thought of Bicycle Traffic Development under Low - Carbon Background[C]. Proceedings of the Third International Conference on Transportation Engineering，2011：3280-3285.

[8] 余詳宣，崔國華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)[M]. 2版. 武漢：華中科技大學(xué)， 1998.

[9] 喻菡.遺傳算法的求解TSP 的研究[D]. 成都： 西南交通大學(xué)，2006： 12-15.