生鮮電商配送的開放式時變車輛路徑問題研究

付朝暉，劉長石

1.長沙民政職業(yè)技術(shù)學(xué)院 軟件學(xué)院，長沙410004

2.湖南工商大學(xué) 工商管理學(xué)院，長沙410205

生鮮電商已經(jīng)成為我國農(nóng)產(chǎn)品上行的主要渠道之一，根據(jù)中商產(chǎn)業(yè)研究院的數(shù)據(jù)，2019年我國生鮮電商行業(yè)的市場交易規(guī)模約為3 225 億元，較上年同期增長49.4%，大有可為。但是，由于生鮮農(nóng)產(chǎn)品具有易腐易損性，生鮮電商客戶具有單次購買量小、購買頻次高且具有服務(wù)時間窗等特點，使得生鮮電商的物流配送成本高昂。物流配送已成為生鮮農(nóng)產(chǎn)品“最后一公里”的關(guān)鍵環(huán)節(jié)，解決生鮮電商的配送問題，有利于提高生鮮電商核心競爭力，促進(jìn)生鮮農(nóng)產(chǎn)品銷售、農(nóng)民增收與農(nóng)村發(fā)展。

解決生鮮電商配送問題的關(guān)鍵是科學(xué)規(guī)劃配送車輛的行駛路線，即求解生鮮農(nóng)產(chǎn)品配送的車輛路徑問題（Vehicle Routing Problem，VRP）。由于生鮮農(nóng)產(chǎn)品主要采用普通車輛配送，大部分學(xué)者研究常溫條件下生鮮農(nóng)產(chǎn)品配送的VRP。文獻(xiàn)[1]針對新鮮蔬菜配送問題，以總配送成本最小為目標(biāo)構(gòu)建帶時間窗車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW）優(yōu)化模型，設(shè)計一種啟發(fā)式算法求解。文獻(xiàn)[2]針對生鮮農(nóng)產(chǎn)品市場需求的時變性與模糊不確定性特點，構(gòu)建生鮮農(nóng)產(chǎn)品“多供應(yīng)點選擇”與“最早分發(fā)”為優(yōu)化目標(biāo)的VRP模型。文獻(xiàn)[3]針對生鮮農(nóng)產(chǎn)品配送時效性強(qiáng)的特點引入生鮮農(nóng)產(chǎn)品生鮮度損耗系數(shù)，以總配送成本最小和顧客滿意度最大為目標(biāo)建立多目標(biāo)VRP模型。文獻(xiàn)[4]考慮B2C 環(huán)境下顧客需求特點，以總配送成本最小和顧客滿意度最大為目標(biāo)構(gòu)建VRP 模型。以上文獻(xiàn)具有一定參考價值。經(jīng)過長期的生鮮農(nóng)產(chǎn)品物流實踐，業(yè)界與學(xué)者們認(rèn)為冷鏈物流能有效提高生鮮農(nóng)產(chǎn)品配送質(zhì)量。文獻(xiàn)[5]根據(jù)生鮮農(nóng)產(chǎn)品冷鏈配送特性，以總成本最小為目標(biāo)構(gòu)建生鮮農(nóng)產(chǎn)品冷鏈配送的VRPTW模型，設(shè)計改進(jìn)遺傳算法求解。文獻(xiàn)[6]以生鮮農(nóng)產(chǎn)品冷鏈物流的網(wǎng)點建設(shè)成本和運(yùn)營成本為優(yōu)化目標(biāo)構(gòu)建非線性混合整數(shù)規(guī)劃模型。文獻(xiàn)[7]以生產(chǎn)者收益最大為目標(biāo)建立冷鏈配送的VRPTW 模型。文獻(xiàn)[8]根據(jù)生鮮品運(yùn)輸?shù)臅r效性設(shè)計相應(yīng)的時間窗及懲罰成本，構(gòu)建冷鏈環(huán)境下以車輛運(yùn)輸成本、派遣成本以及時間懲罰成本和生鮮損耗成本之和最小為目標(biāo)的VRP模型。文獻(xiàn)[9]考慮到生鮮農(nóng)產(chǎn)品需求的高鮮活度、多品種與小批量特性，以配送成本最小為目標(biāo)建立冷鏈環(huán)境下生鮮農(nóng)產(chǎn)品多隔室的VRP模型。這些研究能為生鮮農(nóng)產(chǎn)品冷鏈配送提供方法參考。考慮到客戶對生鮮農(nóng)產(chǎn)品有新鮮度要求，學(xué)者們研究新鮮度限制條件下生鮮農(nóng)產(chǎn)品配送的VRP。文獻(xiàn)[10]研究不同配送環(huán)境、不同時間窗要求以及不同產(chǎn)品變質(zhì)系數(shù)條件下生鮮農(nóng)產(chǎn)品的新鮮度與配送成本。文獻(xiàn)[11]綜合考慮企業(yè)運(yùn)營成本和顧客對產(chǎn)品新鮮度要求，以總配送成本最小、交付產(chǎn)品的新鮮度最大為目標(biāo)，建立具有最低新鮮度限制的易腐品生產(chǎn)-配送協(xié)同調(diào)度雙目標(biāo)優(yōu)化模型，設(shè)計非支配排序遺傳算法求解。以上研究成果可為提高生鮮農(nóng)產(chǎn)品配送的客戶滿意度提供理論支撐。由于生鮮電商的客戶主要分布在城市，城市路網(wǎng)具有時變特性，部分學(xué)者研究生鮮電商配送的時變車輛路徑問題（Time-Dependent Vehicle Routing Problem，TDVRP）。文獻(xiàn)[12]研究車輛靈活出發(fā)時間條件下生鮮農(nóng)產(chǎn)品配送的TDVRP。文獻(xiàn)[13]優(yōu)化實時路況信息條件下生鮮農(nóng)產(chǎn)品的配送路徑。文獻(xiàn)[14]綜合考慮路況、時間窗與生鮮損耗等因素構(gòu)建生鮮農(nóng)產(chǎn)品配送的多目標(biāo)VRP 模型。文獻(xiàn)[15]基于經(jīng)濟(jì)成本與環(huán)境成本兼顧的視角，研究生鮮電商配送的TDVRP。以上研究比較符合生鮮電商配送的實際情況，具有一定借鑒價值。

已有文獻(xiàn)為深入研究生鮮農(nóng)產(chǎn)品配送問題提供良好基礎(chǔ)，但仍存如下缺口：（1）已有成果大多研究生鮮農(nóng)產(chǎn)品配送的封閉式VRP。然而，由于資金不足或者僅注重核心業(yè)務(wù)等原因，許多中小型生鮮電商都把配送業(yè)務(wù)外包給第三方物流企業(yè)。這種情況下，配送車輛在生鮮電商的倉庫裝貨后開始服務(wù)，完成任務(wù)后不必回到生鮮電商的倉庫，即開放式車輛路徑問題（Open Vehicle Routing Problem，OVRP）。但是，關(guān)于生鮮電商配送的OVRP 研究文獻(xiàn)較少。（2）已有文獻(xiàn)大都設(shè)定車輛在同一時間從倉庫出發(fā)。實際上，為保障生鮮農(nóng)產(chǎn)品送達(dá)客戶時的鮮活度，配送車輛應(yīng)該根據(jù)實際情況在不同時間從倉庫出發(fā)。（3）生鮮電商的客戶主要分布在城市，城市路網(wǎng)具有時變特性。然而，同時考慮城市路網(wǎng)的時變特性、生鮮農(nóng)產(chǎn)品送達(dá)客戶時的新鮮度限制、客戶需求量與時間窗等因素的研究成果不多。（4）已有研究大多根據(jù)行駛距離計算車輛使用成本，但在時變路網(wǎng)環(huán)境下，行駛距離最短并不一定對應(yīng)行駛時間最短，有可能導(dǎo)致較高的人力成本與車輛油耗成本，使得總配送成本不是最低。本文針對以上研究缺口，研究鮮活度限制條件下生鮮電商配送的開放式時變車輛路徑問題（Open Time-Dependent Vehicle Routing Problem，OTDVRP）數(shù)學(xué)模型與求解算法，以期為生鮮電商提供物流配送的方法借鑒與決策參考。

1 問題描述

某生鮮電商將配送業(yè)務(wù)外包給一個第三方物流企業(yè)，有多個客戶需要配送，各客戶地理位置與時間窗已知，需求量都小于車輛容量，有且只能有一輛車服務(wù)一次。為明確本文適用范圍，做出如下假設(shè)：（1）車輛可以根據(jù)需要在不同時間從生鮮電商的倉庫出發(fā)，完成任務(wù)后不必回到該倉庫。（2）車輛可以提前到達(dá)客戶位置，但必須等待至該客戶的最早開始服務(wù)時間才能配送。（3）生鮮農(nóng)產(chǎn)品送達(dá)客戶時具有最低鮮活度限制。（4）交通路網(wǎng)具有時變特性，車輛在不同時間段內(nèi)的行駛速度不同。（5）車輛有固定使用成本，根據(jù)車輛使用時間（包括車輛行駛時間、等待時間與服務(wù)時間）產(chǎn)生相應(yīng)的人力成本。決策問題：第三方物流企業(yè)如何合理規(guī)劃配送車輛路徑，使得總配送成本最少？

2 數(shù)學(xué)模型

2.1 跨時間段的路段行駛時間計算

由于早晚交通高峰、交通管制與意外事故等原因，城市路網(wǎng)的交通狀況具有時變特性，車輛在不同時間段內(nèi)以不同速度行駛。時變路網(wǎng)條件下，車輛可能需要跨越多個時間段才能行駛完某一路段，車輛行駛時間難以直接計算，需要合理處理[16]。

文獻(xiàn)[17-18]采用“先進(jìn)先出”準(zhǔn)則設(shè)計時變路網(wǎng)條件下的車輛行駛時間計算方法。本文借鑒已有方法，將全天24 個小時平均劃分為多個時間段，設(shè)定不同時間段內(nèi)的車輛行駛速度不同。

令Z為時間段的固定時間長度；T={T0,T1,…,TL}為時間段集合；[Th-1,Th]為第h個時間段；Shijk為時間段h內(nèi)車輛k在路段(i,j)上的行駛速度。不同時間段內(nèi)的車輛行駛速度如圖1所示。

圖1 車輛在各時間段內(nèi)的行駛速度

令為時間段h內(nèi)車輛k在路段(i,j)上的行駛時間；lik為車輛k從節(jié)點i的出發(fā)時間，lik∈[Th-1,Th]；ajk為車輛k到達(dá)節(jié)點j的時間。依據(jù)圖2，各時間段內(nèi)車輛k在路段(i,j)上的行駛時間分為3種情況：（1）出發(fā)時間段內(nèi)的車輛行駛時間為Th-lik。（2）中間時間段內(nèi)的車輛行駛時間為Z。（3）最后時間段內(nèi)的車輛行駛時間為ajk-Th+β。

圖2 車輛在各時間段內(nèi)的行駛時間

令Lij為路段(i,j)上的距離；為時間段h內(nèi)車輛k在路段(i,j)上的行駛距離，為在時間段h后車輛k行駛完路段(i,j)全程還需要行駛的距離；tijk為車輛k行駛完路段(i,j)全程的行駛時間。跨時間段的路段行駛時間計算方法步驟如下：

步驟1 出發(fā)時間段內(nèi)的車輛行駛時間計算。=(Th-lik)，如果≥Lij，tijk=，路段行駛時間計算完畢；否則，=Lij-=Th-lik，轉(zhuǎn)步驟2。

2.2 生鮮農(nóng)產(chǎn)品的鮮活度度量

文獻(xiàn)[3]定義生鮮農(nóng)產(chǎn)品隨時間變化的新鮮度損耗計算方法。文獻(xiàn)[11]給出常溫條件下農(nóng)產(chǎn)品運(yùn)達(dá)客戶時的鮮活度度量方法?？紤]到本文設(shè)定生鮮電商通常采用普通車輛配送貨物，采用文獻(xiàn)[11]的生鮮農(nóng)產(chǎn)品鮮活度度量函數(shù)：

其中，tik表示生鮮農(nóng)產(chǎn)品經(jīng)由車輛k送達(dá)客戶i的時間，1 為生鮮農(nóng)產(chǎn)品從倉庫運(yùn)出時的鮮活度，Tb為生鮮農(nóng)產(chǎn)品的最大保質(zhì)時間，tik≤Tb。

2.3 數(shù)學(xué)模型

2.3.1 符號與變量

符號：C為客戶集合；N為物流網(wǎng)絡(luò)內(nèi)的所有集合，N=C?0，0 表示倉庫，i,j∈N；di為客戶i的需求量；V為車輛集合；Q為車輛容量；c1為車輛使用的固定成本；c2為車輛使用的單位時間成本；B為生鮮農(nóng)產(chǎn)品送達(dá)客戶時的最低鮮活度；[bi,ei]為客戶i的服務(wù)時間窗；si為客戶i的服務(wù)時間；wik為車輛k提前駛達(dá)客戶i的等待時間，如果aik ＜bi，wik=bi-aik，否則wik=0。

變量：vk如果車輛k被啟用，值為1，否則為0；xijk如果車輛k從節(jié)點i行駛到節(jié)點j，值為1，否則為0；如果車輛k在時間段h內(nèi)行駛在路段(i,j) 上，值為1，否則為0；zik如果客戶i由車輛k服務(wù)，值為1，否則為0。

2.3.2 OTDVRP數(shù)學(xué)模型

以總配送成本最小為目標(biāo)，構(gòu)建鮮活度限制條件下生鮮電商配送的OTDVRP數(shù)學(xué)模型如下：

式（2）為目標(biāo)函數(shù)，表示最小化車輛使用的固定成本與車輛使用時間（包括車輛行駛時間、等待時間與服務(wù)時間）產(chǎn)生的人力成本之和。約束式（3）表示如果車輛被啟用，必須從倉庫出發(fā)。約束式（4）表示每輛車最多啟用一次。約束式（5）表示每個客戶能且只能被一輛車服務(wù)一次。約束式（6）表示車輛裝載量不能超過容量限制。約束式（7）表示路段距離與車輛在各時間段內(nèi)行駛距離之間的關(guān)系。約束式（8）表示車輛關(guān)于某路段的行駛時間與車輛在各時間段內(nèi)行駛時間之間的關(guān)系。約束式（9）與（10）表示客戶服務(wù)必須在時間窗內(nèi)進(jìn)行。約束式（11）表示車輛到達(dá)客戶時間、等待時間、服務(wù)時間與離開客戶時間之間的關(guān)系。約束式（12）表示車輛從上一個節(jié)點行駛到下一個節(jié)點之間的時間計算方法。約束式（13）表示車輛為客戶配送貨物的具體時間計算方法。約束式（14）表示生鮮農(nóng)產(chǎn)品送達(dá)客戶時必須滿足最低鮮活度。約束式（15）表示變量的取值約束。

3 求解算法設(shè)計

VRP 屬于NP-hard 問題，難以求得最優(yōu)解，通常采用啟發(fā)式算法求得滿意解。OTDVRP比普通VRP更加復(fù)雜，求解將更加困難。蟻群算法是一種啟發(fā)式全局優(yōu)化算法，具有啟發(fā)式搜索、分布計算與信息正反饋等優(yōu)勢，已經(jīng)成功應(yīng)用在VRP、指派問題、Job-shop 調(diào)度、網(wǎng)絡(luò)路由問題等方面[19-20]。本文根據(jù)OTDVRP模型特性，設(shè)計一種改進(jìn)蟻群算法（Improved Ant Colony Algorithm，IACA），思路如下：（1）為優(yōu)先配送時間窗較窄的客戶，在轉(zhuǎn)移規(guī)則里面引入時間窗寬度啟發(fā)式因子；（2）為避免蟻群算法過早陷入局部最優(yōu)、增強(qiáng)蟻群算法搜索的全局性，引入自適應(yīng)信息素啟發(fā)式因子和期望啟發(fā)式因子。

IACA的具體步驟如下：

步驟1 初始化。初始化程序的所有參數(shù)與變量，令maxiter表示程序最大迭代次數(shù)，iter表示當(dāng)前迭代次數(shù)，mincost為最優(yōu)成本，loadk為車輛當(dāng)前裝載量，M為螞蟻數(shù)量，iter=1，mincost=+∞。

步驟2 構(gòu)建可行解。（1）將所有螞蟻都放在倉庫，令m=1。（2）依次派出螞蟻m，令k=1。（3）令loadmk表示螞蟻m當(dāng)前使用的車輛k的貨物裝載量，loadmk=Q。（4）計算螞蟻m的車輛k從當(dāng)前節(jié)點i行駛到節(jié)點j的轉(zhuǎn)移概率pij：

其中，τij為信息度濃度啟發(fā)式因子；ηij為能見度啟發(fā)式因子，ηij=1/Lij；φij為節(jié)點j的時間窗寬度啟發(fā)式因子，φij=1/(ej-bj)；α、δ與?分別表示信息素啟發(fā)式因子、期望啟發(fā)式因子與時間窗寬度啟發(fā)因子的重要性，allowedm表示螞蟻m的所有未訪問節(jié)點集合。（5）找出轉(zhuǎn)移概率pij值最大的節(jié)點jb，采用公式（6）計算節(jié)點jb是否滿足車輛容量限制，采用跨時間段的路段行駛時間計算方法與公式（8）計算車輛k從節(jié)點i行駛到節(jié)點jb的行駛時間tijbk，采用公式（13）計算農(nóng)產(chǎn)品由車輛k送達(dá)客戶的時間tjbk，采用公式（1）計算生鮮農(nóng)產(chǎn)品送達(dá)客戶的鮮活度X(tjbk)，如果滿足車輛裝載量、客戶時間窗、生鮮農(nóng)產(chǎn)品送達(dá)客戶時的最低鮮活度等限制，車輛k從節(jié)點i行駛到節(jié)點jb，loadmk=loadmk-djb，jb?allowed；否則，k=k+1，重新從倉庫派出車輛服務(wù)，轉(zhuǎn)（3）。（6）如果螞蟻m還有節(jié)點未訪問，轉(zhuǎn)（4）。（7）如果所有螞蟻訪問完畢，轉(zhuǎn)步驟3，否則，m=m+1，轉(zhuǎn)（2）。

步驟3 當(dāng)前迭代的結(jié)果計算。（1）計算當(dāng)前迭代的最優(yōu)總成本costiter，如果costiter ＜mincost，mincost=costiter。（2）計算每輛車的出發(fā)時間、車輛使用時間、行駛距離，iter=iter+1。

步驟4 自適應(yīng)信息素啟發(fā)式因子和期望啟發(fā)式因子設(shè)計。參考文獻(xiàn)[20-21]的方法，令α=1+3(iter/maxiter)，δ=3-2(iter/maxiter)。

步驟5 信息素更新。更新當(dāng)前迭代最優(yōu)路徑的組成路段信息素，即：

其中，ρ為信息素?fù)]發(fā)性，0 ≤ρ ＜1；Δτm ij為螞蟻m在路段(i,j)上信息素增加量；F為常數(shù)；fm表示螞蟻m的總配送成本。

步驟6 算法結(jié)束條件。如果iter≤maxiter，轉(zhuǎn)步驟2，否則算法結(jié)束。

4 算例分析

4.1 實驗設(shè)置

由于目前沒有生鮮農(nóng)產(chǎn)品配送的標(biāo)準(zhǔn)數(shù)據(jù)庫，同時也考慮到生鮮電商客戶分布的多樣性，采用VRPTW數(shù)據(jù)庫[22]的C 類型、R 類型與RC 類型算例為本文測試算例。C 類型、R 類型與RC 類型算例的客戶坐標(biāo)分別屬于集中分布、隨機(jī)分布與混合分布。各算例有1個倉庫與100個客戶，第一行數(shù)據(jù)為倉庫坐標(biāo)，其余100行數(shù)據(jù)是客戶坐標(biāo)、需求量與時間窗。另外，為滿足測試需要，補(bǔ)充如下數(shù)據(jù)：（1）設(shè)定倉庫的工作時間為早上7：00。（2）設(shè)定每個客戶的服務(wù)時間為5 min，各時間段的時間長度為10 min。（3）將8：00至9：00、18：00至19：00設(shè)為交通擁堵時間段，車輛行駛速度設(shè)定為20 km/h。（4）非交通擁堵時間段內(nèi)的車輛行駛速度設(shè)定如下：令4種車速分別為[55,40,65,30]，根據(jù)時間段h采用求余函數(shù)Y=mod(h,4)，當(dāng)Y取值為1、2、3 與0 時分別對應(yīng)4 種車速。

參考文獻(xiàn)[17，19]的方法，將算法參數(shù)設(shè)置如下：c1=200元/輛，c2=0.3元/min，Q=1 000單位，maxiter=600，M=30，ρ=0.15 ，?=3、F=20，Tb=780 min、B=0.7。算法采用Matlab R2016a 編程，在Intel?Core ? i5-8250U CPU @1.60 GHz 1.80 GHz，RAM 8.00 GB的微機(jī)上運(yùn)行。

4.2 實驗結(jié)果

4.2.1 多類型算例的開放式車輛路徑規(guī)劃分析

為檢驗本文IACA 算法的可行性與有效性，采用C類型、R 類型與RC 類型多種客戶分布的多個算例進(jìn)行實驗。計算結(jié)果如表1 所示。表中，IN 表示算例名稱，TC表示總配送成本（單位：元），VUT表示車輛總使用時間（單位：min），VTD 表示車輛總行駛距離（單位：km），VN 表示車輛使用數(shù)量（單位：輛），RT 表示算法運(yùn)行時間（單位：s）。

表1 不同類型算例的計算結(jié)果

根據(jù)表1 的數(shù)據(jù)可以得出如下結(jié)論：（1）根據(jù)TC、VUT 與VN 的計算結(jié)果可知，相對于R 類型與RC 類型的算例來說，C 類型算例的總配送費用相對較高，車輛使用時間較長，車輛使用數(shù)量較多。主要原因在于C類型算例屬于集中分布，每個客戶都與倉庫的距離較遠(yuǎn)（參見圖3（a）算例C109 的配送路徑規(guī)劃），車輛行駛到第一個客戶時需要較長的時間，從而影響該車輛運(yùn)載的生鮮農(nóng)產(chǎn)品送達(dá)后續(xù)客戶時的鮮活度；而R 類型與RC類型算例的客戶分布相對均勻，車輛配送路線是由近至遠(yuǎn)，每輛車先配送離倉庫近的客戶，再配送離該客戶較近的客戶，縮短車輛駛達(dá)客戶時間，有效提高生鮮農(nóng)產(chǎn)品送達(dá)客戶時的鮮活度（參見圖3（b）算例R209 與圖3（c）算例RC206的配送路徑規(guī)劃）。（2）根據(jù)VTD與VN的結(jié)果可知，同一類型的算例中，車輛總行駛距離越長，車輛使用數(shù)量越多。（3）算法的最大運(yùn)行時間為264.94 s，最小運(yùn)行時間為240.57 s，說明本文算法能夠在較短時間內(nèi)求解不同客戶分布類型的算例，給出決策者滿意解，具有可行性與有效性。

算例C109、R209 與RC206 的配送路徑規(guī)劃如圖3所示。圖3中的黑色菱形代表倉庫，米字形黑點代表客戶，實線代表車輛行駛路徑。從圖3可知，C類型算例的各客戶離倉庫具有一定距離，客戶呈集中分布，各區(qū)域內(nèi)的臨近客戶大都由同一車輛配送；R 類型與RC 類型算例的客戶呈隨機(jī)分布，各車輛首先服務(wù)離倉庫距離最近的客戶，再依次服務(wù)距離較遠(yuǎn)的客戶。

4.2.2 開放式車輛路徑策略與封閉式車輛路徑策略的對比分析

為分析開放式車輛路徑策略的有效性，采用多類型算例將本文算法進(jìn)行開放式車輛路徑策略與封閉式車輛路徑策略（車輛從倉庫出發(fā)，完成配送任務(wù)后回到原倉庫）的對比實驗，計算結(jié)果如表2所示。表2中各符號的含義同表1所示。

根據(jù)表2的實驗結(jié)果可知：

（1）所有算例中，開放式車輛路徑策略求得的總配送成本（TC）要遠(yuǎn)遠(yuǎn)低于封閉式車輛路徑策略求得的值，平均低10.32%，最高要低19.89%（算例R208），最少要低3.56%（算例C106）。

（2）開放式車輛路徑策略求得的各算例車輛總使用時間（VUT）要遠(yuǎn)遠(yuǎn)低于封閉式車輛路徑策略求得的值，平均低9.06%，最高要低12.51%（算例RC204），最少要低4.17%（算例R207）。

（3）開放式車輛路徑策略求得的各算例車輛總行駛距離（VTD）要遠(yuǎn)遠(yuǎn)低于封閉式車輛路徑策略求得的值，平均低24.25%，最高要低38.97%（算例C105），最少要低11.36%（算例R208）。

（4）開放式車輛路徑策略求得的各算例車輛使用數(shù)量（VN）與算法運(yùn)行時間（RT）要優(yōu)于封閉式車輛路徑策略求得的值。因此，開放式車輛路徑策略能有效降低生鮮電商的總配送成本，節(jié)約車輛使用時間，縮短車輛行駛距離，減少車輛使用數(shù)量。

4.2.3 不同車輛使用成本計算標(biāo)準(zhǔn)的對比分析

為驗證采用車輛總使用時間作為車輛使用成本計算標(biāo)準(zhǔn)的合理性，在所有參數(shù)不變的前提下，采用不同類型算例將本文方法與以車輛總行駛距離作為車輛使用成本計算標(biāo)準(zhǔn)方法進(jìn)行對比實驗。各算例實驗結(jié)果如表3所示。表3中各符號的含義同表1所示。

圖3 不同類型算例的車輛路徑規(guī)劃

表2 開放式車輛路徑策略與封閉式車輛路徑策略的計算結(jié)果

表3 車輛使用成本的不同計算標(biāo)準(zhǔn)的計算結(jié)果

表4 不同算法的計算結(jié)果

由表3的計算結(jié)果可知：（1）在不同的計算標(biāo)準(zhǔn)下，本文算法都能求解出各種標(biāo)準(zhǔn)下的滿意解。（2）以車輛總使用時間（VUT）作為車輛使用成本計算標(biāo)準(zhǔn)求得的各算例總配送成本（TC）要遠(yuǎn)遠(yuǎn)低于以車輛總行駛距離（VTD）作為車輛使用成本計算標(biāo)準(zhǔn)求得的解，平均要低25.91%，最多要低32.92%（算例R204），最少要低13.05%（算例C101）。（3）根據(jù)車輛使用數(shù)量（VN）的計算結(jié)果，以車輛總使用時間（VUT）作為車輛使用成本計算標(biāo)準(zhǔn)求得各算例的車輛使用數(shù)量（VN）要遠(yuǎn)遠(yuǎn)低于以車輛總行駛距離（VTD）作為車輛使用成本計算標(biāo)準(zhǔn)求得的解。說明在時變路網(wǎng)條件下，應(yīng)使用車輛總使用時間作為車輛使用成本計算標(biāo)準(zhǔn)。

4.2.4 不同算法的對比分析

為驗證本文改進(jìn)蟻群算法（IACA）的可行性與合理性，另外編寫了求解OTDVRP 的遺傳算法（Genetic Algorithm，GA）程序。在所有參數(shù)不變的條件下，將本文IACA與文獻(xiàn)[23]的蟻群算法（ACA）、GA進(jìn)行對比分析。ACA設(shè)定轉(zhuǎn)移規(guī)則里面僅有信息度濃度啟發(fā)式因子與能見度啟發(fā)式因子，沒有自適應(yīng)信息素啟發(fā)式因子和期望啟發(fā)式因子。設(shè)定GA 的種群數(shù)量為100，變異概率為0.1，交叉概率為0.9，迭代次數(shù)為600次。各算例的計算結(jié)果如表4所示。表4中所有符號的含義同表1所示。

根據(jù)表4 的計算結(jié)果可知：（1）關(guān)于總配送成本（TC），IACA 求得各算例的值最優(yōu)。比ACA 求得的解平均要低9.02%，最多要低15.94%（算例RC102），最少要低5.29%（算例R201）；比GA 求得的解平均要低8.59%，最多要低18.01%（算例C103），最少要低1.68%（算例R201）。（2）關(guān)于車輛總使用時間（VUT），所有算例中IACA 求得的值最優(yōu)。比ACA 求得的解平均要低7.35%，最多要低15.52%（算例R201），最少要低3.99%（算例R202）；比GA求得的解平均要低16.21%，最多要低25.19%（算例C103），最少要低5.33%（算例R201）。（3）IACA求解各算例的車輛使用數(shù)量（VN）顯著優(yōu)于其余兩種算法求得的解。因此，IACA 在轉(zhuǎn)移規(guī)則里面引入時間窗寬度啟發(fā)式因子優(yōu)先服務(wù)時間窗較窄的客戶，以及自適應(yīng)信息素啟發(fā)式因子和期望啟發(fā)式因子增強(qiáng)蟻群算法搜索的全局性等方法能有效降低總配送成本，縮短車輛使用時間，減少車輛使用數(shù)量，具有可行性與合理性。

5 結(jié)論

本文首先根據(jù)城市路網(wǎng)的時變特性設(shè)計車輛行駛時間計算方法；再綜合考慮客戶需求量、時間窗、生鮮度限制與開放式路徑等因素，以總配送成本最小為目標(biāo)構(gòu)建帶鮮活度限制的OTDVRP 優(yōu)化模型，設(shè)計IACA 求解；采用多類型算例驗證本文方法的可行性與有效性。仿真實驗結(jié)果說明：（1）相對于封閉式車輛路徑策略來說，開放式車輛路徑策略能有效降低生鮮電商的總配送成本，節(jié)約車輛使用時間，縮短車輛行駛距離，減少車輛使用數(shù)量。（2）生鮮電商的客戶主要在城市，城市路網(wǎng)具有時變特性，應(yīng)使用車輛總使用時間作為車輛使用成本的計算標(biāo)準(zhǔn)。（3）根據(jù)IACA 與ACA、GA 的比較實驗計算結(jié)果，IACA具有更好的優(yōu)化效果。

進(jìn)一步的研究將考慮車輛碳排放、油耗等環(huán)境因素，以期促進(jìn)生鮮電商物流配送與環(huán)境保護(hù)的和諧發(fā)展。