許美賢，鄭 琰

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

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

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

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

1 問題描述

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

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

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

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

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

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

故障共享單車回收依照著特定的準(zhǔn)則，根據(jù)回收系統(tǒng)的4個組成要素：故障共享單車、初始服務(wù)節(jié)點、回收車輛、回收維修服務(wù)中心，設(shè)計了一個雙層空間回收網(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è)計若干個回收維修服務(wù)中心。每個回收維修服務(wù)中心承擔(dān)著其管轄區(qū)域內(nèi)的故障單車回收處理任務(wù)，設(shè)計規(guī)定在每個正常工作日對故障共享單車的位置信息進行數(shù)據(jù)統(tǒng)計，對出現(xiàn)故障單車數(shù)量較多的區(qū)域及時執(zhí)行一次回收任務(wù)，而該區(qū)域中后續(xù)新增的故障單車則留在下一次再回收處理。

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

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

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

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

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

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

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

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

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

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

2 故障共享單車空間聚類

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

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

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

(1)

s.t.

(2)

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

2.2 故障共享單車聚類步驟

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

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

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

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

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

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

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

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

3.1 模型假設(shè)

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

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

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

(3)搬運工人在裝卸搬運故障共享單車時，平均每輛所花費的時間一樣。

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

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

3.2 符號說明

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

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

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

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

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

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

(15)

Aq={f-Tq}

(16)

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

(17)

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

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

σij(t)=σmax

(18)

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

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

(19)

(20)

(21)

(22)

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

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

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

4 上海市摩拜單車回收實例分析

4.1 故障摩拜單車聚類

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

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

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

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

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

表 3 K-means算法得到的12個聚類中心信息表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è)置

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

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

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

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

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

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

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

4.4 算法性能驗證分析

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

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

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

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

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

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

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

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

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

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

4.5.2 聚類服務(wù)點個數(shù)不同對比分析

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

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

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

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

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

5 結(jié)論

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