城市故障共享單車回收路徑優(yōu)化
——以摩拜單車為例

許美賢，鄭 琰

(南京林業(yè)大學(xué)汽車與交通工程學(xué)院，南京 210037)

共享單車行業(yè)的蓬勃發(fā)展極大地方便了人們的出行，但是新興事物運(yùn)營(yíng)過程難免會(huì)導(dǎo)致各種各樣的問題。在共享單車初始發(fā)展階段，企業(yè)為了搶占市場(chǎng)，耗費(fèi)巨資生產(chǎn)大量車輛進(jìn)行投放，而且每家企業(yè)運(yùn)營(yíng)模式基本一致，導(dǎo)致供給遠(yuǎn)遠(yuǎn)大于需求。而在投放使用階段，政府和企業(yè)缺乏相關(guān)運(yùn)營(yíng)管控經(jīng)驗(yàn)，由于亂停亂放、人為毀壞、系統(tǒng)故障等因素導(dǎo)致共享單車的故障率不斷上升。故障共享單車的出現(xiàn)以及回收的延時(shí)性，不僅會(huì)造成大量壞車堆積，嚴(yán)重占用城市空間資源，還將危及用戶的人身和信息安全，降低運(yùn)營(yíng)企業(yè)的服務(wù)質(zhì)量，這些問題都阻礙著共享單車系統(tǒng)的持續(xù)健康發(fā)展。因此為了解決故障車輛對(duì)用戶、企業(yè)、社會(huì)帶來的影響，及時(shí)回收數(shù)量龐大的故障共享單車來進(jìn)行維修或更新成為當(dāng)務(wù)之急，而合理優(yōu)化故障車輛回收路徑，提高回收效率等研究已成為學(xué)者和企業(yè)關(guān)注的焦點(diǎn)問題。

近幾年關(guān)于共享單車的研究大多數(shù)是分析其發(fā)展?fàn)顩r、盈利模式、監(jiān)管措施等幾方面，但對(duì)于故障共享單車回收問題的研究較為少見，僅有的也只在文字?jǐn)⑹錾险归_討論，并不能把定量數(shù)據(jù)和定性分析相結(jié)合，如Liu等[1]在對(duì)固體廢棄物治理方案的理論基礎(chǔ)上進(jìn)行梳理后，認(rèn)為造成共享單車故障率偏高的主要因素是車輛本身質(zhì)量問題及系統(tǒng)的不完善，同時(shí)明確了共享單車在現(xiàn)代交通中起到的重要作用，因此針對(duì)廢舊共享單車回收問題提出了一種回收二階段法，旨在提高故障共享單車回收效率； Wang等[2]提議以整體效益最大化為目標(biāo)，減少個(gè)人遺憾等因素對(duì)回收成本的影響，引入第三方物流供應(yīng)商助力回收工作，優(yōu)化回收管理流程從而達(dá)到最大限度地提高回收效益的目的。這些文獻(xiàn)研究深度大多停留在探究影響故障車輛回收因素的表面上，鮮有能夠全面系統(tǒng)地針對(duì)故障共享單車回收問題優(yōu)化服務(wù)進(jìn)行深入分析。

因此，現(xiàn)主要針對(duì)城市故障共享單車回收問題進(jìn)行優(yōu)化研究，通過構(gòu)建科學(xué)的故障共享單車回收框架，并利用K-means算法對(duì)回收維修服務(wù)中心區(qū)域內(nèi)的故障車輛進(jìn)行聚類處理，形成初始服務(wù)節(jié)點(diǎn)。以回收總成本最小為優(yōu)化目標(biāo)建立路徑優(yōu)化模型，并設(shè)計(jì)改進(jìn)的蟻群算法對(duì)所建模型進(jìn)行求解，分析滿載率大小和聚類服務(wù)節(jié)點(diǎn)個(gè)數(shù)對(duì)優(yōu)化結(jié)果產(chǎn)生的影響，驗(yàn)證模型和方法的可行性。

1 問題描述

1.1 故障共享單車定義和分類

把共享單車故障車輛定義為在運(yùn)營(yíng)過程中因車輛發(fā)生損壞而無法保障正常騎行、存在安全隱患的車輛。另外為了更好地開展后續(xù)回收問題的研究工作，有必要對(duì)故障共享單車進(jìn)行分類處理，將其分為三大類。

(1)由于人為毀壞、車輛自身缺陷等因素造成的不符合安全標(biāo)準(zhǔn)的故障單車(類型一)。這類車輛通常可以由用戶掃碼解鎖時(shí)被識(shí)別出來，如果用戶發(fā)現(xiàn)將要使用的車輛存在二維碼丟失或損壞、無法解鎖等問題，可以馬上在手機(jī)APP進(jìn)行報(bào)修，運(yùn)營(yíng)企業(yè)的線上運(yùn)維系統(tǒng)就能確定故障單車的設(shè)備信息和地理位置，及時(shí)進(jìn)行回收處理。

(2)超過規(guī)定使用年限，強(qiáng)制要求報(bào)廢更新維修的故障單車(類型二)。政府規(guī)定共享單車的正常使用壽命是三年，在車輛投放市場(chǎng)超過規(guī)定期限后，無論車輛是否喪失使用價(jià)值，所有共享單車都必須進(jìn)行回收更新。企業(yè)的運(yùn)營(yíng)管理系統(tǒng)能夠根據(jù)市場(chǎng)投放時(shí)間自動(dòng)識(shí)別此類車輛，并列入故障單車名單，切換運(yùn)行系統(tǒng)使得車輛無法解鎖騎行，從而防止用戶的誤騎。

(3)因?yàn)檐囨i的GPS定位器損壞，而無法定位或定位不準(zhǔn)的故障共享單車(類型三)。當(dāng)企業(yè)運(yùn)維系統(tǒng)對(duì)某輛共享單車的位置信息追蹤不到時(shí)，通常都會(huì)將其標(biāo)識(shí)為定位出現(xiàn)故障的車輛，智能查找位置信息記錄條，追蹤搜索此車輛上一次所在的地址和狀態(tài)，并根據(jù)這些信息在鄰近范圍尋查故障單車。

1.2 故障共享單車的回收準(zhǔn)則

故障共享單車回收依照著特定的準(zhǔn)則，根據(jù)回收系統(tǒng)的4個(gè)組成要素：故障共享單車、初始服務(wù)節(jié)點(diǎn)、回收車輛、回收維修服務(wù)中心，設(shè)計(jì)了一個(gè)雙層空間回收網(wǎng)絡(luò)，該網(wǎng)絡(luò)主要由上下兩層平面網(wǎng)絡(luò)構(gòu)成，中間屬于投影的連接[3]。

根據(jù)圖 1故障共享單車的回收網(wǎng)絡(luò)，分析回收過程需要依照的具體準(zhǔn)則如下。

圖 1 故障共享單車回收網(wǎng)絡(luò)Fig.1 Unusable sharing bicycle recycling network

(1)在城市中，為了能夠容納大量的故障單車，需要規(guī)劃設(shè)計(jì)若干個(gè)回收維修服務(wù)中心。每個(gè)回收維修服務(wù)中心承擔(dān)著其管轄區(qū)域內(nèi)的故障單車回收處理任務(wù)，設(shè)計(jì)規(guī)定在每個(gè)正常工作日對(duì)故障共享單車的位置信息進(jìn)行數(shù)據(jù)統(tǒng)計(jì)，對(duì)出現(xiàn)故障單車數(shù)量較多的區(qū)域及時(shí)執(zhí)行一次回收任務(wù)，而該區(qū)域中后續(xù)新增的故障單車則留在下一次再回收處理。

(2)在每個(gè)回收維修服務(wù)中心的管轄區(qū)域內(nèi)，需要依據(jù)故障共享單車的數(shù)量和位置決定形成若干的初始服務(wù)節(jié)點(diǎn)，如圖1中A點(diǎn)，在執(zhí)行回收任務(wù)時(shí)，回收車輛停放在初始服務(wù)節(jié)點(diǎn)，搬運(yùn)工人需要將一定區(qū)域中散落錯(cuò)亂的故障共享單車移送至該初始服務(wù)節(jié)點(diǎn)，當(dāng)把該節(jié)點(diǎn)區(qū)域內(nèi)的故障單車收集完成后，駕駛回收車輛訪問下一個(gè)節(jié)點(diǎn)區(qū)域繼續(xù)執(zhí)行故障單車回收任務(wù)。

(3)在規(guī)劃設(shè)計(jì)的若干回收維修服務(wù)中心內(nèi)配備著一定數(shù)量的回收車輛，執(zhí)行回收任務(wù)時(shí)，回收車輛會(huì)從某個(gè)回收維修服務(wù)中心內(nèi)出發(fā)，訪問歷經(jīng)每個(gè)初始服務(wù)節(jié)點(diǎn)，最后把收集到的故障單車全部送到回收維修服務(wù)中心，完成一次回收任務(wù)。

綜上，故障共享單車的回收過程劃分成兩個(gè)環(huán)節(jié)：①先依據(jù)回收維修服務(wù)中心管轄區(qū)域內(nèi)故障共享單車的數(shù)量和位置決定形成若干的初始服務(wù)節(jié)點(diǎn)，再把位置錯(cuò)亂的故障共享單車聚集在鄰近的初始服務(wù)節(jié)點(diǎn)上；②運(yùn)算設(shè)計(jì)出能夠?qū)崿F(xiàn)優(yōu)化目標(biāo)的回收車輛行駛路線，同時(shí)滿足訪問歷經(jīng)每個(gè)初始服務(wù)節(jié)點(diǎn)的要求。

1.3 故障共享單車的回收流程

結(jié)合上述對(duì)故障共享單車回收準(zhǔn)則的分析，確定回收流程，主要包括四大步驟，如圖 2所示。

圖 2 故障共享單車回收流程圖Fig.2 Flow chart of unusable sharing bicycles recycling

步驟一收集處理數(shù)據(jù)。主要針對(duì)類型一和類型二的故障共享單車數(shù)量和位置信息進(jìn)行收集，其中類型一在用戶報(bào)修時(shí)即時(shí)登記報(bào)備車輛位置信息；類型二在運(yùn)營(yíng)企業(yè)系統(tǒng)中會(huì)自動(dòng)記錄其投放市場(chǎng)的起始時(shí)間，待超過規(guī)定使用年限時(shí)，及時(shí)納入回收范圍；而針對(duì)類型三需查找該種車輛上一次停放的地址，并據(jù)此在鄰近范圍追蹤其數(shù)量和位置。當(dāng)管轄區(qū)域內(nèi)三種類型故障共享單車的數(shù)量和位置確定后，即可進(jìn)行統(tǒng)計(jì)分析。

步驟二聚類故障單車。圖 2中，上層平面網(wǎng)絡(luò)就是故障共享單車的聚類環(huán)節(jié)。根據(jù)步驟一統(tǒng)計(jì)處理的結(jié)果，把回收維修服務(wù)中心管轄區(qū)域中的故障共享單車?yán)肒-means算法實(shí)行聚類處理，算出的聚類中心就是根據(jù)每次回收情況可進(jìn)行調(diào)整的初始服務(wù)節(jié)點(diǎn)，保障回收車輛能充分地訪問遍歷回收空間。搬運(yùn)工人把節(jié)點(diǎn)區(qū)域的所有故障共享單車移送至初始服務(wù)節(jié)點(diǎn)。

步驟三優(yōu)化回收路徑。圖 2中，下層平面網(wǎng)絡(luò)就是規(guī)劃設(shè)計(jì)出執(zhí)行回收任務(wù)時(shí)，回收車輛從回收維修服務(wù)中心出發(fā)，遍歷所有初始服務(wù)節(jié)點(diǎn)，最后返回至回收維修服務(wù)中心的最佳行駛線路。依據(jù)聚類處理的結(jié)果，設(shè)立故障單車回收總成本最小的優(yōu)化目標(biāo)，綜合考慮回收車輛的車載容量限制、回收時(shí)間限制等約束因素的影響，規(guī)劃設(shè)計(jì)出每輛回收車輛的最優(yōu)回收路線。

步驟四完成回收工作。當(dāng)確定初始服務(wù)節(jié)點(diǎn)和優(yōu)化回收路徑后，把回收工作分派給各車輛的工作人員，把聚類信息及回收線路傳送至車輛調(diào)度監(jiān)控終端，回收工作人員根據(jù)終端分配的任務(wù)按照優(yōu)化方案逐一完成。

2 故障共享單車空間聚類

2.1 基于K-means算法的故障共享單車聚類模型

K-means算法適用于處理小中等體量的數(shù)據(jù)集，運(yùn)算耗時(shí)短，復(fù)雜程度低。考慮到在選取初始服務(wù)節(jié)點(diǎn)時(shí)，需滿足各故障共享單車到初始服務(wù)節(jié)點(diǎn)的距離總和最小化，以距離作為前提條件，同時(shí)收集的數(shù)據(jù)規(guī)模屬于小中等體量，所以選取K-means 聚類算法進(jìn)行初始服務(wù)節(jié)點(diǎn)的聚類分析，確定其數(shù)量及位置。

首先，假定由N個(gè)二維隨機(jī)變量即x1，x2，…，xn組成樣本數(shù)據(jù)集X={x1，x2，…，xn}；其次，根據(jù)用戶指定需要的聚類簇?cái)?shù)K，把樣本數(shù)據(jù)集X={x1，x2，…，xn}劃分成K個(gè)類簇；再次，引進(jìn)P={pk，k=1，2，…，K}的二維向量組，其中pk指的是第k個(gè)聚類中心；最后，計(jì)算樣本數(shù)據(jù)點(diǎn)x1，x2，…，xn分配到各聚類中心pk的歐式距離，并保證最小化其距離的平方和。兩次計(jì)算各個(gè)聚類中心的位置誤差平方和公式為

(1)

s.t.

(2)

式中： SEE為各個(gè)聚類中心的位置誤差平方和；tnk為0～1的整數(shù)變量。回收車輛的工作服務(wù)地點(diǎn)是各個(gè)聚類中心，需要利用K-means空間聚類算法進(jìn)行聚類中心數(shù)量的求解[4]。

2.2 故障共享單車聚類步驟

使用K-means聚類算法對(duì)故障共享單車進(jìn)行聚類處理，實(shí)際上就是在回收問題中選取初始服務(wù)節(jié)點(diǎn)[5]。求解流程步驟如下。

步驟一依據(jù)回收維修服務(wù)中心的管轄區(qū)域中故障共享單車的數(shù)據(jù)信息，輸入用戶指定的初始服務(wù)節(jié)點(diǎn)數(shù)量K以及故障共享單車樣本數(shù)據(jù)集合(X={x1，x2，…，xn})。

步驟二在N個(gè)故障共享單車數(shù)據(jù)點(diǎn)中任意選取K個(gè)樣本數(shù)據(jù)作為初始服務(wù)節(jié)點(diǎn)。

步驟三計(jì)算各故障共享單車數(shù)據(jù)點(diǎn)到初始服務(wù)節(jié)點(diǎn)的二維空間直線距離，并把故障共享單車數(shù)據(jù)點(diǎn)逐一分配給與之相距最近的初始服務(wù)節(jié)點(diǎn)上。

步驟四待分配完所有故障共享單車數(shù)據(jù)點(diǎn)后，再次運(yùn)算確定K個(gè)初始服務(wù)節(jié)點(diǎn)在聚類后的中心位置。

步驟五對(duì)比分析聚類前和聚類后K個(gè)初始服務(wù)節(jié)點(diǎn)的位置信息，判斷各初始服務(wù)節(jié)點(diǎn)位置是否有改變；若已經(jīng)改變，重新回到步驟二；若前后兩次各初始服務(wù)節(jié)點(diǎn)的位置均無改變，則進(jìn)入步驟六。

步驟六輸出聚類結(jié)果P={p1，p2，…，pk}。

3 故障共享單車回收路徑優(yōu)化模型

3.1 模型假設(shè)

由于回收過程相對(duì)煩瑣，需要考慮的影響因素和涉及的參數(shù)數(shù)量都比較龐大。因此，為使后續(xù)研究更加方便以及所建模型的可操作性更強(qiáng)，在構(gòu)建故障共享單車回收路徑優(yōu)化模型[6]，需要提出以下假設(shè)。

(1)無法定位或定位不準(zhǔn)的故障共享單車(即類型三)的地理位置信息是精確無誤的。

(2)回收車輛在城市網(wǎng)絡(luò)中每個(gè)初始服務(wù)節(jié)點(diǎn)之間的往返距離是固定的，行駛時(shí)間也是已知及相同的，不受道路條件、實(shí)時(shí)車流等因素影響。

(3)搬運(yùn)工人在裝卸搬運(yùn)故障共享單車時(shí)，平均每輛所花費(fèi)的時(shí)間一樣。

(4)執(zhí)行回收任務(wù)過程中，回收車輛的行駛速度保持勻速且已知，不需考慮交通擁堵。

(5)在一次回收任務(wù)中，各初始服務(wù)節(jié)點(diǎn)管轄范圍內(nèi)的故障共享單車數(shù)量及位置不變，是靜態(tài)的。

3.2 符號(hào)說明

根據(jù)上述對(duì)故障共享單車回收問題的描述及模型假設(shè)，現(xiàn)對(duì)其模型中的參數(shù)符號(hào)作出詳細(xì)定義，如表 1所示。

表 1 故障共享單車回收模型具體參數(shù)符號(hào)及詳細(xì)定義Table1 Specific parameter symbols and detailed defini- tions of the recovery model of unusable sharing bicycles

3.3 模型建立

在傳統(tǒng)車輛路徑優(yōu)化模型的基礎(chǔ)上，考慮以執(zhí)行一次回收任務(wù)的總成本最小為優(yōu)化目標(biāo)，構(gòu)建故障共享單車回收路徑優(yōu)化模型，即

(3)

s.t.

(4)

(5)

(6)

(7)

Hj≤Lw+S(1-yjw)，?j∈R{O}，w∈W

(8)

Hj≥0，?j∈R{O}

(9)

xijw∈{0，1}，?i∈R，?j∈R，w∈W

(10)

yiw∈{0，1}，?i∈R，w∈W

(11)

(12)

(13)

|V|≥2，w∈W

(14)

在所建模型中目標(biāo)函數(shù)式(3)表示進(jìn)行一次回收工作的總成本最小，即包括兩部分成本最小化：①回收車輛運(yùn)輸故障單車的行駛成本最小化；②人工搬運(yùn)故障單車到各服務(wù)節(jié)點(diǎn)的勞動(dòng)力成本最小化。約束條件中，式(4)表示各個(gè)初始服務(wù)節(jié)點(diǎn)均能被回收車輛訪問且只可訪問一次；式(5)表示回收車輛從回收維修服務(wù)中心駛出時(shí)所要求的數(shù)量；式(6)及式(7)表示初始服務(wù)節(jié)點(diǎn)i和j只可由同一輛回收車輛訪問，即在先后到達(dá)和離開節(jié)點(diǎn)i和j的都是同一回收車輛；式(8)表示回收車輛訪問完節(jié)點(diǎn)j離開時(shí)所裝載的故障單車數(shù)量不能超過額定容納量；式(9)表示回收車輛在訪問完任意初始服務(wù)節(jié)點(diǎn)時(shí)所裝載的故障單車數(shù)量為非負(fù)數(shù)；式(10)及式(11)表示決策變量的0～1取值類型和范圍。式(12)表示每輛回收車輛裝載故障單車的數(shù)量不得小于規(guī)定最低的裝載率；式(13)表示進(jìn)行一次回收工作時(shí)每輛回收車輛花費(fèi)的總用時(shí)上限；式(14)表示以防回收車輛在行駛過程中出現(xiàn)閉合子回路的情況。

3.4 改進(jìn)蟻群算法設(shè)計(jì)

考慮到蟻群算法在求解性能上有很強(qiáng)的魯棒性和全局搜索能力，其編碼易于實(shí)現(xiàn)和理解；同時(shí)參考以往大量的車輛路徑優(yōu)化問題研究文獻(xiàn)，發(fā)現(xiàn)蟻群算法模型的主要參數(shù)的取值范圍比其他算法更加清晰明確，有利于對(duì)解決方案進(jìn)行優(yōu)化處理，但傳統(tǒng)蟻群算法的收斂時(shí)間長(zhǎng)、易陷入局部最優(yōu)[7]。因此，將設(shè)計(jì)改進(jìn)蟻群算法對(duì)故障共享單車回收路徑優(yōu)化模型進(jìn)行求解。算法的關(guān)鍵參數(shù)定義如表 2所示。

表 2 改進(jìn)蟻群算法關(guān)鍵參數(shù)定義Table2 Definition of key parameters of improved ant colony algorithm

(1)初始化蟻群系統(tǒng)。開始先將信息素濃度進(jìn)行初始化處理，輸入螞蟻數(shù)量q(q=1，2，…，z)。在t時(shí)刻，螞蟻q遵循狀態(tài)轉(zhuǎn)移規(guī)則從回收維修服務(wù)中心出發(fā)，任意選取符合滿載率和回收時(shí)間限制的初始服務(wù)節(jié)點(diǎn)準(zhǔn)備執(zhí)行回收工作。倘若螞蟻q無法找到符合條件的初始服務(wù)節(jié)點(diǎn)，那么將返回至回收維修服務(wù)中心。當(dāng)把故障共享單車運(yùn)送到回收維修服務(wù)中心后，需使所有螞蟻逐一用相同的方式訪問完每個(gè)初始服務(wù)節(jié)點(diǎn)[8]。

(15)

Aq={f-Tq}

(16)

在式(15)中，信息啟發(fā)式因子ω≥0，當(dāng)ω越大時(shí)，螞蟻根據(jù)信息素濃度選取將要爬行的線路可能性越大，相互之間的交流配合更加密切；期望啟發(fā)式因子λ≥0，當(dāng)λ越大時(shí)，其狀態(tài)轉(zhuǎn)移規(guī)則就會(huì)越靠近貪心概率。下面將以啟發(fā)式信息ηij(t)作為初始服務(wù)節(jié)點(diǎn)i到j(luò)之間距離的倒數(shù)，具體如公式為

(17)

為了取得更大概率的最優(yōu)解，在其中添加2-opt搜索運(yùn)作機(jī)制，使得當(dāng)前最優(yōu)解在搜索路徑回路中進(jìn)行多次更新[9]。

(3)改進(jìn)的信息素更新。為了加快收斂速度以及避免陷入局部最優(yōu)解的情況，只選擇進(jìn)行全局更新的方法，在每次迭代計(jì)算后進(jìn)行全局更新，尋找最短路線上的信息素濃度[10]。先將t時(shí)刻連接初始服務(wù)節(jié)點(diǎn)i與j之間的路徑(i，j)信息素濃度進(jìn)行初始化，公式為

σij(t)=σmax

(18)

在每次迭代計(jì)算后，只對(duì)最短路徑上的螞蟻信息素進(jìn)行更新，使得最優(yōu)的解得以加強(qiáng)，全局信息素更新規(guī)則公式為

σij(t+1)=τσij(t)+Δσij

(19)

(20)

(21)

(22)

式中： avg=f/2；g為進(jìn)行一次搜索能夠?qū)ふ业饺肿罴崖肪€的概率。

另外利用所設(shè)計(jì)的改進(jìn)蟻群算法尋找最優(yōu)路徑的流程如圖 3所示。

圖 3 利用改進(jìn)蟻群算法尋找最優(yōu)路徑的流程圖Fig.3 Flow chart of finding the optimal path using improved ant colony algorithm

4 上海市摩拜單車回收實(shí)例分析

4.1 故障摩拜單車聚類

以上海南站為中心，選取2km的方形區(qū)域內(nèi)的摩拜單車作為研究對(duì)象，并把上海南站假定為所在區(qū)域的回收維修服務(wù)中心。從摩拜公司2019年4月某日的原始訂單數(shù)據(jù)中隨機(jī)選取238輛摩拜單車作為待回收的故障車輛，制作其分布的熱力圖如圖 4 所示，紅色部分代表故障摩拜單車密度高，黃色次之，亮綠色適中，藍(lán)色代表其數(shù)量較少，這些顏色部分組成了回收維修中心所要管轄的區(qū)域。

圖 4 故障摩拜單車分布的熱力圖Fig.4 Heat map of malfunctioning Mobike distribution

設(shè)定K-means算法參數(shù)進(jìn)行求解，得到聚類結(jié)果。K-means聚類算法在選取數(shù)量不同的聚類點(diǎn)運(yùn)算過程中，迭代次數(shù)通常不超過20次，其迭代運(yùn)算效率相對(duì)較高。K-means算法誤差平方和收斂圖如圖 5 所示，當(dāng)設(shè)置聚類點(diǎn)個(gè)數(shù)為12時(shí)，位置誤差平方和值為51.96km2，數(shù)值變化曲線趨于穩(wěn)定，代表算法進(jìn)行了收斂，由此該案例設(shè)定聚類點(diǎn)數(shù)量為12個(gè)，將其代入求解初始服務(wù)節(jié)點(diǎn)的位置[11]。

圖 5 不同聚類點(diǎn)試驗(yàn)下誤差平方和收斂圖Fig.5 Squared error and convergence plots under different clustering point tests

經(jīng)過求解出各聚類中心的位置信息，具體如表 3 所示。將上海南站設(shè)置為回收維修服務(wù)中心(O點(diǎn))，以深藍(lán)色文字顯示，將各聚類中心所在位置用氣球形的紅點(diǎn)進(jìn)行地圖標(biāo)記(圖 6)，使得位置分布更加直觀。

表 3 K-means算法得到的12個(gè)聚類中心信息表Table3 12 Cluster center informationTable obtained by K-means algorithm

圖 6 標(biāo)記聚類中心所在位置的地圖Fig.6 Map marking the location of cluster centers

4.2 優(yōu)化模型參數(shù)設(shè)置

本實(shí)例給回收維修服務(wù)中心配備4輛類型一致的回收車輛，規(guī)定每輛回收車輛最多能夠裝載70輛故障摩拜單車。利用百度地圖進(jìn)行測(cè)距，確定回收車輛在各初始服務(wù)節(jié)點(diǎn)以及回收維修服務(wù)中心每?jī)傻刂g的行駛時(shí)間[12]，列出具體時(shí)間矩陣(表 4)，優(yōu)化模型的主要參數(shù)設(shè)置如表 5所示。

4.3 路徑優(yōu)化結(jié)果分析

在計(jì)算機(jī)型號(hào)為intel core i7-8565U，處理器主頻為2.6GHz，內(nèi)存為4GB，操作系統(tǒng)為Windows10的MATLAB R2019b計(jì)算軟件上進(jìn)行運(yùn)算求出每輛回收車輛對(duì)應(yīng)行駛的路徑，并根據(jù)結(jié)果分析車輛的裝載情況、行駛花費(fèi)的時(shí)間[13]，從而進(jìn)一步求出執(zhí)行回收任務(wù)所需的總成本，改進(jìn)蟻群算法具體求解優(yōu)化結(jié)果如表 6所示。

表 4 12個(gè)初始服務(wù)節(jié)點(diǎn)的行程時(shí)間矩陣Table4 Travel time matrix of 12 initial service nodes

表 5 優(yōu)化模型的主要參數(shù)值Table5 Optimize the main parameter values of the model

表 6 運(yùn)用改進(jìn)蟻群算法求解案例模型所得的優(yōu)化結(jié)果Table6 The optimization results obtained by using the improved ant colony algorithm to solve the case model

在案例得出的最優(yōu)結(jié)果中，回收故障摩拜單車所需花費(fèi)的總成本為2905元，即可得知平均每回收一輛故障摩拜單車需要花費(fèi)12.21元。從表 6可知，在4條回收路徑中，每輛回收車輛的行駛用時(shí)與人工搬運(yùn)故障摩拜單車用時(shí)的總和，即每輛回收車輛進(jìn)行回收工作耗費(fèi)的總時(shí)間在438～534min，花費(fèi)時(shí)間相差比較少，這說明了本案例中故障摩拜單車的聚類處理結(jié)果和規(guī)劃出來的回收行駛路徑均是科學(xué)合理的。除此之外，4輛回收車輛裝載故障摩拜單車數(shù)量分別為64、60、52、62輛，4輛回收車輛的滿載率均在74.29%及以上。因此，結(jié)合所建的回收路徑優(yōu)化模型判斷得出，4輛回收車輛在符合滿載率約束、回收工作時(shí)間約束等限制條件下，均實(shí)現(xiàn)了回收行駛路徑最優(yōu)化的目的。

4.4 算法性能驗(yàn)證分析

文章應(yīng)用MATLAB進(jìn)行有效的目標(biāo)函數(shù)值優(yōu)化處理，其中圖 7表示在10次計(jì)算迭代中最快、平均以及最慢的爬行搜索路徑過程，該算例中4輛回收車輛運(yùn)輸行駛完全部路程的總時(shí)間為224min，改進(jìn)蟻群算法在迭代計(jì)算時(shí)最快在72代收斂求得最佳路徑，10次計(jì)算平均收斂所在代數(shù)為82，最慢的在236代收斂求得最佳爬行路徑。

圖 7 改進(jìn)蟻群算法迭代計(jì)算收斂圖Fig.7 Improved ant colony algorithm iterative calculation convergence graph

圖 8 3種算法最快收斂情況對(duì)比圖Fig.8 Comparison of the fastest convergence of the three algorithms

為了對(duì)比驗(yàn)證提出的改進(jìn)蟻群算法的有效性，根據(jù)所構(gòu)建的路徑優(yōu)化模型分別對(duì)傳統(tǒng)蟻群算法和模擬退火算法進(jìn)行修改，選取3種算法的最快收斂情況進(jìn)行對(duì)比分析，如圖 8所示。提出的改進(jìn)蟻群算法最快在72代收斂，螞蟻爬行總時(shí)間為224min；傳統(tǒng)蟻群算法最快在187代收斂，搜索總時(shí)間為231min；模擬退火算法最快在216代收斂，總行程時(shí)間和傳統(tǒng)蟻群算法一樣。對(duì)比結(jié)果表明，改進(jìn)蟻群算法能夠顯著降低回收車輛行駛路徑總時(shí)間，比兩種傳統(tǒng)算法計(jì)算收斂的速度更快，從而有效降低運(yùn)輸總成本，并證明了該算法的合理適用性。

4.5 靈敏度分析4.5.1 滿載率不同情況下對(duì)比分析

為進(jìn)一步驗(yàn)證所建回收路徑優(yōu)化模型和改進(jìn)的蟻群算法的正確性與合理適用性，只改變回收車輛滿載率系數(shù)μ，保持其他主要參數(shù)不變的情況下，設(shè)計(jì)進(jìn)行多組對(duì)比驗(yàn)證實(shí)驗(yàn)，從而探究滿載率系數(shù)μ的改變對(duì)求解優(yōu)化結(jié)果產(chǎn)生的影響。其中： 在設(shè)置的4種滿載率約束條件下，4輛回收車輛進(jìn)行回收工作時(shí)分別裝載故障摩拜單車的數(shù)量如圖 9所示。

圖 9 不同滿載率情況下各回收車輛裝載故障摩拜單車的數(shù)量Fig.9 The number of failed Mobike bikes loaded on each recovered vehicle under different full load rates

根據(jù)對(duì)比實(shí)驗(yàn)求解得出的優(yōu)化結(jié)果能夠看出，當(dāng)設(shè)置的回收車輛滿載率系數(shù)μ越大時(shí)，每輛回收車輛最終裝載故障摩拜單車的數(shù)量更加均衡，這表明了選取不同滿載率進(jìn)行限制對(duì)最終優(yōu)化結(jié)果會(huì)產(chǎn)生一定的影響[14-15]。

表 7 不同滿載率情況下的最優(yōu)求解結(jié)果Table7 Optimal solution results under different full load ratios

根據(jù)表 7可知，滿載率系數(shù)μ與回收車輛行駛用時(shí)呈現(xiàn)正相關(guān)性，就是說當(dāng)滿載率系數(shù)越小時(shí)，則回收車輛行駛用時(shí)越短，執(zhí)行回收任務(wù)所需總成本越少。在設(shè)置的4個(gè)系數(shù)中，0.5的滿載率系數(shù)值最小，因而在該系數(shù)下，回收車輛行駛用時(shí)最短僅需212min，最后所需回收總成本最少僅為2845元；0.8的滿載率系數(shù)值最大，其回收車輛行駛用時(shí)最長(zhǎng)為230min，最后所需回收總成本最多為2935元。其中對(duì)比分析圖 9中各組優(yōu)化結(jié)果能夠得出，當(dāng)選取較大的滿載率系數(shù)時(shí)，4輛回收車輛裝載故障摩拜單車的數(shù)量極差相距較小，所以當(dāng)回收路線相同的情況下，首先選擇較高的滿載率系數(shù)來代入模型求解得出的結(jié)果最優(yōu)。綜上所述，選取不同的滿載率系數(shù)不僅會(huì)直接影響各回收車輛裝載故障摩拜單車的效率，還會(huì)體現(xiàn)回收工作量分配的合理公平性。因此在實(shí)際回收任務(wù)安排中，上層決策者需要結(jié)合實(shí)際回收情況的工作量，考慮在故障共享單車回收路徑優(yōu)化數(shù)學(xué)模型原有的目標(biāo)函數(shù)基礎(chǔ)上增加最大滿載率系數(shù)，使得模型更加貼合實(shí)際規(guī)劃需求[16-17]。

4.5.2 聚類服務(wù)點(diǎn)個(gè)數(shù)不同對(duì)比分析

針對(duì)聚類服務(wù)節(jié)點(diǎn)數(shù)量進(jìn)行設(shè)置，對(duì)比分析其個(gè)數(shù)差異對(duì)最后求解得到的優(yōu)化結(jié)果產(chǎn)生的影響。從表 8中可知，當(dāng)回收車輛滿載率系數(shù)不同時(shí)，選取聚類服務(wù)節(jié)點(diǎn)個(gè)數(shù)為10的情況下，回收工作所需的總成本最高；當(dāng)回收車輛滿載率系數(shù)相同時(shí)，選取聚類服務(wù)節(jié)點(diǎn)個(gè)數(shù)為14的情況下，回收工作所需的總成本最高[18-20]，所以能夠得出以下兩方面的結(jié)論。

表 8 不同聚類服務(wù)節(jié)點(diǎn)個(gè)數(shù)對(duì)優(yōu)化結(jié)果的影響Table8 The Influence of the number of different clustering service nodes on the optimization results

(1)若選取數(shù)量較少的聚類服務(wù)節(jié)點(diǎn)，則將增加人工搬運(yùn)故障摩拜單車所需的時(shí)間，從而提高了整個(gè)回收工作最終花費(fèi)的總成本。

(2)若選取數(shù)量較多的聚類服務(wù)節(jié)點(diǎn)，則將增加回收車輛行駛所需的時(shí)間，從而提高了車輛運(yùn)輸成本，導(dǎo)致增加了執(zhí)行回收任務(wù)耗費(fèi)的總成本。

因此，對(duì)比分析說明了所建模型和設(shè)計(jì)的算法能夠應(yīng)用到實(shí)際故障共享單車回收任務(wù)中，而在進(jìn)行實(shí)際回收工作前，應(yīng)綜合考慮回收車輛每分鐘產(chǎn)生的運(yùn)營(yíng)成本Cw以及搬運(yùn)故障摩拜單車每分鐘產(chǎn)生的勞動(dòng)力成本Ce的數(shù)值變化，從而制訂合理的回收計(jì)劃。

5 結(jié)論

以上海市徐匯區(qū)部分區(qū)域的故障摩拜單車作為研究對(duì)象，利用K-means聚類算法對(duì)故障摩拜單車進(jìn)行聚類處理，找出初始服務(wù)節(jié)點(diǎn)所在位置，接著建立路徑優(yōu)化模型并設(shè)計(jì)改進(jìn)蟻群算法對(duì)其進(jìn)行求解，得到回收路徑優(yōu)化結(jié)果，并結(jié)合優(yōu)化后的行駛路徑對(duì)進(jìn)行回收工作花費(fèi)的時(shí)間及總成本進(jìn)行分析。針對(duì)滿載率系數(shù)大小和聚類服務(wù)節(jié)點(diǎn)個(gè)數(shù)進(jìn)行對(duì)照實(shí)驗(yàn)，分析幾種選擇下對(duì)算例結(jié)果產(chǎn)生的影響，研究發(fā)現(xiàn)滿載率系數(shù)與回收車輛行駛用時(shí)呈現(xiàn)正相關(guān)性，以及服務(wù)節(jié)點(diǎn)個(gè)數(shù)同時(shí)影響著人工搬運(yùn)時(shí)間和行駛時(shí)間，從而對(duì)回收總成本產(chǎn)生較大影響。同時(shí)驗(yàn)證了所建模型和方法能夠應(yīng)用在實(shí)際回收工作中，回收系統(tǒng)流程可以為共享單車企業(yè)在選擇最佳回收路徑方案時(shí)提供良好的參考。但由于數(shù)據(jù)獲取過程中的回收維修服務(wù)中心以及各初始服務(wù)節(jié)點(diǎn)兩地之間的行程時(shí)間矩陣數(shù)據(jù)是使用百度地圖測(cè)距獲取的，過于理想化；同時(shí)設(shè)置回收車輛在各自的優(yōu)化路徑中運(yùn)輸行駛速度一致且保持勻速，沒有充分考慮實(shí)際城市交通道路架構(gòu)、高峰擁堵以及突發(fā)事件等方面的因素；另外規(guī)定故障共享單車在回收工作進(jìn)行時(shí)是保持靜態(tài)的，但實(shí)際車輛狀態(tài)和位置是動(dòng)態(tài)變化的。因此，在后續(xù)研究中需要著手分析動(dòng)態(tài)情況下故障共享單車的回收優(yōu)化，開展系統(tǒng)全面的實(shí)地調(diào)研工作，緊密聯(lián)系研究區(qū)域的實(shí)際交通網(wǎng)絡(luò)情況來處理模型計(jì)算數(shù)據(jù)，使案例分析結(jié)果更加貼合實(shí)際。