考慮訂單取件時間和柔性時間窗的取送貨車輛路徑問題

孫欣蕊, 李昆鵬, 劉騰博

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

0 引言

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

本文所考慮的取送貨配送模式：首先，用戶在平臺下單，每個訂單信息包括任務起點和終點的具體位置、物品屬性、取件時間限制及送達時間窗要求；然后，配送中心對一定時間內的客戶訂單，根據訂單的取件時間要求及起終點位置為騎手派單并規劃路線。在此配送模式下，為保障騎手權益，系統根據起終點位置之間的距離設定合理送達時間窗限制；為提升客戶滿意度，若騎手在送達時間窗外延遲或提前將物品送達，平臺將根據偏離時間窗的程度采取一定懲罰，即用戶預期送達時間窗為柔性時間窗約束且具有一定的懲罰成本，平臺總懲罰成本越低說明配送準時率及客戶滿意度越高。基于此，本文以配送成本和懲罰成本之和最小為目標，研究具有訂單取件時間和柔性時間窗約束的取送貨車輛路徑問題(PDVRPORDFTW)。

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

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

1 數學模型

1.1 問題描述及假設

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

1.2 符號說明

R:客戶訂單集合R={1,…,n}；P={1,…,n}：訂單起點集合，第i個訂單對應第個起點；D={n+1,…,2n}：訂單終點集合，第i個訂單對應第n+i個終點；N=P∪D∪{0,2n+1}：節點集合，0和2n+1均表示配送站；A：弧的集合,A={(i,j)|i∈N,j∈N}；V：車輛集V=={1,…,K}；c：單位距離運輸成本；C：單位時間延遲成本；T：車輛的最長工作時間；dij：從節點i到節點j的行駛距離；tij：車輛服務節點i的時間與從節點i到節點j的行駛時間之和；Q：車輛的最大運載量；ETi：訂單起點i的最早可取件時間；(qi+qn+i)：qi和qn+i分別表示訂單起點i和終點n+i的配送量，qi=-qn+i≥0；[ETn+i,LTn+i]：訂單終點n+i的預期送達時間窗；ELTn+i：訂單終點n+i的最遲送達時間；xij：若車輛從節點i行駛至節點j，則為1；否則為0；Ai:車輛到達節點i的時間；Bi：車輛開始服務節點i的時間；Qi：車輛訪問節點i后的車載量；vi：表示節i點的路徑標志符號。

1.3 數學模型

1.3.1 模型建立

(28)

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

1.3.2 模型的線性化

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

為使(14)-(15)線性化，定義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)

為線性化(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)

從而為使目標(1)線性化，考慮

(44)

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

2 有效不等式

2.1 車容量不等式

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

(45)

(46)

2.2 優先順序不等式

(47)

(48)

2.3 加強子回路移除不等式

考慮集合S?P∪D,則任意一個可行解滿足以下不等式：

(49)

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

(50)

2.4 路徑不可行不等式

命題1W=(n+i,j,n+k)表示包含三個節點的路徑，其中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不包含在任意可行解中。

證明假設W存在一個可行解中，因車輛配送滿足優先約束，則節點i和節點k在W之前被訪問，節點n+j在W之后被訪問。然而，與假設條件矛盾，因此W不包含在任意可行解中。

命題2對于節點i∈P,有qi+qj>Q,?j∈P{i}。令R={0,j,n+j,i}，其中i,j∈P,n+j∈D。如果對任意j∈P，R不可行，則節點i是車輛離開節點0后訪問的第一個節點。

證明假設節點i不是車輛離開節點0后訪問的第一個節點，且對于任意節點j∈P{i}，有qi+qj>Q，從而節點h∈P{i}和n+h∈D滿足0→h→n+h→i。然而，與假設條件矛盾，因此節點i是車輛離開節點0后訪問的第一個節點。

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

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

(51)

x0i=1,R不可行

(52)

3 改進分支切割算法

3.1 預處理

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

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

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

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

3.2 分離算法

3.2.1 分離車容量不等式

3.2.2 分離優先不等式

3.2.3 分離子回路移除不等式

3.3 改進分支切割算法求解步驟

步驟1初始化：令Φ表示活躍節點的集合，當前活躍節點t為根節點0，將其添加到Φ；zbest為目標最優解，zbest←+∞。

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

步驟7節點選擇：若Φ是空集，則算法停止；若Φ不是空集，則根據下界優先策略選擇一個節點t進行求解，令Φ←Φ{t}，并轉到步驟4。

步驟8分支：從{xij|?i,j∈N}中選取一個對應的解是小數解的變量進行分支，生成兩個子節點，并添加到Φ。

4 數值實驗

4.1 算例構造

根據某平臺的訂單數據，提取預約模式下某時段內的訂單數據。利用百度拾取坐標系統，計算任意兩個節點之間的距離。在此基礎上構造5組不同訂單規模的算例進行測試{10,20,30,40,50}，每種規模隨機生成5個算例，共25個算例，各項實驗參數如下：車輛裝載能力Q=7；車輛最長工作時間T=60；單位配送成本c=0.2；單位時間延遲成本C=0.2；任意兩節點間的行駛時間tij=dij/speed(speed=21km/h)；客戶節點的時間窗長度W=25；對每個訂單(i,n+i)，對應的需求量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 有效不等式性能分析

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

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

表1 有效不等式的結果比較

4.3 改進分支切割算法與CPLEX默認的分支切割算法的比較

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

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

表2 改進分支切割算法與CPLEX默認分支切割算法的結果比較

4.4 參數對成本的影響分析

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

圖1 不同車輛數下平均成本折線圖

圖2 不同裝載能力下平均成本折線圖

圖3 車載能力與車輛數交互作用下成本折線圖

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

5 結論

本文研究了考慮訂單取件時間和柔性時間窗的取送貨車輛路徑問題，并使配送成本和超時懲罰成本之和最小。首先，提出混合整數線性模型；根據該問題的特性，提出四種有效不等式；設計改進的分支切割算法。其次，通過數值算例，比較每種有效不等式的有效性，結果顯示每種不等式能夠不同程度的提高模型下界；最后，在有限的運行時間內，與CPLEX的分支切割策略相比，驗證算法的有效性。本文不僅可以豐富車輛路徑問題文獻，還為評價城市物流平臺設計的啟發調度算法性能提供參考。此外，適當的減少車輛數，適當的增加車輛裝載能力，可有效的降低成本。

本文考慮了有確定性因素的帶時間窗的取送貨問題，而隨著訂單的需求個性化的不斷增加，未來研究可以考慮訂單分配和路徑規劃中的不確定因素。