孟 楠,王 靜
(武漢科技大學(xué) 管理學(xué)院,湖北 武漢 430070)
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ǔ)給的行為感知。
某一配送中心服務(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ù)。
為了建立數(shù)學(xué)模型,引入以下符號(hào),見(jiàn)表1。
表1 符號(hào)一覽表
物流配送服務(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。
以車(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)用。
本文構(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)行求解。
遺傳算法中將所有節(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。
由于在形成初始染色體時(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.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é)果。
某小型物流配送中心共有三輛同型號(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)信息
通過(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 配送方案其他信息
本文以純電動(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ù)雜。