溫 廷 新， 李 可 昕， 趙 琳 琳， 栗 業(yè)， 周 甜， 何 燕

( 1.遼寧工程技術(shù)大學(xué) 工商管理學(xué)院， 遼寧 葫蘆島 125105；2.山東工商學(xué)院 管理科學(xué)與工程學(xué)院， 山東 煙臺 264005 )

0 引 言

隨著工業(yè)的迅猛發(fā)展，全球氣候問題日益突出，能源轉(zhuǎn)型戰(zhàn)略深入，低碳、節(jié)能、環(huán)保等方面問題引起廣泛關(guān)注．2021年中國提出構(gòu)建以新能源為主體的新型電力系統(tǒng)．采用電動汽車進行物流配送，成為未來物流發(fā)展的方向和趨勢．電動汽車低能耗、低噪聲，但是因充電時間長及當前充電站短缺，而受到極大約束，如何對電動汽車進行合理調(diào)派成為熱議問題[1-2]．

已有眾多國內(nèi)外學(xué)者對物流配送過程中碳排放的產(chǎn)生展開研究．韓颯[3]根據(jù)車聯(lián)網(wǎng)技術(shù)，提出了一種道路交叉口環(huán)保駕駛汽車路徑優(yōu)化控制模型．唐金環(huán)等[4]針對考慮顧客有限“碳行為”偏好的選址-路徑-庫存聯(lián)合優(yōu)化問題，引入環(huán)保度系數(shù)作為碳排放量的特征向量，構(gòu)建了選址-路徑-庫存系統(tǒng)中考慮有“碳行為”偏好的聯(lián)合優(yōu)化模型．戢守峰等[5]根據(jù)道路類型和行駛狀態(tài)的不同，將限速和擁堵因素嵌入模型的構(gòu)建．Guo等[6]考慮到車輛的負載和驅(qū)動距離，建造了相應(yīng)的碳排放模型并將其設(shè)為優(yōu)化目標．魯建廈等[7]為提高子母穿梭車密集倉儲系統(tǒng)運作效率，對系統(tǒng)的復(fù)合作業(yè)三維路徑規(guī)劃問題進行了研究．

近年來，電動汽車的應(yīng)用使碳排放過高的問題得到部分解決．電動汽車的合理調(diào)派問題已經(jīng)成為諸多學(xué)者正向熱議的話題．郭戈等[8]分析電動汽車的發(fā)展現(xiàn)狀，并從充電優(yōu)化、路徑優(yōu)化及車隊配置優(yōu)化等角度進行了車輛路徑優(yōu)化．鄧友均等[9]為提高電動汽車的配送效率，避免大規(guī)模無序充電的影響，借助群感知技術(shù)，提出了基于實時交通信息感知的充電站充電服務(wù)費計價模型和基于排隊論的充電排隊等候時間估算模型．為進一步求解模型，多數(shù)學(xué)者采用了智能優(yōu)化算法，如結(jié)合分散搜索和改進蟻群算法的混合啟發(fā)式算法[10]、禁忌搜索-改進Clarke-Wright節(jié)省的兩階段啟發(fā)式算法[11]、基于細菌趨化的改進粒子群算法[12]、多階段啟發(fā)式算法MCWIGALNS[13]、自適應(yīng)改進的蟻群算法[14]、變鄰域搜索算法[15]、改進的粒子群算法[16]等．

綜合上述研究，大多數(shù)學(xué)者對電動汽車配送網(wǎng)絡(luò)中設(shè)施選址與配送路徑優(yōu)化方面的問題展開研究，但是罕見學(xué)者考慮充電過程成本和不同溫層貨損的電動汽車多溫共配路徑優(yōu)化問題．鑒于此，本文在滿足生鮮品的新鮮程度、車輛限載及電動汽車電量限制等約束條件下，將電動汽車充電所產(chǎn)生電費及充電時生鮮品貨損成本納入目標函數(shù)，構(gòu)建以帶軟時間窗的路徑優(yōu)化模型為基礎(chǔ)的電動汽車多溫共配路徑優(yōu)化模型，引入K-means聚類，并采用免疫遺傳算法對同一聚類單元進行優(yōu)化．

1 生鮮品運輸路徑優(yōu)化模型建立

1.1 問題描述

本文所研究的問題具體可以描述為某生鮮企業(yè)采用電動汽車進行配送的問題．電動汽車與傳統(tǒng)汽車相比具有節(jié)能減排、降低總體運輸成本、符合當下低碳生活的背景以及政府扶持政策較多等優(yōu)勢，但同時也有很多的不足之處：首先，電動汽車電池成本較高；其次，電動汽車的蓄電池受季節(jié)因素影響較大，隨著溫度的降低，續(xù)航時間將會縮短；最后，電池充電時間較長，在充電時間內(nèi)汽車處于停滯狀態(tài)．

配送采用電動汽車作為主要交通工具，并在車輛上放置處于不同溫層的蓄冷箱，每個蓄冷箱在每日結(jié)束工作后進行蓄冷以保證第二天的使用．配送車輛從配送中心充滿電后出發(fā)為顧客提供配送服務(wù)．每輛車可以為多個顧客提供配送服務(wù)，而每位顧客只能接受一輛車的配送服務(wù)，車輛完成配送服務(wù)后要返回配送中心．每輛車有配送的容量限制，因此其所服務(wù)的顧客的總需求量不得超過車輛的最大載重．每輛車所行駛的最大路程與車輛的蓄電量成正比，文中假設(shè)每個顧客的需求及時間窗已知，時變路網(wǎng)數(shù)據(jù)信息已從交通部門獲取，電動汽車處于低電量時需在顧客點進行快速充電并支付一定的費用．文中所建模型暫不考慮極端天氣和電池損耗等因素影響，并默認電動汽車可在各節(jié)點進行充電并支付相應(yīng)的費用．

1.2 符號及參數(shù)

(1)集合

N表示路網(wǎng)中所有節(jié)點的集合．其中0表示配送中心．

(2)參數(shù)

q、Q分別表示電動汽車最大載重和電動汽車裸車重；v表示電動汽車的行駛速度；Mmax表示電動汽車的最大電池容量；Mijh表示電動汽車h從節(jié)點i到節(jié)點j的耗電量；Mjh表示電動汽車h在節(jié)點j的剩余電量；R表示電動汽車的充電頻率；h表示第h輛電動汽車；H表示電動汽車集合；n表示電動汽車總數(shù)；m表示節(jié)點總數(shù)；F表示單位車輛固定成本；B表示車輛單位運輸成本；d表示節(jié)點之間的距離；P1表示冷凍區(qū)貨物的價格；P2表示冷藏區(qū)貨物的價格；P3表示常溫區(qū)貨物的價格；w1表示運輸過程中冷凍區(qū)單位貨損比例；w2表示服務(wù)顧客過程中冷凍區(qū)單位貨損比例；w3表示充電過程中冷凍區(qū)單位貨損比例；z1表示運輸過程中冷藏區(qū)單位貨損比例；z2表示服務(wù)顧客過程中冷藏區(qū)單位貨損比例；z3表示充電過程中冷藏區(qū)單位貨損比例；tij表示配送車輛從節(jié)點i到節(jié)點j的時間；tj1表示車輛為顧客j服務(wù)時冷凍區(qū)所產(chǎn)生的時間；tj2表示車輛為顧客j服務(wù)時冷藏區(qū)所產(chǎn)生的時間；rj表示在顧客j處充電時間；α、β分別表示時間窗的機會成本和懲罰成本；S表示配送車輛到達時間；(L，T)表示顧客的配送時間窗；U表示損失的冷量；E表示單位冷量需要的電量；P4表示單位電量所需的電價；a1表示在運輸過程中冷凍區(qū)冷量損失；a2表示在運輸過程中冷藏區(qū)冷量損失；b1表示在服務(wù)顧客時冷凍區(qū)冷量損失；b2表示在服務(wù)顧客時冷藏區(qū)冷量損失；k表示充電每小時所需的電費；e1表示每個顧客在冷凍區(qū)需求；e2表示每個顧客在冷藏區(qū)需求；e3表示每個顧客在常溫區(qū)需求．

(3)決策變量

xijh表示車輛h在道路(i，j)路段行駛時為1，否則為0；yjh表示車輛h為顧客j服務(wù)時為1，否則為0；zjh表示車輛h在顧客j處充電時為1，否則為0．

1.3 相關(guān)因素分析

1.3.1 耗電性能及充電需求分析 電動汽車的耗電量不僅與車輛的自身屬性有關(guān)，還與車輛的實際行駛距離和速度有關(guān)，因此，實際最大載重q的電動汽車h以速度v行駛，運行功率為

(1)

式中：g為重力加速度；η為傳動系統(tǒng)機械效率；ε、Cd、A分別表示汽車滾動阻力系數(shù)、空氣阻力系數(shù)和汽車迎風面積．

電動汽車在運輸?shù)缆飞舷牡碾娏繛?/p>

Mijh=P(qh，vij)tij

(2)

在電動汽車的剩余電量不足以滿足配送下一位顧客時，需要在配送途中進行快速充電，電動汽車在充電站充電的時間為

(3)

1.3.2 時變路網(wǎng)分析 在時變路網(wǎng)的交通下，不同時間段內(nèi)電動汽車的行駛速度不同，行駛速度的不同導(dǎo)致在相同路程下的配送時間難以計算，全天各時間段行駛速度函數(shù)為

(4)

1.4 模型建立

1.4.1 配送成本計算

(1)配送車輛的固定成本C1

在生鮮品的冷鏈物流配送過程中，配送車輛將會產(chǎn)生一定的固定成本，包括電動汽車電池的折舊成本、蓄冷箱的購買及損耗成本、車輛的折舊費、車輛派遣費、司機的駕駛費、裝卸工人的工資等．

C1=nF

(5)

(2)配送車輛的運輸成本C2

車輛的運輸成本，即車輛在物流配送過程中從一位顧客到下一位顧客途中所產(chǎn)生的費用．所產(chǎn)生的費用與車輛行駛的距離成正比．

(6)

(3)配送車輛在運輸過程中所產(chǎn)生的貨損成本C3

配送車輛在運輸過程中會產(chǎn)生三部分的貨損．第一部分是在車輛正常行駛過程中產(chǎn)生的貨損；第二部分是配送車輛在服務(wù)顧客時，打開冷凍箱車門導(dǎo)致溫度驟然升高使生鮮品的新鮮程度降低產(chǎn)生的貨損；第三部分是電動汽車在其電量不滿足到下一位顧客所需電量時要進行充電，在車輛充電過程中會造成生鮮品產(chǎn)生一定的貨損．

(7)

(4)配送時間窗的機會成本及懲罰成本C4

配送車輛要在一定的時間范圍內(nèi)進行配送，以保證生鮮品的質(zhì)量，在時間窗之前到達會產(chǎn)生部分機會成本，而在時間窗之后到達會產(chǎn)生部分懲罰成本．

(8)

(5)配送車輛的制冷成本C5

配送車輛的蓄冷儲存部分相當于一個大型的蓄冷箱，由大塊的蓄冷板制造而成，并采用充電的方式進行蓄冷．蓄冷箱在運輸過程中損失多少冷量，就相當于蓄冷箱在之前要儲存多少冷量，而蓄冷需要消耗很多電，所謂的制冷成本也就是蓄冷箱蓄冷時所耗的電量．

C5=UEP4

(9)

(10)

(6)配送車輛的充電費用C6

配送車輛的剩余電量無法滿足服務(wù)下一位顧客時，需要在運輸途中采用快速充電模式進行充電，所耗的電費與充電時間成正比．

C6=rk

(11)

1.4.2 目標函數(shù)建立 建立目標函數(shù)如下：

minC=C1+C2+C3+C4+C5+C6

(12)

約束如下：

(13)

(14)

Lj≤Sj≤Tj； ?j∈N

(15)

M0≤Mih≤Mmax； ?i∈N

(16)

xijh∈{0，1}； ?i，j∈N，h∈H

(17)

yjh∈{0，1}； ?j∈N，h∈H

(18)

zjh∈{0，1}； ?j∈N，h∈H

(19)

其中，式(13)表示每位顧客只接受一輛車服務(wù)；式(14)表示配送車輛的載重不得超過車輛的最大載重；式(15)表示顧客只接受在一定時間段內(nèi)進行配送；式(16)表示電動汽車在每個節(jié)點的電量約束；式(17)～(19)為決策變量．

2 算法及求解過程

2.1 聚類過程

K-means聚類是最經(jīng)典、應(yīng)用最廣泛的聚類分析方法，其目標是使類內(nèi)距離盡可能最小，類間距離盡可能最大．本文采用K-means聚類對“充電站及顧客節(jié)點”進行聚類，聚類數(shù)目為承擔配送任務(wù)的電動汽車數(shù)目．由于本文內(nèi)充電站及顧客節(jié)點均為坐標值，各屬性間的量化標準相同，無須考慮加權(quán)問題．成本函數(shù)表示為類內(nèi)距離平方和與類間距離平方和之比．

(20)

式中：D表示待聚類對象的集合；Kji表示對象j第i維的值；cl表示離對象j最近的類中心；cli表示cl第i維的值；θlj表示對象j是否屬于類l，是為1，否則為0．

傳統(tǒng)K-means聚類算法對初始聚類中心選取是隨機的，如果選取不當會影響其迭代次數(shù)．因此本文采用密度網(wǎng)格的方式選取聚類中心[17]，改進后的K-means聚類算法流程如下(見圖1)：

圖1 聚類流程圖

Step 1聚類數(shù)目初始化n=γ(γ=min{車輛數(shù)，未完成訂單數(shù)})．

Step 2初始化n個聚類中心．

Step 2.2在維度i上，在取值范圍內(nèi)f平分，得到f4個網(wǎng)格．

Step 2.3計算每個網(wǎng)格中數(shù)據(jù)點的個數(shù)，并將網(wǎng)格按數(shù)據(jù)點個數(shù)從大到小排列．

Step 2.4取排序在前的n個網(wǎng)格，將點數(shù)記為δ1，δ2，…，δn，如果δn=0，則f=int(f/2)，重復(fù)Step 2.2～Step 2.4；否則從網(wǎng)格中任取一點為代表點，則這n個代表點為初始中心．

Step 3計算各節(jié)點到類中心距離，將每個對象賦予其最近的類．

Step 5計算目標函數(shù)值，更新各類的中心．

Step 6重復(fù)Step 3～Step 5，連續(xù)兩次目標函數(shù)值相同，則輸出．

根據(jù)對各節(jié)點的聚類分析，可以得出完成訂單所需的車輛數(shù)、每輛車所需服務(wù)的顧客及電動汽車所需的充電站．

2.2 算法設(shè)計

按照上文中的聚類方法，可以直接得出車輛與顧客及電動汽車充電站的直接配送關(guān)系，之后為每輛車尋找最優(yōu)的配送方案．本文采用免疫遺傳算法對車輛的最優(yōu)配送方案進行優(yōu)化．

(1)抗原侵入及抗體編碼：抗原侵入即目標函數(shù)及約束條件導(dǎo)入．在算法的運行過程中，不能對空間數(shù)據(jù)進行處理，需要對其進行編碼處理．本文采用自然數(shù)編碼方法，形成抗體編碼．對m個顧客節(jié)點進行編碼，抗體長度為π．

例：(i)π=4，抗體為(4，2，1，3)，表示從配送中心0出發(fā)，路線為0-4-2-1-3-0，回到配送中心．

(ii)π=5，抗體為(3，1，5，2，4)，表示從配送中心0出發(fā)，路線為0-3-1-5-2-4-0，最后回到配送中心．

(iii)π=7，抗體為(6，2，4，1，5，3，7)，表示從配送中心0出發(fā)，路線為0-6-2-4-1-5-3-7-0，最后回到配送中心．

(2)初始抗體產(chǎn)生：隨機產(chǎn)生初始抗體，并當記憶系統(tǒng)存在時從中產(chǎn)生初始群體．

(3)對所有抗體進行評估，用適應(yīng)度函數(shù)逐個評價，形成父代群體．

(4)父代抗體在一定概率下進行交叉變異，以得到新的抗體群體．

(i)交叉：采用OX交叉操作．

例如：父代個體A為123/456/789，B為987/654/321；將中間段作為交配區(qū)，將A、B的交配區(qū)進行交叉．A′為123/654/789，B′為987/456/321．

交叉操作在算法中起重要作用，交叉操作可以形成新的種群，并不斷地保持種群個體的多樣性．

(ii)變異：按照一定的概率進行突變，在父代染色體按突變概率進行突變，然后重新進行適應(yīng)度評估，變異成功的會產(chǎn)生新的基因串加入新的子代中；變異失敗的就會被淘汰．

(5)是否滿足約束條件，若滿足條件則輸出，若不滿足則重新進行迭代．

算法流程圖如圖2所示．

3 實驗仿真

3.1 求解參數(shù)及環(huán)境

本文采用MATLAB進行編碼，為了研究方便，本文假設(shè)70×70的網(wǎng)格為配送節(jié)點網(wǎng)格．汽車的行駛時間按行駛路程與行駛速度之比進行計算，本文電動汽車行駛速度為45 km/h．本文求解參數(shù)中，重力加速度g為9.81 m/s2，傳動系統(tǒng)機械效率η為1.46，汽車滾動阻力系數(shù)ε為0.015，空氣阻力系數(shù)Cd為0.6，汽車迎風面積A為6 m2，電動汽車充電頻率R為4.5 kWh/min，電動汽車最大電池容量Mmax為200 kWh．車輛最大載重4.5 t，裸車2 t，電動汽車內(nèi)部：冷凍區(qū)溫度保持在-18～-20 ℃；冷藏區(qū)溫度保持在-3～-5 ℃(文中限定常溫為20 ℃)．本文中種群設(shè)定為100，最大進化代數(shù)為200，交叉概率為0.9，變異概率為0.1．

3.2 算例驗證

以某生鮮品電商企業(yè)為例(本文數(shù)據(jù)從網(wǎng)站http://neumann.hec.ca/chairedistributique/data/獲取)，要為20位顧客配送其所需要的貨物，配送中心及顧客節(jié)點的位置見表1，編號1～20代表顧客節(jié)點，編號0為物流配送中心，文中假設(shè)配送車輛可以在配送中心及顧客節(jié)點處充電(需向顧客支付一定費用)，車輛總數(shù)為4輛，設(shè)定配送車輛工作時間為6：00，每30 min為一個時間段，根據(jù)城市交通規(guī)律，7：00～9：00為交通擁堵時間(車速為30 km/h)．車輛的正常行駛速度為45 km/h，在滿足車輛不超載的約束條件下，合理安排路線．在運輸途中，保證所運輸?shù)呢浳锊淮叮?/p>

表1 坐標節(jié)點

每位顧客在不同溫層的需求量及裝卸時間見表2．車輛的固定成本F=100元/車，單位運輸成本B=2.5元/km；冷凍區(qū)生鮮品貨物單價P1=50元/t；冷藏區(qū)生鮮品貨物單價P2=100元/t；常溫區(qū)生鮮品貨物單價P3=80元/t；運輸過程及充電時冷凍區(qū)單位貨損比例w1=w3=0.001 5；在開關(guān)門服務(wù)顧客時冷凍區(qū)單位貨損比例w2=0.025；運輸過程及充電時冷藏區(qū)單位貨損比例z1=z3=0.001；在開關(guān)門服務(wù)顧客時冷藏區(qū)單位貨損比例z2=0.002；根據(jù)現(xiàn)實條件時間窗的機會成本α=0，懲罰成本β=4元/h；運輸過程中冷凍區(qū)冷量損失a1=0.002；服務(wù)顧客時冷凍區(qū)冷量損失b1=0.003；運輸過程中冷藏區(qū)冷量損失a2=0.001 5；服務(wù)顧客時冷藏區(qū)冷量損失b2=0.002 5；蓄冷箱儲存單位冷量所需電量E=2；單位電量所需的電價P4=3元；充電每小時電費k=1.5元．

表2 顧客的需求量及裝卸時間

通過程序進行實證分析，借助MATLAB軟件進行優(yōu)化．經(jīng)過MATLAB迭代得出模型的最優(yōu)配送路線，見圖3和表3．最終求出模型的最優(yōu)成本為1 651.45元．

表3 車輛路徑優(yōu)化結(jié)果

3.2.1 對比實驗1 為驗證電動汽車多溫共配改進方案是否合理有效，將電動汽車和普通燃油汽車的常規(guī)運輸方式與多溫共配運輸方式進行比較分析，比較結(jié)果如表4所示．

根據(jù)表4的實驗結(jié)果可知，首先針對常規(guī)運輸方式進行比較，采用電動汽車進行運輸其運輸成本與燃油汽車運輸成本的1/4相當，極大程度地降低了運輸成本，與此同時采用電動汽車更加環(huán)保，無碳排放的產(chǎn)生．其次，針對電動汽車的不同運輸方式進行比較，采用多溫共配的運輸方式，其運輸?shù)目偝杀窘朴诔Ｒ?guī)運輸方式的1/3．由以上結(jié)果分析可知，以電動汽車為主要運輸工具并采取多溫共配的運輸方式，既可以極大程度地降低運輸成本，又可以節(jié)能減排，是一種非常合理有效的運輸方式．

表4 電動汽車與燃油汽車運輸方案對比

3.2.2 對比實驗2 為驗證免疫遺傳算法的求解性能，分別采用遺傳算法、免疫遺傳算法、粒子群算法和模擬退火算法對文中的電動汽車多溫共配路徑優(yōu)化模型進行求解，并比較其求解情況，如表5所示．

表5 算法結(jié)果對比

根據(jù)表5的實驗結(jié)果可知：遺傳算法經(jīng)過100次迭代完成算法收斂，免疫遺傳算法和粒子群算法分別經(jīng)過140次迭代和180次迭代完成算法收斂，雖然遺傳算法的收斂速度比免疫遺傳算法的收斂速度快，但是從配送成本上看，遺傳算法的結(jié)果略高于免疫遺傳算法和粒子群算法的結(jié)果；粒子群算法與模擬退火算法分別經(jīng)過180次迭代和160次迭代完成算法收斂，可見免疫遺傳算法的收斂速度高于粒子群算法和模擬退火算法的收斂速度．采用免疫遺傳算法既可以避免遺傳算法局部搜索能力差的缺點，還具有相對于粒子群算法和模擬退火算法較高的收斂速度．

4 結(jié) 論

(1)本文針對不同溫層生鮮品運輸問題，提出了以電動汽車為主要運輸工具的多溫共配運輸方式，充分考慮了時變路網(wǎng)及耗電性能與充電需求等實際情況，合理安排出發(fā)時間和路線，從而降低運輸成本，合理避免車輛擁堵．

(2)本文所采用的電動汽車多溫共配的運輸方式是傳統(tǒng)車輛路徑優(yōu)化的拓展類型，經(jīng)過多種對比分析，從運輸工具及運輸方式上看，電動汽車多溫共配是一種既節(jié)能減排又節(jié)約成本的運輸方式．

(3)為了提高算法的求解性能，本文采用免疫遺傳算法對電動汽車多溫共配路徑優(yōu)化模型進行求解．根據(jù)實證分析，免疫遺傳算法可以有效地避免出現(xiàn)局部搜索能力較差的現(xiàn)象，能夠快速地收斂得到求解結(jié)果，是求解電動汽車多溫共配路徑優(yōu)化問題的一種有效算法．

(4)當前研究未考慮時變路網(wǎng)下電動汽車電池消耗、極端天氣狀況等問題，今后將進一步展開相關(guān)研究．