郝斌斌 呂 斌▲ 陳京榮

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

0 引 言

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

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

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

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

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

1.1 最小點(diǎn)覆蓋定義

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

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

1.2 基于最短路的最小點(diǎn)覆蓋算法[6]

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

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

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

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

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

1.3 模型建立

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

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

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

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

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

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

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

本文對(duì)1.2中引用文獻(xiàn)[6]的最小的覆蓋算法進(jìn)行改進(jìn)，原算法中點(diǎn)和邊的權(quán)值為固定值，本文對(duì)此算法中頂點(diǎn)的權(quán)值引入函數(shù)，對(duì)邊的權(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)計(jì)算圖G各頂點(diǎn)的調(diào)度成本(本文模型算法選取fvi=[avi,bvi])。

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

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

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

u1…un

(1)

(2)

(3)

2 算例

2.1 算例求解

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

2.2 算例求解過(guò)程

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

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

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

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

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

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

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

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

表1 點(diǎn)覆蓋計(jì)算結(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

因此，得到

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

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

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

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

2.3 結(jié)果分析

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

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

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

3 結(jié) 論

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