時變路網(wǎng)下電動冷藏車配送路徑優(yōu)化研究

王玖河，安聰琢，郭田宇

(1.燕山大學 經(jīng)濟管理學院，河北 秦皇島 066004；2.燕山大學 京津冀協(xié)同發(fā)展管理創(chuàng)新研究中心，河北 秦皇島 066004；3.遼寧工程技術(shù)大學 工商管理學院，遼寧 葫蘆島 125105)

隨著城市化進程不斷加快，我國的交通日趨便利，但與此同時城市的交通擁堵問題也日益嚴重。在物流配送過程中，車輛的行駛速度和行駛時間受當前路況的影響較大，而基于車輛勻速行駛的靜態(tài)路網(wǎng)假設(shè)的理想狀態(tài)下所求解的最優(yōu)路徑問題與實際情況偏差較大，考慮時變路網(wǎng)下的車輛配送路徑更加符合現(xiàn)實情況。面對當前環(huán)境污染嚴重、石油資源短缺等問題，傳統(tǒng)燃油車的弊端日益顯露，電動冷藏車憑借著環(huán)保、節(jié)能等優(yōu)勢在實現(xiàn)“最后一公里”的物流配送終端得到了廣泛的利用。因此，研究時變路網(wǎng)下電動冷藏車的配送路徑問題更加符合現(xiàn)實運輸環(huán)境的需要，具有重要的理論意義和現(xiàn)實價值。

對于電動車輛的路徑問題，國內(nèi)外學者展開了廣泛的研究。揭婉晨等[1]建立電動汽車車輛路徑問題的混合整數(shù)規(guī)劃模型，并采用改進的分支定界算法進行求解。Gerhard等[2]研究帶時間窗和充電站的混合車輛路徑問題，建立考慮車輛充電時間和充電地點的路徑優(yōu)化模型。Verma[3]提出一種帶有時間窗和充電站的電動汽車路徑問題，允許可用的充電站同時作為充電站和電池交換站。Keskin等[4]針對充電站容量有限這一實際情況，建立考慮車輛排隊時間的帶時間窗的電動汽車路徑優(yōu)化模型，并結(jié)合自適應(yīng)大鄰域搜索算法和混合整數(shù)線性規(guī)劃解的數(shù)學算法進行求解。葛顯龍等[5]針對電動汽車配送過程中的問題，建立考慮部分充電策略的EVRPTW模型，并利用混合模擬退火算法進行求解。

在考慮時變路網(wǎng)下的車輛路徑問題的研究上，Kok等[6]考慮交通擁堵狀況以及駕駛時間規(guī)則等因素，引入時變網(wǎng)絡(luò)理論，建立以駕駛時間最短為目標函數(shù)的路徑優(yōu)化模型。Tas等[7]研究具有軟時間窗和隨機出行時間的車輛路徑問題，建立以運輸成本和服務(wù)成本最小化為目標函數(shù)的數(shù)學模型，并利用分支定界算法對模型進行求解。吳瑤等[8]考慮交通的時變性，針對易腐食品，建立時變路網(wǎng)下的生產(chǎn)?配送優(yōu)化模型，并設(shè)計了改進的遺傳算法對模型進行求解。張濟風等[9]研究冷鏈物流配送的路徑優(yōu)化問題，并利用模擬退火算法計算出在時變交通下的滿足總配送成本最低的最優(yōu)路徑。Zheng[10]以配送成本最小化和平均不滿意度最低為目標函數(shù)，建立基于時變交通流的多模糊時間窗車輛路徑問題模型。付朝暉等[11]以生鮮配送為研究對象，設(shè)計時變路網(wǎng)下的車輛行駛時間計算方法以及考慮生鮮鮮活度的開放式時變車輛路徑優(yōu)化模型，并設(shè)計改進的蟻群算法進行求解。

綜上，大多數(shù)學者都是將電動車輛的路徑優(yōu)化問題與時變路網(wǎng)下的車輛路徑問題獨立開來進行研究。對于電動車輛路徑問題的研究中，多數(shù)都是基于恒定速度的靜態(tài)路網(wǎng)假設(shè)下進行研究，忽視了交通路網(wǎng)的時變特性對電動車輛實際配送過程中的影響，導致求解結(jié)果可能與實際情況有較大誤差。因此，本文將電動車輛的路徑優(yōu)化問題與時變路網(wǎng)下的車輛路徑問題相結(jié)合，同時引入多模糊時間窗約束，建立考慮時變路網(wǎng)的電動冷藏車配送模型，運用AP聚類算法對配送區(qū)域進行劃分，提高配送效率，并設(shè)計改進遺傳算法對模型進行求解，最后通過設(shè)置算例將靜態(tài)網(wǎng)絡(luò)與時變網(wǎng)絡(luò)下的配送成本進行對比，驗證模型及算法的有效性。

1 問題描述與假設(shè)

1.1 問題描述

在現(xiàn)實生活中，交通路網(wǎng)具有時變特性，車輛的行駛速度受當前所處時段的影響。本文研究時變路網(wǎng)下的車輛配送路徑，將配送過程看作若干個時段，根據(jù)各個時段交通擁堵狀況的不同，每個時段的車速也可能不同，如圖1所示。時段劃分越細，求解結(jié)果越準確。本研究中采用電動車輛進行生鮮配送，且在配送過程中車輛電量不足以行駛至下一需求點時，需到就近的充電樁進行充電。同時，相較于傳統(tǒng)VRPTW模型中的單時間窗約束，本文引入多模糊時間窗約束，旨在滿足車輛載重約束、電量約束、時間窗約束等條件下，求解使得總配送成本最小的最優(yōu)路徑。

圖1 各時段速度對應(yīng)示意圖Figure 1 Schematic diagram of the corresponding speed in each period

1.2 模型假設(shè)

1) 只有一個配送中心，所有車輛均從配送中心出發(fā)，且配送完成后返回配送中心；

2) 每個需求點只能有一輛車進行配送；

3) 不同配送區(qū)域間車輛不可跨區(qū)域配送；

4) 充電樁的電量足夠車輛需要；

5) 任一客戶點的需求量均小于車輛最大載重量；

6) 同一需求點的不同時間窗不會重合；

7) 交通路網(wǎng)時變區(qū)間為20 min。

2 符號設(shè)定及模型構(gòu)建

2.1 主要符號設(shè)定

K為車輛編號集合，K={1,2,···,p}，k∈K；

I為節(jié)點編號集合，I={0,1,2,···,i}，其中，0表示物資分配中心;

H為客戶的時間窗編號集合，H={1,2,···,h};R為充電樁編號集合，R={1,2,···,r}；

N為客戶點編號集合，N={4,5,···,n}；

為時段的集合，Tn′={T0,T1,T2,···,Tn}，其中[Tn?1,Tn]表 示第n個 時段；

dij為 任意節(jié)點i到 節(jié)點j的距離(i≠j)；

a為單位車輛單位時間的早到懲罰成本；

b為單位車輛單位時間的延遲懲罰成本；

L為車輛的最大載重量；

Qi為 客戶i的需求量；

t0為發(fā)車時刻；

ti為到達節(jié)點i的時刻；為客戶i的 第 ?個時間窗要求，其中，為客戶i所能接受的最早服務(wù)時間，為客戶i所期待的最早服務(wù)時間，為客戶i所期待的最晚服務(wù)時間，為客戶i所能接受的最晚服務(wù)時間。

決策變量如下。

2.2 模型構(gòu)建

2.2.1 時變路網(wǎng)模型

其中，tij表 示行駛完i、j段 所需時間；tiserve表示客戶i的 服務(wù)時間；tik表 示車輛k到客戶i的 時間；t表示此時所處的時刻；Tn表 示時刻t所 對應(yīng)的時段；t’表示Tn時 段的剩余時間，即Tn?t，其中t∈[Tn?1,Tn]；di j表 示i與j之 間 的 距 離；di’

j表示車輛已經(jīng)行駛的距離；vn表示Tn時 段所對應(yīng)的速度；表示在t時刻車輛已經(jīng)行駛了di’

j距 離，繼續(xù)行駛完dij所需要的時間；di’’j表

示t時刻已行駛了di’j距離，繼續(xù)以速度vn行駛完Tn中的剩余時間，所行駛的距離。

式(1)、(2)表示物流節(jié)點i與j之間的行駛時間橫跨多個時段的情況。其中，式(1)表示在配送完客戶i后去往客戶j的途中，已經(jīng)行駛了di’j距離，繼續(xù)行駛到客戶j所需時間；式(2)表示在客戶i處服務(wù)完畢后(還未出發(fā))繼續(xù)行駛到下一客戶j處所需時間；式(3)表示在一個時段之內(nèi)即可完成i與j之間的配送時所需要的時間。

2.2.2 充電耗電模型

同種類型的電車在行駛過程中，耗電量與貨物重量和行駛速度有關(guān)。本文引用目前廣泛應(yīng)用的功率及功耗計算方法[12]，則功率計算公式為

其中，Pkv(Q)為 車輛k載重為Q且以速度v行駛時的功率；M為車輛自重；g為重力加速度，本研究取 9.8 m/s2；f為汽車滾動阻力系數(shù)；Cd為空氣阻力系數(shù)；S′為 汽車迎風面積； η為傳動系統(tǒng)機械效率。

功耗計算公式為

若車輛k配送完客戶i后電量不足以行駛到下一客戶j，則需要到距離最近的充電站充電，充電時間為

2.2.3 配送成本模型

式(7)表示完成配送任務(wù)所需的固定成本，其中P1為單位車輛固定成本(元/輛)；式(8)表示完成配送任務(wù)所需的車輛行駛成本，P2為單位車輛單位距離行駛成本(元·km?1·輛?1)；式(9)表示完成配送任務(wù)所需的耗電成本，P3為單位車輛耗電成本(元/kWh)；式(10)表示完成配送任務(wù)所需的制冷成本，P4為單位車輛制冷成本(元/kcal)，R′為 熱轉(zhuǎn)換系數(shù)，S為車廂表面積，φ為車廂內(nèi)外溫差，λ為車廂劣化程度；式(11)表示完成配送任務(wù)所需的充電成本，P5為單位充電成本(元/kWh)，Em為電池最大容量(kWh)，為車輛k到 充電樁時所剩電量(kWh)，uik為0或1的決策變量；式(12)表示懲罰成本，tik為 車輛k到達客戶i的時間；式(13)為模型的目標函數(shù)，即求最低總配送成本。

2.2.4 約束條件

式(14)表示車輛不能超載；式(15)表示一個客戶只能被一輛車服務(wù)，且所有客戶配送完畢，車輛必須返回配送中心；式(16)表示同一客戶的不同時間窗區(qū)間不能重合；式(17)表示車輛到達客戶點的時間應(yīng)處于任意一個時間窗范圍內(nèi)；式(18)表示車輛經(jīng)過充電樁i時的電量變化，表示車輛到達充電樁i時的電量，表示離開節(jié)點i的電量；式(19)表示車輛經(jīng)過節(jié)點i后的時間變化，表示車輛k離開節(jié)點i時的時間，tik表示車輛k到達充電樁i時的時間；式(20)表示車輛k從離開節(jié)點i至到達節(jié)點j過程中的電量變化，表 示車輛k離開節(jié)點i時的剩余電量，Ejk表示車輛k到達節(jié)點j時的剩余電量，B為一個數(shù)值很大的常數(shù)；式(21)表示車輛k到達節(jié)點i與離開節(jié)點i的時間變化；式(22)表示車輛所剩電量必須大于最低行駛變量。式(23) ～ (27)為相關(guān)決策變量，分別表示車輛k從i行 駛到j(luò)，則xijk為1，否則為0；客戶i由 車輛k配送，則yik為1，否則為0；車輛k從配送中心發(fā)車，則x0ik為 1，否則為0；車輛到達客戶i處于第 ?個時間窗內(nèi)，則為1，否則為0；車輛k在充電樁i充 電，則uik為1，否則為0。

3 算法設(shè)計

目前對于常規(guī)VRP問題的研究較為成熟，常用的求解算法有遺傳算法[13]、蟻群算法[14]、模擬退火算法[15-16]等。相比于常規(guī)的VRPTW問題，本文的模型中引入了電車充電模型及多時間窗的情況，采用AP算法對客戶點進行聚類后，對各個區(qū)域分別使用遺傳算法進行求解。

3.1 AP聚類算法

仿 射 傳 播 聚 類 算 法(affinity propagation)簡 稱AP聚類算法，是基于數(shù)據(jù)點間的“信息傳遞”的一種聚類算法。算法的基本思想：將全部樣本看作網(wǎng)絡(luò)節(jié)點，通過網(wǎng)絡(luò)中各條邊的消息傳遞計算出各樣本的聚類中心。聚類過程中，共有兩種消息在各節(jié)點間傳遞，分別是吸引度(responsibility)和歸屬度(availability)。通過在點之間傳遞信息，通過不斷地傳遞信息，最終選出代表元以完成聚類[17]。AP算法通過迭代過程不斷更新每一個點的吸引度和歸屬度值，直到產(chǎn)生m個高質(zhì)量的exemplar(類似于質(zhì)心)，同時將其余的數(shù)據(jù)點分配到相應(yīng)的聚類中。

其中有兩個重要參數(shù)，分別為吸引度矩陣R=[r(i,k)]，歸屬度矩陣Ψ =[ψ(i,k)]，均為N階矩陣，矩陣更新公式為

式(28)為吸引度矩陣更新公式，表示數(shù)據(jù)點k適合作為數(shù)據(jù)點i的聚類中心的程度；式(29)歸屬度矩陣更新公式，表示數(shù)據(jù)點i選擇數(shù)據(jù)點k作為其聚類中心的合適程度。本文為了避免迭代更新的過程中出現(xiàn)不可控震蕩，也為了加快計算速度，在上述操作后引入衰減系數(shù)λ ，λ為(0,1)之間的某實數(shù)，一般取0.5。衰減公式為

式(30)為吸引度矩陣的衰減公式；式(31)為歸屬度矩陣的衰減公式。

在迭代的過程中，要先對吸引度矩陣進行迭代，再使用迭代后的吸引度矩陣去計算歸屬度矩陣，最后對其進行衰減，完成一次迭代。重復迭代的過程，直至達到設(shè)置的最大迭代次數(shù)或聚類結(jié)果。經(jīng)多次迭代不再改變后，跳出循環(huán)，結(jié)束算法。

3.2 改進遺傳算法

3.2.1 染色體編碼及形成初始種群

本文選用實數(shù)編碼，染色體中的基因代表各個物流節(jié)點(配送中心、充電樁、客戶點)，其中0代表配送中心，1、2、3代表充電樁，其余代表客戶點。在染色體中實數(shù)的順序代表了配送車輛的路徑。例如，有一個配送中心、3個充電樁和10個客戶點，則染色體至少需要有25個基因位。若算法運行結(jié)果為0-7-4-6-9-8-2-5-10-0，則表示車輛從配送中心出發(fā)，依次配送客戶點4、客戶點6、客戶點9和客戶點8，并在配送完客戶點8之后返回充電樁2進行充電，之后繼續(xù)配送客戶點5和客戶點10，配送完畢后返回配送中心。初始種群的形成，首先隨機生成一個NP×CN的矩陣，NP代表種群規(guī)模，CN代表染色體長度，這里的染色體中不包含配送中心及充電樁的基因位，僅代表各個客戶點，例如，某染色體為4-7-9-6-5，意為配送順序為客戶點4、7、9、6、5，但并未計算在配送途中何時需返回充電樁進行充電以及返回哪個充電樁，確定充電樁的工作在計算適應(yīng)度的操作中完成。

3.2.2 計算適應(yīng)度

在初始種群初步形成之后，需要根據(jù)各條染色體適應(yīng)度的大小決定進入遺傳操作的優(yōu)秀父代染色體，由于本研究的優(yōu)化目標是成本最小，故適應(yīng)度函數(shù)取成本函數(shù)的倒數(shù)，即

計算適應(yīng)度之前，需要確定車輛配送過程中返回充電樁的時刻。在初始種群形成后，得到了一個VRP問題的初始解，對應(yīng)染色體中并不包含代表充電樁的基因。由于車輛本身的電量有限，所以形成的初始解可能為不可行解，因此需要在合適的位置插入充電樁，使其變?yōu)榭尚薪?。在充電樁的插入策略中，若車輛通過節(jié)點i后，其電量不足以行駛至下一個節(jié)點j，則稱節(jié)點i為整條路徑中的中斷點，在算法識別到中斷點時，需要在中斷點后插入充電樁。

考慮到極限情況的存在，車輛在配送完任意一個客戶點之后都有可能進行充電，所以在編程的過程中，任意兩個代表客戶點或者配送中心的基因位之間，都必須存在一個空基因位用來儲存可能存在的代表充電樁的基因，在染色體的兩端還需要加入兩個基因位來儲存代表配送中心的基因。在上述條件下，用于計算適應(yīng)度的染色體長度需為2+客戶點數(shù)量+(2+客戶點數(shù)量?1)，即2×客戶點數(shù)量+3。在車輛按照初始種群染色體中的基因順序行駛完任意一個節(jié)點后，若滿足式(20)，則不需加入充電樁。若不滿足，則需在該節(jié)點與下一節(jié)點之間的空基因位加入代表充電樁的基因，判斷該點與所有待選充電樁的距離，并選擇代表最近的充電樁的基因，充電后將電量補滿繼續(xù)行駛，直至遍歷完所有節(jié)點，完成新染色體的構(gòu)建。使用式(32)計算新染色體的適應(yīng)度，并選擇適應(yīng)度最大的個體進行后續(xù)進化操作。

3.2.3 選擇、交叉和變異

為了確保最優(yōu)個體可以進入子代，本文選用保留最佳個體與輪盤賭選擇法相結(jié)合的方式選擇染色體[18]。具體操作過程如下。

步驟 1以適應(yīng)值函數(shù)的值為序，使染色體由好到壞進行重排，fh越 大，則染色體h越好，其序號越小。設(shè)參數(shù)a∈(0,1)給定，定義基于序的評價函數(shù)為

其中，i=1時 染色體最好，i=n時染色體最差。選擇序號為1的染色體復制到下一代，其余染色體按以下步驟操作。

步驟 2對每個染色體hi計 算累計概率pi。

步驟 3產(chǎn)生隨機實數(shù)r∈(0,pn).

步驟 4若pi?1＜r＜pi，則選擇第i個 染色體hi。

步驟 5重復步驟 3和步驟 4，n?1次 ，得到n?1個染色體。

選擇兩點交叉，并對常規(guī)變異算子進行改進，將其分為交換變異、逆轉(zhuǎn)變異和插入變異。具體操作過程如下。

步驟 1交換變異，即常規(guī)的變異算子，在染色體內(nèi)隨機取兩個不穩(wěn)定基因進行互換。

步驟 2逆轉(zhuǎn)變異，即隨機選取逆轉(zhuǎn)區(qū)間，對逆轉(zhuǎn)區(qū)間的基因取倒序后重新計算該染色體的適應(yīng)度，并與原適應(yīng)度比較，若適應(yīng)度得到提升則保留新染色體，否則保留原染色體。逆轉(zhuǎn)操作有助于提高種群的多樣性，防止陷入近親繁殖。

步驟 3插入變異，考慮到輪盤賭選擇法容易漏掉小概率個體，故在逆轉(zhuǎn)變異后進行插入操作，將按適應(yīng)度降序排列染色體的前n條(n為父代與子代種群規(guī)模的差值)選中，與上述步驟形成的子代種群結(jié)合，形成新的種群。示例如下。

插入前：

父代種群

0 2 7 2 9 8 0 0 6 3 4 9 2 0 0 5 2 7 4 6 0

子代種群

0 9 8 5 6 3 0 0 7 4 2 8 6 0

假設(shè)父代種群3條染色體對應(yīng)適應(yīng)度分別為9、12、8，進行降序排列后為12、9、8，分別代表第2、1、3條染色體。

插入后

0 6 3 4 9 2 0 0 9 8 5 6 3 0 0 7 4 2 8 6 0

4 算例分析

4.1 參數(shù)設(shè)置

本文假設(shè)某企業(yè)為X市生鮮零售點配送生鮮產(chǎn)品，共有1個配送中心、3個充電樁和20個客戶點。其中，0代表配送中心；1 ～ 3代表充電樁，4 ～ 23代表客戶點。同時，為了更加貼合實際，各節(jié)點之間采用直線距離乘迂回系數(shù)代表實際距離，交通路網(wǎng)更新時段設(shè)置為20 min，發(fā)車時間為早8:00，出發(fā)時默認滿電。各參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置Table 1 Parameter settings

各個時段對應(yīng)的平均車速如表2所示。

表2 各時段車速對應(yīng)表Table 2 Corresponding table of vehicle speed in each period

配送中心、充電樁和客戶點坐標數(shù)據(jù)如表3所示。

表3 配送信息Table 3 Distribution Information

4.2 聚類結(jié)果分析

將20個客戶點坐標代入式(28) ～ (31)，設(shè)置最大迭代次數(shù)為500，當不變迭代次數(shù)為50時，輸出聚類結(jié)果。運用Matlab編程計算可知，共聚類為3簇，聚類的合適度(tmpnetsim)為 ?4.183 6e+03，相似度(net similarity)為 ?4 183.64。第1簇客戶點編號(區(qū)域1)為8、9、13、18、19、20；第2簇客戶點編號(區(qū)域2)為4、5、6、7、21、22、23；第3簇客戶點編號(區(qū)域3)為10、11、12、14、15、16、17。聚類圖像如圖2所示。

圖2 聚類效果圖Figure 2 Clustering effect diagram

4.3 路徑優(yōu)化結(jié)果分析

遺傳算法參數(shù)設(shè)置如下。種群數(shù)量100，最大迭代次數(shù)200，交叉概率0.9，變異概率0.05。車輛行駛成本如表4所示，車輛行駛路徑及時間點如表5所示。所有車輛固定成本均為200元。

表5 配送路徑Table 5 Distribution path

配送路徑圖如圖3。

圖3 配送路徑圖Figure 3 Distribution path diagram

由表4可知，本次配送共派出3輛車，每輛車負責一個配送區(qū)域，負責區(qū)域1、2、3的車輛配送成本 分 別 為768.185 0元、1 176.721 1元 和845.177 5元，則配送總成本為2 790.083 6元。

表4 配送結(jié)果及路程Table 4 Path optimization results

4.4 對比研究

4.4.1 動態(tài)?靜態(tài)對比

為了檢驗?zāi)Ｐ偷挠行?，本文將時變路網(wǎng)下的求解方案與固定速度的靜態(tài)路網(wǎng)下的求解方案進行對比。計算表2中各時段車速的平均速度作為車輛行駛的固定速度，并重新進行配送成本計算。通過計算可知各時段的平均速度為45.67 km/h。分別在固定速度下以及引入時變路網(wǎng)理論下對模型求解5次，其計算出的總配送成本對比如表6所示。

由表6可以看出時變模型的配送成本普遍要低于固定速度模型的配送成本。為了更加方便區(qū)分，將表6中數(shù)據(jù)繪制成折線圖如圖4所示。

圖4 配送成本對比圖Figure 4 Comparison of distribution costs

表6 不同速度配送總成本對比Table 6 Comparison of total delivery costs at different speeds

由圖4及表6可知，在5次計算中，固定速度模型的配送總成本均在3 000元以上，平均值為3 118.382 5元；時變速度模型的配送成本均低于3 000元，平均值為2 737.896 4元。與固定速度相比，時變速度模型計算得到的平均配送成本降低12.201%，且更加符合實際情況，為企業(yè)壓低預算，驗證了模型的有效性。

計算結(jié)果在一定范圍內(nèi)波動是由于遺傳算法進化過程的隨機性引起的，且隨著種群規(guī)模的擴大和迭代次數(shù)的增加，曲線的波動會越來越小，但計算時間也會相應(yīng)地增加。由于本文種群規(guī)模設(shè)置為100，最大迭代次數(shù)設(shè)置為200，且通過圖4可以看出兩條曲線的波動范圍不大，故本算法參數(shù)設(shè)置合理，計算結(jié)果可以接受。

4.4.2 不同規(guī)模對比

為了進一步驗證模型的普適性，本文以配送中心為圓心，在半徑40 km內(nèi)隨機生成不同規(guī)模的需求點分別運行模型，各時段車速依然選擇表2中數(shù)據(jù)，除需求點的配送信息外其他參數(shù)均保持不變，計算結(jié)果如表7。

由表7可知，生成的10組對照數(shù)據(jù)中，在時變路網(wǎng)下的配送成本均低于傳統(tǒng)靜態(tài)路網(wǎng)下的配送成本。配送成本與需求點最終的聚類簇數(shù)有關(guān)，聚類簇數(shù)越多，則配送成本相對越高，這是由于聚類簇數(shù)反映了需求點的分布情況，簇數(shù)越多說明需求點分布較廣，增加了車輛的行駛距離，也相應(yīng)地增加了成本。通過這10組數(shù)據(jù)可以看出，在聚類簇數(shù)差別不大的情況下，需求點規(guī)模越大，基于時變路網(wǎng)規(guī)劃出的配送路徑所節(jié)約的配送成本越多。

表7 不同規(guī)模成本對比Table 7 Comparison of different scale costs

5 結(jié)論

本文研究時變路網(wǎng)下的電動冷藏車輛路徑優(yōu)化問題。首先，在傳統(tǒng)的VRPTW模型的基礎(chǔ)上，引入時變路網(wǎng)理論，設(shè)計與行駛時段相關(guān)的車速計算公式，并針對電動冷藏車電池容量小、充電頻繁等短板，建立時變路網(wǎng)下考慮充電站的多時間窗約束的電動車輛路徑優(yōu)化模型；其次，運用AP聚類算法對配送區(qū)域進行劃分以提高配送效率，并針對遺傳算法的缺陷，設(shè)計改進的遺傳算法對模型進行求解，以增強其尋優(yōu)能力；最后，通過對比實驗對模型的可行性進行驗證。對固定速度下與時變速度下的配送成本進行對比分析，結(jié)果表明，與固定速度相比，時變速度下的配送方案可以使配送成本減少12.201%，為進一步驗證模型的普適性，選取10組不同規(guī)模的案例進行驗證，計算結(jié)果表明時變路網(wǎng)下的配送成本均低于靜態(tài)路網(wǎng)下的配送成本。因此，本文基于交通的時變特性所建立的路徑優(yōu)化模型可以科學地規(guī)劃配送路徑，有效降低配送成本，對于企業(yè)配送方案的制定提供了決策支持，具有一定的現(xiàn)實意義。