王玖河，高 輝，劉 歡

(燕山大學(xué) 1. 經(jīng)濟(jì)管理學(xué)院；2.京津冀協(xié)同發(fā)展管理創(chuàng)新研究中心，河北 秦皇島 066000)

共享助力車面臨用戶需求的潮汐性所導(dǎo)致的電子圍欄站點(diǎn)之間的數(shù)量不平衡問題，并且在顧客使用中會(huì)耗費(fèi)電池電量。因此，共享助力車的調(diào)度由兩部分組成：1) 單車數(shù)量上的平衡；2) 對(duì)缺電助力車更換電池。在實(shí)際的調(diào)度過程中運(yùn)營(yíng)方把助力車數(shù)量平衡與電池更換分開進(jìn)行。這種調(diào)度方式不僅增加了運(yùn)營(yíng)方的調(diào)度次數(shù)，同時(shí)還不利于消費(fèi)者的消費(fèi)體驗(yàn)，即會(huì)出現(xiàn)站點(diǎn)的助力車的數(shù)量足夠，個(gè)別助力車缺電而無法使用的情況。

有部分學(xué)者對(duì)公共自行車和有固定?？奎c(diǎn)的共享單車進(jìn)行研究。Mao等[1]通過得到自行車各站點(diǎn)的可視化信息，實(shí)時(shí)預(yù)測(cè)進(jìn)出流量，從而建立了一種新的動(dòng)態(tài)調(diào)度方法Tir-G。Xu等[2]采用改進(jìn)的遺傳算法研究了公共自行車的動(dòng)態(tài)調(diào)度問題。Zhu等[3]提出了一個(gè)全新的公共自行車多媒體交互調(diào)度系統(tǒng)，使用遺傳算法求解最短的調(diào)度路徑、最長(zhǎng)的調(diào)度運(yùn)輸距離和調(diào)度車輛數(shù)。崔元洋等[4]建立用車谷和用車峰兩時(shí)期的公共自行車調(diào)度模型，使用遺傳混合蟻群算法來求解該模型。賈永基等[5]對(duì)共享單車的調(diào)度問題引入了電子圍欄，采用改進(jìn)變鄰域搜索算法求解最優(yōu)路徑。呂暢等[6]提出了一新的站點(diǎn)分塊策略，采用雙層禁忌搜索算法求解較優(yōu)解。對(duì)于共享電動(dòng)車的電池配送，馮春等[7]結(jié)合軟時(shí)間窗進(jìn)行車輛路徑規(guī)劃，采用掃描算法和遺傳算法解決共享電動(dòng)車的電池配送問題。

對(duì)于車輛路徑問題，陳玉光等[8]首次提出將準(zhǔn)時(shí)送貨和最小耗油相結(jié)合，建立多約束VRP模型，利用改進(jìn)的粒子群算法求出最優(yōu)解。李嘉等[9]引入了裝載量和行駛距離作為影響因素，采用變鄰域搜索和模擬退火的混合啟發(fā)式算法進(jìn)行求解。張景玲等[10]針對(duì)車輛運(yùn)輸中的同時(shí)取送貨的特性，運(yùn)用禁忌搜索和模擬退火混合算法進(jìn)行求解。張明偉等[11]研究車輛碳排放，引入動(dòng)態(tài)負(fù)載，提出一種混合蟻群算法，求解出碳排放量最低的配送方案。王濤等[12]針對(duì)車輛路徑問題提出了改進(jìn)智能水滴遺傳混合算法。

本文將共享助力車的調(diào)度與電池的更換同時(shí)進(jìn)行，因當(dāng)前大多數(shù)運(yùn)營(yíng)商還是采用燃油車來實(shí)行調(diào)度，故本文以燃油調(diào)度車輛的耗油成本為目標(biāo)。在考慮到路徑和不同載重下車輛的耗油量的不同等綜合因素影響下求成本最低，對(duì)調(diào)度路徑進(jìn)行合理規(guī)劃。

1 問題描述與模型構(gòu)建

1.1 問題描述

共享助力車的調(diào)度優(yōu)化問題與共享單車的重平衡問題有著類似的地方，但本文提出的調(diào)度方案涉及到助力車的電池更換，因此又與傳統(tǒng)的單車調(diào)度不同。調(diào)度過程如下：調(diào)度車輛從起點(diǎn)車庫(kù)出發(fā)，依次經(jīng)過并服務(wù)其調(diào)度區(qū)域內(nèi)的電子圍欄，并且不會(huì)對(duì)服務(wù)過的電子圍欄進(jìn)行重復(fù)訪問，且每到一個(gè)電子圍欄處時(shí)，如果助力車的數(shù)量超出標(biāo)準(zhǔn)存量，則運(yùn)走多余的助力車，同時(shí)對(duì)該點(diǎn)需要更換電池的助力車更換電池；如果該點(diǎn)助力車少于標(biāo)準(zhǔn)存量，則從調(diào)度車上卸下相應(yīng)數(shù)量的助力車來進(jìn)行補(bǔ)充。因?yàn)檎{(diào)度車的自身容量和承載重量的限制，每輛調(diào)度車所能攜帶的電池的數(shù)量有限，本文在受到里程和載重的雙重約束下，尋求一個(gè)最優(yōu)的服務(wù)順序和路徑規(guī)劃。

共享助力車調(diào)度過程的簡(jiǎn)單示例圖如圖1。其中，有1個(gè)車輛起點(diǎn)(終點(diǎn))，5個(gè)電子圍欄，3個(gè)點(diǎn)有裝車的需要，2個(gè)點(diǎn)有卸車的需要，同時(shí)有4個(gè)點(diǎn)需要更換電池，1個(gè)點(diǎn)不需要更換電池。共享助力車的調(diào)度過程具有以下特征。

圖 1 助力車調(diào)度平衡的簡(jiǎn)單示例Figure 1 A simple example of the dispatching balance of a bicycle

1) 調(diào)度車從開始到結(jié)束回到調(diào)度中心時(shí)車上的裝載量應(yīng)為0；

2) 因?yàn)檎{(diào)度的目的是為了實(shí)現(xiàn)助力車數(shù)量平衡，所以每輛車，每條路徑都是混合裝卸的；

3) 調(diào)度過程還要考慮更換電池，所以調(diào)度的過程中需要換電池的助力車的數(shù)量不能超過調(diào)度車所攜帶的電池?cái)?shù)量。

模型假設(shè)如下。

1) 假設(shè)整個(gè)區(qū)域內(nèi)的助力車總數(shù)量保持不變，每個(gè)調(diào)度區(qū)域的助力車數(shù)量也保持一定，沒有助力車被回收，也沒有新助力車投入使用，且每一輛車都能被使用。

2) 假設(shè)每一輛調(diào)度車的型號(hào)相同，承載容量相同，最長(zhǎng)里程相同。

3) 假設(shè)每輛調(diào)度車在任何情況下的耗油能力都一致，且都是與路程和載重成線性正相關(guān)，不考慮城市的復(fù)雜路況和調(diào)度車輛自身新舊程度不同所產(chǎn)生的影響。

4) 假設(shè)調(diào)度車在每次調(diào)度過程中出發(fā)時(shí)都是滿油狀態(tài)，且在整個(gè)調(diào)度過程中不需要加油。

1.2 模型構(gòu)建

本文研究不僅考慮路徑的長(zhǎng)短對(duì)燃油調(diào)度車油耗的影響，還考慮到不同載重的狀態(tài)下對(duì)燃油調(diào)度車輛油耗的影響，從而綜合規(guī)劃路線。目前將車輛油耗當(dāng)作路徑優(yōu)化目標(biāo)的研究較少，這主要是因?yàn)槿加蛙囕v的耗油影響因素很多，且很難分清楚各個(gè)因素對(duì)車輛耗油的影響是多少，此類研究的困難之處在于計(jì)算路徑、載重與耗油量的關(guān)系式。當(dāng)前有一些學(xué)者已經(jīng)對(duì)車輛燃油問題進(jìn)行了一些研究[13-14]，建立了不同的模型，提出了不同的計(jì)算方法。因本文主要研究路徑規(guī)劃，所以采用已有方法中較為簡(jiǎn)單的“負(fù)載估計(jì)法”[15]。該方法認(rèn)為車輛的行駛距離和載重決定著耗油量，且載重與耗油之間存在線性關(guān)系，其關(guān)系式如下

在式(1)中， ρ0為車輛空載時(shí)的車輛耗油率；ρ?為滿載時(shí)的車輛耗油率；p為負(fù)載重量。本文以最小耗油成本為研究目標(biāo)，因此將 ρ0當(dāng)作車輛僅裝載電池時(shí)的每公里耗油量， ρ為每增加一輛助力車所要付出的耗油量， μ2為每公里燃油成本。在此基礎(chǔ)上，假設(shè)pij為i點(diǎn)到j(luò)點(diǎn)的助力車數(shù)量，dij為i點(diǎn)到j(luò)點(diǎn)的距離，從而得出以下車輛從i到j(luò)的耗油成本。

在此限制條件下求出的調(diào)度路線可能不會(huì)是車輛行駛距離最短的路線，但因?yàn)槌杀镜南拗?，?huì)使調(diào)度車輛盡可能地在每段運(yùn)輸路線中裝載較少的助力車數(shù)量，以實(shí)現(xiàn)成本最低。符號(hào)說明見表1。

考慮耗油成本最小化的調(diào)度模型目標(biāo)函數(shù)。

表 1 符號(hào)說明Table 1 Symbolic Description

總成本最小函數(shù)模型為

約束條件。

1) 限制了調(diào)度車經(jīng)過且服務(wù)一個(gè)電子圍欄后不會(huì)重復(fù)訪問。

2) 為了實(shí)現(xiàn)車輛必須從i點(diǎn)到j(luò)點(diǎn),且最后回到起點(diǎn)，實(shí)現(xiàn)閉環(huán)運(yùn)輸。

3) 保證運(yùn)輸車從i點(diǎn)到j(luò)點(diǎn)的運(yùn)載量不會(huì)發(fā)生變化，到達(dá)每個(gè)服務(wù)點(diǎn)時(shí)的運(yùn)載量的變化具有合理性，且確保了運(yùn)載量不會(huì)超出車輛運(yùn)載容量。

5) 在每個(gè)電子圍欄需要更換電池的助力車數(shù)量不能大于現(xiàn)有數(shù)量。

6) 整個(gè)調(diào)度過程中每階段需要更換電池的總數(shù)不能大于攜帶電池的上限。

2 基于AP算法的調(diào)度區(qū)域與調(diào)度中心的確定

共享助力車的調(diào)度情況分為小規(guī)模和大規(guī)模2種，小規(guī)模的類型可以直接進(jìn)行調(diào)度的路徑規(guī)劃，但大規(guī)模的類型需要多輛調(diào)度車進(jìn)行調(diào)度，因此需要提前劃分好調(diào)度區(qū)域，以便更好地實(shí)行調(diào)度安排，同時(shí)也降低了求解問題的難度。本文引入仿射傳播聚類算法(affinity propagation，AP算法)，流程見圖2。對(duì)所有的電子圍欄進(jìn)行分類，得出各個(gè)調(diào)度區(qū)域。

圖 2 AP算法流程Figure 2 AP algorithm flow

2.1 AP算法

AP算法是一種依托于數(shù)據(jù)點(diǎn)之間進(jìn)行信息傳遞的聚類算法。該算法的特點(diǎn)在于不用事先確定聚類的個(gè)數(shù)，并且算法本身會(huì)把每一個(gè)樣本點(diǎn)都當(dāng)成潛在的聚類中心，并通過不斷地迭代吸引度和歸屬度的數(shù)值來調(diào)整最佳的聚類中心，再把其他的樣本點(diǎn)劃分到這些中心點(diǎn)的類中。

本文的算法具有以下優(yōu)點(diǎn)：1)無需事先指定聚類數(shù)量參數(shù)；2)明確的質(zhì)心，樣本中的每一個(gè)點(diǎn)都有機(jī)會(huì)成為聚類中心；3)對(duì)初始值不敏感，多次聚類的結(jié)果是一樣的；4)此算法求出的誤差平方和比其他的方法得出的都要低；5)與K-Means相比具有更強(qiáng)的魯棒性和準(zhǔn)確度。

2.2 AP算法實(shí)施流程

AP聚類算法實(shí)施步驟如下。

步驟1計(jì)算待聚類的電子圍欄集N={N1,N2,···,NN}的相似度矩陣。

式中，相似度矩陣s(i，j)的值為各個(gè)電子圍欄之間的歐氏距離的負(fù)值，可以理解為點(diǎn)j成為i的聚類中心的合適程度；P為Preference，是指參考度或偏好參數(shù)，P值可以取相似矩陣的最小值、中位數(shù)或兩倍的中位數(shù)，其取值大小決定了聚類數(shù)量的多少。

步驟2計(jì)算并更新k點(diǎn)對(duì)于i點(diǎn)的吸引度r(i，k)。

式(13)中， λ為阻尼因子，取值范圍在[0,1]，其作用是為了讓算法快速收斂，此公式為吸引度r(i，j)的更新規(guī)則，a(i，k′)表達(dá)除k以外的其他點(diǎn)對(duì)于i點(diǎn)的歸屬度值，初始值為0；s(i,k′)表示除k以外的其他點(diǎn)對(duì)i點(diǎn)的合適度；r(i，k)表示數(shù)據(jù)點(diǎn)k成為數(shù)據(jù)點(diǎn)i聚類中心的累積證明，r(i，k)大于0，則表示k成為聚類中心的能力強(qiáng)。

步驟3計(jì)算并更新k點(diǎn)對(duì)于i點(diǎn)的歸屬度a(i，j)。

式(14)、(15)為歸屬度a(i，j)的更新公式，a(i,k)表示i點(diǎn)選擇k點(diǎn)作為聚類中心的合適程度。K為所有k的集合。

步驟4確定聚類中心。

式(17)表示i點(diǎn)對(duì)于自身的吸引度和歸屬度大于0時(shí)選擇對(duì)應(yīng)的頂點(diǎn)作為聚類中心。

步驟5劃分?jǐn)?shù)據(jù)點(diǎn)與聚類中心的隸屬關(guān)系。

選擇與當(dāng)前頂點(diǎn)i吸引度與歸屬度之和最大的頂點(diǎn)j作為其聚類中心，即把點(diǎn)i歸為j類中。

根據(jù)以上步驟最終可以確定各地區(qū)的共享助力車可以劃分為多少個(gè)調(diào)度區(qū)域，并且確定在空間位置上最優(yōu)的調(diào)度中心，使其到其所屬區(qū)域所有電子圍欄的直線距離最短。

3 遺傳算法

本文模型所要求解的過程復(fù)雜度較高，且隨著調(diào)度區(qū)域數(shù)量的增加，求解的難度和復(fù)雜度將會(huì)呈幾何式增長(zhǎng)。因此，本文采用遺傳算法(genetic algorithm)進(jìn)行求解，該算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，遺傳算法流程見圖3。此算法的優(yōu)點(diǎn)在于原理、操作較為簡(jiǎn)單，魯棒性強(qiáng)，不易受限制條件的約束，還具有一定的隱含并行性和較強(qiáng)的全局尋優(yōu)能力，在解決組合優(yōu)化問題中得到廣泛的應(yīng)用。

3.1 算法實(shí)現(xiàn)步驟

3.1.1 構(gòu)造初始可行解

在各個(gè)不同的調(diào)度區(qū)域分別進(jìn)行初始解的構(gòu)造，具體步驟如下。

步驟1設(shè)置一條初始調(diào)度路徑，其上節(jié)點(diǎn)為空。

步驟2將原有的電子圍欄節(jié)點(diǎn)順序打亂，根據(jù)約束條件(7)對(duì)該集合進(jìn)行一次提取，符合條件的電子圍欄節(jié)點(diǎn)提取出來放到新的集合里，并將原始集合里的該節(jié)點(diǎn)刪除；不斷重復(fù)該操作，直到將原始集合里的所有節(jié)點(diǎn)都提取到新的初始解集合中。車輛行駛路線初始解見圖4。

圖4(a)為此次樣本數(shù)據(jù)集，包含一個(gè)調(diào)度中心，為編號(hào)1，編號(hào)2～10為電子圍欄，需求量總數(shù)為零，每個(gè)電子圍欄的標(biāo)準(zhǔn)存量為20，調(diào)度車的電池載量為20，助力車載量為15。圖4(b)表示受到裝載量的限制，形成的初始解中調(diào)度車的裝載量每次都不會(huì)超過15。

步驟3對(duì)步驟2形成的初始解進(jìn)行檢驗(yàn)，判斷其更換電池的總數(shù)是否不超過調(diào)度車輛所攜帶的電池?cái)?shù)量，即若在點(diǎn)i處首次出現(xiàn)更換電池的數(shù)量超過車輛攜帶量，則在該點(diǎn)之前插入調(diào)度中心，并將所有電池更新為滿電狀態(tài)；從i點(diǎn)開始重新統(tǒng)計(jì)剩下節(jié)點(diǎn)的需換電池的數(shù)量，以同樣的原則插入調(diào)度中心，直到整條路線滿足條件(9)，形成最終的初始解。插入調(diào)度中心見圖5。圖5對(duì)圖4 (b)的初始解進(jìn)行調(diào)度中心插入，兩個(gè)調(diào)度中心之間的換電量不超過20。

圖 3 遺傳算法流程Figure 3 genetic algorithms flow

圖 4 車輛行駛路線初始解Figure 4 Initial solution of vehicle route

圖 5 插入調(diào)度中心Figure 5 Insert dispatch center

3.1.2 遺傳算法操作步驟

步驟1設(shè)置初始解集Xcs；

步驟2構(gòu)造初始可行解；

步驟3在初始可行解中進(jìn)行選擇，挑選出新的解集Xgx；

步驟4對(duì)新的解集Xgx進(jìn)行交叉與變異操作，與初始可行解Xcs合并，保留最優(yōu)解集Xyj；

步驟5返回步驟3重復(fù)求解，直到滿足最大迭代次數(shù)，輸出最優(yōu)解Xbest。

4 算例仿真分析

4.1 算例設(shè)計(jì)

本文模型采用Matlab R2018a編寫程序，計(jì)算機(jī)操作系統(tǒng)為Windows 8.1 64位操作系統(tǒng)，CPU為Intel(R) Core(TM) i5-3337U，內(nèi)存為4.00 GB。

本文使用算例驗(yàn)證算法的可行性，并且構(gòu)造10組算例，每組算例擁有的電子圍欄的數(shù)量為200，電子圍欄在[0, 400]的區(qū)間內(nèi)隨機(jī)生成坐標(biāo)，每個(gè)電子圍欄的標(biāo)準(zhǔn)停放量為20輛，且每個(gè)站點(diǎn)的助力車需求量在[-20, 20]之間隨機(jī)生成，換電池?cái)?shù)量在不超過單車數(shù)量的范圍內(nèi)隨機(jī)生成。燃油調(diào)度車的參數(shù)根據(jù)設(shè)置：助力車的裝載量為Q1=30，電池的攜帶量為Q2=50，車輛固定使用成本為μ1=300元，僅裝載電池時(shí)的單位里程耗油成本μ2ρ0=0.6元/km，每增加一輛助力車的每公里耗油成本μ2ρ=0.005元/km。單獨(dú)進(jìn)行電池配送的成本為200元。

本文經(jīng)過多次聚類調(diào)整后確定在P=2*median(s)，即2倍的相似矩陣中位數(shù)，s為相似度矩陣。 λ=0.5時(shí)得到的聚類結(jié)果相似度最大，為最優(yōu)結(jié)果。設(shè)置遺傳算法初始種群為200，遺傳代數(shù)為1 000。

4.2 算例結(jié)果

本文模型結(jié)果如表2所示，在調(diào)度過程中總的更新電池的次數(shù)不超過35次，最少的為28次，平均每個(gè)小區(qū)域的更新次數(shù)為4～5次。與原調(diào)度模式相比調(diào)度成本顯著降低，圖6為SL1的聚類分區(qū)結(jié)果。算例測(cè)試結(jié)果證明本文設(shè)立的模型能有效降低助力車的調(diào)度成本。

表 2 算例求解結(jié)果Table 2 Solution results of numerical examples

圖 6 SL1的聚類分區(qū)圖Figure 6 Cluster partition diagram of SL1

5 總結(jié)

本文將共享助力車的電池配送與助力車的調(diào)度相結(jié)合同時(shí)進(jìn)行，并且考慮載重對(duì)燃油調(diào)度車耗油的影響。利用AP算法對(duì)一個(gè)大范圍的服務(wù)區(qū)域進(jìn)行聚類，實(shí)現(xiàn)電子圍欄的歸屬劃分，確定助力車的服務(wù)范圍，并確定各個(gè)區(qū)域的調(diào)度中心，利用遺傳算法對(duì)各區(qū)域進(jìn)行調(diào)度路線的求解。本文所構(gòu)建的模型和提出的調(diào)度方案有效地降低了運(yùn)營(yíng)方的調(diào)度成本，減少了調(diào)度所要花費(fèi)的時(shí)間，并且最終能更好地服務(wù)于顧客，提升顧客的消費(fèi)體驗(yàn)。

未來還可以研究的方向如下：1) 個(gè)別助力車停放在電子圍欄以外區(qū)域的調(diào)度問題；2) 尋找更好的算法解決本文的調(diào)度方案；3) 當(dāng)共享單車也引入電子圍欄后單車和助力車共同調(diào)度的問題。