魏東慶，趙 旭

（大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026）

1 引言

配送市場(chǎng)競(jìng)爭(zhēng)的加劇以及客戶(hù)對(duì)配送時(shí)間準(zhǔn)確性的要求不斷提高，給配送業(yè)務(wù)帶來(lái)了很大的影響。為了加強(qiáng)配送業(yè)務(wù)的管理，降低配送成本，提高配送效率，國(guó)內(nèi)外對(duì)車(chē)輛路徑問(wèn)題（Vehicle Routing Problem,VRP）做了大量研究。最早是由Dantzig和Ramser[1]于1959年首次提出，傳統(tǒng)的車(chē)輛路徑問(wèn)題可解釋為一組車(chē)輛從一個(gè)配送中心出發(fā)，為多個(gè)地理位置分散的顧客點(diǎn)提供運(yùn)輸服務(wù)，使得每個(gè)顧客的需求得到滿(mǎn)足，并在業(yè)務(wù)完成后所有車(chē)輛返回原配送中心，同時(shí)實(shí)現(xiàn)在運(yùn)輸過(guò)程中車(chē)輛行駛里程最短、運(yùn)輸總成本最低、耗費(fèi)時(shí)間最短等目標(biāo)。

由于要滿(mǎn)足實(shí)際生活的需求，應(yīng)用到現(xiàn)實(shí)場(chǎng)景中，VRP模型也更加復(fù)雜。帶有時(shí)間窗的車(chē)輛路徑問(wèn)題（VRPTW）是VRP的一個(gè)重要分支，最早由Solomon[2]于1987年提出，并給出了該問(wèn)題的經(jīng)典算例。經(jīng)典帶時(shí)間窗的車(chē)輛路徑問(wèn)題一般包含最早服務(wù)時(shí)間和最晚服務(wù)時(shí)間，表示為[ai,bi],分為帶硬時(shí)間窗、軟時(shí)間窗和模糊時(shí)間窗的VRP問(wèn)題。這些問(wèn)題具有確定性的假設(shè)，如需求、容量、配送中心和時(shí)間窗等信息。但實(shí)際配送業(yè)務(wù)中有些信息無(wú)法提前準(zhǔn)確預(yù)知，例如車(chē)輛的平均行駛速度。而根據(jù)以往經(jīng)驗(yàn)可以大致判斷出車(chē)輛的平均行駛速度會(huì)在某一個(gè)區(qū)間內(nèi)波動(dòng)，由此引起車(chē)輛的行駛時(shí)間隨機(jī)，比如到某個(gè)客戶(hù)點(diǎn)的時(shí)間可能是20到30分鐘，所以研究平均隨機(jī)行駛時(shí)間的VRPTW問(wèn)題更符合實(shí)際情況。李兵飛[3]等構(gòu)建了不確定條件下速度時(shí)變VRPTW問(wèn)題模型，并設(shè)計(jì)了一種改進(jìn)的雙重進(jìn)化人工蜂群算法求解該模型。吳瑤，馬祖軍[4]考慮實(shí)際配送中路網(wǎng)交通的時(shí)變性，建立了以系統(tǒng)總成本最小為目標(biāo)、帶時(shí)間窗的易腐食品生產(chǎn)配送問(wèn)題優(yōu)化模型，并設(shè)計(jì)了一種混合遺傳算法求解。李妍峰[5]等結(jié)合交通流量特征研究行駛時(shí)間隨機(jī)的VRP。Laporte[6]等研究了隨機(jī)旅行時(shí)間的VRP，建立了三種數(shù)學(xué)規(guī)劃模型并設(shè)計(jì)了分支裁剪算法進(jìn)行求解。郭強(qiáng)[7]等在Laporte等的研究基礎(chǔ)上，提出了一個(gè)考慮車(chē)輛容量有限的隨機(jī)旅行時(shí)間VRP的機(jī)會(huì)約束模型，并構(gòu)造了求解該模型的遺傳算法。候鈴娟，周泓等[8]研究了不確定需求和旅行時(shí)間下的車(chē)輛路徑問(wèn)題，并設(shè)計(jì)了改進(jìn)遺傳算法進(jìn)行求解。李鋒，魏瑩[9]等研究了隨機(jī)旅行時(shí)間的CVRP問(wèn)題，并設(shè)計(jì)了混合遺傳算法進(jìn)行求解。石建力，張錦[10]研究了行駛時(shí)間隨機(jī)的分批配送車(chē)輛路徑問(wèn)題模型與方法，并且設(shè)計(jì)了改進(jìn)的粒子群優(yōu)化算法進(jìn)行求解?；谝陨戏治霭l(fā)現(xiàn)，大多數(shù)學(xué)者在研究VRPTW問(wèn)題時(shí)都是直接研究時(shí)變速度或隨機(jī)行駛時(shí)間，而不是直接考慮速度波動(dòng)對(duì)配送時(shí)間以及整個(gè)配送路徑的影響，這樣就會(huì)造成數(shù)據(jù)量過(guò)大以及不夠準(zhǔn)確，而且還會(huì)造成求解困難，降低效率。因此，本文提出了考慮平均行駛速度波動(dòng)的城市快遞配送車(chē)輛路徑問(wèn)題研究，引入了車(chē)輛的平均速度分布函數(shù)，根據(jù)約束條件建立相應(yīng)的模型，設(shè)計(jì)改進(jìn)遺傳算法進(jìn)行求解，最后通過(guò)具體實(shí)例對(duì)模型進(jìn)行驗(yàn)證。

2 問(wèn)題描述

基于配送成本最低的城市快遞車(chē)輛路徑問(wèn)題可以描述為：由單一配送中心向多個(gè)具有不同需求量的客戶(hù)點(diǎn)派遣相同類(lèi)型的車(chē)輛進(jìn)行配送，考慮車(chē)輛固定成本、車(chē)輛運(yùn)輸成本、時(shí)間成本（包括車(chē)輛早到的時(shí)間損失成本和車(chē)輛晚到的時(shí)間懲罰成本）。

模型的基本假設(shè)條件如下：

（1）配送中心只有1個(gè)且位置已知，需要配送的物資量充足。

（2）所有配送車(chē)輛載重量及各項(xiàng)性能相同。

（3）車(chē)輛的起點(diǎn)和終點(diǎn)都在配送中心。

（4）所有客戶(hù)位置、需求量及要送達(dá)的軟時(shí)間窗已知。

（5）每個(gè)客戶(hù)僅有1輛車(chē)為其配送，且所有客戶(hù)必須配送到。

（6）除配送外車(chē)輛無(wú)其它時(shí)間方面的需求。

（7）假設(shè)車(chē)輛都從配送中心出發(fā)，配送完成后返回配送中心，不考慮車(chē)輛作業(yè)時(shí)間，早到車(chē)輛只計(jì)算時(shí)間成本，不在客戶(hù)點(diǎn)等待。

3 模型建立

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

本文研究帶有軟時(shí)間窗的VRP問(wèn)題，參數(shù)設(shè)置如下：

D：配送中心，用自然數(shù)0表示；

F(V)：車(chē)輛的平均速度分布函數(shù)，在此假設(shè)服從均勻分布；

V：車(chē)輛行駛速度；

Vmax：車(chē)輛以往配送時(shí)可達(dá)到的最大平均行駛速度；

Vmin：車(chē)輛以往配送時(shí)可到達(dá)的最小平均行駛速度；

Tk：車(chē)輛k離開(kāi)配送中心的時(shí)間；

Tik：車(chē)輛k到達(dá)客戶(hù)點(diǎn)i的時(shí)間；

g(Tik)：車(chē)輛k到達(dá)客戶(hù)點(diǎn)i的時(shí)間概率分布函數(shù)；

minTik：車(chē)輛正常行駛預(yù)計(jì)到達(dá)節(jié)點(diǎn)i的最早達(dá)到時(shí)間；

maxTik：車(chē)輛正常行駛預(yù)計(jì)到達(dá)節(jié)點(diǎn)i的最晚到達(dá)時(shí)間；

Δc：車(chē)輛使用的固定成本；

ce：車(chē)輛早到單位時(shí)間損失成本；

cl：車(chē)輛晚到單位時(shí)間懲罰成本；

cv：車(chē)輛的單位距離運(yùn)輸成本；

djk：車(chē)輛k從配送中心到客戶(hù)點(diǎn)j的總行駛距離；

Wi(Tik)：車(chē)輛到達(dá)客戶(hù)點(diǎn)i的時(shí)間損失或懲罰成本；

xijk：決策變量，當(dāng)節(jié)點(diǎn)i到j(luò)由車(chē)輛k配送時(shí)，xijk=1,否則為0；

yik：決策變量，當(dāng)客戶(hù)點(diǎn)i由車(chē)輛k配送時(shí)，yik=1，否則為0。

3.2 模型建立

基于上述分析，建立以配送成本最低的路徑規(guī)劃模型，車(chē)輛固定成本、車(chē)輛運(yùn)輸成本、時(shí)間成本分別記為 Z1，Z2，Z3，其中：

求解積分表達(dá)式，得到新的時(shí)間成本表達(dá)式為：

所以，目標(biāo)函數(shù)及約束如下：

其中，式（1）表示車(chē)輛固定成本；式（2）表示車(chē)輛的運(yùn)輸成本；式（3）表示車(chē)輛的時(shí)間損失和懲罰成本；式（4）表示配送總成本最低的目標(biāo)函數(shù)；式（5）表示車(chē)輛的載重量約束；式子（6）表示每個(gè)客戶(hù)都會(huì)被服務(wù)到；式（7）、（8）表示每個(gè)客戶(hù)不會(huì)被重復(fù)訪(fǎng)問(wèn)；式（9）表示消除子回路約束；式（10）表示車(chē)輛從配送中心出發(fā)，配送完成后返回配送中心,且每輛車(chē)只有一條線(xiàn)路；式（11）表示進(jìn)出平衡約束；式（12）表示車(chē)輛從配送中心到j(luò)點(diǎn)時(shí)所行駛的距離；式（13）表示車(chē)輛k到達(dá)客戶(hù)點(diǎn)i的時(shí)間表達(dá)式；式（14）、（15）為模型中的自變量。

4 模型求解

本文采用遺傳算法求解，并結(jié)合模型特點(diǎn)對(duì)遺傳算法進(jìn)行改進(jìn)，具體步驟如下：

4.1 染色體編碼

染色體編碼方式的好壞在很大程度上會(huì)影響遺傳算法的運(yùn)算效率和運(yùn)算結(jié)果，因此選擇合適的編碼方式對(duì)于遺傳算法的實(shí)現(xiàn)非常重要。

本文采用較為直觀的染色體編碼方式進(jìn)行編碼，具體編碼方式如下：對(duì)n個(gè)需要配送的客戶(hù)點(diǎn)依次進(jìn)行編號(hào)，分別用自然數(shù)1,2,...,n表示，配送中心用自然數(shù)0表示，m為確定的車(chē)輛數(shù)。采用自然數(shù)編碼方式的染色體可表示為{0,C1,...,0,C2,...,C3,0,...Cn,0}。其中，Ci表示第i個(gè)客戶(hù)點(diǎn)。整個(gè)染色體編碼串的長(zhǎng)度為n+m+1。在染色體中兩個(gè)0之間代表一條子路徑，即配送車(chē)輛從配送中心出發(fā)完成對(duì)最后客戶(hù)點(diǎn)的配送任務(wù)后返回配送中心。例如，染色體編碼串{0,1,2,3,0,4,5,6,0,7,8,9,0}表示有3輛車(chē)負(fù)責(zé)對(duì)9個(gè)客戶(hù)點(diǎn)進(jìn)行配送任務(wù)，共有3條子路徑，具體安排如下：

子路徑1：0→1→2→3→0

子路徑2：0→4→5→6→0

子路徑3：0→7→8→9→0

4.2 初始種群的選取

對(duì)于帶時(shí)間窗的VRP問(wèn)題，初始解的質(zhì)量對(duì)算法迭代效率有重要影響，本文采用基于最小成本的最鄰近算法生成初始解，在此基礎(chǔ)上引入車(chē)輛載重限制，構(gòu)造高質(zhì)量的初始解。具體操作如下：

（1）路徑初始點(diǎn)為配送中心0，路徑的第一個(gè)客戶(hù)點(diǎn)是客戶(hù)中心集合{1,2,...,30}隨機(jī)取得的5個(gè)客戶(hù)點(diǎn)中成本最小的客戶(hù)點(diǎn)j，計(jì)算前一個(gè)配送中心0到當(dāng)前j路徑累加的客戶(hù)需求Q1；

（2）客戶(hù)中心集合{1,2,...,30}移除j；

（3）判斷需求Q1是否超過(guò)車(chē)輛最大載重量，如果是，則路徑移除該點(diǎn)，客戶(hù)中心集合{1,2,...,30}加入該點(diǎn)j，并且配送中心0到當(dāng)前j路徑隨機(jī)一個(gè)0插入前面序列，否則繼續(xù)進(jìn)行；

（4）以此類(lèi)推隨機(jī)選擇5個(gè)客戶(hù)點(diǎn)中的最小成本的點(diǎn)作為下一個(gè)客戶(hù)中心。

4.3 適應(yīng)度函數(shù)的設(shè)定

適應(yīng)度函數(shù)是評(píng)價(jià)個(gè)體優(yōu)劣的重要指標(biāo)，可以區(qū)分群體中個(gè)體優(yōu)劣并作出取舍。適應(yīng)度函數(shù)值越大的個(gè)體就說(shuō)明適應(yīng)環(huán)境的能力越強(qiáng)，表明其越優(yōu)，反之則越差。遺傳算法的適應(yīng)度函數(shù)可由目標(biāo)函數(shù)轉(zhuǎn)換而來(lái)，由于本文配送的目標(biāo)函數(shù)是配送總成本最低，因此可以選擇目標(biāo)函數(shù)的倒數(shù)來(lái)作為種群個(gè)體的適應(yīng)度函數(shù)fitness。當(dāng)配送成本越低即目標(biāo)函數(shù)值越小時(shí)，適應(yīng)度函數(shù)值fitness也就越大，表明其適應(yīng)性越好，被遺傳到下一代的概率也就越大。

式（16）中的Zi為染色體i對(duì)應(yīng)的目標(biāo)函數(shù)值。

4.4 停止準(zhǔn)則

本文采用最大迭代次數(shù)停止準(zhǔn)則，若迭代次數(shù)達(dá)到所設(shè)定的最大迭代次數(shù)則停止迭代，輸出運(yùn)算結(jié)果。

4.5 遺傳操作

4.5.1 選擇算子。種群個(gè)體的選擇是建立在種群個(gè)體適應(yīng)度評(píng)價(jià)的基礎(chǔ)上的，以一定的概率從種群中選擇若干個(gè)個(gè)體作為父代染色體，遵循優(yōu)勝劣汰的原則。常用的方法有輪盤(pán)賭選擇、隨機(jī)競(jìng)爭(zhēng)選擇、精英選擇、期望值方法、排序選擇法、比例選擇方法等。目前選擇算子常用基于適應(yīng)度比例輪盤(pán)賭選擇法。輪盤(pán)賭方法是利用種群中的個(gè)體適應(yīng)度函數(shù)值占總最大值的比例來(lái)決定選擇概率的放回式隨機(jī)采樣方法。其原理類(lèi)似于多盤(pán)操作原理：將輪盤(pán)劃分為若干個(gè)區(qū)域，根據(jù)每一個(gè)區(qū)域面積的大小來(lái)標(biāo)注所占的比值，當(dāng)旋轉(zhuǎn)的輪盤(pán)停止時(shí)，指針?biāo)甘镜膮^(qū)域就是所選擇的適應(yīng)度值對(duì)應(yīng)的個(gè)體，如圖1所示。

圖1 輪盤(pán)賭選擇法

輪盤(pán)賭選擇法可以保證種群多樣性但同時(shí)隨機(jī)性較大，難以保證算法收斂。本文結(jié)合模型分析，在輪盤(pán)賭算子的基礎(chǔ)上引入最優(yōu)保存策略，防止適應(yīng)度高的個(gè)體因?yàn)殡S機(jī)的原因不被選中，避免適應(yīng)度高的個(gè)體被后續(xù)的遺傳操作改變，使群體向最優(yōu)化方向進(jìn)化，提高收斂能力。具體選擇操作為：

（1）計(jì)算個(gè)體的適應(yīng)度f(wàn)i，將每一代具有最大適應(yīng)度的個(gè)體直接進(jìn)行保存；

（2）計(jì)算每個(gè)個(gè)體被遺傳到下一代中的概率：

（3）計(jì)算個(gè)體的累計(jì)概率：

（4）在[0,1]之間隨機(jī)產(chǎn)生一個(gè)均勻分布的數(shù)值t，若t＜a1,則選擇個(gè)體1進(jìn)入子代種群，若ak-1＜t≤ak,選擇個(gè)體k進(jìn)入子代總?cè)骸?/p>

（5）重復(fù)步驟（4），直到子代種群選擇完畢生成新一代種群，并將適應(yīng)度最低的個(gè)體用父代適應(yīng)度最高的染色體進(jìn)行替換。

4.5.2 交叉算子。交叉操作是指兩個(gè)父代個(gè)體之間某個(gè)或某些基因位進(jìn)行交換，從而生成新個(gè)體的操作。交叉操作能夠改變父代個(gè)體中的基因，是產(chǎn)生新個(gè)體的主要來(lái)源。在交叉操作中，種群內(nèi)部染色體之間通過(guò)交叉生成新一代染色體，能在最大范圍內(nèi)搜索最優(yōu)解。另一方面，具有優(yōu)良基因的個(gè)體需要保留，避免交叉操作破壞優(yōu)良的基因。因此，本文交叉算子采用適合自然數(shù)編碼的部分映射交叉法（Partial-Mapped Crossover,PMX），具體步驟為：

（1）隨機(jī)選擇一對(duì)染色體（父代）中幾個(gè)基因的起止位置（兩染色體被選位置相同）：

（3）做沖突檢測(cè)，根據(jù)交換的兩組基因建立一個(gè)映射關(guān)系，如下所示，以1-6-3這一映射關(guān)系為例，可以看到第二步結(jié)果中子代1存在兩個(gè)基因1，這時(shí)將其通過(guò)映射關(guān)系轉(zhuǎn)變?yōu)榛?，以此類(lèi)推至沒(méi)有沖突為止，最后所有沖突的基因都會(huì)經(jīng)過(guò)映射，確保形成的新一代子基因無(wú)沖突。

PMX與傳統(tǒng)的單點(diǎn)交叉或多點(diǎn)交叉相比，在一定程度上保持了種群的多樣性，降低了算法在求解過(guò)程中易陷入局部最優(yōu)解的可能，并且使算法的搜索機(jī)制較好的遍歷所有的客戶(hù)點(diǎn)，以尋求最優(yōu)解。

4.5.3 變異算子。變異算子指的是染色體中某一位或者某幾位的基因值發(fā)生改變，轉(zhuǎn)變?yōu)槠渌任换?，從而產(chǎn)生新的個(gè)體。變異算子能夠微調(diào)交叉算子生成新的個(gè)體，從而改善算法的局部搜索能力，增加種群的多樣性，并可以防止算法出現(xiàn)過(guò)早收斂。傳統(tǒng)的變異算子有邊界變異、均勻變異、高斯變異等。邊界變異適用于最優(yōu)點(diǎn)或接近可行解問(wèn)題，而所謂的均勻變異是滿(mǎn)足一定區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)，并以一個(gè)較小的概率來(lái)替代個(gè)體編碼中某一個(gè)基因座上的原個(gè)體基因值，該方法主要適用于算法的初級(jí)運(yùn)行階段；高斯變異適用于在原個(gè)體附近的某個(gè)范圍區(qū)間進(jìn)行重點(diǎn)搜索。本文根據(jù)自然數(shù)編碼的特點(diǎn)，設(shè)計(jì)的變異算子具體操作如下：

（1）首先隨機(jī)產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)r；（2）判斷隨機(jī)數(shù)r是否小于等于Pm；

（3）若滿(mǎn)足條件（2），隨機(jī)產(chǎn)生兩個(gè)基因變異位；

（4）交換兩個(gè)變異位置的基因。

示例如下：

4.5.4 關(guān)鍵參數(shù)設(shè)計(jì)。在遺傳算法中，交叉概率和變異概率的選擇一定程度上會(huì)影響算法的性能，直接影響算法的收斂性。交叉概率越大，新個(gè)體產(chǎn)生的速度就越快。然而，交叉概率過(guò)大時(shí)遺傳模式被破壞的可能性也越大，使得具有高適應(yīng)度的個(gè)體結(jié)構(gòu)很快就會(huì)被破壞；如果交叉概率過(guò)小，會(huì)使搜索過(guò)程非常緩慢，甚至停滯不前。對(duì)于變異概率來(lái)說(shuō)，如果其取值過(guò)小，就不易產(chǎn)生新的個(gè)體結(jié)構(gòu)，如果其取值過(guò)大，遺傳算法就變成了純粹的隨機(jī)搜索算法。對(duì)于不同的優(yōu)化問(wèn)題，需要反復(fù)試驗(yàn)來(lái)確定交叉概率和變異概率，一般很難找到適應(yīng)于每個(gè)問(wèn)題的最佳值。

Srinvivas[11]等提出了一種自適應(yīng)遺傳算法，交叉和變異概率能夠隨適應(yīng)度改變而自動(dòng)改變。當(dāng)種群各個(gè)體適應(yīng)度趨于一致或者趨于局部最優(yōu)時(shí)，增大交叉和變異概率。當(dāng)群體適應(yīng)度比較分散時(shí)，對(duì)適應(yīng)度較高的個(gè)體，降低其交叉概率和變異概率，使該個(gè)體得以保護(hù)進(jìn)入下一代。而對(duì)于低于平均適應(yīng)度的個(gè)體，會(huì)由于相對(duì)較高的交叉和變異概率而被淘汰。自適應(yīng)遺傳算法中交叉概率Pc和變異概率Pm的計(jì)算公式如下：

其中，fmax表示群體中最大適應(yīng)度值；favg表示群體平均適應(yīng)度值；fi表示要交叉的兩個(gè)個(gè)體中適應(yīng)度值較大的；fj'表示要變異個(gè)體的適應(yīng)度值，k1＜ k2，k3＜ k4。

算法流程圖如圖2所示。

5 算例分析

5.1 數(shù)據(jù)準(zhǔn)備

為了驗(yàn)證本文所建立的模型及設(shè)計(jì)算法的有效性，本文選擇了路徑規(guī)劃領(lǐng)域的Solomon測(cè)試集中的部分?jǐn)?shù)據(jù)作為測(cè)試算例，并根據(jù)本文需求對(duì)其進(jìn)行一定的數(shù)據(jù)調(diào)整和補(bǔ)充。算例如下：某時(shí)間段內(nèi)需要配送的客戶(hù)數(shù)為30個(gè)，配送中心獲知的客戶(hù)信息表見(jiàn)表1，客戶(hù)編號(hào)為1,2,…,30，0表示配送中心。配送中心最多提供5臺(tái)車(chē)執(zhí)行配送任務(wù)，每臺(tái)車(chē)最大承載量為300，具體信息見(jiàn)表1。

根據(jù)客戶(hù)的坐標(biāo)信息，利用Excel繪制出了各節(jié)點(diǎn)的散點(diǎn)圖，其中帶陰影圓形標(biāo)記部分為配送中心，如圖3所示。

圖2 改進(jìn)遺傳算法流程圖

圖3 節(jié)點(diǎn)坐標(biāo)散點(diǎn)圖

表1 客戶(hù)及配送點(diǎn)信息匯總

5.2 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

根據(jù)本文設(shè)計(jì)的求解算法，在windows10系統(tǒng)計(jì)算機(jī)（Intel(R)Core(TM)i5 1.80GHz,內(nèi)存4GB）上基于java仿真軟件進(jìn)行操作，通過(guò)編程實(shí)現(xiàn)對(duì)模型的求解。改進(jìn)遺傳算法實(shí)驗(yàn)參數(shù)設(shè)定：種群規(guī)模80，最大迭代次數(shù)600，交叉概率pc上界0.85，下界0.52；變異概率上界0.2，下界0.02；在以上算例基礎(chǔ)上，對(duì)本文與配送成本相關(guān)參數(shù)進(jìn)行設(shè)定，見(jiàn)表2。

表2 相關(guān)參數(shù)

5.3 測(cè)試結(jié)果與分析

獲取客戶(hù)的信息后，利用本文提出的改進(jìn)遺傳算法對(duì)模型進(jìn)行運(yùn)算，得到的最優(yōu)解為：===＞0,16,14,19,7,26,24,20,25,18,0===＞0,21,8,1,29,28,17,27,9,12,22,23,0===＞0,3,30,11,4,13,5,10,15,2,6,0。 總 配 送成本為1 552，車(chē)輛軌跡如圖4所示。

圖4 配送軌跡圖

配送車(chē)輛訪(fǎng)問(wèn)各客戶(hù)點(diǎn)的順序描述如下：

路徑1：配送中心-客戶(hù)16-客戶(hù)14-客戶(hù)19-客戶(hù)7-客戶(hù)26-客戶(hù)24-客戶(hù)20-客戶(hù)25-客戶(hù)18,-配送中心；

路徑2：配送中心-客戶(hù)21-客戶(hù)8-客戶(hù)1-客戶(hù)29-客戶(hù)28-客戶(hù)17-客戶(hù)27-客戶(hù)9-客戶(hù)12-客戶(hù)22-客戶(hù)23-配送中心；

路徑3：配送中心-客戶(hù)3-客戶(hù)30-客戶(hù)11-客戶(hù)4-客戶(hù)13-客戶(hù)5-客戶(hù)10-客戶(hù)15-客戶(hù)2-客戶(hù)6-配送中心。

為了更好地了解算法的求解性能，在進(jìn)行車(chē)輛配送路徑求解的過(guò)程中繪制了目標(biāo)函數(shù)結(jié)果優(yōu)化迭代圖，通過(guò)觀察算法求得的最優(yōu)解的迭代次數(shù)對(duì)算法設(shè)計(jì)的有效性進(jìn)行衡量?？梢钥吹?，在第450代時(shí)最優(yōu)解已趨近收斂，如圖5所示。

5.4 影響評(píng)估

為了與車(chē)速恒定時(shí)的配送成本作比較，本文選取了運(yùn)算過(guò)程中成本最低的10條路徑配送成本為基數(shù)，將10次成本的平均值作為配送成本，見(jiàn)表3。

圖5 最優(yōu)解進(jìn)化圖

表3 速度波動(dòng)配送成本

假設(shè)車(chē)速波動(dòng)非常小，近似為恒定，為17.5，其余數(shù)據(jù)均不變，利用本文所設(shè)計(jì)的遺傳算法進(jìn)行求解，得到的最優(yōu)路線(xiàn)為：0,6,13,5,10,2,3,8,30,11,1,4,29,28,27,22,0===＞0,9,17,25,24,7,14,18,20,12,21,26,23,15,19,16,0,最低配送成本為1 479，依然選取運(yùn)算過(guò)程中成本最低的10條路徑配送成本作為基數(shù)，并求平均值，見(jiàn)表4。

從測(cè)試結(jié)果中的數(shù)據(jù)可以看出，在其他參數(shù)不變的條件下，當(dāng)車(chē)速近似為恒定值17.5，車(chē)輛數(shù)為2，10條最低線(xiàn)路配送平均成本為1 526.5；當(dāng)車(chē)速在區(qū)間[15,20]服從均勻分布波動(dòng)時(shí)，車(chē)輛數(shù)為3，平均配送成本為1 614.9，相差約5.4%。

6 結(jié)語(yǔ)

本文針對(duì)帶時(shí)間窗的城市快遞配送車(chē)輛路徑問(wèn)題，考慮了車(chē)輛實(shí)際行駛時(shí)平均速度存在一定波動(dòng)的情況，建立了以總配送成本最低為目標(biāo)函數(shù)的模型，并根據(jù)模型特點(diǎn)設(shè)計(jì)改進(jìn)遺傳算法進(jìn)行求解。通過(guò)對(duì)算例分析可知，車(chē)輛的行駛速度波動(dòng)會(huì)對(duì)車(chē)輛的配送成本和線(xiàn)路產(chǎn)生一定的影響，研究成果可以為實(shí)際配送路徑規(guī)劃提供指導(dǎo)。為簡(jiǎn)化計(jì)算，本文將速度波動(dòng)形式設(shè)為平均分布，但是車(chē)輛實(shí)際行駛速度波動(dòng)情況及分布函數(shù)需要根據(jù)以往經(jīng)驗(yàn)及數(shù)學(xué)理論進(jìn)行判斷，有待進(jìn)一步研究。