陳其賽，倪 靜

（上海理工大學 管理學院，上海 200093）

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

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

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

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

1 模 型

1.1 問題描述

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

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

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

1.2 符號與決策變量

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

1.3 模型

建立數(shù)學模型：

約束條件：

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

2 算法設計

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

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

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

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

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

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

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

式中：τi(gen+1)為第gen+1代第i個螞蟻對應信息素；ρ為信息素揮發(fā)因子；τi(gen)為第gen代第i個螞蟻對應信息素。

信息素增強的公式為

式中：Δτi(gen+1)為第gen+1代第i個螞蟻的信息素增量；Qx為信息素增強因子；yi為第i個螞蟻對應的目標函數(shù)值。

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

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

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

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

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

3.1 參數(shù)設置

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

3.2 算法驗證

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

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

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

表1 30個客戶求解結果Tab.1 Solution results of 30 clients

3.3 混合算法有效性分析

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

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

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

3.4 算法運行時間分析

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

表3 算法運行時間對比Tab.3 Comparison of algorithm running time

3.5 送取貨模式分析

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

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

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

4 結束語

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

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