曹珍　韓曙光

摘 要： 在充電站有充電容量約束的情況下，研究充電調(diào)度電動(dòng)無(wú)人車配送路徑規(guī)劃問(wèn)題。首先以極小化車隊(duì)中電動(dòng)無(wú)人車的最大行駛距離為目標(biāo)，構(gòu)建數(shù)學(xué)規(guī)劃模型，為電動(dòng)無(wú)人車車隊(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)無(wú)人車路徑和充電策略；最后對(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)無(wú)人車車隊(duì)的最長(zhǎng)子路徑的長(zhǎng)度和總行駛距離。該研究可以為物流公司的電動(dòng)無(wú)人車配送業(yè)務(wù)發(fā)展提供參考，幫助企業(yè)提高電動(dòng)無(wú)人車的運(yùn)輸效率和服務(wù)水平，降低配送成本。

關(guān)鍵詞： 電動(dòng)無(wú)人車；配送路徑規(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)無(wú)人車配送路徑規(guī)劃問(wèn)題研究［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 引 言

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

本文中的符號(hào)及其含義見(jiàn)表1。無(wú)向圖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輛無(wú)人車可以被分配來(lái)執(zhí)行送貨任務(wù)。

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

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

2 模型求解

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

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

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

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

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

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

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

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

a）確定染色體編碼規(guī)則。在模型求解過(guò)程中，要確定電動(dòng)無(wú)人車數(shù)量、每輛車需要服務(wù)的客戶集合以及訪問(wèn)的充電樁，采用自然數(shù)編碼會(huì)比較直觀得到每輛無(wú)人車的配送順序，用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，最后采用輪盤(pán)比例選擇適應(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）選擇充電站插入。由于車輛的電池容量有限，配送過(guò)程中要考慮電動(dòng)無(wú)人車的電量情況。GA算法構(gòu)造的未插入充電站的初始路徑解中可能存在違背距離約束的配送路徑，因此，這些路徑還要插入充電站，對(duì)應(yīng)車輛需要去充電站補(bǔ)充電量。由于配送網(wǎng)絡(luò)中含有的充電站數(shù)量相對(duì)較少，所以電動(dòng)無(wú)人車在充電站處可能產(chǎn)生等待時(shí)間。

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

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

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

步驟3。對(duì)當(dāng)前在該充電站內(nèi)的電動(dòng)無(wú)人車按到達(dá)充電站（站內(nèi)有m個(gè)充電樁）時(shí)間順序進(jìn)行編號(hào)｛n1，n2，…，ni｝，根據(jù)先到先充原則充電，若ni≤m，說(shuō)明有充電樁空閑，車輛無(wú)需等待可馬上充電；若ni>m，說(shuō)明車輛等待充電樁空閑才能充電，接在充滿電后離開(kāi)此充電站的有最小編號(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編程語(yǔ)言對(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)無(wú)人車最大數(shù)量為3，該類型的無(wú)人車的裝載容量為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輛無(wú)人車只有2輛車前往充電站充電，此算例沒(méi)有等待時(shí)間，3條子路徑長(zhǎng)度為77.97、68.53、63.22，因此車隊(duì)中電動(dòng)無(wú)人車的最大行駛距離是77.9，該值即為目標(biāo)函數(shù)值。各客戶點(diǎn)、倉(cāng)庫(kù)點(diǎn)橫縱坐標(biāo)X和Y的位置信息，以及算例一電動(dòng)無(wú)人車配送路徑如圖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)無(wú)人車最大數(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)無(wú)人車車隊(duì)的最大行駛距離盡可能地小，合理調(diào)度充電車輛，減少充電次數(shù)以及排隊(duì)等待充電時(shí)間，提高配送效率。

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

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

3.3 算例三分析

為了進(jìn)一步驗(yàn)證本文提出的算法求解不同類型和規(guī)模算例的性能，結(jié)合客戶總需求，假設(shè)可使用的無(wú)人車最大數(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ì)比記錄見(jiàn)表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)無(wú)人車車隊(duì)中最長(zhǎng)子路徑的長(zhǎng)度顯著，與單純的GA算法相比，優(yōu)化率（未改進(jìn)結(jié)果與改進(jìn)結(jié)果的差值與未改進(jìn)結(jié)果的百分比）達(dá)30%以上，極大地提高了電動(dòng)無(wú)人車的配送效率。雖然算法的求解時(shí)間隨著問(wèn)題規(guī)模的增大而增加，但求解結(jié)果更優(yōu)、質(zhì)量更高?？梢灶A(yù)測(cè)，在求解更大規(guī)模的實(shí)際物流配送問(wèn)題時(shí)，該算法也將表現(xiàn)出更快的求解速率和更好的優(yōu)化性能，能合理有效地給出電動(dòng)無(wú)人車車隊(duì)的物流配送路徑規(guī)劃和充電調(diào)度，給物流公司提供一些指導(dǎo)性意見(jiàn)。

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

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

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

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

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

4 結(jié) 語(yǔ)

本文研究了在充電站有充電容量約束的情況下，考慮配送途中的充電次數(shù)以及可能存在的充電等待時(shí)間的電動(dòng)無(wú)人車的路徑規(guī)劃和充電調(diào)度優(yōu)化問(wèn)題，建立了MMEVRP的數(shù)學(xué)規(guī)劃模型。針對(duì)小規(guī)模算例，應(yīng)用DP算法精確求解無(wú)人車配送路徑；針對(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)無(wú)人車來(lái)進(jìn)行物流配送提供一定參考，幫助物流企業(yè)提高電動(dòng)無(wú)人車的利用率和配送效率，降低物流公司的配送成本。

在實(shí)際城市無(wú)人物流配送系統(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)車輛路徑問(wèn)題建模與優(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)汽車車輛路徑問(wèn)題及其改進(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í)魚(yú)群算法［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)汽車路徑問(wèn)題［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］袁森，陳開(kāi)奇，李江坤， 等.最小最大圈覆蓋問(wèn)題的精確算法［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