一種電瓶換電柜布局城市的選址模型

梁會軍， 沈 兵

（1. 湖北民族大學，湖北恩施 445000；2. 中國核工業第二二建設有限公司，湖北武漢 430050）

0 引言

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

1 選址模型影響因素及前提假設

1.1 選址模型影響因素

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

1.2 選址模型前提假設

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

在模擬騎手接單送餐過程中，將與城區騎手數相同的目標隨機分配到每個道路節點上。假設每個目標擁有50 km 的續航里程，即d=50 000，應用所有節點接單概率和送餐概率，通過輪盤賭機制計算各個節點商家需要騎手接單和外賣用戶需要騎手送餐狀態。然后確定距離目標點所在節點i 最近的需要騎手接單節點a和需要騎手送餐節點b，計算剩余續航里程d=d-dia-dab，并設定該目標點此時所在節點為b 節點。循環上述操作直至d＜5000 時，得到該目標點所在節點是此騎手欲換電地點。收集所有欲換電地點形成最終的目標點集合作為基礎數據參與換電柜選址模型的迭代運算。

2 換電柜選址模型的求解

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

圖1 換電柜安置點選址模型整體框圖

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

應用K-means聚類算法迭代求解選址方案時將應用dav、num、ddis_av三個指標對選址結果進行評價。其中dav表示所有目標點到最近聚類中心的平均值；num 表示離群點數，離群點是到最近聚類中心的距離超過離群點閾值的目標點；ddis_av指離群點到最近聚類中心平均距離。同時模型將記錄下dav、num、ddis_min歷史最小值分別為dav_min、nummin、ddis_av_min，在此基礎上乘以擴展倍數或加上擴展個數形成對選址方案的評價指標limit。通過評價指標篩選后的選址方案再應用Pareto多目標優化算法擇取出最前沿的優質方案形成選址方案集，為換電柜服務公司在規劃城區換電柜建設過程中提供參考方案。

3 換電柜選址模型測試

為檢驗換電柜選址模型的可行性，本次測試以某市的道路規劃、城市布局以及外賣業發展情況為例進行分析。首先根據該市的發展概況和道路間的關聯性，在城區中擇取了150個重要節點，繪制出如圖2 所示的城區道路規劃及重要節點分布簡圖。換電柜選址模型通過改進的Dijkstra 算法對重要節點分布簡圖進行分析，獲得城區節點間的路徑表path和距離表distance。

圖2 某市城區道路規劃及重要節點分布簡圖

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

表1 換電柜安置點數為5-8的各項參數

為進一步驗證選址結果的有效性，此次選取每組中dav_min值最小的選址結果進行展示。圖3 是在平面坐標系中，聚類中心為5 h～8 h 換電柜安置點分布情況。表2是4個選址方案的相關參數。

表2 四個優質解的相關參數

由表2 可以看出，增加換電柜配置點能有效降低外賣騎手前往換電的距離，避免騎手遠距離換電，但配置點增多也將增加投資和運營成本，最終還需根據實際情況擇取最適應的選址方案。以上4個優質選址方案僅是選址模型輸出方案集中的一種，換電柜投資商可對比多個優質選址方案，再結合當地各路段土地性價比等實際情況選擇換電柜最終的選址與配置方案。

4 結論

應用改進的Dijkstra 算法分析城區道路規劃，在當地外賣業發展現狀的基礎上通過改進的Kmeans 聚類算法優化換電柜安置點選址方案，最后設定評價指標并應用Pareto多目標優化算法擇取優質解形成換電柜選址方案集合。投資商依據實際情況對比后選擇合適方案建設換電柜，既能避免電瓶車換電柜在街頭亂建現象，又能促進換電柜資源隨用戶需求而配置，降低換電柜的運營成本。