曹珍　韓曙光

摘 要： 在充電站有充電容量約束的情況下，研究充電調(diào)度電動(dòng)無人車配送路徑規(guī)劃問題。首先以極小化車隊(duì)中電動(dòng)無人車的最大行駛距離為目標(biāo)，構(gòu)建數(shù)學(xué)規(guī)劃模型，為電動(dòng)無人車車隊(duì)安排配送路徑，使得各車的行駛距離盡可能均衡；其次應(yīng)用動(dòng)態(tài)規(guī)劃算法（Dynamic programming algorithm， DP）求解小規(guī)模算例，改進(jìn)遺傳-模擬退火算法（Genetic-simulated annealing algorithm， GA-SA）優(yōu)化較大規(guī)模算例的電動(dòng)無人車路徑和充電策略；最后對(duì)相關(guān)因素進(jìn)行靈敏度分析，以驗(yàn)證所提出算法的可行性與合理性。結(jié)果表明：DP算法解小規(guī)模算例表現(xiàn)良好；改進(jìn)GA-SA算法與單純遺傳算法（Genetic algorithm， GA）相比，求解大規(guī)模算例時(shí)優(yōu)化的路徑效果更佳，且大大縮短電動(dòng)無人車車隊(duì)的最長(zhǎng)子路徑的長(zhǎng)度和總行駛距離。該研究可以為物流公司的電動(dòng)無人車配送業(yè)務(wù)發(fā)展提供參考，幫助企業(yè)提高電動(dòng)無人車的運(yùn)輸效率和服務(wù)水平，降低配送成本。

關(guān)鍵詞： 電動(dòng)無人車；配送路徑規(guī)劃；充電容量約束；充電調(diào)度；動(dòng)態(tài)規(guī)劃；遺傳-模擬退火算法

中圖分類號(hào)： O223.1；O223.4

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1673-3851 （2023） 11-0784-11

引文格式：曹珍，韓曙光.考慮充電調(diào)度的電動(dòng)無人車配送路徑規(guī)劃問題研究［J］. 浙江理工大學(xué)學(xué)報(bào)（自然科學(xué)），2023，49（6）：784-794.

Reference Format： CAO Zhen， HAN Shuguang. Research on the distribution routing problem of electric unmanned vehicle considering charging scheduling［J］. Journal of Zhejiang Sci-Tech University，2023，49（6）：784-794.

Research on the distribution routing problem of electric unmanned vehicle considering charging scheduling

CAO Zhen， HAN Shuguang

Abstract：? Under the restriction that the charging station has charging capacity constraints， we focus on researching the distribution routing problem of electric unmanned vehicles with charge scheduling. A mathematical programming model was firstly established with the objective of minimizing the maximum travel distance of electric unmanned vehicles of the fleet， so as to arrange the distribution path for the unmanned vehicle fleet and balance the travel distance of each vehicle as much as possible. Secondly， dynamic programming （DP） algorithm was applied to solve small-scale examples， and genetic-simulated annealing algorithm （GA-SA） was improved to optimize the route and charging strategy of electric unmanned vehicles for large-scale examples. Finally， related factors were analyzed to verify the feasibility and rationality of the proposed algorithm. The results show that the DP algorithm performs well in solving small-scale examples. Compared with the simple genetic algorithm （GA）， the improved GA-SA can get a more reasonable solution when solving large-scale examples， and greatly shorten the length of the longest sub-path and the total driving distance of the electric unmanned vehicle fleet. This study can provide reference for the development of electric unmanned vehicle distribution business of logistics companies， help enterprises improve the transportation efficiency and service level of electric unmanned vehicles， and reduce distribution costs.

Key words： electric unmanned vehicles; distribution route planning; charging capacity constraints; charging scheduling; dynamic programming; genetic-simulated annealing algorithm

0 引 言

近年來，隨著能源價(jià)格不斷上漲，電動(dòng)無人車在城市物流配送環(huán)節(jié)逐漸成為傳統(tǒng)內(nèi)燃機(jī)汽車的替代品，但電動(dòng)無人車在實(shí)際配送中面臨電池續(xù)航能力不強(qiáng)、充電設(shè)施不足等問題。因此，研究電動(dòng)車輛（Electric vehicle，EV）的路徑規(guī)劃和充電策略，對(duì)于推廣電動(dòng)無人車進(jìn)行物流配送具有重要的現(xiàn)實(shí)意義。

傳統(tǒng)的車輛路徑規(guī)劃問題（Vehicle routing problem，VRP）最早由Dantzig等［1］提出，是組合優(yōu)化中研究最廣泛的問題之一，至今已有大量的相關(guān)研究成果。張玉州等［2］考慮救災(zāi)物資車輛路徑規(guī)劃問題，極小化救災(zāi)車輛的總運(yùn)輸距離，根據(jù)任務(wù)緊急度設(shè)計(jì)了任務(wù)再分配策略的遺傳算法（Genetic algorithm，GA），優(yōu)化了應(yīng)急物資的配送路徑；Tamke等［3］研究有二維裝載容量約束的車輛路徑規(guī)劃問題，設(shè)計(jì)了分支切割算法求解。隨著綠色環(huán)保的電動(dòng)汽車的普及與發(fā)展，電動(dòng)車輛路徑規(guī)劃問題（Electric vehicle routing problem，EVRP）擴(kuò)展了傳統(tǒng)的VRP問題，逐漸成為路徑規(guī)劃的研究熱點(diǎn)。葛顯龍等［4］結(jié)合部分充電策略建立整數(shù)規(guī)劃模型，設(shè)計(jì)了混合模擬退火算法（Simulated annealing algorithm，SA），優(yōu)化了電動(dòng)汽車的物流配送路徑；揭婉晨等［5］考慮了客戶需求可拆分的情況，通過改進(jìn)分支定價(jià)算法求得EVRP問題的最優(yōu)解；Wu等［6］采用自適應(yīng)調(diào)整信息素?fù)]發(fā)因子和突變算子，提出了一種混合的蟻群算法以求解帶時(shí)間窗的EVRP問題。以上研究的優(yōu)化目標(biāo)多是極小化總行駛距離；然而，在實(shí)際生活中，物流公司追求的往往不是尋求整個(gè)車隊(duì)的總行駛距離最短，而是均衡利用車輛，降低電池的退化率。該問題的優(yōu)化目標(biāo)可以描述為極小化車隊(duì)中車輛的最大行駛距離，這類問題稱為最小最大車輛路徑規(guī)劃問題（Min-max vehicle routing problem，MMVRP），如在線m-steiner旅行商問題［7］、災(zāi)區(qū)無人機(jī)監(jiān)控［8］等均屬于該類問題。

目前MMVRP問題的相關(guān)研究主要集中在近似算法和啟發(fā)式算法上。當(dāng)無固定倉庫點(diǎn)，起點(diǎn)任意且車輛的數(shù)量k也任意時(shí)，Yu等［9］給出了一個(gè)5-近似算法；隨后Yu等［10］證明了MMVRP問題的最壞情況界下界為5/4；Yakc［11］考慮了單配送中心的最小最大車輛路徑規(guī)劃問題，采用蟻群優(yōu)化以及其他隨機(jī)方法分配客戶給車輛，進(jìn)一步用3-opt方法局部?jī)?yōu)化；Sze等［12］研究了有容量約束的MMVRP問題，通過并行貪婪插入方法生成初始解，再利用自適應(yīng)變量鄰域搜索改進(jìn)；李小川等［13］根據(jù)問題特征并結(jié)合人工魚群算法的尋優(yōu)思想，提出了一種精英反向?qū)W習(xí)魚群算法來解決MMVRP問題。近些年智能物流配送逐漸發(fā)展，研究最小最大電動(dòng)車輛路徑規(guī)劃問題（Min-max electrical vehicle routing problem，MMEVRP）具有一定的現(xiàn)實(shí)意義；然而以上帶充電的路徑規(guī)劃研究往往都忽略了充電站容量問題，一般假設(shè)一個(gè)充電站可同時(shí)容納無數(shù)車輛充電。

近年來已有學(xué)者開始研究充電站有容量約束的充電路徑規(guī)劃問題以及相關(guān)求解算法。例如：Bruglieri等［14］考慮了充電站內(nèi)的充電樁數(shù)量有限的電動(dòng)車輛路徑問題，基于弧變量建立混合整數(shù)規(guī)劃模型，設(shè)計(jì)割平面的方法精確求解小規(guī)模算例；李默涵等［15］考慮了充電站內(nèi)車輛排隊(duì)等待充電的時(shí)間對(duì)路徑成本的影響，采用自適應(yīng)大規(guī)模鄰域搜索算法求解路徑；Keskin等［16］研究充電站出現(xiàn)排隊(duì)情況對(duì)路徑選擇的影響，考慮依賴排隊(duì)時(shí)間的分段線性充電，使用自適應(yīng)大鄰域搜索可行空間和確定可行路徑。

雖然有關(guān)充電站有容量約束的路徑規(guī)劃問題研究已取得了一定的進(jìn)展，但涉及充電站有容量約束的MMEVRP問題研究相對(duì)較少，且現(xiàn)有模型并沒有考慮充電等待時(shí)間。本文在上述研究基礎(chǔ)上，結(jié)合物流配送的實(shí)際狀況，針對(duì)充電站有容量限制的情況，以極小化車隊(duì)中電動(dòng)無人車的最大行駛距離為目標(biāo)，結(jié)合充電等待時(shí)間建立了可多次完全充電的混合整數(shù)規(guī)劃模型，研究電動(dòng)無人車的路徑規(guī)劃和充電調(diào)度。最后應(yīng)用動(dòng)態(tài)規(guī)劃算法（Dynamic programming algorithm，DP）和改進(jìn)遺傳-模擬退火算法（Genetic-simulated annealing algorithm，GA-SA）求解該模型，并通過Solomon標(biāo)準(zhǔn)算例驗(yàn)證算法的有效性和策略的可行性。電動(dòng)無人車路徑規(guī)劃研究可為物流企業(yè)運(yùn)營(yíng)調(diào)度車輛提供決策性參考意見。

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

1.1 問題描述

假設(shè)某物流快遞公司配有一個(gè)配送中心，另有若干個(gè)充電站點(diǎn)，充電站的充電樁數(shù)量有限，由若干數(shù)量的裝載容量和電池容量均相同的電動(dòng)無人車組成配送車隊(duì)給客戶派送貨物。在不超過車輛的裝載容量的情況下，電動(dòng)無人車充滿電后出發(fā)，完成配送任務(wù)后返回配送中心；由于車輛的電池容量有限，在行駛過程中可能需要根據(jù)實(shí)時(shí)電量前往充電站進(jìn)行充電。例如：受充電站數(shù)量限制，電動(dòng)無人車1和電動(dòng)無人車2在行駛過程中需要前往同一個(gè)充電站補(bǔ)充電量，此時(shí)可能存在排隊(duì)等待充電的情況，對(duì)應(yīng)的電動(dòng)無人車車隊(duì)的配送路徑示意圖如圖1所示。本文作如下假設(shè)：a）為保證交付效率，每個(gè)客戶只訪問一次；b）電動(dòng)無人車以恒定速度行駛，且電池電量消耗系數(shù)恒定，消耗的電量與行駛距離呈線性關(guān)系；c）充電站內(nèi)的充電樁數(shù)量有限，每個(gè)充電樁充電功能均正常，且充電速率一樣；d）當(dāng)電動(dòng)無人車前往充電站充電時(shí)，車輛的電池總是充滿電離開的；e）電動(dòng)無人車在客戶點(diǎn)停留過程中不消耗電量；f）不考慮客戶點(diǎn)與充電站的時(shí)間窗限制。

以極小化車隊(duì)中電動(dòng)無人車的最大行駛距離為目標(biāo)，研究充電站有容量限制的電動(dòng)無人車的路徑規(guī)劃和充電調(diào)度問題，合理地安排各無人車的行駛路徑和充電計(jì)劃，以滿足客戶的配送需求，盡可能減少充電次數(shù)和排隊(duì)充電等待時(shí)間，均衡各無人車的工作時(shí)長(zhǎng)。

1.2 MMEVRP數(shù)學(xué)模型構(gòu)建

本文中的符號(hào)及其含義見表1。無向圖j表示配送網(wǎng)絡(luò)；V=｛C∪F′∪｛o｝｝表示全部點(diǎn)的集合；E=（i，j）i，j∈V，i≠j表示弧集，每條弧關(guān)聯(lián)一個(gè)非負(fù)的行駛時(shí)間tij和距離dij；車輛集合K是由電池容量和裝載容量均相同的同一車型組成，表示至多有k輛無人車可以被分配來執(zhí)行送貨任務(wù)。

考慮充電站容量有限的電動(dòng)無人車車輛路徑規(guī)劃問題數(shù)學(xué)模型如下：

式（1）表示極小化車隊(duì)中電動(dòng)無人車的最大行駛距離；式（3）—（4）表示所有客戶點(diǎn)的貨物僅由一輛電動(dòng)無人車配送一次；式（5）—（6）表示電動(dòng)無人車均從配送中心出發(fā)，最終返回配送中心；式（7）表示到達(dá)和離開同一點(diǎn)的弧的數(shù)量相等，即每個(gè)點(diǎn)需保持流量平衡；式（8）表示消除不包含配送中心的子回路；式（9）表示電動(dòng)無人車的載貨能力限制；式（10）表示電動(dòng)無人車從客戶點(diǎn)i行駛到客戶點(diǎn)j時(shí)，載重量的變化約束；式（11）表示電動(dòng)無人車的電池電量的變化；式（12）表示到達(dá)任意客戶點(diǎn)的電量和離開該客戶點(diǎn)的電量是一樣的，即在客戶點(diǎn)處不耗電池電量；式（13）表示電動(dòng)無人車的電池電量不大于電池容量；式（14）表示電動(dòng)無人車在充電站的充電量；式（15）—（16）表示每輛電動(dòng)無人車到達(dá)各節(jié)點(diǎn)的時(shí)間變化約束；式（17）表示電動(dòng)無人車在充電站處完全充電所需時(shí)間；式（18）表示在充電站處電動(dòng)無人車等待充電的時(shí)間；式（19）表示0-1變量約束。

2 模型求解

2.1 動(dòng)態(tài)規(guī)劃算法

傳統(tǒng)的VRP問題是NP難問題，而最小最大電動(dòng)車輛路徑規(guī)劃問題是VRP問題的擴(kuò)展，因此MMEVRP問題也是NP難問題。由于該問題的復(fù)雜性，大部分研究利用GA算法或蟻群算法等啟發(fā)式算法求解，這些算法通?？梢栽谳^短的時(shí)間內(nèi)得到解，但無法保證解的質(zhì)量，因此本文先采用可精確求解的DP算法求解此問題。

DP算法常用來解決多階段決策過程的優(yōu)化問題，在路徑規(guī)劃方面也有較好的應(yīng)用成果，利用DP算法求解最優(yōu)路徑可以節(jié)省反復(fù)搜索可行路徑的時(shí)間。

由袁森等［17］證明的引理可知，最小最大圈覆蓋問題的最優(yōu)解將客戶集C恰好劃分成了k個(gè)子集，構(gòu)成集合C=｛S1，S2，…，Sk｝。為解決小規(guī)模的MMEVRP問題，首先逆時(shí)針依次篩選出一定角度范圍內(nèi)的所有客戶點(diǎn)，這些客戶點(diǎn)的貨物需求之和不能超過無人車的裝載容量，所有客戶點(diǎn)恰好分成k個(gè)客戶集合，分別由k輛車派送。

DP算法可快速求解MMEVRP問題小規(guī)模實(shí)例，但隨著問題規(guī)模的增大計(jì)算時(shí)間會(huì)呈指數(shù)型增長(zhǎng)，導(dǎo)致算法性能降低，甚至可能無法求解出問題的最優(yōu)解，因此精確算法在求解大規(guī)模實(shí)例時(shí)不再適用。此時(shí)需要利用尋優(yōu)性能好的啟發(fā)式算法對(duì)大規(guī)模算例進(jìn)行求解，本文改進(jìn)GA算法能在可接受時(shí)間內(nèi)得到問題較好的全局最優(yōu)解。

2.2 改進(jìn)遺傳-模擬退火算法

GA算法是源于生物界的啟發(fā)式算法，是一種高效的隨機(jī)全局搜索優(yōu)化方法，常用來求解各種車輛路徑規(guī)劃問題。為更好地求解電動(dòng)無人車的配送路徑以及選取合適的充電站充電，本文對(duì)GA算法進(jìn)行了兩個(gè)方面的改進(jìn)。首先為優(yōu)化充電站位置的選取與充電策略的選取，設(shè)計(jì)了一個(gè)充電站最優(yōu)插入策略；其次由于GA算法容易陷入局部最優(yōu)，引入Metropolis準(zhǔn)則，以一定概率接受劣質(zhì)解，增大算法迭代過程中的搜索空間，提高所提出算法的求解質(zhì)量。

改進(jìn)遺傳-模擬退火GA-SA算法的主要步驟如下：

a）確定染色體編碼規(guī)則。在模型求解過程中，要確定電動(dòng)無人車數(shù)量、每輛車需要服務(wù)的客戶集合以及訪問的充電樁，采用自然數(shù)編碼會(huì)比較直觀得到每輛無人車的配送順序，用o表示配送中心，用1，2，…，n表示對(duì)應(yīng)的客戶點(diǎn)，n+1，n+2，…，n+p表示配送網(wǎng)絡(luò)中的充電樁編號(hào)，即配送網(wǎng)絡(luò)中一共存在p個(gè)充電樁（包括虛擬充電樁），最后在起點(diǎn)和終點(diǎn)分別插入配送中心，即構(gòu)成1條染色體。

b）計(jì)算適應(yīng)度函數(shù)。適應(yīng)度函數(shù)用于評(píng)價(jià)種群中染色體優(yōu)劣以及趨近于最優(yōu)解的程度，適應(yīng)度越大，表明染色體質(zhì)量越高，被選擇的可能性越大，本文的目標(biāo)函數(shù)是使得車輛的最大距離最小，取目標(biāo)函數(shù)f的倒數(shù)作為適應(yīng)度函數(shù)fit（i）。

c）選擇算子。基于對(duì)個(gè)體適應(yīng)度的評(píng)估，計(jì)算種群的每個(gè)個(gè)體的fit（i），遺傳概率為pi=fit（i）/∑nj=1fit（j），計(jì)算個(gè)體累計(jì)概率為qi=∑nj=1pj，最后采用輪盤比例選擇適應(yīng)度較大的個(gè)體進(jìn)入下一次迭代。

d）設(shè)計(jì)搜索算子。使用部分匹配交叉和基因倒位插入變異兩種策略進(jìn)行尋優(yōu)。鄰域?qū)?yōu)策略示意圖如圖2所示。交叉操作分別在兩個(gè)染色體中隨機(jī)截取相同大小的基因片段，拼接到另一個(gè)染色體前端，再將拼接后的兩個(gè)染色體中與拼接基因重復(fù)的基因刪去，部分匹配交叉操作的示意圖如圖（a）所示；在一個(gè)染色體上隨機(jī)挑選兩個(gè)基因片段互換位置。這樣可以保證種群的多樣性，避免交叉操作引起的局部收斂，變異操作的示意圖如圖（b）所示。

e）運(yùn)用自適應(yīng)Metropolis準(zhǔn)則。對(duì)原始種群進(jìn)行GA算法的選擇、交叉、變異等操作后，形成新一代種群，再運(yùn)用Metropolis準(zhǔn)則增強(qiáng)算法的局部搜索能力，分情況選擇個(gè)體。若新解w′的目標(biāo)函數(shù)f（w′）小于初始解w的目標(biāo)函數(shù)f（w），即f（w′）

f）選擇充電站插入。由于車輛的電池容量有限，配送過程中要考慮電動(dòng)無人車的電量情況。GA算法構(gòu)造的未插入充電站的初始路徑解中可能存在違背距離約束的配送路徑，因此，這些路徑還要插入充電站，對(duì)應(yīng)車輛需要去充電站補(bǔ)充電量。由于配送網(wǎng)絡(luò)中含有的充電站數(shù)量相對(duì)較少，所以電動(dòng)無人車在充電站處可能產(chǎn)生等待時(shí)間。

為此本文設(shè)計(jì)了一個(gè)充電站最優(yōu)插入策略，改進(jìn)GA-SA算法流程如圖3所示，具體步驟如下：

步驟1。找出所有未插入充電站的解中違背距離約束的不可行配送路徑。

步驟2。在不可行配送路徑中，找到電動(dòng)無人車出發(fā)后電量低于電池安全電量閾值α之前能到達(dá)的最遠(yuǎn)客戶點(diǎn)，此時(shí)安排該車輛前往附近充電站充電，若不能到達(dá)則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟3。

步驟3。對(duì)當(dāng)前在該充電站內(nèi)的電動(dòng)無人車按到達(dá)充電站（站內(nèi)有m個(gè)充電樁）時(shí)間順序進(jìn)行編號(hào)｛n1，n2，…，ni｝，根據(jù)先到先充原則充電，若ni≤m，說明有充電樁空閑，車輛無需等待可馬上充電；若ni>m，說明車輛等待充電樁空閑才能充電，接在充滿電后離開此充電站的有最小編號(hào)的車輛nj（j

步驟4。電量低于電池電量閾值α?xí)r不能到達(dá)附近充電站視為不可行路徑，繼續(xù)迭代搜索可行路徑解。

步驟5。若所有車輛均完成貨物配送，則結(jié)束本次調(diào)度；否則重復(fù)以上步驟，直到達(dá)到迭代次數(shù)條件，結(jié)束算法。

3 實(shí)驗(yàn)分析

本文使用Matlab 2016a與Python3.7編程語言對(duì)算例進(jìn)行求解，運(yùn)行環(huán)境為64位Windows操作系統(tǒng)，運(yùn)行內(nèi)存為4 GiB，處理器為Intel（R） Core（TM） i5-7200U CPU@2.50 GiHz 2.71 GiHz的計(jì)算機(jī)。選取Solomon標(biāo)準(zhǔn)測(cè)試集中部分?jǐn)?shù)據(jù)［18］進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集根據(jù)客戶的分布特點(diǎn)分為三類：C類數(shù)據(jù)集的點(diǎn)是聚類分布的，R類數(shù)據(jù)集的點(diǎn)是隨機(jī)分布的，RC類數(shù)據(jù)集是半聚類半隨機(jī)分布的。

3.1 算例一分析

首先選取Solomon算例中C101的9個(gè)點(diǎn)作為基礎(chǔ)測(cè)試，編號(hào)0表示配送中心，編號(hào)5和9表示配送網(wǎng)絡(luò)中的充電站，站內(nèi)只有單個(gè)充電樁，設(shè)配送中心內(nèi)可使用的相同類型電動(dòng)無人車最大數(shù)量為3，該類型的無人車的裝載容量為50 kg，距離約束為65 km，電池耗電系數(shù)為1.1 kWh/km，充電系數(shù)為100 kWh/h，恒定的行駛速度為60 km/h，利用DP算法可以快速求出具體路徑分別是：0-3-1-9-0、0-7-8-5-6-0、0-2-4-0。由于配送網(wǎng)絡(luò)中有2個(gè)充電站，3輛無人車只有2輛車前往充電站充電，此算例沒有等待時(shí)間，3條子路徑長(zhǎng)度為77.97、68.53、63.22，因此車隊(duì)中電動(dòng)無人車的最大行駛距離是77.9，該值即為目標(biāo)函數(shù)值。各客戶點(diǎn)、倉庫點(diǎn)橫縱坐標(biāo)X和Y的位置信息，以及算例一電動(dòng)無人車配送路徑如圖4所示。

3.2 算例二分析

算例二以“數(shù)據(jù)類別-客戶點(diǎn)數(shù)量-充電站數(shù)量-每個(gè)站內(nèi)充電樁數(shù)量”命名，例如“C101-40-1-2”表示在C101標(biāo)準(zhǔn)實(shí)例中選取前40個(gè)點(diǎn)進(jìn)行實(shí)驗(yàn)，取1個(gè)點(diǎn)為充電站，該充電站中有充電樁接口2個(gè)。設(shè)C101-40-1-2中配送中心編號(hào)為0，充電站編號(hào)為29，設(shè)配送中心中可使用的電動(dòng)無人車最大數(shù)量為5輛，車輛的裝載容量為200 kg，距離約束為80 km，電池耗電系數(shù)為1.1 kWh/km，充電速率為100 kWh/h，行駛速度為60 km/h，電池電量閾值α設(shè)為20%，同時(shí)設(shè)定算法的最大迭代次數(shù)G=2000次，初始溫度為10000 ℃，冷卻因子為0.99，交叉概率為pc=0.9，變異概率為pm=0.1，變異次數(shù)為10次。目標(biāo)是使得電動(dòng)無人車車隊(duì)的最大行駛距離盡可能地小，合理調(diào)度充電車輛，減少充電次數(shù)以及排隊(duì)等待充電時(shí)間，提高配送效率。

利用單純的GA得到的目標(biāo)函數(shù)值為196.16，車輛的總配送距離為925.83，無人車隊(duì)在充電站處共充電9次，充電時(shí)間共為552.63，等待充電時(shí)間為44.60，其中車輛1的充電等待時(shí)間達(dá)28.40，車輛4的充電等待時(shí)間為16.20，其他車輛充電沒有排隊(duì)等待時(shí)間；而使用本文提出的改進(jìn)GA-SA求解的最小最大子路徑長(zhǎng)度為100.51，車隊(duì)的總配送距離為498.11，電動(dòng)無人車車輛在充電站共充電5次，總的充電時(shí)間為366.59，充電等待時(shí)間均為0。優(yōu)化后的目標(biāo)函數(shù)值，即最小最大子回路長(zhǎng)度縮短了48.76%，電動(dòng)無人車車隊(duì)的總行駛距離減少了46.20%，而且充電時(shí)間與等待時(shí)間也顯著減少，電動(dòng)無人車配送工作效率提高明顯。

表2為改進(jìn)GA-SA算法求解MMEVRP算例的求解結(jié)果，從表中數(shù)據(jù)可以看出，各無人車的路徑長(zhǎng)度相差較小，工作時(shí)長(zhǎng)較均衡，符合目標(biāo)要求。改進(jìn)GA-SA算法生成的電動(dòng)無人車配送路徑如圖5所示，GA算法和改進(jìn)GA-SA算法求解的優(yōu)化過程收斂曲線對(duì)比如圖6所示，改進(jìn)GA-SA算法在迭代1000次左右時(shí)逐漸收斂，得到最優(yōu)目標(biāo)函數(shù)值，雖然比GA算法的收斂速度慢，但是從適應(yīng)度函數(shù)值的變化過程可看出本文改進(jìn)的算法優(yōu)化效果更佳，求解質(zhì)量更優(yōu)。

3.3 算例三分析

為了進(jìn)一步驗(yàn)證本文提出的算法求解不同類型和規(guī)模算例的性能，結(jié)合客戶總需求，假設(shè)可使用的無人車最大數(shù)量增加為8輛，其他參數(shù)設(shè)置同算例二，對(duì)一些算例進(jìn)行仿真實(shí)驗(yàn)，分別用未改進(jìn)的GA算法和所提出的改進(jìn)GA-SA算法單獨(dú)求解10次，記錄每次的運(yùn)行結(jié)果、充電次數(shù)以及程序運(yùn)行時(shí)間，將10次計(jì)算的平均運(yùn)行時(shí)間和最優(yōu)解對(duì)比記錄見表3。

從上述求解結(jié)果可以看出，本文所提出的改進(jìn)GA-SA算法在求解不同類型和規(guī)模的MMEVRP實(shí)例時(shí)都給出了更優(yōu)的配送路徑，安排更少的充電次數(shù)能夠滿足電量需求。在配送網(wǎng)絡(luò)完全相同的情況下，從目標(biāo)函數(shù)列中可以看出對(duì)比未改進(jìn)前結(jié)果，改進(jìn)GA-SA算法縮短電動(dòng)無人車車隊(duì)中最長(zhǎng)子路徑的長(zhǎng)度顯著，與單純的GA算法相比，優(yōu)化率（未改進(jìn)結(jié)果與改進(jìn)結(jié)果的差值與未改進(jìn)結(jié)果的百分比）達(dá)30%以上，極大地提高了電動(dòng)無人車的配送效率。雖然算法的求解時(shí)間隨著問題規(guī)模的增大而增加，但求解結(jié)果更優(yōu)、質(zhì)量更高。可以預(yù)測(cè)，在求解更大規(guī)模的實(shí)際物流配送問題時(shí)，該算法也將表現(xiàn)出更快的求解速率和更好的優(yōu)化性能，能合理有效地給出電動(dòng)無人車車隊(duì)的物流配送路徑規(guī)劃和充電調(diào)度，給物流公司提供一些指導(dǎo)性意見。

3.4 影響無人車行駛距離的關(guān)鍵因素的靈敏度分析

在MMEVRP問題中，實(shí)驗(yàn)的計(jì)算結(jié)果會(huì)受無人車數(shù)量和充電站中充電樁數(shù)量影響，因此下文將分析這兩個(gè)因素的改變對(duì)計(jì)算結(jié)果的影響。從C101中選取數(shù)據(jù)進(jìn)行測(cè)試，客戶數(shù)為50，充電站數(shù)量為2，站內(nèi)只有單個(gè)充電樁。

a）無人車數(shù)量。將電動(dòng)無人車的耗電系數(shù)設(shè)為1.1 kWh/km，最多可使用的無人車數(shù)量分別設(shè)為3輛、5輛、7輛。電動(dòng)無人車的數(shù)量與其最大行駛距離和總行駛距離的關(guān)系如圖7所示，從該圖可以看出電動(dòng)無人車數(shù)量對(duì)不同算例的子路徑中的最大行駛距離和車隊(duì)的總行駛距離的變化趨勢(shì)。當(dāng)電動(dòng)無人車的耗電系數(shù)不變，車輛數(shù)量增加時(shí)，無人車隊(duì)中最長(zhǎng)配送子路徑長(zhǎng)度逐漸減小，這符合實(shí)際配送情況，所需要服務(wù)的相同客戶數(shù)量時(shí)，可使用的車輛數(shù)量越多，分配給各無人車的客戶數(shù)量會(huì)相應(yīng)減少，因此配送路徑中的最大行駛距離會(huì)變小，但是車隊(duì)的總行駛距離相應(yīng)的有所增加。車隊(duì)中的最大行駛距離和總行駛距離都受數(shù)據(jù)集中客戶點(diǎn)分布影響，由于R101和RC101數(shù)據(jù)中客戶點(diǎn)分布較分散，行駛過程中車輛的充電次數(shù)不可避免地增加，此時(shí)目標(biāo)函數(shù)和總行駛距離都會(huì)比聚類分布的C101大。

b）車輛的耗電系數(shù)。將最多可使用的無人車數(shù)量設(shè)為5輛，車輛的耗電系數(shù)分別設(shè)為0.8、1.1 kWh/km和1.4 kWh/km，電動(dòng)無人車耗電系數(shù)與無人車的最大行駛距離和總行駛距離的關(guān)系如圖8所示。從圖8可以看出，當(dāng)電動(dòng)無人車的耗電系數(shù)越來越大時(shí)，充電次數(shù)會(huì)有所增加，所以最大子路徑長(zhǎng)度也會(huì)隨之增加，車隊(duì)行駛的總距離也逐漸增加。這符合實(shí)際情況，耗電系數(shù)越大，說明電動(dòng)無人車行駛單位距離電池電量消耗的越多，而符合電量約束的可行路徑減少，電量不足時(shí)無人車需要多次前往充電站充電，所以會(huì)改變無人車的行駛路徑，這時(shí)各輛無人車的行駛距離以及車隊(duì)的總距離都會(huì)相應(yīng)地有所增加。同樣地，由于數(shù)據(jù)集中客戶點(diǎn)分布情況不同，耗電系數(shù)增大時(shí)，較為分散的數(shù)據(jù)集R101和RC101行駛過程中充電次數(shù)增加的可能更多，此時(shí)子路徑的最長(zhǎng)距離和車隊(duì)的總行駛距離都隨之增大。

由以上實(shí)驗(yàn)可以看出，利用電動(dòng)無人車在城市中配送貨物，可以通過增加電動(dòng)無人車數(shù)量和開發(fā)新技術(shù)降低耗電系數(shù)使得最長(zhǎng)子路徑距離盡可能地短，均衡各無人車的工作時(shí)長(zhǎng)。

4 結(jié) 語

本文研究了在充電站有充電容量約束的情況下，考慮配送途中的充電次數(shù)以及可能存在的充電等待時(shí)間的電動(dòng)無人車的路徑規(guī)劃和充電調(diào)度優(yōu)化問題，建立了MMEVRP的數(shù)學(xué)規(guī)劃模型。針對(duì)小規(guī)模算例，應(yīng)用DP算法精確求解無人車配送路徑；針對(duì)中大規(guī)模算例，改進(jìn)GA-SA算法求解，增強(qiáng)算法搜索能力，避免算法陷入局部最優(yōu)。數(shù)值實(shí)驗(yàn)以及靈敏度分析結(jié)果表明，本文提出的優(yōu)化算法可以減少充電次數(shù)以及充電等待時(shí)間，同時(shí)縮短車隊(duì)中最長(zhǎng)子路徑的長(zhǎng)度和車隊(duì)的總行駛距離，使得車隊(duì)中車輛的工作時(shí)間更加均衡，減少車輛的電池?fù)p耗率。本文為物流企業(yè)選取電動(dòng)無人車來進(jìn)行物流配送提供一定參考，幫助物流企業(yè)提高電動(dòng)無人車的利用率和配送效率，降低物流公司的配送成本。

在實(shí)際城市無人物流配送系統(tǒng)中，還需考慮客戶點(diǎn)的服務(wù)時(shí)間窗口等其他限制，因此后續(xù)研究可以進(jìn)一步考慮客戶時(shí)間窗的路徑規(guī)劃、部分充電的充電調(diào)度策略等。

參考文獻(xiàn)：

［1］Dantzig G B， Ramser J H. The truck dispatching problem［J］. Management Science，1959，6（1）： 80-91.

［2］張玉州，徐廷政，鄭軍帥， 等.考慮緊急度的救災(zāi)車輛路徑問題建模與優(yōu)化［J］.計(jì)算機(jī)應(yīng)用，2019，39（8）：2444-2449.

［3］Tamke F， Buscher U. A branch-and-cut algorithm for the vehicle routing problem with drones［J］. Transportation Research Part B： Methodological， 2021，144：174-203.

［4］葛顯龍，李祖?zhèn)?，葛小?考慮靈活充電策略的帶時(shí)間窗物流配送路徑優(yōu)化研究［J］.控制理論與應(yīng)用，2020，37（6）：1293-1301.

［5］揭婉晨，侍穎，楊珺， 等.需求可拆分電動(dòng)汽車車輛路徑問題及其改進(jìn)分支定價(jià)算法研究［J］.管理學(xué)報(bào)，2020，17（12）：1873-1880.

［6］Wu H G， Gao Y L， Wang W T， et al. A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows［J］. Complex & Intelligent Systems， 2023， 9（3）： 2491-2508.

［7］Zhang Y B， Zhang Z， Liu Z H， et al.An asymptotically tight online algorithm for m-Steiner Traveling Salesman Problem［J］. Information Processing Letters， 2022，174：106177.

［8］Guo Q， Peng J， Xu W Z， et al. Minimizing the longest tour time among a fleet of UAVs for disaster area surveillance［J］. IEEE Transactions on Mobile Computing， 2022， 21（7）： 2451-2465.

［9］Zhang Y B， Zhang Z， Liu Z H，Yu W， Liu Z H.Improved approximation algorithms for some min-max and minimum cycle cover problems［J］. Theoretical Computer Science， 2016，654： 45-58.

［10］Yu W，Liu Z H.Better approximability results for min-max tree/cycle/path cover problems［J］. Journal of Combinatorial Optimization， 2019，37（2）：563-578.

［11］Yakc E.A heuristic approach for solving a rich min-max vehicle routing problem with mixed fleet and mixed demand［J］. Computers & Industrial Engineering， 2017，109：288-294.

［12］Sze J F，Salhi S，Wassan N.The cumulative capacitated vehicle routing problem with min-sum and min-max objectives：An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search［J］. Transportation Research Part B： Methodological， 2017，101：162-184.

［13］李小川，劉媛華，王影歌.求解最小最大VRP的精英反向?qū)W習(xí)魚群算法［J］.傳感器與微系統(tǒng)，2020，39（2）：140-143.

［14］Bruglieri M，Mancini S，Pisacane O. The green vehicle routing problem with capacitated alternative fuel stations［J］. Computers & Operations Research， 2019，112： 104759.

［15］李默涵，毛李帆，鄭從鎮(zhèn)， 等.考慮充電等待成本的電動(dòng)汽車路徑問題［J］.廣東電力，2020，33（7）：33-41.

［16］Keskin M，Laporte G，atay B.Electric vehicle routing problem with time-dependent waiting times at recharging stations［J］. Computers & Operations Research， 2019， 107： 77-94.

［17］袁森，陳開奇，李江坤， 等.最小最大圈覆蓋問題的精確算法［J］.中國(guó)科學(xué)：信息科學(xué)，2022，52（6）：960-970.

［18］Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987，35（2）： 254-265.

（責(zé)任編輯：康 鋒）

收稿日期： 2022-11-29網(wǎng)絡(luò)出版日期：2023-06-07

基金項(xiàng)目： 國(guó)家自然科學(xué)基金項(xiàng)目（12071436）

作者簡(jiǎn)介： 曹 珍（1998- ），女，江西贛州人，碩士研究生，主要從事組合優(yōu)化方面的研究。

通信作者： 韓曙光，E-mail：zist001@163.com