基于時(shí)間窗指派的污染路徑問題

葛顯龍,冉小芬

(1.重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074；2.重慶交通大學(xué) 智能物流網(wǎng)絡(luò)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400074)

0 引言

為提高物流配送效率、響應(yīng)國家減排政策，學(xué)者們對(duì)長期固定的物流配送方案中需求時(shí)間窗的合理性展開研究。現(xiàn)有的分銷網(wǎng)絡(luò)中，很多零售商店對(duì)貨物的交貨時(shí)間幾乎總是在一周的同一天的同一時(shí)間，并且會(huì)維持一年時(shí)間[1]。大多交貨的時(shí)間是在預(yù)定的時(shí)間窗之內(nèi)，這樣預(yù)定的時(shí)間窗一般是因?yàn)殚L期的合作后約定俗成的一種決策，而在不確定客戶需求情況下指派的時(shí)間窗，稱為時(shí)間窗指派問題。在固定的時(shí)間進(jìn)行配送，對(duì)客戶或者零售商而言，可以對(duì)庫存進(jìn)行有效管理和人員的合理安排;對(duì)物流企業(yè)或經(jīng)銷商而言，可以減少配送的可變性，提高配送效率，進(jìn)而節(jié)省成本[2]。而當(dāng)今的物流配送，不只是考慮單方面(如配送時(shí)間、預(yù)期成本要求)的配送目標(biāo)，企業(yè)也增強(qiáng)了減排意識(shí)，運(yùn)輸領(lǐng)域是溫室氣體最大的來源之一，是有關(guān)節(jié)能減排戰(zhàn)略方面必須關(guān)注的一個(gè)環(huán)節(jié)，而在污染路徑問題中，車輛油耗是碳排放的一個(gè)重要標(biāo)準(zhǔn)。為此，本文基于時(shí)間窗指派對(duì)污染路徑問題進(jìn)行研究。

據(jù)文獻(xiàn)分析，Spliet等[1]引入了時(shí)間窗指派車輛路徑問題(Time Window Assignment Vehicle Routing Problem,TWAVRP)，該問題是在不確定客戶需求的情況下對(duì)客戶進(jìn)行指派配送時(shí)間窗，當(dāng)?shù)弥蛻粜枨蠛?，?duì)客戶進(jìn)行有目標(biāo)的車輛配送，以最小化期望總運(yùn)輸成本對(duì)連續(xù)的時(shí)間窗指派車輛路徑問題進(jìn)行研究;Spliet等[2]以最小化期望總運(yùn)輸成本離散的時(shí)間窗指派車輛路徑問題進(jìn)行研究，并使用分支定價(jià)和切割算法對(duì)問題進(jìn)行求解;Dalmeijer等[3]在時(shí)間窗指派車輛路徑問題中引入優(yōu)先不等式，研究了最小化預(yù)期旅行成本;Subramanyam等[4]開發(fā)了一種新的場景分解算法來解決該隨機(jī)模型，適應(yīng)連續(xù)和離散的可行時(shí)間窗口分配集;Spliet等[5]在與時(shí)間相關(guān)的時(shí)間窗指派車輛路徑問題中，考慮了與時(shí)間相關(guān)的旅行時(shí)間，提出了旅行時(shí)間計(jì)算方法，其目標(biāo)函數(shù)是使得預(yù)期的運(yùn)輸總成本包括弧上的旅行成本和駕駛員工資最小化。上述的研究均以最小化總預(yù)期成本的單目標(biāo)進(jìn)行的，并未考慮給客戶指派時(shí)間窗后對(duì)配送時(shí)間的影響。

有關(guān)車輛配送的另一方面需要考慮的因素就是考慮車輛排放的問題，其被稱為污染路徑問題(Pollution Routing Problem, PRP)。Bektas等[6]首次提出的污染路徑問題，其中確定了每條弧(i,j)的最優(yōu)行進(jìn)速度，以最小化包括燃料消耗、排放和駕駛員成本的綜合目標(biāo)函數(shù);Xiao等[7]根據(jù)車輛空載與有效載荷燃料消耗率的關(guān)系，考慮載重與行駛距離因素，從而計(jì)算車輛的燃料消耗;Eshtehadi等[8]在需求和旅行時(shí)間不確定的情況下對(duì)PRP進(jìn)行研究，提出了3種情況下的魯棒優(yōu)化技術(shù)。目前，有關(guān)研究同時(shí)考慮碳排放和配送時(shí)間的文獻(xiàn)較少，因此本文主要集中于碳排放和配送時(shí)間兩方面的研究。二氧化碳排放量與車輛的燃料消耗率成正比，而車輛的燃料消耗率又取決于車輛類型、車輛的速度、載荷、加速度、環(huán)境和交通擁堵等相關(guān)參數(shù)[6]。根據(jù)文獻(xiàn)[9]的研究，每輛車都有一個(gè)最佳的速度，產(chǎn)生最低的燃料消耗，但一般這個(gè)速度低于車輛駕駛者偏好的速度，減少配送時(shí)間可以通過較高的行駛速度實(shí)現(xiàn)，但與減少碳排放產(chǎn)生了沖突，因此提出了多目標(biāo)優(yōu)化的解決方法，其中包含加權(quán)法、歸一化權(quán)重法、ε-約束法和混合法(結(jié)合了自適應(yīng)加權(quán)和ε-約束法);Kumar等[10]構(gòu)建了總運(yùn)營成本和總排放最小的多目標(biāo)函數(shù)，提出一種混合自適應(yīng)粒子群優(yōu)化方法解決帶時(shí)間窗PRP(Pollution Routing Problem with Time Window, PRP-TW);Suzuki[11]在多目標(biāo)污染路徑問題中考慮了實(shí)際的PRP，運(yùn)用模擬退火和禁忌搜索的混合啟發(fā)式算法進(jìn)行求解，先使用模擬退火近似帕累托邊界，再使用禁忌搜索改進(jìn)每個(gè)元素的邊界;李進(jìn)等[12]利用一種基于劃分的多起點(diǎn)禁忌搜索算法對(duì)多車型低碳車輛路徑問題進(jìn)行求解，增強(qiáng)了算法搜索能力的多樣性;王君等[13]研究了模糊預(yù)約時(shí)間窗的車輛路徑優(yōu)化問題，先采用隨機(jī)車輛配載的方式生成初始解，再使用可行鄰域結(jié)構(gòu)與并行禁忌搜索的禁忌搜索算法求解多目標(biāo)模型，最后得到帕累托最優(yōu)解;趙燕偉等[14]采用一種基于量子進(jìn)化算法和粒子群分段優(yōu)化的算法解決帶有時(shí)間窗的隨機(jī)需求車輛路徑問題的多目標(biāo)優(yōu)化問題;陳玉光等[15]在車輛配送中研究了準(zhǔn)時(shí)送貨與最小油耗問題，運(yùn)用改進(jìn)的粒子群算法解決了配送時(shí)間和油耗最少的雙目標(biāo)模型。

為此，針對(duì)時(shí)間窗指派污染路徑問題(Time Window Assignment Pollution Routing Problem, TWAPRP)，同時(shí)考慮成本(碳排放成本和旅行成本)與配送時(shí)間最小化的雙目標(biāo)優(yōu)化，建立TWAPRP雙目標(biāo)模型；并設(shè)計(jì)了混合遺傳—禁忌搜索算法對(duì)TWAPRP模型進(jìn)行求解；最后根據(jù)需求場景模擬需求不確定性，進(jìn)行數(shù)值實(shí)驗(yàn)，從而驗(yàn)證模型與算法的有效性和適用性。

1 問題描述

如圖1所示為時(shí)間窗指派前后兩種不同配送方案的示意圖。圖1a和圖1b分別表示具有1個(gè)配送中心、8個(gè)常配客戶的配送網(wǎng)絡(luò)，圖1b中客戶集下的數(shù)字代表客戶的時(shí)間窗。圖1a為沒有給客戶指派時(shí)間窗前的配送方案，由于客戶對(duì)貨物的配送時(shí)間并沒有很強(qiáng)的要求，只是以物流企業(yè)的配送到達(dá)時(shí)間為準(zhǔn)，經(jīng)過長期由同一物流企業(yè)配送后，客戶與配送企業(yè)會(huì)根據(jù)業(yè)務(wù)運(yùn)作經(jīng)驗(yàn)約定配送的時(shí)間窗。為滿足到達(dá)時(shí)間一致性，在不確定客戶需求的情況下，物流企業(yè)根據(jù)歷史數(shù)據(jù)確定時(shí)間窗寬度，以便給客戶指派一個(gè)時(shí)間窗(如圖1b)。當(dāng)客戶實(shí)際訂單生成后，則重新優(yōu)化新的配送方案，進(jìn)而滿足物流企業(yè)在配送過程中的碳排放成本和旅行成本。

2 模型建立

2.1 時(shí)間窗指派策略與碳排放成本的計(jì)算

(1)時(shí)間窗指派策略

在TWAPRP的第一階段，對(duì)客戶進(jìn)行時(shí)間窗指派；第二階段，針對(duì)每個(gè)需求場景，尋求遵守各約束的車輛配送路徑方案，并使得成本最小化與配送時(shí)間最小化。第一階段的時(shí)間窗指派是內(nèi)生時(shí)間窗指派，由客戶需求產(chǎn)生配送時(shí)間。因此，為模擬需求的不確定性，引入需求場景及場景發(fā)生概率。第二階段簡化為帶有指定時(shí)間窗的污染路徑問題，根據(jù)許諾給客戶的時(shí)間窗，進(jìn)行有目標(biāo)的配送。

對(duì)客戶進(jìn)行時(shí)間窗指派的主要目的是對(duì)客戶進(jìn)行配送時(shí)能夠使到達(dá)時(shí)間一致。首先確定客戶的時(shí)間窗寬度wi，即基于每次給同一客戶配送最早與最晚到達(dá)的時(shí)間差tdif的歷史數(shù)據(jù)，限制時(shí)間窗寬度tdif≤wi；然后確定客戶i服務(wù)開始時(shí)間yi，根據(jù)內(nèi)生時(shí)間窗序列為客戶指派一個(gè)時(shí)間窗；最后根據(jù)需求場景s發(fā)生的概率，對(duì)客戶進(jìn)行配送，并滿足目標(biāo)條件。如圖2所示為歷史配送數(shù)據(jù)中不同配送周期配送到客戶的時(shí)間跨度tdf與時(shí)間窗寬度wi的關(guān)系，圖2中深灰色代表最早和最晚服務(wù)的客戶。tdif1表示客戶1的最早與最晚的到達(dá)時(shí)間差，tdif2表示客戶2的最早與最晚的到達(dá)時(shí)間差，w1表示客戶1的指派時(shí)間窗寬度，w2表示客戶2的指派時(shí)間窗寬度。顯然，指定的時(shí)間窗寬度可以滿足客戶對(duì)配送的時(shí)效要求。

(2)碳排放成本的計(jì)算

PRP中有關(guān)燃料消耗的計(jì)算是Bektas等[6]基于Barth等[16]和Barth等[17]描述的綜合排放模型，其給出的目標(biāo)是基于燃油在給定的一個(gè)時(shí)刻估計(jì)燃料消耗的瞬時(shí)模型，Demir等[18]延伸應(yīng)用了PRP的規(guī)劃。根據(jù)瞬時(shí)模型，得到燃料消耗率，如式(1)所示：

FR=ζ(μBV+P/η)/κ。

(1)

式中μ和κ為常數(shù)，參數(shù)

P=Ptract/ηtf+Pa。

(2)

參數(shù)Ptract可由式(3)計(jì)算為：

Ptract=(Mτ+Mgsinθ+0.5CdρAv2+

MgCrcosθ)v/1 000。

(3)

式中：M=w+f；w為車輛自重；f為車輛負(fù)載。車輛在弧上(i,j)的油耗是與距離d、速度v和負(fù)載f有關(guān)的函數(shù)，表示為：

F(v)=λ(kNV+wγαv+βγv3+γαfv)d/v

=λ[kNVd/v+βγdv2+γα(w+f)d]。

(4)

其中λ,γ,α,β為常數(shù)。為了簡化表示，令λ=ζ/(κψ)和γ=1/(1 000ntfη)為常數(shù)，α=δ+gsinθ+gCrcosθ和β=0.5CdρA分別為車輛弧特定常數(shù)和車輛特定常數(shù)。δ,θ,v,d,w和f分別表示車輛的加速度、道路坡度、速度、空車重量和有效載荷。如表1所示為碳排放計(jì)算相關(guān)參數(shù)的定義及經(jīng)典值。

本文假設(shè)車輛在無坡度的道路行駛，燃料消耗和二氧化碳排放量的成本可以估算為TFco2=fcF，則在時(shí)間窗指派污染路徑問題中，燃料和碳排放成本函數(shù)表示如下所示：

(5)

表1 碳排放計(jì)算相關(guān)參數(shù)定義

3.2 建立TWAPRP模型

模型中使用到的符號(hào)介紹如下：

s為需求場景，s∈S，其中S表示需求場景的集合;

ps為需求場景s中的發(fā)生概率;

[si,ei]為外生時(shí)間窗的限制，開始時(shí)間為si，結(jié)束時(shí)間為ei;

yi為客戶i的時(shí)間窗的開始時(shí)間，yi∈[si,ei-wi];

wi為客戶i的時(shí)間窗寬度;

tij為車輛在弧上(i,j)的行駛時(shí)間;

cij為車輛在弧上(i,j)的旅行成本;

目標(biāo)函數(shù)由兩部分構(gòu)成:第一部分Z1為碳排放成本和在弧上的固定旅行成本；第二部分Z2為配送時(shí)間。其目的是使得這兩部分最小化。

(6)

(7)

s.t.

(8)

(9)

(10)

(11)

(12)

(13)

?i∈V0,j∈V0,s∈S;

(14)

(15)

(16)

(17)

yi∈[si,ei-wi],?i∈V0;

(18)

(19)

?(i,j)∈A,r∈R;

(20)

?(i,j)∈A,s∈S;

(21)

(22)

4 設(shè)計(jì)求解算法

車輛路徑問題是NP-難問題，當(dāng)客戶規(guī)模增加到50后，難以使用精確算法求解，從而轉(zhuǎn)向啟發(fā)式算法[19]。根據(jù)本文模型的特征，使用混合遺傳—禁忌搜索算法進(jìn)行求解，結(jié)合遺傳算法具有良好的全局搜索能力和禁忌搜索算法具有優(yōu)秀的局部搜索能力[20-21]，設(shè)計(jì)改進(jìn)的混合遺傳—禁忌搜索算法，對(duì)本文模型進(jìn)行求解。

4.1 編碼方式及初始種群的生成

本文采用遺傳算法的自然數(shù)序列編碼方式對(duì)配送中心和客戶進(jìn)行編碼，由n個(gè)客戶構(gòu)成的配送網(wǎng)絡(luò)需要m輛車進(jìn)行配送，可以構(gòu)成一條編碼長度為n+m+1的染色體。其中n表示具有n個(gè)客戶的自然數(shù)全排列，具有m+1個(gè)0，0表示配送中心。如R(0-3-6-1-5-8-0-4-2-7-0)表示r1(0-3-6-1-5-8-0)和r2(0-4-2-7-0)兩條子路徑。

遺傳算法對(duì)初始種群的要求不太高，但是一個(gè)良好的初始種群有利于快速地找到較好的解，因此采用掃描算法[22]生成群規(guī)模為N的初始種群P1。

4.2 時(shí)間窗指派實(shí)現(xiàn)

在本文配送過程中，得知客戶需求后，根據(jù)為客戶指派的時(shí)間窗，滿足約束條件進(jìn)行配送，其中對(duì)客戶的時(shí)間窗指派主要是基于長期合作得到的經(jīng)驗(yàn)結(jié)果。在算法實(shí)現(xiàn)部分，客戶編碼完成后，對(duì)客戶提前進(jìn)行時(shí)間窗指派的設(shè)置，以一條染色體為例，假設(shè)有8個(gè)客戶，主要操作過程如表2和表3所示。

表2 客戶時(shí)間窗指派

表3 到達(dá)客戶時(shí)刻表

4.3 混合遺傳—禁忌搜索

得到初始種群P1后，對(duì)每條染色體進(jìn)行相應(yīng)的判斷，具體操作步驟如下：

(1)適應(yīng)度評(píng)價(jià)函數(shù)的選擇。本文采用目標(biāo)函數(shù)即兩個(gè)目標(biāo)組合優(yōu)化值的倒數(shù)作為遺傳算法的適應(yīng)度函數(shù)，適應(yīng)度值越大，被選擇的概率就越大，遺傳給下一代的幾率也就越大，反之就越差。

(2)選擇操作。為保留優(yōu)秀個(gè)體，從初始種群中選擇適應(yīng)度大的前20%的個(gè)體直接進(jìn)入下一代，采用最佳保留的輪盤賭選擇的方法進(jìn)行選擇操作。

(3)交叉和變異操作。為增加種群的多樣性，對(duì)種群進(jìn)行交叉概率為pc的改進(jìn)的順序交叉操作和變異概率pm的變異操作，得到新的種群。

(4)遺傳操作得到的新種群P2中的解作為禁忌搜索算法的初始解，進(jìn)行局部鄰域?qū)?yōu)操作。鄰域算子如下所示：

鄰域算子1隨機(jī)選擇一條路徑r1，選中r1中的部分元素(數(shù)量多于兩個(gè)元素)，進(jìn)行順時(shí)針逆轉(zhuǎn)。

鄰域算子2隨機(jī)選擇一條元素?cái)?shù)目大于4的路徑r1，選中4個(gè)連續(xù)的元素，前后兩個(gè)元素分別進(jìn)行順時(shí)針逆轉(zhuǎn)，如2 675逆轉(zhuǎn)后為6 257。

鄰域算子3隨機(jī)選擇一條路徑r1，選中其中一個(gè)元素，將其插入到另一條路徑中。

鄰域算子4隨機(jī)選擇兩條路徑r1和r2，分別選中每條路徑的一個(gè)元素，將選中的兩點(diǎn)的后續(xù)元素進(jìn)行路徑間交換。

(5)禁忌表更新及特赦準(zhǔn)則。為避免算法陷入局部最優(yōu)，需判斷鄰域解bsf是否優(yōu)于歷史最優(yōu)解Bsf。為此，特赦準(zhǔn)則設(shè)有兩種情況[23]：①若鄰域解優(yōu)于歷史最優(yōu)解，則更新歷史最優(yōu)解為bsf，并將最優(yōu)解未變化次數(shù)更新為pp=0。此時(shí)判斷禁忌表是否被充滿，若禁忌表已滿，則赦免禁忌表中第一個(gè)元素，將其他元素左移一位，將禁忌對(duì)象插入到禁忌表的尾部；否則，直接將禁忌對(duì)象插入到第一個(gè)不為0的位置。②若鄰域解劣于歷史最優(yōu)解，則將最優(yōu)解未變化次數(shù)pp=pp+1，繼續(xù)判斷下一個(gè)鄰域解是否滿足禁忌條件，當(dāng)達(dá)到禁忌次數(shù)時(shí)最優(yōu)解未變化，此時(shí)禁忌解Bsf更新為最優(yōu)解。

(6)對(duì)P2進(jìn)行禁忌搜索后的解，判斷是否滿足可行解池popsize的條件。若滿足，則判斷下一步，是否能夠滿足算法最大迭代次數(shù)的終止條件，若滿足終止條件，則輸出最優(yōu)結(jié)果；否則繼續(xù)進(jìn)行遺傳禁忌搜索操作。如圖3所示為混合遺傳—禁忌搜索算法的簡要流程圖。

5 數(shù)值實(shí)驗(yàn)

采用MATLAB(R2015b)編寫混合遺傳—禁忌搜索算法程序，在Intel(R)Core(TM)i7 CPU 2.0 GHz，內(nèi)存8 GB的計(jì)算機(jī)上運(yùn)行。算法參數(shù)：種群數(shù)量Pop=500，迭代次數(shù)G-max=300，交叉概率Pc=0.8，變異概率Pm=0.02，可行解池popsize=50，禁忌長度T-list=3，pp=200。

5.1 算例生成

5.2 算例結(jié)果分析

為驗(yàn)證模型的有效性，取50個(gè)客戶點(diǎn)對(duì)模型進(jìn)行求解，每個(gè)場景求解兩次，每個(gè)客戶的指派時(shí)間窗在不同的情景中是相同的，其時(shí)間窗指派如表4所示，求解得到的3種情景下的結(jié)果如表5所示。由表5可知每種場景的成本Fc、行駛距離dis、配送時(shí)間Tt、程序運(yùn)行時(shí)間tt和車輛數(shù)量。

表4 時(shí)間窗指派表

續(xù)表4

表5 三種場景下的求解結(jié)果

從表5中觀察相同場景下程序運(yùn)行的結(jié)果Fc與Ts，得到的解為非劣解，為此可證明模型的可行性和算法的有效性。在不同場景下，使用的車輛數(shù)目也不一樣，其中主要是因?yàn)楦鱾€(gè)場景下客戶的需求發(fā)生了改變，需求越高，使用的車輛數(shù)越多；但在不同場景下的成本、行駛距離、配送時(shí)間和程序運(yùn)行時(shí)間的指標(biāo)差異不是很大，說明客戶的需求改變對(duì)這4個(gè)指標(biāo)影響不大，但在車輛使用數(shù)量方面有一定差別。

5.3 算法性能分析

為進(jìn)一步證明算法的有效性，分別對(duì)不同數(shù)據(jù)集在基本的禁忌搜索算法(用于求解雙目標(biāo)的ε-約束法[15])和混合遺傳—禁忌搜索算法進(jìn)行求解，每個(gè)算例是對(duì)應(yīng)算法運(yùn)行后取9次較優(yōu)解的平均值，得到的結(jié)果如表6所示。由表6可知，隨著客戶集增加，兩種算法的各個(gè)指標(biāo)量也逐漸增加。相對(duì)某一客戶集而言，混合遺傳—禁忌搜索算法在成本、行駛距離和配送時(shí)間3個(gè)指標(biāo)都比禁忌搜索算法更優(yōu)，以客戶集20為例，本文算法比基本禁忌搜索算法在成本、行駛距離和配送時(shí)間方面分別改善了7.00%、44.78%和2.94%；30個(gè)客戶集在相應(yīng)方面分別改善了8.44%、50.78%和8.23%；50個(gè)客戶集在相應(yīng)方面分別改善了7.74%、50.40%和4.26%。但是在算法運(yùn)行速度方面，禁忌搜索算法更勝一籌，說明混合遺傳—禁忌搜索算法確實(shí)在尋優(yōu)方面結(jié)合了禁忌搜索的局部搜索的優(yōu)點(diǎn)和遺傳算法全局搜索的長處，也證明了混合遺傳—禁忌搜索算法對(duì)解決本文模型的有效性。

表6 禁忌搜索算法與混合遺傳—禁忌搜索算法比較

5.4 考慮不同優(yōu)化目標(biāo)的比較結(jié)果

為了驗(yàn)證本文所提綜合優(yōu)化目標(biāo)(FC)更符合物流配送運(yùn)作需求，將其與VRP傳統(tǒng)優(yōu)化目標(biāo)總行駛距離(TD)和總配送時(shí)間(TT)進(jìn)行對(duì)比分析，其目標(biāo)函數(shù)的表達(dá)方式如式(23)和式(24)所示：

(23)

(24)

為便于實(shí)驗(yàn)結(jié)果的分析，記錄了碳排放成本和旅行成本(fc)、行駛距離(dis)和配送時(shí)間(ts)3個(gè)測量指標(biāo)。主要分析兩個(gè)方面：不同客戶集下隨機(jī)場景的測量指標(biāo)和同一客戶集下不同場景(以30個(gè)客戶為例)的測量指標(biāo)。所有實(shí)驗(yàn)數(shù)值以FC的實(shí)驗(yàn)結(jié)果為基準(zhǔn)進(jìn)行歸一化處理，所有實(shí)驗(yàn)數(shù)據(jù)都是根據(jù)混合遺傳—禁忌搜索算法運(yùn)行后取9次較優(yōu)解的平均值進(jìn)行處理。

表7 不同客戶集下隨機(jī)場景的測量指標(biāo)結(jié)果

從表7可看出，TD和TT都比FC都需要更多的成本(碳排放成本和旅行成本fc)，且TT需要的更多，TD在成本方面平均增加了4.95%，且同時(shí)可以得知，TD在配送時(shí)間方面也耗費(fèi)更多，平均增加了1.41%，但在行駛距離方面卻平均減少了6.95%，這說明在以距離為優(yōu)化目標(biāo)的情形下，TD雖然在成本有所增加，但是盡可能滿足了優(yōu)化目標(biāo)。TT在比FC在成本方面和行駛距離都增加了，行駛距離的增加幅度比成本增加幅度小，在成本方面平均增加了7.76%，行駛距離平均增加了1.54%，然而在配送時(shí)間方面比FC減少了，配送時(shí)間平均減少了3.34%，這說明TT與FC的關(guān)系具有更加緊密的背反關(guān)系。由客戶集方面可知，在TD中，隨著客戶集的增加，各指標(biāo)基本維持相應(yīng)的增加趨勢，但30個(gè)客戶的指標(biāo)稍微不同；在TT中，隨著客戶集的改變，各指標(biāo)的變化無明顯的規(guī)律。這說明配送客戶的大小也會(huì)對(duì)指標(biāo)產(chǎn)生一定影響，但也不排除場景的影響因素。

表8 同一客戶集下不同場景的測量指標(biāo)結(jié)果

由表8可知，三種場景中成本方面均有所增加，行駛距離方面均有減少了。不管在場景1、2和3，TD和TT比FC耗費(fèi)更多的成本，但是場景1需要更多的成本。TD比FC在成本和時(shí)間兩個(gè)指標(biāo)都需要更多，TD的成本平均增加6.37%，隨著客戶需求的減少，成本指標(biāo)相應(yīng)減少，TD的行駛距離平均減少了7.75%，且在場景1中減少了高達(dá)11.45%，TD的配送時(shí)間平均增加了2.49%。TT在成本方面平均增加了6.55%，但在行駛距離和配送時(shí)間方面都減少了，在行駛距離方面平均減少了0.55%，在場景1中減少最多，減少了4.37%，但在另外兩個(gè)場景中的行駛距離均增加了，在配送時(shí)間方面平均減少了2.13%，而在場景1中減少的時(shí)間最多，平均減少了4.49%。根據(jù)場景由高到低觀察，隨著場景的需求增加，成本指標(biāo)相應(yīng)增加，且在需求最高的場景中，成本增長最大，但行駛距離和配送時(shí)間最小。這說明客戶的高需求能夠讓企業(yè)集中配送，耗費(fèi)更少的時(shí)間，但同時(shí)需要更多的配送車輛，因此在碳排放上，因客戶需求增加而增加。

6 結(jié)束語

本文研究了基于指派時(shí)間窗情形下的污染路徑問題，考慮到客戶配送前的不確定需求和配送前需給客戶指定配送時(shí)間窗的因素，引入了需求場景的概念，構(gòu)建了基于TWAPRP的最小成本(碳排放成本和旅行成本)與最小配送時(shí)間的雙目標(biāo)優(yōu)化模型，并根據(jù)模型的特征設(shè)計(jì)了混合遺傳—禁忌搜索算法進(jìn)行求解。求解結(jié)果表明了配送時(shí)間與成本之間有著制約關(guān)系，驗(yàn)證了模型的可行性和算法的有效性。將禁忌搜索算法與混合遺傳—禁忌搜索算法的求解結(jié)果進(jìn)行對(duì)比分析，進(jìn)一步驗(yàn)證了本文算法的有效性。最后，以傳統(tǒng)車輛路徑的最短行駛距離和最小配送時(shí)間為目標(biāo)與本文所提綜合優(yōu)化目標(biāo)為基準(zhǔn)進(jìn)行對(duì)比分析，驗(yàn)證了所設(shè)計(jì)算法在減少成本和配送時(shí)間的有效性，同時(shí)也表明不同企業(yè)的配送方案會(huì)因選擇的目標(biāo)不同而存在差別。

然而，在實(shí)際配送過程中，充滿著各種不確定因素，如交通擁堵、時(shí)變旅行等。未來可以將這兩方面進(jìn)行結(jié)合，并進(jìn)行深入研究。