孫欣蕊, 李昆鵬, 劉騰博

(華中科技大學(xué) 管理學(xué)院,湖北 武漢 430074)

0 引言

近年來(lái)，同城配送市場(chǎng)不僅涌現(xiàn)一批新興跑腿公司，而且傳統(tǒng)快遞企業(yè)、外賣(mài)企業(yè)紛紛擴(kuò)展同城跑腿業(yè)務(wù)，從而同城跑腿配送已成為企業(yè)競(jìng)相爭(zhēng)奪的藍(lán)海市場(chǎng)。順豐2019年同城業(yè)務(wù)營(yíng)收19.52億元，同比增長(zhǎng)96.12%；2020年母親節(jié)期間，UU跑腿當(dāng)日訂單量增幅50%以上。由于我國(guó)同城配送市場(chǎng)仍處于行業(yè)發(fā)展初期，各平臺(tái)跑腿業(yè)務(wù)雖增速明顯但配送模式尚未成熟。目前平臺(tái)通常采用用戶(hù)在平臺(tái)下單，配送系統(tǒng)根據(jù)訂單信息，將訂單分配至騎手，待取件后平臺(tái)自動(dòng)生成預(yù)計(jì)到達(dá)時(shí)間再由騎手完成配送的模式。但因用戶(hù)在下單時(shí)無(wú)法設(shè)置預(yù)期送達(dá)時(shí)間，導(dǎo)致訂單完成時(shí)間多取決于騎手，存在很大不確定性，故此配送模式不適用于客戶(hù)希望在指定時(shí)間內(nèi)送達(dá)，騎手盡可能多地接收訂單的實(shí)際場(chǎng)景。因此，基于此場(chǎng)景，如何科學(xué)的制定配送方案，進(jìn)而提高配送效率、節(jié)約運(yùn)力資源是需深入研究的重要課題。

本文所考慮的取送貨配送模式：首先，用戶(hù)在平臺(tái)下單，每個(gè)訂單信息包括任務(wù)起點(diǎn)和終點(diǎn)的具體位置、物品屬性、取件時(shí)間限制及送達(dá)時(shí)間窗要求；然后，配送中心對(duì)一定時(shí)間內(nèi)的客戶(hù)訂單，根據(jù)訂單的取件時(shí)間要求及起終點(diǎn)位置為騎手派單并規(guī)劃路線(xiàn)。在此配送模式下，為保障騎手權(quán)益，系統(tǒng)根據(jù)起終點(diǎn)位置之間的距離設(shè)定合理送達(dá)時(shí)間窗限制；為提升客戶(hù)滿(mǎn)意度，若騎手在送達(dá)時(shí)間窗外延遲或提前將物品送達(dá)，平臺(tái)將根據(jù)偏離時(shí)間窗的程度采取一定懲罰，即用戶(hù)預(yù)期送達(dá)時(shí)間窗為柔性時(shí)間窗約束且具有一定的懲罰成本，平臺(tái)總懲罰成本越低說(shuō)明配送準(zhǔn)時(shí)率及客戶(hù)滿(mǎn)意度越高?；诖耍疚囊耘渌统杀竞蛻土P成本之和最小為目標(biāo)，研究具有訂單取件時(shí)間和柔性時(shí)間窗約束的取送貨車(chē)輛路徑問(wèn)題(PDVRPORDFTW)。

具有不同約束條件的取送貨問(wèn)題一直是研究熱點(diǎn)，常見(jiàn)的約束條件包括：客戶(hù)需求特點(diǎn)、車(chē)容量、車(chē)輛限制等。同時(shí)取送貨車(chē)輛路徑問(wèn)題(VRPSPD)(馬艷芳等[1])；需求可拆分的取送貨問(wèn)題(VRPSPD)(李寒梅[2])；帶時(shí)間窗的取送貨車(chē)問(wèn)題(VRPTW)(祁文祥等[3]，邊展等[4])。本文考慮實(shí)際客戶(hù)需求，研究具有訂單取貨時(shí)間和柔性時(shí)間窗約束的取送貨車(chē)輛路徑問(wèn)題(PDVRPRDFTW)，目前尚未有學(xué)者對(duì)具有兩個(gè)客戶(hù)時(shí)間約束的車(chē)輛路徑問(wèn)題進(jìn)行探討，相關(guān)研究多集中在帶硬時(shí)間窗的取送貨問(wèn)題(PDPTW)以及帶軟時(shí)間窗的取送貨問(wèn)題(PDPSTW)。很多學(xué)者針對(duì)PDPTW提出精確算法和啟發(fā)式算法進(jìn)行求解。其中精確算法包括：分支-定價(jià)算法(Sun等[5]；Ghilas等[6])。分支切割算法(Ropke等[7]，F(xiàn)urtado等[8])。分支-切割-定價(jià)算法(Ropke等[9])，動(dòng)態(tài)規(guī)劃(Mahmoudi等[10])，基于集合分割的精確算法(Baldacci等[11])。相關(guān)啟發(fā)式算法包括：禁忌搜索算法(Nanry等[12]；Goeke[13])，自適應(yīng)大鄰域搜索算法(Ropke等[14])，模擬退火算法(Li等[15])。祁文祥等[3]對(duì)PDPSTW提出節(jié)約算法進(jìn)行求解。分析發(fā)現(xiàn)，極少有學(xué)者對(duì)PDPSTW問(wèn)題展開(kāi)研究；對(duì)PDPTW問(wèn)題的研究，集中在算法性能的優(yōu)化及求解規(guī)模的提升。此外，已有文獻(xiàn)在構(gòu)造數(shù)學(xué)模型時(shí)多考慮車(chē)容、取貨或送貨的時(shí)間窗、訪(fǎng)問(wèn)優(yōu)先級(jí)等約束，顯然無(wú)法適用于客戶(hù)對(duì)取貨和送貨時(shí)間均有要求的同城配送場(chǎng)景?；诖?，本文在構(gòu)建模型時(shí)將客戶(hù)的取貨和送貨時(shí)間均考慮在內(nèi)，并設(shè)計(jì)改進(jìn)分支切割算法。相較于現(xiàn)有研究，更符合同城配送平臺(tái)跑腿業(yè)務(wù)的實(shí)際需求，并且采用精確算法得到的最優(yōu)解可以用來(lái)評(píng)價(jià)啟發(fā)式算法的有效性，具有一定的指導(dǎo)作用。

本文的主要貢獻(xiàn)包含：(1)構(gòu)建了混合整數(shù)模型，并將非線(xiàn)性約束進(jìn)行線(xiàn)性化轉(zhuǎn)換；(2)根據(jù)問(wèn)題的特性，考慮四種有效不等式，設(shè)計(jì)改進(jìn)分支切割算法對(duì)模型進(jìn)行求解；(3)根據(jù)實(shí)際數(shù)據(jù)構(gòu)造算例，驗(yàn)證算法的有效性。

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

1.1 問(wèn)題描述及假設(shè)

本文所研究的問(wèn)題描述如下：針對(duì)多個(gè)訂單，配送企業(yè)進(jìn)行訂單分配和規(guī)劃配送路線(xiàn)。已知信息包括:每個(gè)訂單相應(yīng)的起點(diǎn)和終點(diǎn)地址信息、訂單需求量、每個(gè)訂單對(duì)應(yīng)的起點(diǎn)有相應(yīng)的訂單取件時(shí)間；每個(gè)訂單對(duì)應(yīng)的終點(diǎn)有相應(yīng)的服務(wù)時(shí)間窗?？蛻?hù)對(duì)車(chē)輛的提早或延遲到達(dá)有一定的容忍度，因此考慮柔性的服務(wù)時(shí)間窗。目標(biāo)是配送成本和懲罰成本之和最小。為了方便建模，考慮以下假設(shè)：(1)配送車(chē)輛數(shù)固定、車(chē)輛同質(zhì)且勻速行駛、電量充足；(2)每個(gè)訂單對(duì)應(yīng)的需求量不超過(guò)車(chē)輛的裝載能力；(3)每個(gè)訂單由同一車(chē)輛進(jìn)行配送；(4)車(chē)輛允許提前到達(dá)訂單終點(diǎn)，但需在相應(yīng)的時(shí)間限制內(nèi)服務(wù)客戶(hù)。(5)車(chē)輛服務(wù)客戶(hù)的時(shí)間超出系統(tǒng)預(yù)計(jì)的時(shí)間窗，但未超出最晚到達(dá)時(shí)間時(shí)，有相應(yīng)的懲罰。

1.2 符號(hào)說(shuō)明

R:客戶(hù)訂單集合R={1,…,n}；P={1,…,n}：訂單起點(diǎn)集合，第i個(gè)訂單對(duì)應(yīng)第個(gè)起點(diǎn)；D={n+1,…,2n}：訂單終點(diǎn)集合，第i個(gè)訂單對(duì)應(yīng)第n+i個(gè)終點(diǎn)；N=P∪D∪{0,2n+1}：節(jié)點(diǎn)集合，0和2n+1均表示配送站；A：弧的集合,A={(i,j)|i∈N,j∈N}；V：車(chē)輛集V=={1,…,K}；c：?jiǎn)挝痪嚯x運(yùn)輸成本；C：?jiǎn)挝粫r(shí)間延遲成本；T：車(chē)輛的最長(zhǎng)工作時(shí)間；dij：從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛距離；tij：車(chē)輛服務(wù)節(jié)點(diǎn)i的時(shí)間與從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間之和；Q：車(chē)輛的最大運(yùn)載量；ETi：訂單起點(diǎn)i的最早可取件時(shí)間；(qi+qn+i)：qi和qn+i分別表示訂單起點(diǎn)i和終點(diǎn)n+i的配送量，qi=-qn+i≥0；[ETn+i,LTn+i]：訂單終點(diǎn)n+i的預(yù)期送達(dá)時(shí)間窗；ELTn+i：訂單終點(diǎn)n+i的最遲送達(dá)時(shí)間；xij：若車(chē)輛從節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j，則為1；否則為0；Ai:車(chē)輛到達(dá)節(jié)點(diǎn)i的時(shí)間；Bi：車(chē)輛開(kāi)始服務(wù)節(jié)點(diǎn)i的時(shí)間；Qi：車(chē)輛訪(fǎng)問(wèn)節(jié)點(diǎn)i后的車(chē)載量；vi：表示節(jié)i點(diǎn)的路徑標(biāo)志符號(hào)。

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

1.3.1 模型建立

(28)

其中(1)為目標(biāo)函數(shù)，使配送成本和懲罰成本之和最小。(2)表示有IN輛車(chē)從配送中心出發(fā)，執(zhí)行配送任務(wù)，車(chē)輛訪(fǎng)問(wèn)的第一個(gè)節(jié)點(diǎn)是訂單對(duì)應(yīng)的起點(diǎn)。(3)～(4)表示每個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)一次，并保證流平衡。(5)保證所有車(chē)輛配送訪(fǎng)問(wèn)的最后一個(gè)節(jié)點(diǎn)是配送站。(6)～(7)表示車(chē)輛訪(fǎng)問(wèn)節(jié)點(diǎn)后，車(chē)輛裝載量的限制。(8)保證車(chē)輛裝載量的一致性。(9)表示車(chē)輛到達(dá)節(jié)點(diǎn)后才開(kāi)始服務(wù)。(10)保證車(chē)輛連續(xù)先后訪(fǎng)問(wèn)節(jié)點(diǎn)i和節(jié)點(diǎn)時(shí)，Bj≥Bi+tij。(11)表示一個(gè)訂單只能由一輛車(chē)配送，并且車(chē)輛需先到訂單對(duì)應(yīng)的起點(diǎn)取貨，再配送至訂單對(duì)應(yīng)的終點(diǎn)。(12)～(13)保證當(dāng)車(chē)輛先后連續(xù)訪(fǎng)問(wèn)兩個(gè)節(jié)點(diǎn)i和j后，Aj=Bi+tij。(14)表示當(dāng)車(chē)輛到達(dá)訂單對(duì)應(yīng)起點(diǎn)的時(shí)間小于等于它對(duì)應(yīng)訂單取件時(shí)間，則需在訂單取件時(shí)間取貨。(15)表示當(dāng)車(chē)輛提前到達(dá)訂單對(duì)應(yīng)終點(diǎn)，需要等待，直到訂單對(duì)應(yīng)終點(diǎn)預(yù)期的最早服務(wù)時(shí)間點(diǎn)，才進(jìn)行服務(wù)。(16)表示車(chē)輛需在訂單對(duì)應(yīng)終點(diǎn)可承受的最晚送達(dá)時(shí)間點(diǎn)前服務(wù)。(17)表示當(dāng)配送服務(wù)顧客的時(shí)間點(diǎn)超過(guò)預(yù)期時(shí)間窗，但不超過(guò)最遲服務(wù)時(shí)間點(diǎn)時(shí)，有一定的懲罰。(18)～(23)表明同一車(chē)輛訪(fǎng)問(wèn)的所有節(jié)點(diǎn)的路徑標(biāo)志符號(hào)相同，且路徑標(biāo)志符號(hào)等于該車(chē)輛訪(fǎng)問(wèn)的第一個(gè)節(jié)點(diǎn)序號(hào)。(18)規(guī)定了所有節(jié)點(diǎn)的路徑標(biāo)志號(hào)的取值范圍。(19)～(20)保證當(dāng)車(chē)輛離開(kāi)配送站后訪(fǎng)問(wèn)的第一個(gè)節(jié)點(diǎn)為時(shí),節(jié)點(diǎn)i的路徑標(biāo)識(shí)符號(hào)為i。(21)保證單個(gè)訂單的取貨點(diǎn)和送貨點(diǎn)由同一車(chē)輛進(jìn)行訪(fǎng)問(wèn)。(22)～(23)表示如果車(chē)輛連續(xù)訪(fǎng)問(wèn)節(jié)點(diǎn)i和j時(shí)，則節(jié)點(diǎn)i和j的路徑標(biāo)識(shí)符是相同的。(24)～(28)是定義的變量取值限制。

1.3.2 模型的線(xiàn)性化

由于約束(14)、(15)、(17)是非線(xiàn)性化形式，因此上述模型是非線(xiàn)性的。為降低模型求解的復(fù)雜度，將(14)(15)(17)轉(zhuǎn)化為線(xiàn)性形式。

為使(14)-(15)線(xiàn)性化，定義0-1變量，u0i,?i∈P并用以下約束(29)～(34)代替：

Bi≥Ai,?i∈P∪D

(29)

Bi≤Ai+T(1-u0i),?i∈P∪D

(30)

Bi≥ETi,?i∈P∪D

(31)

Bi≤ETi+Tu0i,?i∈P∪D

(32)

Ai≥ETi-T(1-u0i),?i∈P∪D

(33)

Ai≤ETi+Tu0i,?i∈P∪D

(34)

為線(xiàn)性化(17)，定義變量wn+i,0,wn+i,1,wn+i,2，zn+i,0,zn+i,1并用(35)～(43)代替:

wn+i,0,wn+i,1,wn+i,2≥0,?n+i∈D

(35)

zn+i,0,zn+i,1∈{0,1},?n+i∈D

(36)

wn+i,0+wn+i,1+wn+i,2=1,?n+i∈D

(37)

zn+i,0+zn+i,1=1,?n+i∈D

(38)

wn+i,0≤zn+i,0,?n+i∈D

(39)

wn+i,1≤zn+i,0+zn+i,1,?n+i∈D

(40)

wn+i,2≤zn+i,1,?n+i∈D

(41)

Bn+i=ETn+iwn+i,0+LTn+iwn+i,1+ELTn+iwn+i,2,?n+i∈D

(42)

P(Bn+i)=C(ELTn+i-LTn+i)wn+i,2

(43)

從而為使目標(biāo)(1)線(xiàn)性化，考慮

(44)

因此，混合整數(shù)線(xiàn)性模型為(44)，(2)～(13)，(16)，(18)～(43)。在下述部分中是考慮該線(xiàn)性模型。

2 有效不等式

2.1 車(chē)容量不等式

對(duì)于AS?P∪D，k(S)表示服務(wù)集合S所需車(chē)輛數(shù)的下界。在任意可行解中，服務(wù)S中所有節(jié)點(diǎn)的車(chē)輛數(shù)大于等于k(S)，其中，k(S)可取值為max{1,「q(π(S)S)/Q?,「-q(σ(S)S)/Q?}[9]，則可表示為:

(45)

(46)

2.2 優(yōu)先順序不等式

(47)

(48)

2.3 加強(qiáng)子回路移除不等式

考慮集合S?P∪D,則任意一個(gè)可行解滿(mǎn)足以下不等式：

(49)

基于S，考慮?p∈ρ(S),?n+q∈γ(S)，則式(49)可提升為下述有效不等式：

(50)

2.4 路徑不可行不等式

命題1W=(n+i,j,n+k)表示包含三個(gè)節(jié)點(diǎn)的路徑，其中n+i,n+k∈D,j∈P。令W1=(i,k,n+i,j,n+k,n+j)，W2=(k,i,n+i,j,n+k,n+j)。若W1和W2均不可行，則路徑W不包含在任意可行解中。

證明假設(shè)W存在一個(gè)可行解中，因車(chē)輛配送滿(mǎn)足優(yōu)先約束，則節(jié)點(diǎn)i和節(jié)點(diǎn)k在W之前被訪(fǎng)問(wèn)，節(jié)點(diǎn)n+j在W之后被訪(fǎng)問(wèn)。然而，與假設(shè)條件矛盾，因此W不包含在任意可行解中。

命題2對(duì)于節(jié)點(diǎn)i∈P,有qi+qj>Q,?j∈P{i}。令R={0,j,n+j,i}，其中i,j∈P,n+j∈D。如果對(duì)任意j∈P，R不可行，則節(jié)點(diǎn)i是車(chē)輛離開(kāi)節(jié)點(diǎn)0后訪(fǎng)問(wèn)的第一個(gè)節(jié)點(diǎn)。

證明假設(shè)節(jié)點(diǎn)i不是車(chē)輛離開(kāi)節(jié)點(diǎn)0后訪(fǎng)問(wèn)的第一個(gè)節(jié)點(diǎn)，且對(duì)于任意節(jié)點(diǎn)j∈P{i}，有qi+qj>Q，從而節(jié)點(diǎn)h∈P{i}和n+h∈D滿(mǎn)足0→h→n+h→i。然而，與假設(shè)條件矛盾，因此節(jié)點(diǎn)i是車(chē)輛離開(kāi)節(jié)點(diǎn)0后訪(fǎng)問(wèn)的第一個(gè)節(jié)點(diǎn)。

綜上，則下述不等式有效：

xn+i,j+xj,n+k≤1,W1,W2不可行

(51)

x0i=1,R不可行

(52)

3 改進(jìn)分支切割算法

3.1 預(yù)處理

若任意可行路徑不包含弧(i,j)∈A，則稱(chēng)(i,j)是冗余的。因此，為避免出現(xiàn)冗余的情況，通過(guò)在數(shù)學(xué)模型中加入以下約束，加快求解速度。

(1)對(duì)于滿(mǎn)足條件ETn+i>ELTn+i的送貨點(diǎn)，有n+i,n+j∈D,有xn+i,n+j=0。

(2)如果P=(j,i,n+j,n+i)為不可行路線(xiàn)，則弧(i,n+j)是冗余的，從而xi,n+j=0；同理，如果P=(i,n+i,j,n+j)為不可行路線(xiàn)，則弧(n+i,j)是冗余的，從而xn+i,j=0。

(3)2.4部分的路徑不可行不等式(51)，(52)。

3.2 分離算法

3.2.1 分離車(chē)容量不等式

3.2.2 分離優(yōu)先不等式

3.2.3 分離子回路移除不等式

3.3 改進(jìn)分支切割算法求解步驟

步驟1初始化：令Φ表示活躍節(jié)點(diǎn)的集合，當(dāng)前活躍節(jié)點(diǎn)t為根節(jié)點(diǎn)0，將其添加到Φ；zbest為目標(biāo)最優(yōu)解，zbest←+∞。

步驟2預(yù)處理：根據(jù)3.1部分的預(yù)處理，刪除圖G中冗余的弧，從而減少求解規(guī)模。

步驟7節(jié)點(diǎn)選擇：若Φ是空集，則算法停止；若Φ不是空集，則根據(jù)下界優(yōu)先策略選擇一個(gè)節(jié)點(diǎn)t進(jìn)行求解，令Φ←Φ{t}，并轉(zhuǎn)到步驟4。

步驟8分支：從{xij|?i,j∈N}中選取一個(gè)對(duì)應(yīng)的解是小數(shù)解的變量進(jìn)行分支，生成兩個(gè)子節(jié)點(diǎn)，并添加到Φ。

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

4.1 算例構(gòu)造

根據(jù)某平臺(tái)的訂單數(shù)據(jù)，提取預(yù)約模式下某時(shí)段內(nèi)的訂單數(shù)據(jù)。利用百度拾取坐標(biāo)系統(tǒng)，計(jì)算任意兩個(gè)節(jié)點(diǎn)之間的距離。在此基礎(chǔ)上構(gòu)造5組不同訂單規(guī)模的算例進(jìn)行測(cè)試{10,20,30,40,50}，每種規(guī)模隨機(jī)生成5個(gè)算例，共25個(gè)算例，各項(xiàng)實(shí)驗(yàn)參數(shù)如下：車(chē)輛裝載能力Q=7；車(chē)輛最長(zhǎng)工作時(shí)間T=60；單位配送成本c=0.2；單位時(shí)間延遲成本C=0.2；任意兩節(jié)點(diǎn)間的行駛時(shí)間tij=dij/speed(speed=21km/h)；客戶(hù)節(jié)點(diǎn)的時(shí)間窗長(zhǎng)度W=25；對(duì)每個(gè)訂單(i,n+i)，對(duì)應(yīng)的需求量qi～U[1,7],qn+i=-qi,ri～U[5,10],ETn+i=ri+ti,n+i,LTn+i=ETn+i+W;ELTn+i=LTn+i+5,qi～U[1,7]。

4.2 有效不等式性能分析

為分析提出的有效不等式對(duì)模型的改進(jìn)效果，考慮在搜索樹(shù)的根節(jié)點(diǎn)處添加不同的有效不等式，并比較它們對(duì)下界的影響。表1表示不同的不等式添加策略下的下界值。第1列為算例名稱(chēng)(例如10_1，10個(gè)節(jié)點(diǎn)規(guī)模下第1個(gè)算例)；第2列為只求解模型得到的下界值；Prece、Subtour、Cap分別表示優(yōu)先順序不等式，加強(qiáng)子回路移除不等式和車(chē)容量不等式。第3～8列是在搜索樹(shù)的根節(jié)點(diǎn)處添加對(duì)應(yīng)的不等式的下界值。

結(jié)果表明，對(duì)于8種處理方式下的平均下界，在搜索樹(shù)的根節(jié)點(diǎn)處，相比于只求解模型，7種處理方式均能不同程度的提高搜索樹(shù)根節(jié)點(diǎn)的下界；同時(shí)考慮3種有效不等式具有最好的平均下界。此外，相比于優(yōu)先順序不等式和加強(qiáng)子回路不等式，車(chē)容量不等式的效果最好；在搜索樹(shù)的根節(jié)點(diǎn)處，相比于考慮一種不等式或兩種不等式的添加策略，同時(shí)考慮三種不等式是最好的不等式添加策略。因此，在改進(jìn)分支切割算法中，將同時(shí)考慮三種不等式作為添加策略。

表1 有效不等式的結(jié)果比較

4.3 改進(jìn)分支切割算法與CPLEX默認(rèn)的分支切割算法的比較

為驗(yàn)證改進(jìn)分支切割算法的效果，將其與CPLEX默認(rèn)的分支切割算法進(jìn)行比較。表2表示時(shí)間限制為1h下兩種算法求解的結(jié)果。其中第1列與表1中的第一列有相同的含義。統(tǒng)計(jì)兩種算法下每個(gè)算例的下界，運(yùn)行時(shí)間，Gap。Gap=100%(第5列值-第3列值)/第3列值,“*”表示該算例求得最優(yōu)解。

由表2可知，(1)對(duì)于兩種算法獲得最優(yōu)解的個(gè)數(shù)， 25個(gè)算例中，改進(jìn)分支切割算法能夠獲得25個(gè)算例的最優(yōu)解；CPLEX默認(rèn)的分支切割算法只能夠獲得6個(gè)算例的最優(yōu)解。(2)對(duì)于兩種算法在1h的運(yùn)行時(shí)間內(nèi)獲得的平均下界，改進(jìn)分支切割算法的平均下界為50.94，CPLEX默認(rèn)的分支切割算法的平均下界為38.08，故相比于CPLEX默認(rèn)的分支切割算法，改進(jìn)分支切割算法使平均下界提高33.8%。(3)對(duì)于不同規(guī)模的算例，兩種算法對(duì)規(guī)模為10,20,30,40,50的算例，改進(jìn)分支切割算法分別求得5,5,5,5,5個(gè)算例的最優(yōu)解； CPLEX默認(rèn)的分支切割算法分別求得5,1,0,0,0個(gè)最優(yōu)解。綜上，算例規(guī)模較小時(shí)，改進(jìn)分支切割算法求解時(shí)間短，有實(shí)用性；隨著規(guī)模的增加改進(jìn)分支切割算法可以在較短時(shí)間內(nèi)求得最優(yōu)解；并可代替CPLEX，提供更好的下界，評(píng)估相關(guān)問(wèn)題的啟發(fā)方法的性能。

表2 改進(jìn)分支切割算法與CPLEX默認(rèn)分支切割算法的結(jié)果比較

4.4 參數(shù)對(duì)成本的影響分析

為分析車(chē)輛數(shù)，車(chē)輛裝載能力不同水平對(duì)成本是否有影響，針對(duì)單個(gè)算例30_1，考慮車(chē)輛數(shù)三種水平(nv=3,4,5)，車(chē)輛裝載能力四種水平(Q=7,8,9,10)，構(gòu)造12個(gè)算例。對(duì)所有算例，采用改進(jìn)分支切割算法，求得最優(yōu)解，結(jié)果如下圖所示。

圖1 不同車(chē)輛數(shù)下平均成本折線(xiàn)圖

圖2 不同裝載能力下平均成本折線(xiàn)圖

圖3 車(chē)載能力與車(chē)輛數(shù)交互作用下成本折線(xiàn)圖

結(jié)果表明，(1)對(duì)于不同車(chē)輛數(shù)下的成本，則有成本隨著車(chē)輛數(shù)的增多而增大(圖1所示)；(2)對(duì)于不同車(chē)載能力下的成本，則有成本隨著車(chē)輛裝載能力的增大而減少(圖2所示)(3)對(duì)于車(chē)輛裝載能力與車(chē)輛數(shù)交互作用下的成本，在不同的車(chē)輛數(shù)水平中，各個(gè)車(chē)輛裝載能力下的成本按照相同的規(guī)律變動(dòng)，則有車(chē)輛裝載能力和車(chē)輛數(shù)不存在交互作用(圖3所示)。綜上所述，車(chē)輛數(shù)和車(chē)輛裝載能力不僅對(duì)成本有顯著影響，而且車(chē)輛數(shù)越少，車(chē)輛裝載能力越大，成本越少。

5 結(jié)論

本文研究了考慮訂單取件時(shí)間和柔性時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題，并使配送成本和超時(shí)懲罰成本之和最小。首先，提出混合整數(shù)線(xiàn)性模型；根據(jù)該問(wèn)題的特性，提出四種有效不等式；設(shè)計(jì)改進(jìn)的分支切割算法。其次，通過(guò)數(shù)值算例，比較每種有效不等式的有效性，結(jié)果顯示每種不等式能夠不同程度的提高模型下界；最后，在有限的運(yùn)行時(shí)間內(nèi)，與CPLEX的分支切割策略相比，驗(yàn)證算法的有效性。本文不僅可以豐富車(chē)輛路徑問(wèn)題文獻(xiàn)，還為評(píng)價(jià)城市物流平臺(tái)設(shè)計(jì)的啟發(fā)調(diào)度算法性能提供參考。此外，適當(dāng)?shù)臏p少車(chē)輛數(shù)，適當(dāng)?shù)脑黾榆?chē)輛裝載能力，可有效的降低成本。

本文考慮了有確定性因素的帶時(shí)間窗的取送貨問(wèn)題，而隨著訂單的需求個(gè)性化的不斷增加，未來(lái)研究可以考慮訂單分配和路徑規(guī)劃中的不確定因素。