梁會(huì)軍， 沈 兵

（1. 湖北民族大學(xué)，湖北恩施 445000；2. 中國(guó)核工業(yè)第二二建設(shè)有限公司，湖北武漢 430050）

0 引言

隨著外賣行業(yè)蓬勃發(fā)展，續(xù)航里程為50 km 左右的電瓶車已滿足不了外賣騎手日工作需求，而讓騎手中止工作并花費(fèi)1 h～2 h為電瓶充電將嚴(yán)重影響他們的工作效率[1-2]。因此，外賣平臺(tái)近年已聯(lián)合各換電服務(wù)公司在城市的街頭巷尾陸續(xù)安裝有不同品牌的換電柜[3]。這些換電柜能有效解決外賣騎手即時(shí)性用電問(wèn)題，也能避免電瓶車用戶自行充電誘發(fā)的各種安全隱患[4-6]。但很多換電柜在建設(shè)時(shí)沒(méi)有得到充分考究和規(guī)劃，導(dǎo)致?lián)Q電柜建設(shè)后出現(xiàn)擾民、占用人行橫道、影響市容和資源錯(cuò)配等現(xiàn)象[7-8]。為了均衡配置換電柜資源，讓換電柜更好地融入城市，為電瓶車用戶提供便利性的換電服務(wù)，從外賣騎手的工作特性進(jìn)行分析，結(jié)合地區(qū)外賣行業(yè)發(fā)展現(xiàn)狀和城區(qū)道路規(guī)劃以及城市整體布局，構(gòu)建換電柜選址模型。該模型通過(guò)模擬外賣員接單送餐行為計(jì)算其欲換電地點(diǎn)。在欲換電地點(diǎn)的基礎(chǔ)上，融合遺傳算法思想，應(yīng)用改進(jìn)的K-means聚類算法優(yōu)化種群并應(yīng)用Pareto優(yōu)化排序算法擇取優(yōu)質(zhì)的選址方案，為換電柜規(guī)劃建設(shè)提供優(yōu)質(zhì)的選址方案集。

1 選址模型影響因素及前提假設(shè)

1.1 選址模型影響因素

構(gòu)建換電柜選址模型應(yīng)從換電柜用戶需求、換電服務(wù)公司運(yùn)營(yíng)成本以及城市整體規(guī)劃等方面分析影響因素。為了方便騎手進(jìn)行換電，換電柜安置點(diǎn)應(yīng)在騎手經(jīng)常工作的路徑附近。根據(jù)當(dāng)?shù)赝赓u行業(yè)發(fā)展情況及騎手?jǐn)?shù)確定換電柜配置數(shù)量。應(yīng)與地區(qū)內(nèi)各行政部門做好溝通，采納有效建議，考慮城市5～10年發(fā)展規(guī)劃后擇取選址方案。換電柜選址充分考慮到城區(qū)道路規(guī)劃和商城、醫(yī)院、產(chǎn)業(yè)園區(qū)等公共場(chǎng)所的分布情況。配置換電柜應(yīng)與生活區(qū)和人群密集地區(qū)保持一定距離，在保證用電安全和質(zhì)量安全的前提下不影響市容市貌。

1.2 選址模型前提假設(shè)

經(jīng)過(guò)查閱相關(guān)文獻(xiàn)和走訪調(diào)查后，對(duì)建立換電柜選址模型提出以下假設(shè)：安裝于城市中每臺(tái)換電柜多數(shù)擁有12個(gè)充電箱；為在換電高峰期滿足用戶的換電需求，保證城區(qū)所有換電箱擁有充電箱的總數(shù)應(yīng)為城區(qū)騎手總數(shù)；滿格電瓶續(xù)航里程為50 km，在里程焦慮的作用下續(xù)航里程下降至5 km 時(shí)，騎手會(huì)送完手頭訂單后選擇就近換電。分析城區(qū)的道路結(jié)構(gòu)并選取重要道路節(jié)點(diǎn)，在二維坐標(biāo)系形成平面節(jié)點(diǎn)圖。模擬外賣騎手接單送餐行為并計(jì)算其欲換電地點(diǎn)，需要考察每個(gè)道路節(jié)點(diǎn)附近商鋪數(shù)量和社會(huì)公共場(chǎng)所配套情況定義該節(jié)點(diǎn)的商鋪接單概率η1和外賣用戶需要送餐概率η2。通過(guò)走訪發(fā)現(xiàn)1 號(hào)節(jié)點(diǎn)附近有兩所機(jī)關(guān)單位和較少商鋪，經(jīng)對(duì)比分析定義1 號(hào)節(jié)點(diǎn)的接單概率為0.4，送餐概率為0.6；節(jié)點(diǎn)2 附近有大型商城、賓館及社區(qū)，因此定義其接單概率和送餐概率分別為0.8和0.7。

在模擬騎手接單送餐過(guò)程中，將與城區(qū)騎手?jǐn)?shù)相同的目標(biāo)隨機(jī)分配到每個(gè)道路節(jié)點(diǎn)上。假設(shè)每個(gè)目標(biāo)擁有50 km 的續(xù)航里程，即d=50 000，應(yīng)用所有節(jié)點(diǎn)接單概率和送餐概率，通過(guò)輪盤賭機(jī)制計(jì)算各個(gè)節(jié)點(diǎn)商家需要騎手接單和外賣用戶需要騎手送餐狀態(tài)。然后確定距離目標(biāo)點(diǎn)所在節(jié)點(diǎn)i 最近的需要騎手接單節(jié)點(diǎn)a和需要騎手送餐節(jié)點(diǎn)b，計(jì)算剩余續(xù)航里程d=d-dia-dab，并設(shè)定該目標(biāo)點(diǎn)此時(shí)所在節(jié)點(diǎn)為b 節(jié)點(diǎn)。循環(huán)上述操作直至d＜5000 時(shí)，得到該目標(biāo)點(diǎn)所在節(jié)點(diǎn)是此騎手欲換電地點(diǎn)。收集所有欲換電地點(diǎn)形成最終的目標(biāo)點(diǎn)集合作為基礎(chǔ)數(shù)據(jù)參與換電柜選址模型的迭代運(yùn)算。

2 換電柜選址模型的求解

圖1為換電柜安置點(diǎn)選址模型的整體框圖。選址模型選用改進(jìn)的Dijkstra 算法分析城區(qū)道路間的關(guān)聯(lián)性，形成城區(qū)道路最優(yōu)路徑表和距離表。Dijkstra 算法采用的貪心策略求解起點(diǎn)到終點(diǎn)的最優(yōu)路徑和最近距離。但由于Dijkstra 算法采用的是全局搜索機(jī)制，其計(jì)算量將隨著道路節(jié)點(diǎn)的增多而劇增[6]。在多次試驗(yàn)后發(fā)現(xiàn)，每次求解得到點(diǎn)對(duì)點(diǎn)的最優(yōu)路徑中各點(diǎn)間最優(yōu)路徑也是沿此路經(jīng)，因此模型將每次應(yīng)用Dijkstra 算法求到的最優(yōu)路徑信息盡可能地提取出來(lái)，歸納入最優(yōu)路徑表和距離表，以減輕模型整體計(jì)算量。

圖1 換電柜安置點(diǎn)選址模型整體框圖

根據(jù)城區(qū)規(guī)模大小輸入換電柜安置點(diǎn)數(shù)量后，選址模型以遺傳算法為框架，采用改進(jìn)的K-means聚類算法求解換電柜安置點(diǎn)選址及配置方案。遺傳算法是以優(yōu)勝劣汰的自適應(yīng)機(jī)制為主導(dǎo)思想，應(yīng)用交叉、變異和選擇等操作，將優(yōu)良的基因遺傳給后代，通過(guò)迭代計(jì)算求解出優(yōu)質(zhì)解[10]。K-means 聚類算法是種無(wú)監(jiān)督學(xué)習(xí)的聚類算法，算法首先將K個(gè)聚類中心隨機(jī)分配至目標(biāo)區(qū)域內(nèi)，以目標(biāo)點(diǎn)到聚類中心的歐式距離最小為目標(biāo)函數(shù)將目標(biāo)點(diǎn)聚合成K類[11]。然后目標(biāo)點(diǎn)以類為單位確定新的聚類中心，使該類中的目標(biāo)點(diǎn)到聚類中心的平均距離最小，如此往復(fù)更新聚類中心得到最優(yōu)解。在換電柜安置點(diǎn)選址模型中，將會(huì)應(yīng)用城區(qū)道路距離代替節(jié)點(diǎn)間的歐式距離求解選址方案。為克服K-means聚類算法存在局部收斂性的缺陷，選址模型應(yīng)用枚舉法在種群迭代穩(wěn)定后重新初始化種群參與迭代求解和對(duì)歷史結(jié)果進(jìn)行驗(yàn)算。

應(yīng)用K-means聚類算法迭代求解選址方案時(shí)將應(yīng)用dav、num、ddis_av三個(gè)指標(biāo)對(duì)選址結(jié)果進(jìn)行評(píng)價(jià)。其中dav表示所有目標(biāo)點(diǎn)到最近聚類中心的平均值；num 表示離群點(diǎn)數(shù)，離群點(diǎn)是到最近聚類中心的距離超過(guò)離群點(diǎn)閾值的目標(biāo)點(diǎn)；ddis_av指離群點(diǎn)到最近聚類中心平均距離。同時(shí)模型將記錄下dav、num、ddis_min歷史最小值分別為dav_min、nummin、ddis_av_min，在此基礎(chǔ)上乘以擴(kuò)展倍數(shù)或加上擴(kuò)展個(gè)數(shù)形成對(duì)選址方案的評(píng)價(jià)指標(biāo)limit。通過(guò)評(píng)價(jià)指標(biāo)篩選后的選址方案再應(yīng)用Pareto多目標(biāo)優(yōu)化算法擇取出最前沿的優(yōu)質(zhì)方案形成選址方案集，為換電柜服務(wù)公司在規(guī)劃城區(qū)換電柜建設(shè)過(guò)程中提供參考方案。

3 換電柜選址模型測(cè)試

為檢驗(yàn)換電柜選址模型的可行性，本次測(cè)試以某市的道路規(guī)劃、城市布局以及外賣業(yè)發(fā)展情況為例進(jìn)行分析。首先根據(jù)該市的發(fā)展概況和道路間的關(guān)聯(lián)性，在城區(qū)中擇取了150個(gè)重要節(jié)點(diǎn)，繪制出如圖2 所示的城區(qū)道路規(guī)劃及重要節(jié)點(diǎn)分布簡(jiǎn)圖。換電柜選址模型通過(guò)改進(jìn)的Dijkstra 算法對(duì)重要節(jié)點(diǎn)分布簡(jiǎn)圖進(jìn)行分析，獲得城區(qū)節(jié)點(diǎn)間的路徑表path和距離表distance。

圖2 某市城區(qū)道路規(guī)劃及重要節(jié)點(diǎn)分布簡(jiǎn)圖

依據(jù)該市外賣騎手的數(shù)量設(shè)定目標(biāo)點(diǎn)數(shù)為600，每臺(tái)換電柜擁有充電箱的數(shù)量為12，定義各個(gè)節(jié)點(diǎn)的商鋪接單概率η1和外賣用戶需要送餐概率η2形成節(jié)點(diǎn)需求概率表η。經(jīng)過(guò)市場(chǎng)調(diào)查欲充電地點(diǎn)距離最近的換電柜安置點(diǎn)超過(guò)1000 m 時(shí)將會(huì)給騎手帶來(lái)焦慮情緒，因此設(shè)定離群點(diǎn)閾值為1000。與此同時(shí)，設(shè)定所有目標(biāo)點(diǎn)距離最近聚類中心平均距離的擴(kuò)展倍數(shù)為1.2；離群點(diǎn)到最近聚類中心平均距離的擴(kuò)展倍數(shù)為1.2；最少離群點(diǎn)數(shù)的擴(kuò)展個(gè)數(shù)為10。評(píng)價(jià)指標(biāo)limit 的初始值將被設(shè)定為[inf inf inf]，隨著選址方案的不斷優(yōu)化，擴(kuò)展個(gè)數(shù)和擴(kuò)展倍數(shù)與歷史最優(yōu)值進(jìn)行加/乘后對(duì)評(píng)價(jià)指標(biāo)limit 進(jìn)行持續(xù)更新。最后設(shè)定遺傳算法迭代過(guò)程中的種群大小為1000，種群在迭代7 代且趨于收斂后將被重新初始化，模型迭代總次數(shù)超過(guò)3000且收斂后結(jié)束計(jì)算并輸出結(jié)果。表1 是輸入聚類中心為5 h～8 h時(shí)的相關(guān)參數(shù)。選址模型結(jié)果輸出多個(gè)優(yōu)質(zhì)解及其相關(guān)參數(shù)，評(píng)價(jià)指標(biāo)在迭代運(yùn)算過(guò)程中每次更新至limit =[dav_limitnumlimitddis_av_limit]，三項(xiàng)評(píng)價(jià)指標(biāo)和目標(biāo)點(diǎn)到最近聚類中心的平均距離隨著安置點(diǎn)數(shù)的增多而下降，離群點(diǎn)到最近聚類中心的平均距離都在1250 m以下。

表1 換電柜安置點(diǎn)數(shù)為5-8的各項(xiàng)參數(shù)

為進(jìn)一步驗(yàn)證選址結(jié)果的有效性，此次選取每組中dav_min值最小的選址結(jié)果進(jìn)行展示。圖3 是在平面坐標(biāo)系中，聚類中心為5 h～8 h 換電柜安置點(diǎn)分布情況。表2是4個(gè)選址方案的相關(guān)參數(shù)。

表2 四個(gè)優(yōu)質(zhì)解的相關(guān)參數(shù)

由表2 可以看出，增加換電柜配置點(diǎn)能有效降低外賣騎手前往換電的距離，避免騎手遠(yuǎn)距離換電，但配置點(diǎn)增多也將增加投資和運(yùn)營(yíng)成本，最終還需根據(jù)實(shí)際情況擇取最適應(yīng)的選址方案。以上4個(gè)優(yōu)質(zhì)選址方案僅是選址模型輸出方案集中的一種，換電柜投資商可對(duì)比多個(gè)優(yōu)質(zhì)選址方案，再結(jié)合當(dāng)?shù)馗髀范瓮恋匦詢r(jià)比等實(shí)際情況選擇換電柜最終的選址與配置方案。

4 結(jié)論

應(yīng)用改進(jìn)的Dijkstra 算法分析城區(qū)道路規(guī)劃，在當(dāng)?shù)赝赓u業(yè)發(fā)展現(xiàn)狀的基礎(chǔ)上通過(guò)改進(jìn)的Kmeans 聚類算法優(yōu)化換電柜安置點(diǎn)選址方案，最后設(shè)定評(píng)價(jià)指標(biāo)并應(yīng)用Pareto多目標(biāo)優(yōu)化算法擇取優(yōu)質(zhì)解形成換電柜選址方案集合。投資商依據(jù)實(shí)際情況對(duì)比后選擇合適方案建設(shè)換電柜，既能避免電瓶車換電柜在街頭亂建現(xiàn)象，又能促進(jìn)換電柜資源隨用戶需求而配置，降低換電柜的運(yùn)營(yíng)成本。