末端配送服務模式與路徑聯合優化

楊京帥，楊玉娥，李嫚嫚，李園園

(長安大學 汽車學院，陜西 西安 710021)

末端配送是與客戶聯系最為緊密的物流環節，一方面影響客戶的物流服務質量，另一方面又是物流成本節約的重要領域.末端配送成本約占運輸總成本的28%[1]，合理規劃配送路徑可以顯著降低配送成本，路徑規劃問題因此得到廣泛的研究[2].末端配送服務模式影響客戶的物流服務質量感知與滿意度[3]，企業由此推出了不同的末端配送服務模式.由于末端配送服務模式的配送網絡和服務形式存在差異，不同配送服務模式的配送路線和服務成本不同[4].如何兼顧末端配送服務質量與成本改善，協同決策末端配送服務模式和配送路徑，是值得物流企業探尋的一個問題.

目前常見的末端配送服務模式包括送貨上門、自提柜和自提點3種模式[5].送貨上門是物流企業將貨物送達客戶指定地點的服務模式；自提柜是設置在公共區域的自助取貨柜，存放的貨物數量及種類有一定限制，客戶可在任意時間取件，但是初始投資成本較高[4]；自提點是與物流企業合作的超市、店鋪等，投資成本低，客戶只能在自提點開放時間段取貨[6].末端配送服務模式與路徑規劃的協同優化問題是在考慮多種末端配送服務模式的情況下，以總成本最小化[7]或總運輸距離最小化[8-9]等作為優化目標，對客戶的末端配送服務模式和配送路線進行綜合決策.Du等[10-11]研究末端配送服務模式與同時取送貨型路徑規劃的聯合優化問題.Enthoven等[12-13]研究送貨上門和自提柜模式下的兩階段車輛路徑規劃問題.Zhou等[14]進一步研究多個配送中心下的兩階段車輛路徑規劃問題.周翔等[15-16]考慮自提柜位置對配送路徑的影響，研究多種末端配送服務模式共存情景下的自提柜選址和配送路徑聯合優化問題.常見的末端配送服務模式與路徑聯合優化問題求解算法有模擬退火算法[11]、大鄰域搜索算法[12]、遺傳算法[17]和分支定界算法[18].在進行配送路徑規劃時，鮮有研究同時考慮到送貨上門、自提柜和自提點3種末端配送服務模式，從而無法充分發揮配送系統的最大效能.Suwatcharachaitiwong等[19]雖然考慮到3種末端配送服務模式，但是只從物流服務商角度對末端配送服務模式進行選擇，忽略客戶對于不同模式的偏好，難以高質量提供配送服務.

為了彌補現有研究的不足，本研究同時考慮送貨上門、自提柜和自提點3種末端配送服務模式，從平衡物流企業成本與服務質量的新角度出發，研究末端配送服務模式與路徑聯合優化問題.以配送成本和客戶滿意度為雙目標，考慮到車輛容量限制、客戶收貨模式以及收貨時間窗等約束建立模型，改進NSGA-Ⅱ算法求解模型實現客戶配送模式與配送路徑的聯合優化，為建立高效、高服務質量的末端配送系統提供決策依據與方法.

1 問題描述

末端配送服務模式與路徑聯合優化問題如圖1所示.具體可描述為：在某配送區域存在1個配送中心以及對客戶點提供配送服務的a個自提柜和b個自提點.每個客戶點可接受多種末端配送服務模式，不同模式的對比如表1所示[3-4]，各種末端配送服務模式的客戶滿意度與物流企業配送成本不同.在兼顧配送成本和客戶滿意度的前提下，決策該區域的配送路徑和客戶接受的末端配送服務模式.

圖1 末端配送服務模式與路徑聯合優化問題示意圖Fig.1 Joint optimization diagram of terminal distribution service mode and routing

表1 不同末端配送服務模式對比Tab.1 Comparison of different terminal distribution service modes

2 末端配送服務模式與路徑聯合優化模型構建

2.1 模型假設

1）各個客戶點的位置、需求量、服務時間窗和可接受的末端配送服務模式已知；2）各個自提柜或自提點的位置和所能服務的客戶已知，并且容量是能夠滿足配送需求；3）考慮到3種末端配送服務模式，分別為送貨上門、自提柜和自提點；4）單配送中心，車輛只提供配送服務，不提供收攬服務；5）每個客戶點僅被服務1次，不存在二次配送的情況；6）配送車輛為同類型車，客戶點需求量不可拆分.

2.2 符號定義

構建末端配送服務模式與路徑聯合優化模型所用符號如表2所示.

表2 所提模型定義的符號及含義Tab.2 Notations and meanings of proposed model

2.3 模型構建

建立的末端配送服務模式與路徑聯合優化模型為

式中：T1為配送總成本；Cost_TW為時間窗懲罰成本.式(1)為目標函數，表示最小化由車輛運輸成本、車輛固定成本、配送服務成本和時間窗懲罰成本構成的配送總成本.

式中：T2為客戶滿意度.式(2)為最大化客戶滿意度，也是一個目標函數.

式(4)為每位客戶有且僅有一輛車采用一種配送模式為其提供服務.

式(5)為末端配送服務模式選擇約束.

式(6)為限制每位客戶選擇的模式，和配送路徑決策出的模式為同種模式.

式（7～9）為路徑約束.

式(10)限制一條路徑由同一輛車行駛.

式(11)為車輛到達客戶點的時間約束.

式(12)為車輛到達客戶點的配送量約束.

式(13)為車輛的最大載重量約束.

式（14～15）為決策變量的取值約束.

3 末端配送服務模式與路徑聯合優化模型求解

上述模型是具有多約束的雙目標混合整數規劃模型，混合整數規劃模型的求解是一個NP-Hard問題，為此采用元啟發式算法求解模型[20].元啟發式算法中的NSGA-Ⅱ是目前應用最廣泛的多目標進化算法之一，能夠得到Pareto最優解集，使得各目標函數都盡量達到最優[21].NSGA-Ⅱ具有適用性廣泛、求解速度快等優點[22]，因此改進的NSGA-Ⅱ用于模型求解，具體流程如圖2所示，其中Gen為種群迭代次數，算法涉及的具體操作展示在3.1節～3.5節.

圖2 改進NSGA-Ⅱ的流程Fig.2 Improved NSGA-Ⅱ flowchart

3.1 編碼

末端配送服務模式與路徑聯合優化問題，需要將客戶服務模式、配送車輛指派及配送路徑等決策目標融入編碼過程，將問題的實際方案表達為染色體基因.本研究采用實數編碼，設定每條染色體長度為2×A+B+1（A、B分別為客戶點和配送車輛數量），前A位為末端配送服務模式，后續基因為車輛配送路徑.以5個客戶點生成的染色體為例（如圖3所示），客戶1、3采用上門服務，客戶2、5采用自提柜服務，客戶4采用自提點服務，2輛車的配送路徑由0劃分.

圖3 改進NSGA-Ⅱ的染色體編碼Fig.3 Chromosomal coding of improved NSGA-Ⅱ

3.2 初始種群

為了提高初始解的質量，采用節約里程法（clarke-wright，CW）和隨機生成相結合的策略生成初始種群.CW算法的原理是在滿足車輛容量限制的條件下，盡可能多地將2個配送回路合并，以此減小運輸距離.利用CW算法生成初始解質量較高但易造成種群單一化，因此30%的初始解由CW算法生成，其余70%初始解隨機生成.此方法既加快了收斂，又保證了種群的多樣性.

3.3 快速非支配排序

設共有m個優化目標，若對于任意優化目標k(k=1,2,···,m) 有fk(x1) 不 劣 于fk(x2)，并且至少在1個優化目標上有fk(x1) 優于fk(x2) ，則稱解x1支配解x2.若是x1沒有被其他解所支配，則稱x1為非支配解（即Pareto解）.按照此定義對所有染色體進行排序，稱為快速非支配排序.具體操作過程是從所有染色體中選擇非支配染色體，得到第1層級的非支配染色體，然后從其他未劃分層級的染色體中再次選擇非支配染色體，得到第2層非支配染色體，重復此過程直到所有染色體都被劃分層級.通過快速非支配排序，可以得到Pareto解.Pareto解對應的目標函數值（Pareto前沿），如圖4所示.

圖4 Pareto前沿示意圖Fig.4 Pareto frontier diagram

3.4 擁擠度計算

NSGA-Ⅱ用擁擠度表示種群染色體的空間密度，染色體的擁擠度越大代表種群多樣性越好.以圖5所示染色體分布為例，兩端的染色體擁擠度設為 ∞，其余染色體的擁擠度是距離染色體最近兩點構成的矩形長寬之和，即

圖5 染色體i擁擠度Fig.5 Crowded degree of Chromosome i

式中：id為染色體i的擁擠度，fk(i) 為染色體i在優化目標k的目標函數值.

3.5 遺傳算子

3.5.1 選擇算子 在進行非支配排序和擁擠度計算后，運用競標賽機制選擇父代染色體.隨機選出2條不同的染色體，將排序等級較高的作為父代染色體，如果選出的2條染色體排序等級相同，則選擇擁擠度較大的成為父代染色體.

3.5.2 交叉算子 交叉是對生物遺傳過程中染色體基因重組的模仿，本研究采用多點交叉和POCSX[23]交叉策略.多點交叉是指在父代染色體的末端配送服務模式段和配送路徑段分別隨機選擇一對交叉點，交換相應交叉點間的基因片段.如圖6所示，父代1和父代2交叉點間的基因片段（加粗數字所示，下同）進行交換得到子代1和子代2.對交叉后的子代染色體進行有效性檢驗，如果出現重復節點或車輛超載等情況，則將造成沖突的基因取消交換.

當最優解重復出現10次，表明算法陷入局部最優.為了提高種群進化效率，染色體配送路徑段采取POCSX交叉.POCSX交叉是以子代上一個添加的節點和待選基因池中節點的代價（一般以節點間距離表示）確定子代的下一個節點.待選基因池的生成規則為待選基因池的第1位基因取父代1的第1個基因，剩余基因在父代2中隨機選取.如圖7所示，若設待選基因池大小為3，則需從父代選擇3個基因節點構成待選基因池[5,4,3].在子代首位添加0表示車輛配送的開始，并將待選基因池中距離節點0最小的節點5添進子代，同時將父代中的節點5刪除；按照待選基因池生成規則生成新的待選基因池 [2,1,3]，并將待選基因池中與節點5距離最短的節點1添加到子代，同時父代刪除節點1，重復此過程直至刪除父代染色體全部節點生成子代.

3.5.3 變異算子 變異是對生物遺傳過程中染色體基因突變的模仿.本研究采取反轉突變策略，即在一條染色體的配送服務模式段和配送路徑段分別隨機選擇一對變異點，將變異點間的基因序列顛倒.如圖8所示，將父代變異點1和2之間的染色片段、變異點3和4之間的染色片段都反轉得到子代.

圖8 改進NSGA-Ⅱ的反轉變異算子Fig.8 Inversion mutation operator of improved NSGA-Ⅱ

3.5.4 災變算子 災變模仿了自然進化中的重大災害，是幫助算法跳出局部最優的一種手段.當最優解連續重復出現10次時，算法進行災變操作，即只保留當前種群中質量最好的前30%的染色體，其余70%的染色體重新生成.

4 算例分析

基于Solomon RC102算例，對模型和算法進行驗證.為了使案例符合研究問題，根據自提柜和自提點數量與人口密度顯著正相關的特點[24]，增加自提柜和自提點位置；按照客戶對送貨上門、自提柜、自提點的滿意度高低[3,25]為客戶設置可選末端配送服務模式.例如，客戶對送貨上門模式的滿意度最高，則將送貨上門作為可選模式的客戶數量設置成最多.其余案例參數參照文獻[26-27]設置，具體如表3所示.改進NSGA-Ⅱ利用Matlab編譯，在配置為Intel(R)Core(TM)i5-5200U、2.20 GHz、4 GB RAM，Windows10(64位)的電l腦上運行.算法參數如下：種群規模為100，交叉概率為0.75，變異概率為0.10，Pareto解集數量為150.

表3 算例參數及取值Tab.3 Experimental parameters and values

4.1 模型驗證

為了驗證末端配送模式與路徑聯合優化模型的正確性，調用求解器GUROBI對5個客戶點的小規模算例進行求解.在調用求解器GUROBI對模型進行求解時，采用將配送總成本T1作為目標函數，將客戶滿意度 C S轉化為約束條件的處理方法.如式（17）所示，設置最小滿意度值 C Smin作為模型的1個約束條件，從而將雙目標函數轉化為單目標函數，同時降低模型求解的復雜程度.

GUROBI的求解結果如表4所示.從表4可以看出，所得末端配送服務模式和路徑方案滿足問題約束，即客戶的末端配送服務模式滿意度和車輛載重約束，表明所建模型有效.

表4 GUROBI對小規模算例的求解結果Tab.4 GUROBI results of small-scale example

4.2 算法性能分析

4.2.1 算法穩定性 為了驗證改進NSGA-Ⅱ的穩定性，對11個算例求解20次.11個算例求解20次的配送總成本平均解和最優解如表5所示.Gap為 平均解C2和 最優解C1差異的百分比，即 Gap=(C2-C1)/C1.表5顯示，改進NSGA-Ⅱ求解20次的平均解和最優解相對誤差較小，平均值為1.23%，說明改進NSGA-Ⅱ在求解末端配送服務模式與路徑聯合優化問題時具有較好的穩定性.

表5 改進NSGA-Ⅱ算法穩定性分析Tab.5 Algorithm stability analysis of improved NSGA-Ⅱ

4.2.2 算法性能優越性 為了驗證改進NSGA-Ⅱ的性能，本節將改進NSGA-Ⅱ與GUROBI和傳統NSGA-II算法的求解結果進行對比，17個中小案例的求解結果如表6所示.其中，GUROBI列展示的結果為2000 s求解時間限制下的結果，“-”表 明 在 限 制 時 間 內 沒 有 發 現 可 行 解.G ap1和Gap2分別為傳統NSGA-Ⅱ和改進NSGA-Ⅱ求得的配送總成本最優值C3 ,C1與GUROBI求得的配送總成本最優值C4差 異的百分比，即 Gap1=(C3-C4)/C4，Gap2= (C1-C4)/C4.

表6 三種算法求解末端配送服務模式與路徑聯合優化模型的性能Tab.6 Performances of three algorithms to solve terminal distribution service mode and routing model

通過對比求解器GUROBI和改進NSGA-Ⅱ對相同案例的求解結果可知，當客戶規模小于15時，GUROBI和改進NSGA-Ⅱ的求解質量基本相同，平均差異小于0.1%.當客戶規模大于15時，75%的案例，改進NSGA-Ⅱ得到的解比GUROBI優.GUROBI的求解時間會隨著客戶規模的增大急劇增加.當客戶規模為10時，GUROBI就需要1907 s的求解時間.而改進NSGA-Ⅱ的求解時間增加并不明顯，最大求解時間也不超過240 s，只是GUROBI所用求解時間的1/10.除此之外，改進NSGA-Ⅱ可以一次性求解出Pareto前沿，而GUROBI只能求解出一個解.對比傳統NSGA-Ⅱ和改進NSGA-Ⅱ的結果可知，求解時間平均僅增加23 s，求解質量平均提升了3.37%.綜上可知，所設計的改進NSGA-Ⅱ求解效果優于GUROBI和傳統NSGA-Ⅱ.

4.2.3 Pareto解集 圖9展示60個客戶算例求解的Pareto前沿，可以看出客戶滿意度S和配送總成本C存在正相關關系.送貨上門、自提柜和自提點3種服務模式的服務成然依次遞減，是以客戶滿意度降低為代價.在實際操作中，物流企業需對配送服務質量和成本進行權衡.

圖9 60個客戶案例求解到的Pareto前沿Fig.9 Pareto frontier of 60 customer cases

4.3 敏感度分析

4.3.1 末端配送服務模式分析 為了體現末端配送服務模式與路徑聯合決策模型的優勢，將采用送貨上門、自提柜和自提點的單一末端配送服務模式與三種配送模式混合使用下的配送總成本與客戶滿意度進行對比分析.客戶的可選末端配送服務模式限定為單一模式，即成為相應模式下的只考慮配送成本的路徑決策問題.客戶不可接受末端配送服務模式的滿意度變為相應末端配送服務模式的0.5倍，5個算例求解20次所得配送成本最低的解如表7所示.

從表7可以看出，送貨上門服務模式能夠得到最高的客戶滿意度，但其配送成本也最高；自提點服務模式的配送成本最低，客戶滿意度也最低；自提柜模式的成本和客戶滿意度均介于送貨上門和自提點模式之間.混合模式與自提柜和自提點模式相比，成本分別增加了3.11%和18.71%，但客戶滿意度分別提高了22.48%和47.78%，整體提升了19.37%和29.07%；與送貨上門相比，客戶滿意度降低了8.56%，同時配送成本降低了20.57%，整體提升了12.01%.綜合來看，混合利用多種末端配送服務模式能夠發揮各模式的優勢，達到 既控制配送成本又能提升客戶滿意度的目標.4.3.2 自提柜和自提點數量分析 將100個客戶算例中的自提柜和自提點數量均增加3個，相同客戶滿意度下成本最低的配送方案如表8所示.表中Ct、Cf、Cs和Cw分別為運輸成本、車輛固定成本、服務成本、時間窗成本.增加自提柜和自提點數量后配送總成本降低了115.94元，其中運輸成本降低了11.88%.這說明管理者在投資建設成本允許的情況下，可以通過適當增加自提點和自提柜數量降低配送總成本.

表7 不同末端配送服務模式的配送總成本與客戶滿意度Tab.7 Distribution cost and customer satisfaction with different terminal distribution service modes

表8 不同自提柜和自提點數量下成本最低的配送方案Tab.8 Lowest cost distribution scheme with different number of parcel lockers and pick-up points

4.3.3 時間窗寬度分析 在分析時間窗寬度影響時，保持其它參數不變.在不同時間窗寬度下，利用求解器GUROBI求解8個客戶的小規模算例，利用改進NSGA-Ⅱ求解100個客戶的大規模算例，結果如圖10所示.圖中Cmin 為所得最低配送總 成本，η為原時間窗寬度的變化倍數.

圖10 不同時間窗寬度倍數下的最低配送成本Fig.10 Minimum distribution cost with different time window width multiples

由圖10可知，客戶可接受的服務時間窗寬度會對配送成本產生影響，并且不同規模算例的變化趨勢相同，即客戶可接受的服務時間窗寬度越大，所需配送總成本越低.由表9可知，當客戶時間窗調整比例由0.8倍變為2.0倍時，在相同客戶滿意度下，車輛固定成本保持不變，運輸成本和服務成本以低于0.5%的微弱幅度分別增加和降低，而時間窗成本顯著降低，時間窗成本是配送總成本降低的主要因素.在實踐中，為了降低配送成本，物流企業管理者可以通過與客戶協商談判、提供獎勵等方式，使得客戶接受更寬的服務時間窗.

表9 不同時間窗寬度倍數下的配送方案Tab.9 Distribution schemes with different time window width multiples

5 結語

本研究提供了末端配送服務模式與路徑聯合優化方法.考慮到車輛容量限制、客戶對不同配送服務模式的接受度、收貨時間窗等約束，以配送成本和客戶滿意度為目標，建立了一個混合整數規劃模型，改進NSGA-Ⅱ算法對模型進行求解.算例分析證實了模型的準確性以及所設計算法的優越性能.算例參數敏感度分析發現：

1）相較于單一末端配送服務模式，末端配送服務模式與路徑聯合優化能夠同時對配送成本和客戶滿意度進行改善.

2）管理者可以通過適當增加自提點和自提柜數量，爭取與客戶達成更寬松的收貨時間窗的途徑，實現降低配送成本的目標.