基于同時(shí)送取貨電動(dòng)車選址路徑問題優(yōu)化研究

陳其賽，倪 靜

（上海理工大學(xué) 管理學(xué)院，上海 200093）

隨著國務(wù)院辦公廳《新能源汽車產(chǎn)業(yè)發(fā)展規(guī)劃（2021—2035）》的印發(fā)，未來電動(dòng)汽車代替燃油汽車已成為必然趨勢。對于物流企業(yè)來說，如何降低成本一直是研究的重點(diǎn)。相比傳統(tǒng)燃油汽車，電動(dòng)汽車以極低的運(yùn)輸成本優(yōu)勢逐漸在短距離的市內(nèi)配送中成為企業(yè)首選。此外，在現(xiàn)代物流中，配送方式隨著客戶群體的不同存在不同的運(yùn)輸模式。對于超市、便利店等這類每日既要進(jìn)貨又有未售罄生鮮需要回收的商戶來說，同時(shí)送取貨這一更貼近實(shí)際需求的物流配送模式逐漸成為學(xué)者的研究重點(diǎn)。

對同時(shí)送取貨問題的研究更貼近于實(shí)際，考慮車輛在實(shí)際配送任務(wù)中不同客戶的需求，國內(nèi)外已有不少學(xué)者研究。徐小峰等[1]考慮了同時(shí)送取貨需求帶模糊容量限制的動(dòng)態(tài)選址問題，通過改進(jìn)五角模糊數(shù)隸屬度函數(shù)來表示模糊容量約束，再通過禁忌搜索與自適應(yīng)大規(guī)模領(lǐng)域搜索算法結(jié)合的混合算法來求得可行解；王超等[2]首次設(shè)計(jì)了回溯搜索優(yōu)化算法來解決帶時(shí)間窗同時(shí)送取貨問題并證明有效性；Wang等[3]研究了多配送中心同時(shí)送取貨的車輛路徑問題并利用非支配排序遺傳算法求解；周詠等[4]研究冷鏈物流同時(shí)送取貨車輛路徑優(yōu)化問題；譚巍等[5]研究了車輛負(fù)載量不斷變化情況下引入候選集合的策略，將啟發(fā)因子設(shè)為目標(biāo)函數(shù)值并利用蟻群系統(tǒng)與2-opt方法相結(jié)合的啟發(fā)式算法求解模型；Golsefidi等[6]考慮到供應(yīng)鏈管理中殘缺產(chǎn)品庫存的不確定性，通過適用于等式約束的魯棒優(yōu)化方法以及改進(jìn)模擬退火算法、遺傳算法求解模型并分析算法性能。

電動(dòng)汽車憑借低成本、綠色環(huán)保逐漸在物流配送領(lǐng)域成為主流，但由于其存在著續(xù)航能力較弱、配套的充電設(shè)施布局不健全等問題。如何建立一套完整的電動(dòng)汽車物流配送網(wǎng)絡(luò)體系，對充電設(shè)施的選址以及配送路徑的優(yōu)化成為了當(dāng)下急需解決的問題。楊磊等[7]考慮了電動(dòng)汽車在充電和換電兩種模式下電動(dòng)車的充換電設(shè)施選址問題，分別建立了兩種模式下的數(shù)學(xué)模型并通過改進(jìn)遺傳算法來求解路徑規(guī)劃和選址模型；陸堅(jiān)毅等[8]考慮到電動(dòng)汽車用戶會(huì)繞行一段距離對車輛進(jìn)行充電的特征建立了以充電站建設(shè)成本和繞行成本之和最小為目標(biāo)的雙層整數(shù)規(guī)劃模型，通過包含局部迭代搜索的自適應(yīng)遺傳算法對模型求解；Zhang等[9]考慮了電動(dòng)汽車的能耗問題，基于蟻群算法求解電動(dòng)汽車的最小能耗并說明最小能耗作為目標(biāo)函數(shù)而不是最小距離作為目標(biāo)函數(shù)的好處；楊珺等[10]、敦放等[11]考慮到差異化因素對選址路徑的影響，并分別用改進(jìn)禁忌搜索算法和MCWGATS算法求解該模型，最后用多組算例證明了算法的有效性。

綜上所述，學(xué)者們已對同時(shí)送取貨問題的選址或者配送方法進(jìn)行了研究，但針對電動(dòng)汽車完成同時(shí)送取貨選址路徑優(yōu)化問題的研究較少。電動(dòng)汽車采用同時(shí)送取貨模式進(jìn)行配送可降低成本，本文綜合考慮客戶同時(shí)送取貨需求、時(shí)間窗約束以及電動(dòng)汽車電量與容量約束等因素，建立了帶同時(shí)送取貨和時(shí)間窗約束的電動(dòng)車選址路徑問題模型（ELRPSPDTW）[12-14]，并設(shè)計(jì)了改進(jìn)的混合模擬退火-蟻群算法（SA-ACO）來求解該問題[15-16]。首先，進(jìn)行問題描述并建立相應(yīng)模型；其次，提出混合模擬退火-蟻群算法并介紹相關(guān)優(yōu)化策略；接著，通過隨機(jī)生成不同規(guī)模大小的算例進(jìn)行仿真實(shí)驗(yàn)，并與蟻群（ACO）、禁忌搜索（TS）以及自適應(yīng)大鄰域搜索（ALNS）3種算法的解進(jìn)行比較；此外，再和送取分離的配送模式進(jìn)行對比，驗(yàn)證算法的穩(wěn)定性與實(shí)用性；最后，證明本文提出的模型和算法在解決同時(shí)送取貨問題時(shí)的可行性以及對未來的展望。

1 模 型

1.1 問題描述

構(gòu)建電動(dòng)汽車帶時(shí)間窗和同時(shí)送取貨的選址路徑模型，具體問題描述如下：ELRPSPDTW組成的網(wǎng)絡(luò)圖為G=(N,A)，N=Nc∪S∪{0}，其中，Nc={1,2,···,n}，Nc為顧客點(diǎn)集合，S={1,2,···,s}，S為充電站集合，s∈S，{O}為中心倉庫，A={(i,j)|i,j∈N,i≠j}，A為點(diǎn)i,j弧集合，每條邊(i,j)∈N為兩兩節(jié)點(diǎn)的距離dij，滿足距離關(guān)系式dik+dkj≥dij。該配送中心有m輛車型相同的電動(dòng)汽車，其中，k∈K,K={1,2,···,m}，K為車輛集合。

電動(dòng)汽車充滿電后從配送中心勻速出發(fā)為多個(gè)顧客提供配送服務(wù)，而每個(gè)顧客有且僅能接受一輛電動(dòng)汽車的服務(wù)，電動(dòng)汽車在完成配送任務(wù)之后需要返回配送中心。每輛電動(dòng)汽車有配送容量限制，每個(gè)顧客除了具有送貨需求之外也存在取貨需求且送取貨需求量均已知，每個(gè)顧客都有一定量的貨物需要電動(dòng)汽車送回配送中心，因此，在電動(dòng)汽車服務(wù)過程中，運(yùn)載量不能超過其車身最大裝載量。每個(gè)顧客既存在軟時(shí)間窗限制又存在硬時(shí)間窗限制，軟時(shí)間窗為[ei,li]，硬時(shí)間窗為[Ei,Li],[Ei,Li]?[ei,li]，車輛到達(dá)時(shí)間在硬時(shí)間窗范圍內(nèi)、軟時(shí)間窗范圍外時(shí)存在時(shí)間窗懲罰成本。

在本文中，只有電動(dòng)汽車經(jīng)過配送中心或者充電站才能換上充滿電量的電池，充電站的位置在網(wǎng)絡(luò)中隨機(jī)產(chǎn)生。本文考慮到長期使用以及各種未知因素，采用自建充電站的形式，每一個(gè)充電站的建設(shè)都會(huì)產(chǎn)生固定費(fèi)用。為盡可能減小充電過程中帶來的損失，采用更換電池的充電方式，更換一個(gè)電池所需時(shí)間固定。

1.2 符號與決策變量

為了能更好地描述ELRPSPDTW的數(shù)學(xué)模型，對本文使用的符號作如下說明：G表示一個(gè)配送網(wǎng)絡(luò)，G=(N,A)；N表示節(jié)點(diǎn)集，N=Nc∪S∪{0}，Nc為顧客集，S為充電站集，0為配送中心；A表示邊集；dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離；K為車輛集合；C為單位距離耗電成本；W1為車輛早到等待時(shí)的單位時(shí)間機(jī)會(huì)成本；W2為車輛晚到時(shí)的單位時(shí)間懲罰成本；為車輛k到達(dá)i點(diǎn)時(shí)的時(shí)間；為車輛k離開i點(diǎn)時(shí)的時(shí)間；tsi為車在i點(diǎn)的服務(wù)時(shí)間；v為車速；ei為客戶點(diǎn)i滿意的時(shí)間下限；li為客戶點(diǎn)i滿意的時(shí)間上限；Ei為允許車輛到達(dá)客戶點(diǎn)i的最早時(shí)間；Li為允許車輛到達(dá)客戶點(diǎn)i的最晚時(shí)間；f為單位充電站的建造成本；Ck為電動(dòng)汽車k的發(fā)車成本；pi為i點(diǎn)的送貨量；qi為i點(diǎn)的取貨量；Q為車的最大容量；Qijk為k車在弧(i,j)段時(shí)的負(fù)載量；Bk為電動(dòng)車k電池的最大容量；為電動(dòng)車k到達(dá)節(jié)點(diǎn)i時(shí)的剩余電量；為電動(dòng)車k離開節(jié)點(diǎn)i時(shí)的剩余電量；r為電動(dòng)車單位距離耗電量；h為電動(dòng)車在充電站更換電池所需時(shí)間。決策變量：xijk為k車經(jīng)過弧(i,j)從節(jié)點(diǎn)i到節(jié)點(diǎn)j時(shí)則為1；yi為建造第s個(gè)充電站時(shí)則為1；為k車從i點(diǎn)前往j點(diǎn)過程中需要先經(jīng)過充電站s時(shí)則為1。

1.3 模型

建立數(shù)學(xué)模型：

約束條件：

其中：目標(biāo)函數(shù)式（1）表示電動(dòng)汽車車輛運(yùn)輸成本、時(shí)間窗懲罰成本和充電站服務(wù)設(shè)施建設(shè)成本這3項(xiàng)物流成本最小化；約束式（2）表示每個(gè)顧客被服務(wù)僅被服務(wù)一次；約束式（3）表示車輛進(jìn)出流量平衡，即每輛車進(jìn)入某個(gè)點(diǎn)的次數(shù)和離開某個(gè)點(diǎn)的次數(shù)相等；約束式（4）表示電動(dòng)汽車從配送中心出發(fā)最后返回配送中心；約束式（5）表示每一條路線只有一輛車行駛；約束式（6）為消除子回路；約束式（7）和式（8）表示每條路徑上任意節(jié)點(diǎn)車輛的裝載量不會(huì)超過車輛的裝載能力；約束式（9）表示任意節(jié)點(diǎn)貨物量的送取平衡；約束式（10）表示電動(dòng)汽車從配送中心出發(fā)時(shí)開始計(jì)時(shí)；約束式（11）和式（12）表示車輛k在離開i點(diǎn)和到達(dá)j點(diǎn)時(shí)的時(shí)間；約束式（13）為硬時(shí)間窗約束；約束式（14），（15），（16）表示車輛離開配送中心、離開充電站和離開客戶點(diǎn)時(shí)的電量水平；約束式（17）定義決策變量是0-1變量。

2 算法設(shè)計(jì)

本文研究的ELRPSPDTW模型是以總成本最小為目標(biāo)的選址路徑問題，顯然該問題屬于典型的NP難題。針對選址路徑（LRP）問題，目前國內(nèi)外較為常見的方法主要是將LRP問題分解成選址分配問題（LAP）和車輛路徑問題（VRP）分階段求解。遺傳算法、蟻群算法等啟發(fā)式算法已被證明能很好地解決此類問題，其中，蟻群算法采用分布式并行計(jì)算機(jī)制，有自組織性、正反饋性與較強(qiáng)的魯棒性，可以使問題在較短的時(shí)間內(nèi)找到較為滿意的解，同時(shí)通過引入高斯變異來改進(jìn)對重點(diǎn)搜索區(qū)域的局部搜索性能。蟻群算法雖然可以在較短時(shí)間內(nèi)得到較好的解，但是，當(dāng)求解問題規(guī)模較大時(shí)，蟻群算法容易出現(xiàn)早熟、停滯現(xiàn)象。模擬退火算法是模擬固體退火過程的一種隨機(jī)搜尋算法，具有結(jié)構(gòu)簡單且操作模塊相對獨(dú)立的特點(diǎn)，可以被廣泛地應(yīng)用于多約束耦合求解。由于在使用模擬退火的過程中加入了回火操作，增大了算法對非更優(yōu)解的接受能力，有助于算法對局部較優(yōu)解的跳出，這恰好能解決蟻群算法中容易陷入局部尋優(yōu)的不足，因此，通過結(jié)合兩種算法的優(yōu)點(diǎn)設(shè)計(jì)該模擬退火-蟻群算法來解決本文問題，整體流程圖如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

2.1 初始編碼及編碼規(guī)則

初始解操作的首要目的是生成一個(gè)滿足問題約束的解，有利于后續(xù)目標(biāo)優(yōu)化的展開，本文采用均勻分布隨機(jī)數(shù)產(chǎn)生特定范圍內(nèi)符合約束條件的初始編碼。編碼方式采用三層編碼，第一層編碼為充電站的選擇優(yōu)先度編碼，編碼長度為J，范圍為1-J的不重復(fù)自然數(shù)；第二層編碼為充電站的選擇數(shù)量，編碼長度為1，范圍為1-J的整數(shù)；第三層編碼為需求點(diǎn)的配送優(yōu)先度，編碼長度為K，范圍為1-J的不重復(fù)自然數(shù)。如果J=5,K=6,C=[5,4,2,3,1,3,5,6,3,4,1,2]，則5, 4, 2, 3, 1為第一層編碼，表示充電站是優(yōu)先選擇5，其次4，接著2，再選3，最后是1；3是第二層編碼，表示選擇3個(gè)充電站，按第一層編碼的優(yōu)先度進(jìn)行選擇，即依次選擇5, 4, 2這3個(gè)充電站；5, 6, 3, 4, 1, 2為第三層編碼，表示需求點(diǎn)的配送優(yōu)先度，即配送順序依次為5, 6, 3, 4, 1, 2。

2.2 高斯變異及信息素更新策略

高斯變異作為改進(jìn)遺傳算法對重點(diǎn)搜索區(qū)域的局部搜索性能的另外一種變異操作方法，在變異時(shí)用一個(gè)均值為μ、方差為 σ的正態(tài)分布的一個(gè)隨機(jī)數(shù)來替換原有基因值，其過程與均勻變異類似，

信息素更新是蟻群算法的關(guān)鍵操作之一，若信息素更新過快，容易使算法過早陷入局部尋優(yōu)，信息素更新過慢，則會(huì)影響算法的收斂速度。信息素?fù)]發(fā)的公式為

式中：τi(gen+1)為第gen+1代第i個(gè)螞蟻對應(yīng)信息素；ρ為信息素?fù)]發(fā)因子；τi(gen)為第gen代第i個(gè)螞蟻對應(yīng)信息素。

信息素增強(qiáng)的公式為

式中：Δτi(gen+1)為第gen+1代第i個(gè)螞蟻的信息素增量；Qx為信息素增強(qiáng)因子；yi為第i個(gè)螞蟻對應(yīng)的目標(biāo)函數(shù)值。

2.3 帶回火操作的模擬退火算法求解步驟

帶回火操作的模擬退火算法求解步驟：

a. 設(shè)置退火起始溫度T0，退火終止溫度Tz，退火系數(shù)th，回火系數(shù)hh，回火結(jié)束溫度Th，退火溫度T=T0，設(shè)置迭代次數(shù)Nh。

b. 每當(dāng)退火迭代次數(shù)達(dá)到退火終止溫度，則升高溫度進(jìn)行回火操作，在每次回火過程中，回火的最高溫度隨每次退火過程逐漸降低，最終達(dá)到回火結(jié)束溫度時(shí)則停止運(yùn)行算法。

3 數(shù)值仿真算例分析

3.1 參數(shù)設(shè)置

為了證明該算法的有效性，現(xiàn)利用數(shù)值仿真實(shí)驗(yàn)對算法進(jìn)行實(shí)際應(yīng)用。由于目前沒有與本文問題相關(guān)的標(biāo)準(zhǔn)測試算例，本文的實(shí)驗(yàn)算例由1個(gè)中心倉庫、8個(gè)待選充電站和30個(gè)客戶組成，客戶點(diǎn)的坐標(biāo)由MATLAB 9.6.0軟件的rand()函數(shù)在[0,150]區(qū)間隨機(jī)生成，各個(gè)客戶的送取貨量在[0,360]區(qū)間隨機(jī)生成。設(shè)置車的最大容量Q=1500，電池最大容量Bk=220，車速v=70。相關(guān)參數(shù)設(shè)置：Qx=1，ρ=0.01，T0=2 000，Tz=20，th=0.99，hh=0.75，Nh=200。

3.2 算法驗(yàn)證

算法通過MATLAB 9.6.0編程實(shí)現(xiàn)，計(jì)算機(jī)配置為Intel Core i7-9750H，2.60 GHz，32 GB RAM，在Windows10操作系統(tǒng)下運(yùn)行。分別用SA-ACO，ACO，TS以及ALNS算法對隨機(jī)生成的30個(gè)客戶算例求解，求解得出的最優(yōu)化路徑如圖2所示。其中，中心紅點(diǎn)表示配送中心，C1-C8為隨機(jī)生成的充電站，被選中使用的充電站點(diǎn)由紫色圓環(huán)標(biāo)注，剩余點(diǎn)為待服務(wù)的客戶點(diǎn)。

圖2 不同算法路線求解結(jié)果Fig.2 Solution results of different algorithm routes

表1為30個(gè)客戶在4種算法求解結(jié)果下所需車輛數(shù)、充電站數(shù)以及總成本。在本文所提出的算法求解結(jié)果中，配送中心需要3輛車并啟用了2個(gè)充電站來完成該配送任務(wù)，總成本為1 977.85元。而ACO算法、TS算法以及ALNS算法結(jié)果的總成本分別為2 341.54元，2 748.77和2 276.91元。

表1 30個(gè)客戶求解結(jié)果Tab.1 Solution results of 30 clients

3.3 混合算法有效性分析

為了進(jìn)一步驗(yàn)證算法的有效性，除了生成30個(gè)客戶的算例之外，再分別隨機(jī)生成50，100以及150個(gè)客戶的算例，繼續(xù)進(jìn)行實(shí)驗(yàn)分析，比較結(jié)果如表2所示，其中，GAP表示本文算法的求解結(jié)果優(yōu)于對比算法的百分率。

從表2中可以看出，本文提出的算法比起傳統(tǒng)蟻群算法的求解結(jié)果平均高出12.46%，說明在加入了模擬退火算法從而提高全局尋優(yōu)能力之后確實(shí)能有效幫助蟻群算法得到更優(yōu)解。在求解帶時(shí)間窗和同時(shí)送取貨約束的電動(dòng)車選址路徑問題中，改進(jìn)的模擬退火-蟻群算法比起傳統(tǒng)的啟發(fā)式算法無論在中小規(guī)模算例中都能得到更好的總成本解，說明該算法具有良好的穩(wěn)定性和有效性。另一方面，以150個(gè)客戶的算例為例，用圖3表示4種算法迭代200次的收斂情況。從圖3可知，本文所提出的改進(jìn)模擬退火-蟻群算法收斂效果最優(yōu)，說明與蟻群算法相比，加入了模擬退火算法后不容易陷入局部尋優(yōu)，在迭代160次左右后開始逐漸趨于最優(yōu)解，通過綜合對比后可知，本文算法在求解該類問題上具有一定優(yōu)勢。

圖3 150個(gè)客戶算法收斂對比圖Fig. 3 Convergence comparison chart of 150 client algorithms

3.4 算法運(yùn)行時(shí)間分析

模擬退火算法和蟻群算法在求解這類NP難題可以得出較優(yōu)解，但是，計(jì)算效率都不高。為了從算法運(yùn)行時(shí)間方面進(jìn)一步分析本文算法，本文以150個(gè)客戶的規(guī)模為標(biāo)準(zhǔn)，隨機(jī)生成算例50次，分別用上述4種算法進(jìn)行仿真求解并記錄下4個(gè)算法的求解結(jié)果和所需時(shí)間，取平均值后結(jié)果如表3所示。從表3可以看出，由于加入了高斯變異和回火兩種策略，盡管本文算法由兩種效率較低的算法混合而成，與蟻群算法相比仍可更快跳出局部尋優(yōu)，從而在更短時(shí)間內(nèi)求得更優(yōu)解。與TS算法以及ALNS算法相比，求解時(shí)間上還存在一定差距，但是，考慮實(shí)際環(huán)境，求解所需時(shí)間也還在可接受范圍之內(nèi)，具有可行性。

表3 算法運(yùn)行時(shí)間對比Tab.3 Comparison of algorithm running time

3.5 送取貨模式分析

為了進(jìn)一步驗(yàn)證本文所提出的同時(shí)送取貨模式以及模擬退火-蟻群算法的實(shí)用性，通過更改配送模式，將送貨和取貨分開來先統(tǒng)一進(jìn)行送貨，所有客戶配送完畢后再進(jìn)行取貨工作。取同樣的客戶數(shù)據(jù)再一次進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如表4所示，其中，GAP表示各算法下同時(shí)送取貨模式總成本優(yōu)于送取貨分離模式總成本的百分率。

表4 送取貨結(jié)果對比Tab.4 Comparison of delivery and pickup results

從表4中可以看出，當(dāng)采用送取分離模式進(jìn)行配送之后，總成本平均上升9.38%，而另外3種算法平均上升均超過12%。說明本文所提出的模擬退火-蟻群算法實(shí)用性較好，且同時(shí)送取貨的配送模式更貼近實(shí)際，有效解決了客戶需求。

4 結(jié)束語

為了更加貼近實(shí)際物流的配送情景，考慮了在時(shí)間窗約束下進(jìn)行同時(shí)送取貨這一更貼近實(shí)際的物流運(yùn)輸行為。為更好求解帶同時(shí)送取貨和時(shí)間窗約束的電動(dòng)汽車選址路徑問題，提出了SAACO算法求解問題。在基礎(chǔ)的SA算法與ACO算法中分別加入回火操作以及高斯變異，擴(kuò)大搜尋更優(yōu)解的能力，在整體與局部方面都提高了算法的性能，避免陷入局部尋優(yōu)。但是，SA算法和ACO算法計(jì)算效率相對較低，比起其他算法所需的求解時(shí)間更長，這也是本文算法的一個(gè)缺陷，后續(xù)將嘗試使用機(jī)器學(xué)習(xí)的方式改進(jìn)算法或者使用更新的算法從而使得效率更高、求解效果更好。除了通過與不同規(guī)模、不同算法對比證明本文算法的優(yōu)越性之外，本文還考慮了針對有送取需求的客戶的兩種不同配送模式，并最終證明與送取分離模式相比，同時(shí)送取貨模式的合理性也更符合物流企業(yè)的實(shí)際需求。

基于同時(shí)送取貨的電動(dòng)車選址路徑問題是物流配送領(lǐng)域未來值得深入研究的方向，在下一步問題的研究中還可以考慮客戶送取貨的不確定性需求以及考慮取得的貨物的裝載方式，根據(jù)配送的約束建立更加貼合實(shí)際的目標(biāo)函數(shù)，從而為物流配送領(lǐng)域提供更好的理論支持。