孟 楠，王 靜

（武漢科技大學 管理學院，湖北 武漢 430070）

0 引言

2022年1月18日國務院發(fā)文倡導推廣新能源交通運輸工具，強調(diào)在城市物流配送中電動汽車的使用比例不得低于80%。由此可見，燃油汽車電動化正在加速影響綠色物流中的“最后一公里”環(huán)節(jié)。但是，電動汽車在符合低碳運輸和環(huán)境友好發(fā)展要求的同時，也存在“充電焦慮”和“續(xù)航差”等問題，因此探討其配送路徑優(yōu)化問題具有深刻意義。

近年來，不少學者對帶時間窗的物流配送路徑優(yōu)化問題進行了研究。文獻[1]為了避免提前配送和延遲配送問題，設計了關(guān)于軟時間窗的懲罰成本并納入目標函數(shù)，但其懲罰系數(shù)為自定義參數(shù)。文獻[2]以硬時間窗設計為約束，使貨物送達時間既不得早于訂單的生成時間，也不能晚于客戶允許的最晚服務時間，并且通過綜合考慮硬時間窗和合單配送的滾動時與延遲配送算法求解了生鮮即時域送問題。文獻[3]針對混合時間窗設計了客戶滿意度評價函數(shù)，構(gòu)建了客戶平均滿意度最大化和空載行駛里程最小化的混合整數(shù)規(guī)劃模型。

許多學者針對電動汽車的充電管理展開了大量研究。文獻[4]設計了基于混合柔性充電策略的帶時間窗的電動汽車車輛路徑優(yōu)化數(shù)學模型，通過基于充電站啟發(fā)式插入的蟻群算法證實其能夠降低總體成本。文獻[5]針對考慮貨損的生鮮實例建立了成本最低的數(shù)學模型，得出邊充邊卸模式能夠降低物流配送成本。文獻[6]基于人群感覺設計了電動汽車的充電戰(zhàn)略模型。文獻[7]根據(jù)“峰谷電網(wǎng)”設計電動汽車的充放電管理，得到了兼顧客滿意度最高和配送成本最低的方案。

通過分析上述文獻可以發(fā)現(xiàn)，目前相關(guān)研究多從客觀因素進行分析，但人是有限理性的，對于配送方案的決策需要考慮客戶心理，因此越來越多的學者從主觀心理角度出發(fā)進行深入研究，其中一個重要分支為“前景理論”。文獻[8]基于“滴滴”交通數(shù)據(jù)集和累計前景理論來量化不同決策者的充電行為。文獻[9]通過貝葉斯理論和累積前景理論建立了用戶在活動鏈上的轉(zhuǎn)移關(guān)系和充電需求模型，結(jié)合動態(tài)交通網(wǎng)絡和實例驗證了其有效性。文獻[10]利用改進的前景理論決策方法，建立直覺模糊評價矩陣，解決了集中電動汽車充電中心的選址問題。

通過學者們的研究可知，基于前景理論的價值函數(shù)可以量化用戶的出行選擇概率模型、電動汽車的充電選擇概率、改進的最優(yōu)準測權(quán)重，本文將前景理論納入電動汽車路徑優(yōu)化中，基于前景理論的價值函數(shù)量化了客戶對電量補給的行為感知。

1 模型構(gòu)建

1.1 問題描述

某一配送中心服務于具有特定時間窗和需求量的客戶群，并使用同種類型的電動汽車進行訂單不拆分配送作業(yè)，每輛電動汽車的最大裝載量、最大額定電池容量和最長行駛時間相同。車輛從配送中心出發(fā)時為滿電狀態(tài)，按平均速度勻速行駛，假設電量的消耗與行駛路程是線性相關(guān)的，并且在客戶點停留時不消耗任何電量。當電動汽車的電量不足以到達下一客戶點或者返回配送中心時，需訪問周圍可到達的充電站補充電量，離開時為滿電狀態(tài)，完成任務返回配送中心后不再出車。電動汽車由于電量補給而未在時間窗內(nèi)將貨物送達客戶手中時，需要根據(jù)前景理論支付補償費用。并且，一輛電動汽車可服務于多個客戶，但是每一個客戶能且只能被一輛車服務。

1.2 符號說明

為了建立數(shù)學模型，引入以下符號，見表1。

表1 符號一覽表

1.3 基于前景理論的補償費用

物流配送服務商的核心競爭力之一就是能確保在客戶要求的某一時間段內(nèi)將貨物送達。然而整個配送環(huán)節(jié)中的不確定性風險較多，某些配送中心選擇使用純電動汽車作為基礎設施，其電能補給行為可能會導致延遲配送的情況。這種超出時間窗收貨的焦慮感和不滿感直接影響客戶對配送商的評價以及忠誠感，這種行為與感受與前景理論的刻畫是相符的。因此根據(jù)前景理論的價值函數(shù)和客戶的特定時間窗，向客戶提供補償費用，以彌補失誤且維護后期合作關(guān)系。前景理論中客戶點i的價值函數(shù)可表示為：

其中αi、γi、λi為參數(shù)，i=1,2,...,c，0＜αi＜1，0＜λi＜1，損失厭惡系數(shù)γi＞1表示決策者對損失是厭惡的。

前景理論表示，在決策選擇的初始階段，需要選擇一個適當?shù)膮⒄拯c，此時價值為0，據(jù)此衡量與參照點之間的差距，從而得到結(jié)果是虧損還是盈利。本文選擇時間窗為現(xiàn)狀，即為參照點，用Oi來表示現(xiàn)值與參照點之間的偏差；用表示車輛到達客戶點的時間。根據(jù)前景理論的價值函數(shù)可知，當時，客戶會感到滿足；反之當時，客戶會感知到損失，需支付給客戶補償費用。本文的總目標為成本最低,基于價值函數(shù)的補償函數(shù)可表示為：

其中，式（3）表示偏差的量化方法，可具體解釋為：如果電動汽車到達客戶點時的時間超過了客戶的最遲收貨時間，那么取二者之間的差作為偏差值；如果在時間窗內(nèi)送達或者早于時間窗送達，那么偏差取0。

1.4 建立數(shù)學模型

以車輛行駛費用、基于前景理論的補償費用以及充電費用之和最小為目標，建立基于前景理論的電動汽車配送路徑優(yōu)化模型，具體如下：

具體解釋如下：式（5）保證每個客戶被服務且僅被服務一次；式（6）保證流量的平衡；式（7）保證一輛車只使用一次；式（8）保證派出的電動汽車不超過總車輛數(shù)；式（9）保證配送中心既是起點也是終點；式（10）-（11）保證各個顧客的配送需求量、車輛配送任務不超過電動汽車的最大額定載重量；式（12）表示在客戶點停留時間內(nèi)不消耗任何電量；式（13）保證電動汽車在配送網(wǎng)絡中滿足最大額定電量的限制；式（14）保證電動汽車從充電站或者配送中心出發(fā)時為滿電狀態(tài)；式（15）保證到達下一節(jié)點j的時間與離開上一節(jié)點i時間和行駛時間有關(guān)；式（16）保證離開節(jié)點i的時間只與到達時間和服務時間有關(guān)；式（17）表示如果在客戶點i的開始服務時間在時間窗內(nèi)，超時服務時間為0，晚于最晚到達時間需要支付補償費用。

2 算法設計

本文構(gòu)建的單配送中心多客戶路徑優(yōu)化模型是非線性規(guī)劃模型，屬于NP-hard問題。運籌學中某些精確算法對于小規(guī)模問題能夠求得最優(yōu)解，隨著數(shù)據(jù)規(guī)模變大會出現(xiàn)“組合爆炸”的問題，而啟發(fā)式算法因其穩(wěn)定性和較快的收斂性能夠得到近似最優(yōu)結(jié)果，因此本文采用遺傳算法進行求解。

2.1 編碼與種群初始化

遺傳算法中將所有節(jié)點視為基因，本文通過自然數(shù)編碼構(gòu)成染色體，其長度為c+f+g+1。配送中心的編碼為0；編碼1，2，3，…，c代表各個客戶點被分配的自然數(shù)序號；c+1，c+2，c+3，…，c+f代表各充電站被分配的自然數(shù)序號。

種群是由一定數(shù)量的染色體構(gòu)成的，本文根據(jù)載重量約束構(gòu)造初始種群，需遵循以下步驟：

（1）隨機排列包括充電站的所有節(jié)點；

（2）qi表示客戶節(jié)點i的配送需求量表示一條染色體中第i位基因?qū)目蛻舻呐渌托枨罅?。若滿足則在此染色體第a位基因后插入0；

（3）根據(jù)上述規(guī)則重復多次計算，直至處理完所有客戶點的需求量約束；

（4）將染色體的開頭和結(jié)尾各補1個0，形成一條完整的初始染色體。

（5）重復上述操作構(gòu)造種群數(shù)量為N的初始種群。

比如某一配送中心某一天共有3輛電動汽車服務于8個客戶點，在配送區(qū)域中共有2個充電站。假設經(jīng)過編碼后形成的一條染色體為：0，3，6，9，2，0，1，7，0，4，10，5，8，0，由于每輛電動汽車都是從配送中心出發(fā)，最終又回到配送中心，所以在“0”處進行分割，得出了三條路線，具體解讀如下：第一輛車依次服務于客戶點3，6，2，并且在離開客戶點6后先駛往充電站9，之后再服務客戶2；第二輛車依次服務于客戶1，7；第三輛車服務于客戶4，5，8，并且在離開客戶點4后先駛往充電站10，之后再服務客戶8。

2.2 適應度函數(shù)

由于在形成初始染色體時沒有考慮電動汽車的電量約束，因此通過設計懲罰函數(shù)的方法使其結(jié)果符合電量要求，從而達到保證電動汽車電量補給行為的同時進一步檢驗載重量約束的目的。根據(jù)目標函數(shù)的設計以及研究的問題，需要用懲罰函數(shù)的形式來表示電動汽車的電量和載重量限制，從而得到以下改良目標函數(shù)：

其中，M1、M2分別為極大的正數(shù)。在一條染色體上，某一輛車的載重量或者電量約束不符合條件時，改良目標函數(shù)值會非常大，表明此染色體表示的配送路徑方案是不可行的。

遺傳算法的適應度函數(shù)是通過排序來篩選優(yōu)秀個體的工具，與上述設計的改良目標函數(shù)的作用相同，適應度函數(shù)的值越大，說明此染色體個體越優(yōu)，因此，適應度函數(shù)為：

2.3 遺傳操作

2.3.1 選擇復制。本文沒有采用選擇算子，而是選擇一定比例的個體。首先，采用傳統(tǒng)的輪盤賭法計算每個個體的選擇概率并且進行降序排列；其次，選擇偶數(shù)位的前1/3的染色體進行保留，以便后續(xù)的交叉操作；最后，構(gòu)成新的種群。

2.3.2 交叉操作。傳統(tǒng)的交叉方法的尋優(yōu)能力有限，因此需改進后再運用。首先，對種群中的偶數(shù)位個體A、B隨機選取一段由0開始且由0結(jié)束的路徑1、2，并且分別移動到染色體的頭部，構(gòu)成新的父代A、B；其次，分別將上述子路徑1作為子代染色體C的頭部，將新形成的父代B中非子路徑1的元素按照順序依次加到C中，并且在尾部補足0，按照上述方法形成子代D；最后，在子路徑1、2后的位置中按照適應度值最高原則插入一個0，構(gòu)成最終的子代。

2.3.3 變異操作。采用2-opt算法對交叉后的個體進行變異，即隨機數(shù)小于變異概率時，隨機選擇個體兩個不同位置的基因進行對調(diào)。

2.3.4 終止條件。上述流程循環(huán)次數(shù)達到最大迭代次數(shù)時得到最終結(jié)果。

3 算例設計與分析

3.1 算例介紹

某小型物流配送中心共有三輛同型號的電動汽車，為25位客戶提供配送服務。本文的算例來自于Solomon設計的帶時間窗的車輛路徑標準數(shù)據(jù)庫，采用擁有25個客戶的R101算例。分別將其時間窗、需求量和服務時間進行等比例縮小，且生成2個與客戶分散程度相匹配的充電站，得到更符合小型配送中心實際情況的初始數(shù)據(jù)。各個節(jié)點的具體參數(shù)見表2，其中編號0為配送中心，編號1-25為客戶點，編號26-27為充電站。電動汽車的額定載重量Q為12t，最大額定電量為100kW·h。電動汽車進入充電站后達到滿電狀態(tài)，耗時0.4h，單次花費40元；電動汽車從配送中心出發(fā)的時間為0h，且在配送過程中的行駛速度恒定為30km/h。電動汽車的行駛成本為1元/km，每單位時間消耗的電量為22kW·h，補償金額系數(shù)為2.25，超時厭惡系數(shù)為0.88。

本文采用python3.9對上述算例進行求解，運行環(huán)境為64位的Windows 10家庭版操作系統(tǒng)，運行內(nèi)存為8GB，CPU頻率為2.38GHz。種群大小為200，最大迭代次數(shù)為2 000，變異概率為0.08。

根據(jù)表2的第二列和第三列繪制各節(jié)點的位置分布，如圖1所示，其中“”表示客戶的坐標所在；“”表示配送中心的坐標所在；“”表示充電站的坐標所在。

圖1 各節(jié)點位置分布圖

表2 各節(jié)點信息

3.2 算例結(jié)果與分析

通過本文設計的改進遺傳算法求得最終的結(jié)果為：

其中data表示某配送中心設計的配送方案，由3輛車負責服務25位客戶，其中包括4個“0”，每2個“0”之間為一輛車的服務對象，車輛1號、2號和3號的子路徑的載重量分別對應表3中的第一行、第二行和第三行。

根據(jù)圖1和表3繪制此算例的配送路線，如圖2所示，其中用點劃線表示的閉環(huán)路線表示車輛1號的行動軌跡，用圓點表示的閉環(huán)路線表示車輛2號的行動軌跡，用實線表示的閉環(huán)路線表示車輛3號的行動軌跡。

表3 配送方案與載重量

由表3和圖2可以發(fā)現(xiàn)，車輛1號到3號的裝載率分別為87.50%、89.17%、100%。未充電的車輛1號和2號的裝載量相似，幾乎達到整車配送要求，進行了兩次充電的車輛3號為整車配送，以較高滿意度完成配送任務的同時降低了成本。

圖2 配送路徑

電動汽車的電量補給行為影響著整個配送方案，需通過剩余電量進一步分析配送路徑的優(yōu)化性，每輛車的實時剩余電量如圖3所示。

圖3 車輛電量變化圖

由表4可知，車輛1號和2號回到配送中心時剩余電量較少且沒有充電，較大限度的利用電量資源進行配送。由圖3可知，車輛3號在剩余38.274kW·h電量時到編號為26的充電站進行第一次充電，后續(xù)以滿電狀態(tài)再次出發(fā)，在消耗了71.544kW·h后到達編號為27的充電站進行第二次充電，最終回到配送中心時留有近似一半的電量。雖然剩余電量較多，但由于其充電成本遠小于整車配送的成本節(jié)約，因此具有優(yōu)越性。此外，物流配送商的運營環(huán)境中充滿不確定性，可能還會出現(xiàn)一些偶然意外事件或者臨時性需求，存有一定安全電量的車輛3號可以根據(jù)一定的路線規(guī)劃和運量規(guī)劃執(zhí)行緊急性任務，從而提高整個配送系統(tǒng)的靈活性和響應性。

表4 配送方案其他信息

4 結(jié)語

本文以純電動汽車為研究重點，因客戶會因電動汽車的充電耽誤配送時效而產(chǎn)生一定的不滿情緒，從而需要付出一定的補償費用，以提高顧客滿意度和穩(wěn)固合作關(guān)系，建立了成本最低的配送路徑優(yōu)化模型，突破傳統(tǒng)的衡量顧客對時間緊迫性的度量，通過改進的遺傳算法對處理后的Solomon-R101算例進行求解，得到優(yōu)化的配送方案，使方案更加貼合人性中的非理性部分和現(xiàn)實。

但由于筆者的能力有限，此研究還具有一定的局限性：

（1）本文為單配送中心的配送問題，但現(xiàn)實中多為多配送中心的路徑優(yōu)化。

（2）本文假定電量的消耗是線性消耗，但其與載重量、坡度、時變角度、風速等因素密切相關(guān)。

（3）隨著“綠色產(chǎn)業(yè)、良性發(fā)展”的深入推進，電動汽車的充電行為越來越復雜。