徐奔

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：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

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

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

1 相關理論

1.1 TSP問題

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

1.2 普里姆算法

普里姆算法就是從一個最小的連通子網(wǎng)開始，逐步擴大到最小生成樹。即：設 G=（V，E）是連通網(wǎng)絡，[V={v0，v1，…，vn}]。不失一般性，設[v0]為起始點，U 是入選子網(wǎng)的頂點集，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 公共自行車站點規(guī)劃模型構建

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

2.1 站點規(guī)劃方案

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

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

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

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

2.3價值模型

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

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

3 實證分析

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

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

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

3）將各路程上的站點帶入公式

4 結束語

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

參考文獻：

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

[2] 王劍文，戴光明，謝柏橋，等.求解TSP問題算法[J].計算機工程與科學，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] 余詳宣，崔國華，鄒海明.計算機算法基礎[M]. 2版. 武漢：華中科技大學， 1998.

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