基于時(shí)空聚類預(yù)測(cè)的共享單車調(diào)度優(yōu)化研究

陳植元 林澤慧 金嘉棟 李建斌

(1.武漢大學(xué) 經(jīng)濟(jì)與管理學(xué)院, 湖北 武漢 430072; 2.上海交通大學(xué) 中美物流研究院, 上海 200030;3.華中科技大學(xué) 管理學(xué)院, 湖北 武漢 430074)

0 引言

共享單車服務(wù)是指單車租賃企業(yè)在校園、地鐵站點(diǎn)、公交站點(diǎn)、居民區(qū)、商業(yè)區(qū)、公共服務(wù)區(qū)等區(qū)域提供自行車單車分時(shí)租賃服務(wù)。作為共享經(jīng)濟(jì)熱潮的產(chǎn)物,共享單車在城市公共交通中發(fā)揮著越來越重要的作用,為城市用戶提供了一種更具可持續(xù)性的無碳運(yùn)輸模式,顯著減少了交通擁堵、空氣污染。當(dāng)前共享單車運(yùn)營(yíng)模式分為傳統(tǒng)帶樁共享單車(station-based bike sharing,SBBS)和無樁共享單車(freefloating bike sharing,FFBS)。SBBS系統(tǒng)合理的網(wǎng)絡(luò)設(shè)計(jì)能夠在方便用戶出行的同時(shí)提高運(yùn)營(yíng)商的管理效率,但由于基站的設(shè)立是有限的,當(dāng)最近的基站與用戶目的地相距較遠(yuǎn)時(shí),用戶將增加不必要的行程以停放共享單車。與傳統(tǒng)的帶樁共享單車不同,無樁共享單車(FFBS)不再設(shè)立基站,用戶可以根據(jù)自己的行程自由安排出發(fā)點(diǎn)和停車點(diǎn)。由于FFBS在實(shí)際運(yùn)營(yíng)中展現(xiàn)出了極高的自由度和便利性,越來越多的用戶選擇使用相應(yīng)的服務(wù)。

我國(guó)共享單車服務(wù)行業(yè)近年來發(fā)展迅速,多家提供共享單車服務(wù)企業(yè)的出現(xiàn)加快了服務(wù)模式的升級(jí)和創(chuàng)新。艾媒咨詢(iiMedia Research)提供的數(shù)據(jù)顯示,2018年中國(guó)共享單車用戶規(guī)模已達(dá)到2.35億人,2019年預(yù)計(jì)將增至2.59億人。在共享單車的使用頻率上,45.1%的用戶平均每周使用共享單車5次及以下;54.9%的用戶平均每周使用在5次以上。其中,82.9%的用戶平均每次使用共享單車的時(shí)長(zhǎng)在60分鐘內(nèi)。顯然,共享單車用戶數(shù)量規(guī)模大,且使用單車的主要目的是滿足短途出行需要。巨大的市場(chǎng)規(guī)模與不斷走高的行業(yè)發(fā)展形勢(shì)也帶來了激烈的競(jìng)爭(zhēng),企業(yè)不得不通過降低運(yùn)營(yíng)成本來應(yīng)對(duì)殘酷的價(jià)格戰(zhàn)。由于用戶的行為具有自主性,在實(shí)際運(yùn)營(yíng)中,共享單車的分布會(huì)逐漸偏離均衡,從而導(dǎo)致系統(tǒng)內(nèi)部資源分布的不合理。為了提高運(yùn)營(yíng)效率和用戶滿意度,越來越多的企業(yè)將優(yōu)化目標(biāo)鎖定在了單車調(diào)度上。

共享單車的調(diào)度指通過有效的方式實(shí)現(xiàn)單車資源在網(wǎng)絡(luò)中的合理布局,本文正是對(duì)共享單車的調(diào)度方式進(jìn)行優(yōu)化研究,其可能的貢獻(xiàn)在于:(1) 對(duì)運(yùn)營(yíng)商而言,調(diào)度路徑的優(yōu)化能夠減少調(diào)度車在工作過程中的行駛距離,對(duì)各節(jié)點(diǎn)的調(diào)度任務(wù)進(jìn)行合理分配則可以減少調(diào)度車和相關(guān)工作人員的投入從而降低成本;(2) 對(duì)使用共享單車的用戶而言,調(diào)度方式的優(yōu)化能保證他們?cè)诤线m的距離內(nèi)即時(shí)獲得共享單車。在本文中,如何選擇投車點(diǎn)也是受關(guān)注的一個(gè)重要問題,合理的投車點(diǎn)應(yīng)該在用戶有取車意愿的距離內(nèi),以避免當(dāng)步行距離過大時(shí),用戶使用體驗(yàn)受到影響甚至選擇放棄使用共享單車;(3) 對(duì)社會(huì)總體福利而言,共享單車資源的有效分配有助于提高社會(huì)資源的有效利用水平。共享單車調(diào)度的優(yōu)化有助于識(shí)別服務(wù)區(qū)域內(nèi)共享單車的需求情況,在整體需求無爆炸增長(zhǎng)的情況下,通過調(diào)度以有限的單車資源滿足所服務(wù)區(qū)域的社會(huì)需求。

目前對(duì)于單車調(diào)度的學(xué)術(shù)研究主要集中在基于運(yùn)營(yíng)商的調(diào)度上。共享單車的調(diào)度優(yōu)化本質(zhì)上屬于車輛路徑問題(Vehicle Routing Problem,VRP),車輛路線問題(VRP)最早是由Dantzig和Ramser于1959年提出,它是指一定數(shù)量的用戶,各自有不同數(shù)量的貨物需求,配送中心向用戶提供貨物,由一個(gè)車隊(duì)負(fù)責(zé)分送貨物,組織適當(dāng)?shù)男熊嚶肪€,目標(biāo)是使得用戶的需求得到滿足,并能在一定的約束下,達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。與傳統(tǒng)的車輛路徑問題不同,共享單車調(diào)度中的“用戶”不僅是需求方,也可以是供給方。相應(yīng)地,調(diào)度車輛在完成配貨的同時(shí),也需要完成取貨任務(wù)。作為一個(gè)NP難問題,共享單車調(diào)度優(yōu)化問題目前并沒有直接求解的可行方法,學(xué)術(shù)界主要通過運(yùn)用啟發(fā)式算法對(duì)可行解進(jìn)行優(yōu)化。

本論文的目的是通過聚類分析的方法為研究無樁共享單車的網(wǎng)絡(luò)模型提供新的思路和方法,同時(shí)通過研究共享單車調(diào)度優(yōu)化問題來探討啟發(fā)式算法在解決具體路線問題上的效果,為共享單車調(diào)度優(yōu)化問題的研究提出了從網(wǎng)絡(luò)分析到調(diào)度優(yōu)化的完整框架,論文研究?jī)?nèi)容如下:梳理共享單車調(diào)度優(yōu)化問題研究的相關(guān)文獻(xiàn),分為對(duì)傳統(tǒng)共享單車的研究和對(duì)新式的無樁共享單車的研究;利用共享單車需求的時(shí)空屬性設(shè)計(jì)了聚類模型,以聚類產(chǎn)生的集群為調(diào)度對(duì)象構(gòu)建了以調(diào)度成本最小為目標(biāo)函數(shù)的VRP模型;設(shè)計(jì)了貪心算法、遺傳算法來求解調(diào)度模型,并對(duì)每個(gè)算法的流程進(jìn)行了詳細(xì)的說明;最后進(jìn)行數(shù)據(jù)模擬,按照一定的規(guī)則生成共享單車需求的數(shù)據(jù)以及當(dāng)前時(shí)段的單車網(wǎng)絡(luò)分布情況,通過對(duì)數(shù)據(jù)的模擬來考察思路框架與模型在實(shí)際調(diào)度中發(fā)揮的作用。

1 文獻(xiàn)綜述

當(dāng)前共享單車運(yùn)營(yíng)模式分為傳統(tǒng)帶樁共享單車(stationbased bike sharing,SBBS)和無樁共享單車(free-floating bike sharing,FFBS)。其區(qū)別是相對(duì)于SBBS,FFBS用戶可以根據(jù)自己的行程自由安排出發(fā)點(diǎn)和停車點(diǎn)。國(guó)內(nèi)外對(duì)于共享單車調(diào)度優(yōu)化問題的研究主要分為SBBS調(diào)度和FFBS調(diào)度兩個(gè)方向。

1.1 SBBS調(diào)度優(yōu)化

在SBBS調(diào)度優(yōu)化的相關(guān)研究中,Chemla[1]第一次提出了SBBS中的靜態(tài)完全再平衡問題(SCRP),建立了目標(biāo)函數(shù)為總調(diào)度距離最短的模型。在Chemla[1]之后,Erdo?ɡan[2]提出了靜態(tài)模型的時(shí)間擴(kuò)展網(wǎng)絡(luò)公式并使用混合整數(shù)算法求解;為了解決多輛貨車同時(shí)參與調(diào)度任務(wù)的問題,Albarezvaldes[3]提出了一種解決多輛車調(diào)度的啟發(fā)式算法;Raviv[4]等人研究了多輛調(diào)度車下的共享單車靜態(tài)調(diào)度問題,在模型中提出并量化了顧客滿意度。在SCRP的相關(guān)文獻(xiàn)中,越來越多的算法被引入以解決SBBS的調(diào)度優(yōu)化問題:分支定界法[5];混合大規(guī)模領(lǐng)域搜索算法[6]、社會(huì)網(wǎng)絡(luò)分析法[7]、三階段啟發(fā)式算法[8]、雙層禁忌搜索算法[9]、離散差分進(jìn)化算法[10]、容差插入啟發(fā)式算法[11]等等。

考慮到靜態(tài)調(diào)度對(duì)用戶反應(yīng)的遲緩而無法即時(shí)對(duì)資源進(jìn)行合理調(diào)度,動(dòng)態(tài)調(diào)度的相關(guān)研究逐漸深入。Contardo[12]提出了基于租賃點(diǎn)的調(diào)度分解方案;Pfrommer[13]等通過對(duì)公共自行車服務(wù)點(diǎn)設(shè)定動(dòng)態(tài)變化的租車價(jià)格建立了再平衡調(diào)度模型;

Xu[14]提出了基于短期需求預(yù)測(cè)的動(dòng)態(tài)調(diào)度模型;Mao[15]等學(xué)者建立站點(diǎn)的整體可視化信息,采用梯度提升回歸樹算法實(shí)時(shí)預(yù)測(cè)站點(diǎn)的自行車流入/流出情況;Liu[16]基于GIS的原型系統(tǒng)中建立采用滾動(dòng)視野調(diào)度算法的車輛調(diào)度模型。

國(guó)內(nèi)對(duì)于共享單車的研究雖然起步稍晚,但也取得了相當(dāng)豐富的成果。吳滿金[17]等學(xué)者建立了關(guān)于調(diào)度成本以及用戶滿意度的多目標(biāo)函數(shù),綜合考慮了服務(wù)優(yōu)先級(jí)、時(shí)間窗等約束條件;楊珈惠[18]等學(xué)者提出了允許局部路徑重復(fù)的共享單車調(diào)度模型;文蝶斐[19]提出了以調(diào)度車初始攜帶共享單車數(shù)量最少為目標(biāo)的調(diào)度優(yōu)化模型;王涵霄[20]等學(xué)者在車輛調(diào)度模型的基礎(chǔ)上考慮共享單車的維修問題;盧琰[21]根據(jù)共享單車網(wǎng)絡(luò)的特性構(gòu)建了混合軸輻式網(wǎng)絡(luò)調(diào)度結(jié)構(gòu);徐國(guó)勛[22]等學(xué)者在共享單車調(diào)度問題中考慮了對(duì)損壞自行車的回收;王寧[23]等學(xué)者針對(duì)站點(diǎn)車輛時(shí)空分布不均衡制約共享模式快速發(fā)展的問題,提出基于用戶激勵(lì)的共享電動(dòng)汽車自適應(yīng)調(diào)度的成本最優(yōu)模型。

1.2 FFBS調(diào)度優(yōu)化

隨著FFBS模式的發(fā)展并逐漸成為主流,對(duì)共享單車調(diào)度優(yōu)化問題的研究也由SBBS擴(kuò)展到了FFBS。與SBBS擁有固定的單車停放基站不同,FFBS系統(tǒng)網(wǎng)絡(luò)中單車的分布是隨機(jī)、無序的,沒有任何的先驗(yàn)知識(shí)明確網(wǎng)絡(luò)中單車的分類。因此,如何對(duì)網(wǎng)絡(luò)中的單車進(jìn)行訪問以及如何準(zhǔn)確地預(yù)測(cè)網(wǎng)絡(luò)中單車的分布情況成為了FFBS調(diào)度優(yōu)化研究的重點(diǎn)。

但是目前對(duì)于FFBS調(diào)度優(yōu)化的相關(guān)研究仍然較少,國(guó)外的Pal和Zhang[24]提出了一種處理FFBS靜態(tài)再平衡問題的算法,他們通過分解需求的方法打破了以往調(diào)度模型中調(diào)度車對(duì)節(jié)點(diǎn)訪問次數(shù)的限制,設(shè)計(jì)了嵌套大鄰域搜索和可變鄰域下降的混合算法求解最優(yōu)路徑。Caggiani[25]等為FFBS的動(dòng)態(tài)管理提出了模型框架。通過聚類方法劃分單車網(wǎng)絡(luò)的時(shí)空分布,使用BP神經(jīng)網(wǎng)絡(luò)算法預(yù)測(cè)各聚類群的需求,提出了總體調(diào)度時(shí)間最短為目標(biāo)函數(shù)的調(diào)度模型,設(shè)計(jì)了一種兩階段VPR優(yōu)化算法。David[26]引入了負(fù)價(jià)格的動(dòng)態(tài)定價(jià)方案,通過用戶的自發(fā)行為實(shí)現(xiàn)自行車的調(diào)度。

國(guó)內(nèi)方面,羅毅軍[27]等學(xué)者通過獎(jiǎng)懲機(jī)制建立自動(dòng)規(guī)劃調(diào)度方法,從用戶角度實(shí)現(xiàn)共享單車再平衡;鄢章華[28]利用馬爾可夫鏈與狀態(tài)轉(zhuǎn)移矩陣來分析和描述單車的流轉(zhuǎn)過程,構(gòu)建不同調(diào)度方案下的投放量?jī)?yōu)化模型;高楹[29]等學(xué)者結(jié)合時(shí)間分布特征、土地類型信息提出了共享單車的空間調(diào)度模型;鄧力凡[30]等學(xué)者根據(jù)用戶騎行行為的時(shí)空特征定義了騎行區(qū)域的劃分類型;賈永基[31]針對(duì)無樁式共享單車運(yùn)營(yíng)中所出現(xiàn)的亂停亂放和分布不平衡問題,引入電子圍欄并將其作為單車停放站點(diǎn),通過調(diào)節(jié)各電子圍欄的單車數(shù)量以實(shí)現(xiàn)供需平衡。

同時(shí)隨著大數(shù)據(jù)技術(shù)及數(shù)字化管理的發(fā)展,國(guó)內(nèi)外學(xué)者逐漸將聚類算法與VPR問題相結(jié)合,如設(shè)施選址、車輛路徑、選址-路徑等問題[32]。Calvet[33]等將客戶聚類操作與啟發(fā)式算法結(jié)合提出了一種混合智能算法,經(jīng)過預(yù)測(cè)獲得新客戶對(duì)應(yīng)的服務(wù)費(fèi)用并應(yīng)用方法于求解多中心車輛路徑問題。阮俊虎[34]等提出一種基于聚類的兩階段醫(yī)療物資聯(lián)合運(yùn)輸方法,構(gòu)建了醫(yī)療物資聯(lián)合運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu),在此基礎(chǔ)上建立基于聚類的運(yùn)送路線優(yōu)化模型,確定從應(yīng)急中轉(zhuǎn)點(diǎn)到醫(yī)療救助點(diǎn)的具體運(yùn)送路線。

綜上所述,SBBS調(diào)度的研究已經(jīng)非常成熟,但涉及FFBS調(diào)度研究則相當(dāng)空缺,造成該問題的原因有兩點(diǎn):(1)無樁共享單車興起的時(shí)間比較晚;(2)無樁共享單車網(wǎng)絡(luò)難以描述以及需求的難以預(yù)測(cè)。鑒于此,本文研究FFBS調(diào)度優(yōu)化問題,通過聚類分析的方法將具有相似時(shí)空屬性的單位區(qū)域聚合為調(diào)度集群,提出了將用戶對(duì)取車距離的敏感性量化為考核集群劃分是否合理的懲罰成本,使單車調(diào)度問題轉(zhuǎn)化為有時(shí)間窗與載重量限制的車輛路徑問題,構(gòu)建共享單車調(diào)度路徑優(yōu)化模型,并分別使用了貪婪算法、遺傳算法對(duì)模型進(jìn)行求解。

2 調(diào)度優(yōu)化模型

共享單車作為一種短途出行交通工具,其分布受到用戶行為的影響。與帶樁共享單車不同,無樁共享單車的停放可以是任意位置的,因此如何準(zhǔn)確地對(duì)網(wǎng)絡(luò)中單車的分布情況進(jìn)行描述與分類成為了需求預(yù)測(cè)與調(diào)度的關(guān)鍵。聚類分析是一種在沒有先驗(yàn)知識(shí)的情況下對(duì)物理或抽象對(duì)象進(jìn)行相似分組的統(tǒng)計(jì)方法。結(jié)合共享單車需求的時(shí)空特征,合理利用聚類分析將網(wǎng)絡(luò)中單車分布情況與需求趨勢(shì)相似的地區(qū)聚合成虛擬“基站”進(jìn)行統(tǒng)一調(diào)度是本文處理共享單車網(wǎng)絡(luò)的主要分析方法。本文所構(gòu)建調(diào)度優(yōu)化模型流程如圖1所示。

圖1 基于時(shí)空聚類預(yù)測(cè)的共享單車調(diào)度優(yōu)化模型Figure 1Optimal model of shared bicycle scheduling based on spatio-temporal clustering prediction

2.1 參數(shù)及符號(hào)說明

模型所涉及的參數(shù)與變量如表1所表示。

表1 參數(shù)、變量解釋表Table 1Table of notations

2.2 網(wǎng)絡(luò)聚類模型

2.2.1 時(shí)間聚類

用戶不同時(shí)段的出行選擇導(dǎo)致了需求高峰期以及低谷期的產(chǎn)生,引起時(shí)間維度上的供需失衡,因此需要探究區(qū)域單車使用需求在時(shí)間維度上所呈現(xiàn)出的穩(wěn)定規(guī)律以及變化趨勢(shì),以預(yù)測(cè)某區(qū)域在特定日期的總體需求狀況。

為了盡可能消除特殊樣本對(duì)整體的影響,本文選擇以一年為周期進(jìn)行分析。本文參考WeiKl[35]對(duì)德國(guó)慕尼黑共享汽車需求情況的時(shí)段劃分,根據(jù)用戶出行時(shí)間選擇的特點(diǎn)將一天分成七個(gè)時(shí)段(Time Slice),同時(shí)在兩個(gè)時(shí)段之間留出了一個(gè)小時(shí)的間隔以滿足調(diào)度所需的時(shí)間。選定某個(gè)時(shí)間段作為分析對(duì)象,通過聚類分析得到在該時(shí)段具有類似需求情況的日期的集合,以及不同集群中的日期情況、不同集群之間的需求均值差異等時(shí)間特征。

聚類分析算法可以分為劃分聚類和層次聚類兩個(gè)大類[36]。層次聚類主要包括聚合型層次聚類與分裂型層次聚類,而劃分聚類算法需要預(yù)先指定聚類數(shù)目和聚類中心,將數(shù)據(jù)集分成若干互不相交的簇[37]。其代表算法是 k-means、混合密度聚類、圖聚類、模糊聚類等。1967年提出的 k-means算法使同一類中的數(shù)據(jù)樣本具有高度相似性,不同類中的數(shù)據(jù)樣本具有高度的相異性[38]。該算法是一種基于距離的經(jīng)典算法,因其效果優(yōu)異、易實(shí)現(xiàn)且可解釋性較強(qiáng),被廣泛應(yīng)用于機(jī)器學(xué)習(xí)等領(lǐng)域,因此本文選擇k-means聚類算法對(duì)時(shí)段內(nèi)的需求數(shù)據(jù)進(jìn)行劃分,并將設(shè)定具體的K值。

為分析同一日期不同時(shí)段間的需求變化趨勢(shì),將當(dāng)前時(shí)段與下一時(shí)段的聚類結(jié)果進(jìn)行比對(duì)分析,判斷當(dāng)前時(shí)段的日期集群中在下一時(shí)段是否依然分布集中。如果分布集中,說明此部分日期需求呈現(xiàn)穩(wěn)定變化趨勢(shì)。例如,在當(dāng)前時(shí)段某集群A(i)有85%集中在下一時(shí)段的集群B(j)中,則有理由認(rèn)為B(j)有效地反映了A(i)中日期的需求變化趨勢(shì),并通過對(duì)比B(j)與A(i)中需求均值得到需求變化的趨勢(shì)指數(shù)(Trend)。如果分布過于平均,則需要分析具體情況,如有必要?jiǎng)t對(duì)集群中的樣本分別進(jìn)行計(jì)算。

圖2 時(shí)間段劃分圖Figure 2Time division diagram

2.2.2 空間聚類

不同于時(shí)間特征,共享單車需求的空間特征則是由地區(qū)功能差異引起的。如同帶樁共享單車網(wǎng)絡(luò)設(shè)計(jì)時(shí)需要考慮基站的選址一樣,無樁共享單車調(diào)度系統(tǒng)也需要考慮單車投放地點(diǎn)以盡可能滿足用戶需求。本研究通過投放地點(diǎn)所服務(wù)的地區(qū)間距離、需求情況相似度來確定投放地點(diǎn)以及服務(wù)范圍。

進(jìn)行空間聚類之前,首先需要確定集群的個(gè)數(shù)K值,這取決于運(yùn)營(yíng)成本與用戶服務(wù)之間的權(quán)衡。當(dāng)集群個(gè)數(shù)過多時(shí),用戶到達(dá)單車投放點(diǎn)的平均距離減少,用戶服務(wù)水平提高,但過多的集群將增加調(diào)度成本。當(dāng)集群個(gè)數(shù)過少時(shí),用戶則會(huì)因?yàn)橥斗劈c(diǎn)過遠(yuǎn)而放棄使用共享單車,轉(zhuǎn)而選擇其他交通出行方式。

為具體考量不合理的集群分類帶來的負(fù)面影響,本文提出加入衡量集群劃分是否合理的懲罰成本。假設(shè)若用戶到取車點(diǎn)的距離distance(i)在[0,α],集群內(nèi)潛在用戶不會(huì)因?yàn)槿≤嚲嚯x而產(chǎn)生放棄的意愿;若distance(i)在[α,β]范圍內(nèi),潛在用戶的放棄意愿將隨距離增加而提高,且遞增的速度上升。因此,以e為底的指數(shù)函數(shù)來描述兩者之間的關(guān)系:當(dāng)取車距離在[0.75,1.5]范圍內(nèi)時(shí),用戶的放棄意愿變化趨勢(shì)如圖3所示。步行距離越遠(yuǎn)時(shí),在增加等量步行距離情況下,用戶的放棄意愿上升速度越高。為了將這種放棄意愿的變化轉(zhuǎn)換成對(duì)運(yùn)營(yíng)商的懲罰成本,加入懲罰系數(shù)s,并用歸一化的方法處理該系數(shù)。如果取車距離超出了β,則認(rèn)為幾乎所有的用戶都因?yàn)闊o法忍受過于遠(yuǎn)的步行距離而放棄使用共享單車。懲罰系數(shù)s定義如下:

圖3 放棄意愿變化圖Figure 3Change of willingness to give up

式中,λ是用戶放棄意愿增長(zhǎng)情況的參數(shù)。λ越小,則隨著取車距離的增加,用戶放棄使用共享單車意愿的增速較為平緩。λ越大,則用戶在初期對(duì)取車距離增加的敏感性較低,但隨著該距離的不斷走高,用戶的放棄意愿會(huì)出現(xiàn)爆炸式的增長(zhǎng)。該懲罰系數(shù)的表達(dá)式反映了步行距離對(duì)用戶使用意愿的影響。

在確定用戶損失系數(shù)后,某單位區(qū)域的懲罰成本將表示為:

其中Penalty表示懲罰成本,p表示最高懲罰成本。

為了保證集群內(nèi)部時(shí)間、空間屬性的一致性,需要根據(jù)趨勢(shì)指數(shù)將該地區(qū)劃分成若干個(gè)需求變化特征一致的集群,在已有集群的基礎(chǔ)上按照地理坐標(biāo)的遠(yuǎn)近進(jìn)行空間聚類。通過時(shí)空聚類產(chǎn)生的集群類似于傳統(tǒng)共享單車系統(tǒng)中的基站,調(diào)度車將按照一定的順序依次訪問這些集群的質(zhì)心,并完成期望數(shù)量的裝卸任務(wù)。

2.2.3 需求預(yù)測(cè)

時(shí)空聚類產(chǎn)生的集群內(nèi)部具有相似的需求變化趨勢(shì),可對(duì)此類區(qū)域進(jìn)行集中預(yù)測(cè)。理想的共享單車預(yù)測(cè)數(shù)量應(yīng)滿足按正常趨勢(shì)變化的需求,同時(shí)對(duì)可能出現(xiàn)的特殊情況有所準(zhǔn)備,但趨勢(shì)指數(shù)只反映了周期內(nèi)需求變化的整體情況,需要對(duì)某些特殊需求情況進(jìn)行處理。

令T表示集群的趨勢(shì)指數(shù),表示集群i內(nèi)第j個(gè)單位區(qū)域在當(dāng)前時(shí)段的需求,qt(i)表示集群i當(dāng)前已有的共享單車,n表示集群包含的單位區(qū)域個(gè)數(shù),dsp表示需求的特殊情況,那么集群i在下一時(shí)段的需求Dt+1(i)滿足:

取其平均值:

在獲得集群下一時(shí)段的總預(yù)測(cè)需求后,集群i的裝卸數(shù)量表示為:

2.3 調(diào)度路徑模型

調(diào)度路徑模型的整體框架基于傳統(tǒng)VPR問題的模型,但考慮到共享單車調(diào)度問題的獨(dú)特性,在本文的調(diào)度模型中,調(diào)度成本增加了損失用戶的懲罰成本。在實(shí)際操作中,運(yùn)營(yíng)商需要在規(guī)定時(shí)間內(nèi)完成調(diào)度工作以即時(shí)滿足用戶的使用需求,因此模型對(duì)每輛車在每次調(diào)度任務(wù)中所能行駛的最長(zhǎng)距離進(jìn)行了限制。在聚類分析中,把每天劃分成了7個(gè)時(shí)間段,而每個(gè)時(shí)間段之間的間隔將作為設(shè)定時(shí)間窗條件的依據(jù)。不同于基礎(chǔ)的VPR問題,在共享單車調(diào)度問題中,每個(gè)節(jié)點(diǎn)不僅是需求方,也可以成為供給方。由于每輛調(diào)度車都有規(guī)定的容量上限,因此在調(diào)度過程中需要關(guān)注調(diào)度車的車載情況。

用Qv(i)表示調(diào)度車V在節(jié)點(diǎn)i的車載情況,車輛由節(jié)點(diǎn)i訪問節(jié)點(diǎn)j,其中節(jié)點(diǎn)j需要裝卸的單車數(shù)量為d(j),則調(diào)度車的車載量更新為Qv(j)=Qv(i)+d(j)。調(diào)度路徑模型的目標(biāo)函數(shù)和約束條件如下:

目標(biāo)函數(shù)追求調(diào)度成本最低化。其中,調(diào)度成本由四部分構(gòu)成:每輛調(diào)度車進(jìn)行調(diào)度工作時(shí)的固定成本,本文假設(shè)所有調(diào)度車輛的車況相似,因此用統(tǒng)一的C0作為調(diào)度的固定成本;調(diào)度點(diǎn)之間的運(yùn)輸成本,該成本由調(diào)度車單位可變成本C1(燃料、車損等成本)和調(diào)度點(diǎn)之間的歐式距離決定;不合理的集群劃分帶來的懲罰成本,其中用戶損失系數(shù)s的表示在聚類模型中已經(jīng)說明;在集群內(nèi)裝卸共享單車的成本,每輛共享單車的裝卸成本由C2統(tǒng)一表示。

約束條件:

公式(7)~(8)表示每次調(diào)度都必須由車場(chǎng)派車,且每輛調(diào)度車最終都必須回到車場(chǎng)。

公式(9)表示每個(gè)調(diào)度點(diǎn)只被分配一輛調(diào)度車。

公式(10)表示每個(gè)調(diào)度點(diǎn)一旦產(chǎn)生裝卸需求,就必須被調(diào)度車訪問以完成調(diào)度工作。

公式(11)表示在每個(gè)調(diào)度點(diǎn)完成裝卸工作后,調(diào)度車都需要離開該調(diào)度點(diǎn)以繼續(xù)調(diào)度任務(wù)。

公式(12)表示在調(diào)度過程中的任一時(shí)刻,調(diào)度車的裝載量都必須在規(guī)定的合理限載范圍內(nèi)。

公式(13)表示進(jìn)入某個(gè)需求點(diǎn)的調(diào)度車必定會(huì)從該點(diǎn)離開。

公式(14)保證調(diào)度路徑中不會(huì)出現(xiàn)回路,避免無意義的重復(fù)調(diào)度。

公式(15)規(guī)定了每輛車在每日調(diào)度過程中的距離限制,該約束條件在一定程度上能避免不同工作組之間任務(wù)分配不一致而造成的公平問題,同時(shí)也能保證對(duì)調(diào)度車的合理使用。

公式(16)表示了調(diào)度車所載單車數(shù)量的變化。

公式(18)表示調(diào)度車分配情況的0-1變量,若yiv=1,則表示節(jié)點(diǎn)i由調(diào)度車v訪問。

2.4 VPR優(yōu)化算法

共享單車的調(diào)度問題本質(zhì)上屬于VPR(Vehicle Routing Problem)問題。作為一個(gè)NP-hard問題,VPR目前仍未找到有效的算法。為了找到可行的近似解,本文將采用貪心算法、遺傳算法對(duì)前述模型進(jìn)行求解。調(diào)度優(yōu)化模型的目標(biāo)是整體成本最小,其中懲罰成本、共享單車裝卸成本是由聚類分析的結(jié)果決定的,因此在尋找優(yōu)秀的路徑時(shí)本節(jié)更關(guān)注的是決定調(diào)度可變成本的調(diào)度距離。兩類算法的調(diào)度性能比較將在數(shù)值分析中進(jìn)行詳細(xì)說明。

2.4.1 可行性驗(yàn)證

對(duì)各算法選擇的路徑進(jìn)行調(diào)度可行性驗(yàn)證,即是否滿足調(diào)度車輛行駛距離限制和車容量限制的約束條件。為此,本文設(shè)計(jì)了流程如圖4所示的RouteSort可行性校驗(yàn),分為路徑劃分和車容量限制檢測(cè)。提取測(cè)試路徑集數(shù)據(jù),輸入總路徑數(shù)組r、車容量限制threshold、各質(zhì)心距離矩陣D、各質(zhì)心到車場(chǎng)的距離DOF等信息,進(jìn)行以下兩類檢測(cè),最終輸出該總路徑的可行性與調(diào)度成本。

圖4 RouteSort可行性校驗(yàn)Figure 4RouteSort feasibility check

1)路徑劃分。首先根據(jù)調(diào)度車行駛距離限制把每條路徑分為若干部分,各部分即一輛調(diào)度車的訪問路線,其次輸出每組調(diào)度車訪問調(diào)度點(diǎn)數(shù)量的索引。例如對(duì)于路徑[6 5

3 2 1 4],劃分產(chǎn)生的索引為[2 3 1],則第一輛調(diào)度車的調(diào)度路徑為[6 5],第二輛車的調(diào)度路徑為[3 2 1],第三輛調(diào)度車的調(diào)度路徑為[4]。

2)車容量限制檢測(cè)。模擬每條編碼子路徑的裝卸活動(dòng)進(jìn)行判斷。例如,當(dāng)前調(diào)度車的初始容量為Q(0)=q,d(i)X表示在第i個(gè)節(jié)點(diǎn)的共享單車裝卸量,則調(diào)度車在節(jié)點(diǎn)i的容量為:Q(i)=Q(i-1)+d(i)。如果Q(i)＞Qu,則退出該編碼的檢測(cè),且設(shè)定該條編碼的目標(biāo)值為懲罰值INF。對(duì)于通過檢測(cè)的合理編碼,其成本可以通過目標(biāo)函數(shù)計(jì)算獲得。

3 數(shù)值分析

3.1 需求數(shù)據(jù)設(shè)計(jì)

為了模擬現(xiàn)實(shí)中共享單車需求變化的大致情況,本文設(shè)計(jì)了四種類型的需求情況來抽象反映不同功能區(qū)域的需求特性。在設(shè)計(jì)具體數(shù)據(jù)時(shí),加入了一定的限制來使需求變化的特征更明顯,雖然這與現(xiàn)實(shí)不完全符合,但本文更關(guān)注的是運(yùn)營(yíng)商如何利用需求的時(shí)空特征進(jìn)行調(diào)度優(yōu)化。以下是6:00至8 :30、9 :30至12 :00兩相鄰時(shí)間段的需求數(shù)據(jù),通過兩者的對(duì)比可以得出需求時(shí)間變化的趨勢(shì)值。

3.1.1 工作日早高峰特征需求

由表2的數(shù)據(jù)可見,該類需求特征的區(qū)域在周一至周五的6 :00~8 :30時(shí)段有個(gè)明顯的高峰值(不考慮節(jié)日與特殊情況的出現(xiàn)),而在9 :30~12 :00時(shí)段中,工作日單車需求則處于相對(duì)的低峰狀態(tài)。與工作日不同,周末的需求狀況表現(xiàn)出了截然不同的狀況:用戶需求在9:30~12:00迎來一個(gè)高峰狀態(tài)。該需求模擬了城市中居民區(qū)的共享單車需求特征。在早高峰期間,大量用戶選擇使用共享單車以避免車輛擁堵,而到了上午的工作時(shí)間,留置在居民區(qū)的共享單車使用對(duì)象多數(shù)是非單車活躍用戶的老人與幼兒。

表2 工作日早高峰特征需求表Table 2Demand with morning peak characteristics on weekdays

3.1.2 工作日午高峰特征需求

工作日午高峰需求表現(xiàn)出了與工作日早高峰需求完全相反的特征。如表3所示該類需求特征的區(qū)域在周一至周五的9 :30至12 :00時(shí)段有個(gè)明顯的高峰值(不考慮節(jié)日與特殊情況的出現(xiàn)),而在6 :00至8 :30時(shí)段中,工作日單車需求則處于相對(duì)的低峰狀態(tài)。在周末與節(jié)假日的時(shí)候,該類地區(qū)的需求處于持續(xù)的低峰狀態(tài)。此類需求主要模擬了城市商業(yè)中心共享單車需求變化的特征。在工作日臨近中午的時(shí)間段里,該區(qū)域辦公的用戶出于短距離外出辦公、午間外出就餐等原因而產(chǎn)生了對(duì)共享單車的高峰需求。周末與假期的時(shí)候,大量用戶因無工作任務(wù)安排而基本沒有對(duì)共享單車的需求。

表3 工作日午高峰特征需求表Table 3Demand with noon peak characteristics on weekdays

3.1.3 平穩(wěn)低峰特征需求

平穩(wěn)低峰特征需求描述了類似于景區(qū)等共享單車平時(shí)需求較低的區(qū)域的需求特點(diǎn)。如表4所示,這些區(qū)域在平常的日期里人流量少,對(duì)共享單車的使用需求明顯偏低。而到了節(jié)假日以及一些特殊的日子里,游客的大量涌入產(chǎn)生了高峰需求。

表4 平穩(wěn)低峰特征需求表Table 4Demand with stable low peak characteristics

3.1.4 平穩(wěn)高峰特征需求

如表5所示,該類地區(qū)平均需求高且在兩個(gè)時(shí)段間的需求變化幅度小。此類特征的需求主要是對(duì)城市中人流集中區(qū)域情況的描述。持續(xù)的高需求也要求更高的用戶服務(wù)水平,運(yùn)營(yíng)商需要對(duì)這些地區(qū)給予足夠的重視與關(guān)注。

表5 平穩(wěn)高峰特征需求Table 5Demand with stable high peak characteristics

3.2 聚類分析

3.2.1 共享單車網(wǎng)絡(luò)模擬

進(jìn)行調(diào)度前,需要確定每個(gè)區(qū)域現(xiàn)有的單車數(shù)量以及質(zhì)心位置。本文通過MATLAB的隨機(jī)函數(shù)模擬了一個(gè)大小為3 km×3km的地區(qū)的單車網(wǎng)絡(luò)分布情況,將該地區(qū)劃分成36個(gè)0.5km×0.5km大小的單位區(qū)域,圖中的實(shí)心點(diǎn)代表了網(wǎng)絡(luò)中單車的分布情況。在某些區(qū)域單車密布較為密集,而有些區(qū)域分布則較為稀疏,造成這種密度差異的重要原因是在當(dāng)前時(shí)段用戶使用單車的路徑具有一定的指向性。如工作日午高峰需求特征的地區(qū)在6:00 - 8:30時(shí)間段主要是用戶的目的地,因此單車的分布密度較大。圖中的圓圈代表該地區(qū)單車分布的質(zhì)心,它將代表該區(qū)域作為接下來時(shí)空聚類的輸入。

圖5 共享單車分布網(wǎng)絡(luò)圖Figure 5Distribution network of bike sharing

3.2.2 時(shí)間聚類

時(shí)間聚類的目的是將單車網(wǎng)絡(luò)劃分成若干個(gè)集群,且這些集群內(nèi)部各區(qū)域的需求變化趨勢(shì)相似。本文以各區(qū)域當(dāng)前時(shí)段的需求以及趨勢(shì)指數(shù)為指標(biāo),根據(jù)需求數(shù)據(jù)設(shè)計(jì)中不同特征需求的數(shù)量,采用k-means聚類的方法將對(duì)象地區(qū)劃分成了4個(gè)集群。提取各區(qū)域時(shí)間特征并進(jìn)行聚類后的具體結(jié)果如圖6所示,Origin表示車場(chǎng)的位置,該區(qū)域聚類結(jié)果中共有4個(gè)集群,圖中“?”代表集群質(zhì)心,不同形狀點(diǎn)代表不同聚類類別,同時(shí)加以邊緣線劃分。在該聚類結(jié)果中,集群內(nèi)部空間分散,且集群之間有較大面積重疊。顯然,僅按照時(shí)間特性分類是不理想的,集群之間的重疊導(dǎo)致了各投車點(diǎn)(即集群質(zhì)心)所服務(wù)區(qū)域的重復(fù),造成了資源浪費(fèi)。不僅如此,處于集群邊緣區(qū)域的用戶會(huì)因投車點(diǎn)過遠(yuǎn)而放棄使用共享單車,此類用戶類型的流失對(duì)于運(yùn)營(yíng)商來說是不可原諒的,這也是上文強(qiáng)調(diào)懲罰成本的原因?？紤]到上述因素,本文將在時(shí)間聚類的因素上進(jìn)行空間聚類,從而使集群的分布更為合理。

3.2.3 空間聚類

現(xiàn)有的信息無法確定空間聚類的合理集群數(shù)量,因而本文提出通過在目標(biāo)函數(shù)中加入懲罰成本的方法來確定最優(yōu)集群數(shù)量。通過MATLAB編程,本文設(shè)計(jì)了一個(gè)以集群個(gè)數(shù)為條件的循環(huán)結(jié)構(gòu)。為了減少運(yùn)算量,本文認(rèn)為每個(gè)集群區(qū)域的最小個(gè)數(shù)由α決定,因?yàn)楫?dāng)集群內(nèi)部各區(qū)域到集群質(zhì)心的距離小于該值時(shí),懲罰成本將不再產(chǎn)生,且當(dāng)該距離過小時(shí)將會(huì)增加調(diào)度的運(yùn)營(yíng)成本,因此當(dāng)集群數(shù)量超過特定的值后,成本將增加。以集群數(shù)量為9的一種聚類結(jié)果為例,其具體聚類結(jié)果如圖7時(shí)空聚類結(jié)果圖所示,Origin表示車場(chǎng)的位置,圖中共有9個(gè)集群。對(duì)比圖6、圖7,可以看出相較于僅使用時(shí)間聚類,時(shí)空聚類的結(jié)果重疊面積顯著下降,每個(gè)集群內(nèi)部各區(qū)域的時(shí)間趨勢(shì)相似,且各集群區(qū)分明顯。

圖6 時(shí)間聚類結(jié)果圖Figure 6Results of temporal clustering

圖7 時(shí)間+空間聚類結(jié)果圖Figure 7Results of temporal and spatial clustering

特別要說明的是,該聚類結(jié)果是遺傳算法求解得出的收斂結(jié)果。前文2.2.2部分曾討論過如何決定最佳的集群數(shù)量,這是運(yùn)營(yíng)商調(diào)度成本與用戶服務(wù)水平之間的權(quán)衡,當(dāng)集群數(shù)量過少時(shí),不合理的取車距離會(huì)造成高昂的懲罰成本,而過多的集群數(shù)量則意味著更高的調(diào)度成本,從先前的推斷來判斷,該最優(yōu)化結(jié)果顯然是合理的。不僅如此,這也證明為了降低運(yùn)算量而減少可能的聚類情況的做法是可行的。

3.3 調(diào)度路徑模擬

3.3.1 參數(shù)設(shè)計(jì)

本文引入了貪心算法和遺傳算法解決VPR問題,使用這兩種算法分別對(duì)調(diào)度路徑優(yōu)化模型求解并進(jìn)行對(duì)比。在求解最佳路徑之前,需要整理出車場(chǎng)與節(jié)點(diǎn)、節(jié)點(diǎn)與節(jié)點(diǎn)之間的歐式距離矩陣。

表6展示了集群數(shù)量為8時(shí)的各節(jié)點(diǎn)之間的距離矩陣,其中O表示車場(chǎng),節(jié)點(diǎn)1-8表示8個(gè)集群質(zhì)心鎖在的位置。為了避免各節(jié)點(diǎn)到自己的距離對(duì)搜索的影響,將這些距離設(shè)置為極大值INF,其他聚類結(jié)果的距離矩陣算法與表6一致。

表6 集群數(shù)量為8的距離矩陣Table 6Distance matrix of 8 clusters

在接下來的部分里,本文將對(duì)表7中的參數(shù)組合下貪心算法、遺傳算法的求解結(jié)果進(jìn)行詳細(xì)地說明,并對(duì)各算法進(jìn)行成本優(yōu)化效果方面的對(duì)比。

表7 參數(shù)組合表Table 7Combination of parameters

3.3.2 實(shí)驗(yàn)結(jié)果分析

使用設(shè)計(jì)算法以模擬的數(shù)據(jù)為樣本對(duì)調(diào)度優(yōu)化模型進(jìn)行求解,算法得到的VPR路線圖結(jié)果如圖8所示,表8則詳細(xì)展示了算法收斂解的調(diào)度路徑情況以及調(diào)度車載重量的變化。

表8 各算法調(diào)度路徑結(jié)果Table 8Path results scheduled by various algorithms

圖8 各算法調(diào)度路徑圖Figure 8Paths scheduled by each algorithm

(1)貪心算法

貪心算法(又稱貪婪算法)是指,在對(duì)問題求解時(shí),以追求當(dāng)前最優(yōu)解為目標(biāo)。在調(diào)度優(yōu)化模型中,目標(biāo)函數(shù)追求整體成本最少,其中懲罰成本、共享單車裝卸成本是由聚類分析的結(jié)果決定的,因此在尋找優(yōu)秀的路徑時(shí)更關(guān)注的是決定調(diào)度可變成本的調(diào)度距離。貪心算法在對(duì)問題進(jìn)行求解時(shí)總是以到當(dāng)前節(jié)點(diǎn)的歐式距離最短為依據(jù)尋找下一個(gè)訪問節(jié)點(diǎn),因此共享單車的調(diào)度路徑將在對(duì)節(jié)點(diǎn)的搜索中直接形成而不存在優(yōu)化的過程。

貪心算法所得解出現(xiàn)在[1,3,3,2]聚類結(jié)果中,最低的調(diào)度成本為213.6。運(yùn)營(yíng)商需要派出3輛調(diào)度車分別以[車場(chǎng),5,3,車場(chǎng)],[車場(chǎng),6,1,車場(chǎng)],[車場(chǎng),8,7,9,2,4,車場(chǎng)]的路徑訪問共享單車網(wǎng)絡(luò)。圖8(a)詳細(xì)展示調(diào)度車的路線圖。在載重方面,三條路線的調(diào)度車載重量都在合理的范圍內(nèi)。其中訪問8、7、9、2、4這五個(gè)節(jié)點(diǎn)的調(diào)度車需要從車場(chǎng)攜帶7輛共享單車來補(bǔ)充不足,訪問6、1兩節(jié)點(diǎn)的調(diào)度車則需要從車場(chǎng)攜帶6輛單車。

(2)遺傳算法

不同于貪心算法,遺傳算法的求解是個(gè)不斷優(yōu)化的過程,通過概率化的尋優(yōu)方法,展現(xiàn)出強(qiáng)大的全局搜索能力。使用遺傳算法,所得收斂解的調(diào)度成本為189.14,出現(xiàn)在集群數(shù)為9的聚類結(jié)果[1,4,3,1]中。運(yùn)營(yíng)商只需派出2輛調(diào)度車,調(diào)度車的調(diào)度路線圖的結(jié)果如圖8(b)。通過比較,可以發(fā)現(xiàn)遺傳算法得到的最優(yōu)調(diào)度方案的成本明顯優(yōu)于貪心算法得到的調(diào)度方案的成本,這與預(yù)想一致,貪心算法雖然每一步都做出了當(dāng)前最優(yōu)的選擇,但卻失去了全局優(yōu)化的能力。結(jié)果顯示,遺傳算法在各個(gè)聚類情況下都得到了明顯優(yōu)于貪婪算法的調(diào)度路徑收斂解,說明了全局優(yōu)化算法在尋找最佳調(diào)度方案中的強(qiáng)大能力。

3.3.3 集群數(shù)量分析與算法比較

(1)集群數(shù)量分析

合理的集群的數(shù)量是調(diào)度成本以及用戶服務(wù)權(quán)衡的結(jié)果。當(dāng)集群個(gè)數(shù)過多時(shí),用戶到達(dá)單車投放點(diǎn)的平均距離減少,服務(wù)水平提高,但過多的集群將增加調(diào)度成本;當(dāng)集群個(gè)數(shù)過少時(shí),每個(gè)投車點(diǎn)需要服務(wù)的區(qū)域過大而導(dǎo)致用戶則會(huì)因?yàn)橥斗劈c(diǎn)過遠(yuǎn)而放棄使用共享單車,轉(zhuǎn)而選擇其他交通出行方式。

為了探究集群數(shù)量的變化和不同聚類對(duì)調(diào)度結(jié)果產(chǎn)生的影響,本文設(shè)置了不同的K值進(jìn)行數(shù)值模擬,具體的結(jié)果下表所示。表9所示是僅使用時(shí)間聚類和時(shí)空聚類產(chǎn)生的最低成本對(duì)比;表10中展示了不同集群數(shù)量劃分情況下,重復(fù)進(jìn)行k-means時(shí)空聚類分析并進(jìn)行求解調(diào)度路徑,取最優(yōu)解和平均解。只考慮時(shí)間聚類的情況下,集群數(shù)量較少,由于服務(wù)區(qū)域內(nèi)用戶距離單車投放點(diǎn)位置較遠(yuǎn),導(dǎo)致潛在用戶的流失帶來相應(yīng)的懲罰成本,因此貪心算法總的調(diào)度成本達(dá)317.87,比最低成本高出48.82%;而當(dāng)集群數(shù)量為11時(shí),調(diào)度總成本為222.78,調(diào)度資源的浪費(fèi)增加了約4.3%的成本。類似的,在遺傳算法中,僅使用時(shí)間聚類方法,當(dāng)集群數(shù)量為最小值4時(shí),運(yùn)營(yíng)商需要付出的調(diào)度成本為313.97,比時(shí)空聚類后的最低成本高出66%;而當(dāng)集群數(shù)量設(shè)置為最大值11時(shí),成本則為206.14,更多的資源如調(diào)度車、工作人員的投入以及訪問點(diǎn)的增加導(dǎo)致了8.99%的成本增加。

表9 不同聚類方法最優(yōu)解比較Table 9Comparison of optimal solutions of various clustering methods

(2)算法性能比較

通過比較兩類算法的調(diào)度方案結(jié)果及其所需總運(yùn)營(yíng)成本,雖然貪心算法求解方案明顯不如遺傳算法,但本文依然想探討各種算法在求解不同聚類結(jié)果時(shí)最優(yōu)調(diào)度路徑時(shí)候的整體表現(xiàn)。

表10展示了兩類算法在不同聚類結(jié)果中優(yōu)化的成本情況。從總體表現(xiàn)來說,貪心算法對(duì)路徑的優(yōu)化明顯不如遺傳算法,但在某些情況下,貪心算法獲得與啟發(fā)式算法一樣的優(yōu)化結(jié)果,如集群數(shù)為7時(shí),兩種算法得到的最低成本相同。貪心算法在每一步做出的選擇僅僅是當(dāng)前最佳,但從全局來看并不一定最優(yōu),因此它雖然能在特定情況下獲得與其他算法一樣優(yōu)秀的調(diào)度路徑,但其整體效果有所不足。不同于貪心算法,遺傳算法具有優(yōu)秀的全局搜索能力,求解過程中該算法對(duì)解的構(gòu)造與保留是概率性的,因此其收斂解與最優(yōu)解的差異是可以接受的。

表10 基于時(shí)空聚類的算法調(diào)度路徑結(jié)果分析Table 10Analysis of scheduling path results based on spatio-temporal clustering algorithm

在求解速度方面,由于貪心算法通過各階段尋優(yōu)即可得到最優(yōu)解,因此求解速度明顯快于遺傳算法;在算法穩(wěn)定性上,由圖9與表10對(duì)比了兩種算法在設(shè)置不同K值下平均解偏離的情況,K值即k-means聚類分析中預(yù)設(shè)的質(zhì)心數(shù),同時(shí)表示單車調(diào)度集群數(shù)量,K值設(shè)置過高將提高調(diào)度成本,過低將導(dǎo)致用戶流失、收入降低。因此K值過高/過低情況下,使用不同算法求解得到的聚類分析結(jié)果中可行解成本普遍偏高,導(dǎo)致平均解偏離程度低。而K值設(shè)置適中情況下,聚類分析結(jié)果差異成為主要影響因素,較依賴于聚類中心初始化,多次聚類后的單車集群方案呈現(xiàn)較大差異,導(dǎo)致兩類算法的平均解偏離程度均較高。另外,實(shí)驗(yàn)結(jié)果可以看出相對(duì)于啟發(fā)式算法,貪心算法更容易受到聚類結(jié)果波動(dòng)的影響。

圖9 算法在不同聚類情況下的穩(wěn)定性比較Figure 9Comparison of the stability of each algorithm under different clustering methods

此外,本文也使用模擬退火算法得到了不同的聚類結(jié)果優(yōu)化后的調(diào)度成本情況,在求解質(zhì)量與求解穩(wěn)定性上,模擬退火算法的總體平均解為240.795,總體平均解偏差為7.394%,與遺傳算法趨近,稍劣于遺傳算法。但在求解速度上,遺傳算法收斂迭代次數(shù)穩(wěn)定在20次以內(nèi),而模擬退火算法需要約40次迭代才能找到收斂解,可見在本文的研究問題中遺傳算法在其收斂趨勢(shì)、收斂速度上展現(xiàn)出較大優(yōu)勢(shì),優(yōu)于模擬退火算法,因此本文僅展現(xiàn)遺傳算法的結(jié)果。

4 結(jié)論與展望

本文利用共享單車需求的時(shí)間、空間特征,通過k-means聚類的方法構(gòu)建了共享單車網(wǎng)絡(luò)模型。在產(chǎn)生虛擬基站的基礎(chǔ)上,共享單車調(diào)度問題轉(zhuǎn)化成了有時(shí)間窗與載重量限制的VPR問題,提出在以成本最小的目標(biāo)函數(shù)中增加了一項(xiàng)因集群劃分不合理而產(chǎn)生的懲罰成本,構(gòu)建了調(diào)度優(yōu)化模型,并使用了貪心算法和遺傳算法兩類算法求解,并生成數(shù)據(jù)進(jìn)行模擬實(shí)驗(yàn),驗(yàn)證模型及算法的有效性。

本文所得的結(jié)論帶來了如下管理啟示:①合理的集群數(shù)量是用戶服務(wù)水平與運(yùn)營(yíng)商調(diào)度成本權(quán)衡后的結(jié)果,如何確定調(diào)度時(shí)的訪問對(duì)象是處理共享單車調(diào)度優(yōu)化問題需要首先關(guān)注的問題。本文通過構(gòu)建懲罰成本來尋找這個(gè)權(quán)衡的平衡點(diǎn),通過一系列的比較得出最合理的集群聚類,相較于其他的聚類結(jié)果在成本上有明顯的優(yōu)化。共享單車運(yùn)營(yíng)商需要了解用戶對(duì)于本公司提供的共享單車服務(wù)的粘性與滿意度,確定合適的調(diào)度集群數(shù)量以通過降低調(diào)度成本來獲得競(jìng)爭(zhēng)優(yōu)勢(shì)。②啟發(fā)式算法在優(yōu)化調(diào)度路徑時(shí)展現(xiàn)出了足夠優(yōu)秀的能力。貪心算法按照當(dāng)前最佳選擇的原則進(jìn)行路徑構(gòu)建,能夠在最短的時(shí)間內(nèi)獲得合理的調(diào)度路徑。遺傳算法則按照一定的規(guī)律對(duì)生成的初始解不斷地進(jìn)行構(gòu)造,通過概率化的尋優(yōu)方法來獲得優(yōu)秀的解。相比于另外啟發(fā)式算法而言,貪心算法雖然在求解時(shí)間上具有很大的優(yōu)勢(shì),但其整體優(yōu)化的效果稍顯不如,運(yùn)營(yíng)商在選擇算法時(shí)需要做出時(shí)間與準(zhǔn)確性之間的權(quán)衡。

現(xiàn)階段國(guó)內(nèi)外的研究重點(diǎn)集中在基于運(yùn)營(yíng)商的調(diào)度方案中,而對(duì)于激勵(lì)用戶的調(diào)度方案有所忽視。運(yùn)營(yíng)商派出調(diào)度車訪問個(gè)節(jié)點(diǎn)在時(shí)間上已經(jīng)有所滯后,對(duì)于調(diào)度期間的需求無法迅速做出反應(yīng),如果能通過一定的激勵(lì)來引導(dǎo)用戶的行為以保證資源的合理分配,會(huì)有更好的時(shí)效性。所以,未來關(guān)于共享單車調(diào)度優(yōu)化的研究應(yīng)該給予基于用戶的調(diào)度更多的關(guān)注,研究定價(jià)、規(guī)則等在引導(dǎo)共享單車用戶主動(dòng)調(diào)配資源方面發(fā)揮的作用。