基于最小點覆蓋的共享單車投放點選取方法*

郝斌斌 呂 斌▲ 陳京榮

(1.蘭州交通大學交通運輸學院 蘭州 730070；2.蘭州交通大學數(shù)理學院 蘭州 730070)

0 引 言

共享單車是指企業(yè)在校園、地鐵站點、公交站點、居民區(qū)、商業(yè)區(qū)、公共服務(wù)區(qū)等提供自行車單車共享服務(wù)，是一種分時租賃模式。共享單車是一種新型共享經(jīng)濟。共享單車就其實質(zhì)是一種新型的交通工具租憑業(yè)務(wù)——自行車租憑業(yè)務(wù)，其主要依靠載體為(單車)自行車?？梢院艹浞掷贸鞘幸蚩焖俚慕?jīng)濟發(fā)展而帶來的自行車出行萎靡狀況；最大化的利用了公共道路通過率。第三方數(shù)據(jù)研究機構(gòu)比達咨詢?nèi)涨鞍l(fā)布的《2016中國共享單車市場研究報告》[1]顯示，截至2016年底，中國共享單車市場整體用戶數(shù)量已達到1 886萬，預(yù)計2017年，共享單車市場用戶規(guī)模將繼續(xù)保持大幅增長，年底將達5 000萬用戶規(guī)模。

共享單車的出現(xiàn)解決城市道路出行的“最后一公里”的問題，帶來了諸多好處：①共享單車極大的方便了城市居民的出行，有效的緩解了一部分城市公共交通的壓力；②共享單車低碳環(huán)保，能夠減少了空氣污染，有利于節(jié)約能源和保護環(huán)境；③共享單車的出現(xiàn)帶活了實體經(jīng)濟，使得飛鴿等一批“老字號”自行車制造企業(yè)也迎來了難得的市場機遇。但是，共享單車在短時間的大規(guī)模增長，相應(yīng)的管理制度缺乏，運營管理經(jīng)驗不足，造成共享單車給城市道路交通環(huán)境帶來新的問題：①共享單車亂停、亂放，使用秩序混亂，造成共享單車的停放侵占城市道路；②共享單車存在人為故意破壞、偷盜、私用等問題；③共享單車企業(yè)運營管理經(jīng)驗不足，使得共享在投放點選取、調(diào)度、維修等方面存在問題，造成共享單車利用不高，用戶體驗有待提高等一系列問題。其中，共享單車的投放點的選取尤為重要，投放的點選取直接會影響共享單車的利用率、調(diào)度和維護等成本問題。如果選取城市交通路網(wǎng)中的所有節(jié)點都作為共享單車的投放點，這樣當然可以解決共享單車的投放問題。但是，共享單車的投放點在選取的過程中要考慮諸多問題，過多的投放點會使得共享單車運營企業(yè)的維護和調(diào)度成本增加，不利于共享單車企業(yè)的長遠發(fā)展；其次，選取過多的投放點會使得本來就緊張的城市道路空間變的更為擁擠，會出現(xiàn)大量的共享單車侵占城市道路，給城市道路交通帶來新的問題。共享單車給居民出行帶來便利的同時又給城市道路交通環(huán)境增加了新的問題，為了更好的協(xié)調(diào)兩者之間的關(guān)系，必須科學合理的確定共享單車在城市道路交通環(huán)境的投放點。

當前文獻對于共享單車企業(yè)在運營過程中存在的具體問題少有相關(guān)的研究。本文旨在利用圖論中最小點覆蓋問題，建立科學合理的共享單車投放點選取方法?，F(xiàn)有文獻對于最小點覆蓋問題的研究有：Neidermeier等[2]提出了一個有效的易處理的固定參數(shù)算法用來求解最小加權(quán)點覆蓋問題；Khuri等[3]將最小加權(quán)點覆蓋問題看做一個約束的組合優(yōu)化問題并引入了遺傳算法；Bouamama等[4]人提出一個基于人群的迭代貪婪算法,該算法可以找到一個包括高質(zhì)量解的區(qū)域；Jovanovi等[5]在此基礎(chǔ)上得到一個改進信息素校正規(guī)則的最小點覆蓋蟻群優(yōu)化算法，此算法可避免算法陷入局部極??；Chlebik[6]在一定限制條件下，采用強冠分解方法給出了最小點覆蓋問題的一個性能比小于2的多項式算法；寇磊等[7]提出了基于最短路算法的最小點覆蓋近似算法，該算法對圖沒有太具體的要求，只要求是簡單圖即可，相應(yīng)頂點的度也沒有任何限制，為算法實際應(yīng)用提供了方便；崔笑川等[8]研究了基于蟻群算法的最小點覆蓋問題，針對賦權(quán)圖改進了算法；楊杰等[9]得到一個最優(yōu)頂點覆蓋的貪心邊近似算法，這種算法比傳統(tǒng)的任意邊算法有更優(yōu)的解；周康等[10]等提出了最小頂點覆蓋的一種閉環(huán) DNA 算法，這種方法是由電泳實驗補集去求解最小頂點覆蓋集；閏興篡等[11]等通過頂點的度權(quán)衡了圖局部結(jié)構(gòu)特征，在偽最小覆蓋點選取啟發(fā)式策略的基礎(chǔ)上設(shè)計了一個近似算法；陳京榮等[12]提出了一種多屬性條件下隨機時間依賴網(wǎng)絡(luò)的路徑選擇算法，這種算法可結(jié)合多重屬性值對交通路徑綜合選擇；陳俊鋒等[13]提出了一種基于熵權(quán)-TOPSIS的水上機場選址模型，為水上機場選址提供了理論依據(jù)。針對共享單車目前存在的問題：夏蕓等[14]以西安市為例構(gòu)建了共享單車需求評估模型，此模型可為共享單車企業(yè)選擇調(diào)度路徑和確定調(diào)配車輛數(shù)提供理論方法；趙曼[15]以共享單車網(wǎng)絡(luò)為研究對象，結(jié)合網(wǎng)絡(luò)特征值和聚類子群情況，建立了共享單車優(yōu)化調(diào)度模型；高楹等[16]分析了北京市共享單車的時空分布特性，提出了一種共享單車空間調(diào)度模型，該模型可在一定程度上解決車輛空間分布不均衡的問題；葉錦程等[17]建立一種基于子群劃分的共享單車調(diào)度模型，此模型可為共享單車企業(yè)車輛調(diào)度提供決策依據(jù)；楊珈惠等[18]提出了一種允許存在局部路徑重復(fù)的共享單車調(diào)度模型，此模型可為共享單車企業(yè)在減少車輛調(diào)度成本方面提供理論支持。

現(xiàn)有的文獻對于共享單車的研究都是基于對已有問題的宏觀分析，并提出了一些合理化的建議和管理措施。少有文獻對于共享單車企業(yè)在運營過程中存在的問題進行建模和量化分析。最小點覆蓋是圖論中的經(jīng)典問題，國內(nèi)外學者對于這方面的研究諸多，提出了多種最小點覆蓋問題的求解算法。因此，筆者在總結(jié)最小點覆蓋問題的求解算法基礎(chǔ)上，研究了一種基于最小點覆蓋的共享單車投放點選取算法。將城市交通路網(wǎng)抽象為圖論中的圖，將各個交通路段的交點抽象為圖的節(jié)點，利用最小點覆蓋問題的求解算法求出圖的不同的點覆蓋方案。定義了各節(jié)點之間路段權(quán)值函數(shù)，并且依據(jù)各個節(jié)點的路段權(quán)值構(gòu)造了節(jié)點間調(diào)度成本的規(guī)范化矩陣，以最小投放點和最小調(diào)度成本為優(yōu)選指標對不同點覆蓋方案進行排序，從排序方案中選優(yōu)得到共享單車投放點的選取方案。給出了算法的具體實現(xiàn)步驟，通過算例的闡釋了算法實現(xiàn)過程及有效性。

1 模型的建立及算法設(shè)計

1.1 最小點覆蓋定義

對圖G=(V,E)，其中：V為頂點集；E為邊集。G的1個點覆蓋是指V的1個子集S，使得E中的每條邊都至少有1個端點在S中。對圖G的1個點覆蓋S，如果G中不存在點覆蓋S′，使得|S′|<|S|，則稱S為G的最小點覆蓋。

對圖G中點和邊都有相應(yīng)的權(quán)值，所以圖G是賦權(quán)圖，最小點覆蓋的問題的目標就是找到圖的頂點的1個子集，使得這個子集是1個點覆蓋，并且這些頂點的權(quán)之和最小。

1.2 基于最短路的最小點覆蓋算法[6]

步驟1。初始化S={u1}，L=T=Φ。

步驟2。S={u1,u2,…,ui}，若子圖H=G-S為孤立點集，則算法停止；若H的連通分支中有完全圖或圈或路，求解相應(yīng)的最小點覆蓋，將其并入S。進一步將H中度為1的鄰點并入集合S，但仍然用頂點ui進行搜索，轉(zhuǎn)步驟2；否則轉(zhuǎn)步驟3。

步驟3。計算允許集L=V-S-{H中的孤立點}，在H中調(diào)用Dijkstra算法計算頂點ui到集合L中各點的最路徑長度duv(v∈L)，并計算最短路徑的最大值d及次大值d′。

步驟4。若dviv=wviv,(v∈L)(其中wviv為邊的權(quán)值)，進一步若子圖H=G-S為完全圖、圈或路的不交并，求解相應(yīng)的最小權(quán)點覆蓋并入S，則可得到圖G的一點覆蓋S，輸出∑ui∈Sw(ui)，算法停止；否則取子圖H=G-S中度最大的點記為ui+1，S=S∪{ui+1}，轉(zhuǎn)步驟2。

步驟5。若dviv≠wviv,(v∈L)，則計算結(jié)合T，按給出的原則在集合T中選出頂點ui+1，S=S∪{ui+1}，轉(zhuǎn)步驟2。

1.3 模型建立

在城市路網(wǎng)中，把共享單車的投放點看作是若干個點，2個投放點之間的交通路徑看作是邊，這樣就可以把城市路網(wǎng)中共享單車投放點的選取問題轉(zhuǎn)換為圖論中最小點覆蓋的問題。也就是找到1個點覆蓋，在滿足條件的情況下盡可能選取最少的點，使得點覆蓋頂點和邊的權(quán)值之和最小。

為使得模型更加切合實際情況，本文對各頂點和邊的權(quán)值給出了以下定義。

1)引入?yún)^(qū)間數(shù)[a,b]。在城市交通網(wǎng)絡(luò)圖中，對于圖的節(jié)點和邊屬性值不可能是一個確定的數(shù)值，而是一個依賴環(huán)境變化的數(shù)值。因此，在本文的算法中為了使得算法更具適應(yīng)性，對于節(jié)點和邊的屬性值引入?yún)^(qū)間數(shù)，即節(jié)點和邊的屬性值依賴環(huán)境變化的一個波動區(qū)間(例如，節(jié)點vi的屬性值可以表示為vi[avi,bvi])。

定義其各個頂點的調(diào)度成本函數(shù)為其距離的平方(見圖1)。即，v1點的調(diào)度成本為fv1=min(fv1?v2,fv1?v3,fv1?v4)。

圖1 調(diào)度成本計算示意圖Fig.1 Schematic diagram of scheduling cost calculation

因為實際情況中fvi?vx(xi)的影響因素很多，而且各因素的變化也比較大，很難獲得fvi?vx(xi)的最小值。但是可以獲得fvi?vx(xi)的一個合理的波動區(qū)間，因此vi點的調(diào)度成本可以用fvi?vx(xi)的一個合理波動區(qū)間來表示，即fvi=[avi,bvi]。

共享單車投放點的選取就轉(zhuǎn)換為求解圖G的最小點覆蓋的問題，求出圖G的最小點覆蓋就是城市交通路網(wǎng)中的共享單車投放點。具體的做法就是首先找到圖G任意起點的點覆蓋，然后比較各個點覆蓋的調(diào)度成本，最后選擇覆蓋點數(shù)相對較少，調(diào)度成本最小的覆蓋方案即為共享單車投放點選取的較優(yōu)方案。

本文對1.2中引用文獻[6]的最小的覆蓋算法進行改進，原算法中點和邊的權(quán)值為固定值，本文對此算法中頂點的權(quán)值引入函數(shù)，對邊的權(quán)值引入?yún)^(qū)間數(shù)，即vi的權(quán)值變?yōu)閒vi=min(fvi?vx)或fvi=[avi,bvi]，邊的權(quán)值變?yōu)閐viv=lviv(yi)。

1.4 模型求解算法

步驟1。利用函數(shù)fvi?vx(xi)計算圖G各頂點的調(diào)度成本(本文模型算法選取fvi=[avi,bvi])。

步驟2。利用函數(shù)dvivx=lvivx(yi)計算各邊的權(quán)值。

步驟3。調(diào)用1.2改進算法求出圖G不同初始點的點覆蓋結(jié)果。

步驟4。依據(jù)點覆蓋的計算結(jié)果，ui(i=1,2,…,n)為決策方案；xi(i=1,2,…,m)為決策指標(kij=[avi,bvi]，反映決策指標在一定范圍內(nèi)的波動值)，構(gòu)造調(diào)度成本規(guī)范化決策矩陣X。

u1…un

(1)

(2)

(3)

2 算例

2.1 算例求解

圖2是某城市部分城市交通路網(wǎng)示意圖。利用fvi?vx(xi)計算出各個節(jié)點的調(diào)度成本[avi,bvi]，利用dvivx=lvivx(yi)計算各邊的權(quán)值(fvi?vx(xi)和dvivx=lvivx(yi)函數(shù)關(guān)系依據(jù)實際情況確定)。圖2中vi(i=1,2,3,…,20)表示路網(wǎng)中可作為共享單車投放點的節(jié)點，[avi,bvi]表示vi點的調(diào)度成本區(qū)間，vivj邊上的數(shù)字表示此段交通路徑的長度dvivx。

2.2 算例求解過程

步驟1。計算圖G各頂點的調(diào)度成本，計算結(jié)果見圖2。

圖2 某城市部分城市交通路網(wǎng)示意圖Fig.2 The city traffic network

步驟2。計算各邊的權(quán)值，計算結(jié)果見圖2。

步驟3。首先調(diào)用1.2改進算法求解出圖2不同初始點點覆蓋的結(jié)果(見表1)。

步驟4。由表1點覆蓋計算結(jié)果構(gòu)造調(diào)度成本規(guī)范化決策矩陣X(如表2)。

步驟5。由調(diào)度成本規(guī)范化決策矩陣X求出初始點為vi(i=2,3,7,8,10,11,14,17)點覆蓋方案的調(diào)度成本綜合屬性值(文中假設(shè)各頂點之間的權(quán)重均為w=1)為

步驟6。對于調(diào)度成本的綜合屬性值兩兩比較可以得到可能度矩陣P。

步驟7。對于矩陣P按列求和可到得到。

表1 點覆蓋計算結(jié)果

pv2=3.191 8，pv3=5.806 1，pv7=2.844 5，

pv8=2.149 9，pv10=3.539 1，pv11=2.777 7，

pv14=7.011 4，pv17=4.681 5

因此，得到

因為文中考慮的是各個節(jié)點的調(diào)度成本，所以調(diào)度成本越低的方案就是較優(yōu)方案。若用符號?表示各個方案之間具有可能度的優(yōu)序關(guān)系，則相應(yīng)各不同初始點點覆蓋方案F[vi(i=2,3,7,8,10,11,14,17)]的排序為。

F[v8]?F[v11]?F[v7]?F[v2]?

F[v10]?F[v17]?F[v3]?F[v14]

因此，由模型求解結(jié)果可知，當選取v2,v4,v5,v8,v9,v10,v11,v13,v14,v16,v17,v19,v20為投放點時，可以使得整個系統(tǒng)的調(diào)度成本最低，從而得到方案4為較優(yōu)的共享單車投放點選取方案。

2.3 結(jié)果分析

共享單車的投放點選取時要考率諸多因素，比如最少投放點，最小調(diào)度成本等。最少的投放點方案不一定是調(diào)度成本最小的方案，因此，在選取投放點時要綜合考慮多種因素，從算例中可以很清楚的看到。如果對圖1交通路網(wǎng)單純考慮最少投放點，則由表1可知覆蓋點數(shù)較少的方案是方案2，7，8，選取的投放點個數(shù)均為12，因此可以選取方案2，7，8作為共享單車的投放點選取方案。但是，實際共享單車投放點的選取過程中不僅需要考慮選取最少投放點，還需考慮投放點選取后的調(diào)度成本問題。算例中計算得出了各個節(jié)點的調(diào)度成本區(qū)間，在考慮最少投放點的同時又考慮調(diào)度成本，則綜合優(yōu)選方案為方案4(初始點為v8)，此時選取的投放點個數(shù)為13個。方案2，7，8雖然覆蓋投放點數(shù)少，但是調(diào)度成本相對較大。

表2 調(diào)度成本規(guī)范化決策矩陣X(部分)

現(xiàn)有對于共享單車投放點的選取主要是依據(jù)居民出行量，投放點一般選取為居民出行量較為集中的地區(qū)，沒有考慮投放點對于整個城市交通網(wǎng)絡(luò)的覆蓋情況，不利于居民出行。其次，投放點的選取沒有考慮到各個投放點之間的調(diào)度成本，不利于共享單車企業(yè)高效運營。從算例中可以體現(xiàn)出本文算法在共享單車投放點選取中的優(yōu)勢，在考慮以最少投放點覆蓋城市交通網(wǎng)絡(luò)的同時，又考慮了共享單車的整體調(diào)度成本最小的問題，最終綜合優(yōu)選出較為合理的投放點選取方案，可以共享單車企業(yè)運營調(diào)度，降低成本，建設(shè)電子圍欄提供決策依據(jù)。但是，共享單車投放點在選取的過程中會受到很多因素的影響(例如，投放點場地容量，調(diào)度人員配備，調(diào)度車輛配備，共享單車數(shù)量等)，還會受到一些不可預(yù)測的問題(例如，道路臨時施工，交通事故，交通擁堵等)的干擾。本文方法只考慮最小投放點和最小調(diào)度成本2個指標具有一定局限性，更為合理的方法應(yīng)該是考慮諸多因素，建立更為完善的模型，開發(fā)更為高效的求解算法。

3 結(jié) 論

針對共享單車投放點選取不合理的問題，本文給出了一種基于最小點覆蓋的共享單車投放點選取算法。該算法考慮了每個節(jié)點的調(diào)度成本區(qū)間以及節(jié)點之間距離(或時間、費用)，以調(diào)度成本最小為優(yōu)化目標，可以為共享單車企業(yè)在選取單車投放點、選擇相對固定停車點、建立電子圍欄等提供決策依據(jù)。本文模型考慮共享單車投放點選取方案時只考慮了節(jié)點調(diào)度成本和路段屬性值，但在實際情況中除了以上2個指標外可能還有考慮其他指標(例如，共享單車企業(yè)調(diào)度人員和車輛配備情況等)，所以在考慮問題時應(yīng)該結(jié)合實際情況考慮多重屬性，建立更加完善的模型是下一步應(yīng)該研究的問題。