孟 楠，王 靜

（武漢科技大學(xué) 管理學(xué)院，湖北 武漢 430070）

0 引言

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

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

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

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

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

1 模型構(gòu)建

1.1 問(wèn)題描述

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

1.2 符號(hào)說(shuō)明

為了建立數(shù)學(xué)模型，引入以下符號(hào)，見(jiàn)表1。

表1 符號(hào)一覽表

1.3 基于前景理論的補(bǔ)償費(fèi)用

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

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

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

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

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

以車(chē)輛行駛費(fèi)用、基于前景理論的補(bǔ)償費(fèi)用以及充電費(fèi)用之和最小為目標(biāo)，建立基于前景理論的電動(dòng)汽車(chē)配送路徑優(yōu)化模型，具體如下：

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

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

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

2.1 編碼與種群初始化

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

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

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

（2）qi表示客戶節(jié)點(diǎn)i的配送需求量表示一條染色體中第i位基因?qū)?yīng)的客戶的配送需求量。若滿足則在此染色體第a位基因后插入0；

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

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

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

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

2.2 適應(yīng)度函數(shù)

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

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

遺傳算法的適應(yīng)度函數(shù)是通過(guò)排序來(lái)篩選優(yōu)秀個(gè)體的工具，與上述設(shè)計(jì)的改良目標(biāo)函數(shù)的作用相同，適應(yīng)度函數(shù)的值越大，說(shuō)明此染色體個(gè)體越優(yōu)，因此，適應(yīng)度函數(shù)為：

2.3 遺傳操作

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

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

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

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

3 算例設(shè)計(jì)與分析

3.1 算例介紹

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

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

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

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

表2 各節(jié)點(diǎn)信息

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

通過(guò)本文設(shè)計(jì)的改進(jìn)遺傳算法求得最終的結(jié)果為：

其中data表示某配送中心設(shè)計(jì)的配送方案，由3輛車(chē)負(fù)責(zé)服務(wù)25位客戶，其中包括4個(gè)“0”，每2個(gè)“0”之間為一輛車(chē)的服務(wù)對(duì)象，車(chē)輛1號(hào)、2號(hào)和3號(hào)的子路徑的載重量分別對(duì)應(yīng)表3中的第一行、第二行和第三行。

根據(jù)圖1和表3繪制此算例的配送路線，如圖2所示，其中用點(diǎn)劃線表示的閉環(huán)路線表示車(chē)輛1號(hào)的行動(dòng)軌跡，用圓點(diǎn)表示的閉環(huán)路線表示車(chē)輛2號(hào)的行動(dòng)軌跡，用實(shí)線表示的閉環(huán)路線表示車(chē)輛3號(hào)的行動(dòng)軌跡。

表3 配送方案與載重量

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

圖2 配送路徑

電動(dòng)汽車(chē)的電量補(bǔ)給行為影響著整個(gè)配送方案，需通過(guò)剩余電量進(jìn)一步分析配送路徑的優(yōu)化性，每輛車(chē)的實(shí)時(shí)剩余電量如圖3所示。

圖3 車(chē)輛電量變化圖

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

表4 配送方案其他信息

4 結(jié)語(yǔ)

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

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

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

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

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