軸輻式同城快遞網絡模式研究

李文莉, 李昆鵬, 阮文意

(1.武漢紡織大學 管理學院，湖北 武漢 430200; 2.華中科技大學 管理學院,湖北 武漢 430074)

0 引言

隨著科技飛速發(fā)展以及移動網絡普及率迅速提升，電子商務的發(fā)展越發(fā)迅猛，這為快遞行業(yè)提供了前所未有的發(fā)展機遇。為了更好地服務各地區(qū)人民，網點密度也愈加稠密化，城市鄉(xiāng)鎮(zhèn)的網點覆蓋率也是逐步提升，在全國范圍內已然形成了龐大的物流網絡基礎。同時，快遞和人們生活的聯(lián)系愈加緊密，同城快遞的重要性也逐漸凸顯，提供優(yōu)異的同城快遞服務體驗也成了快遞公司新的競爭點。X公司擁有健全的全國物流網絡結構，以及競爭性的全國快遞時效服務體驗，但是其同城快遞業(yè)務存在極大的時效提升空間。目前其同城快遞網絡結構主要有兩種：一種是中轉場模式即所有快件(不區(qū)分同城異地)集中運輸?shù)街修D場，然后由中轉場再運輸至各個網點；另一種是點對點直通運輸，快件流通量到了一定程度或者到了規(guī)定的送貨時間，網點之間車輛直接對開，如圖1所示。

圖1 直通，中轉場及集散點結構示意

第一種情況加重中轉場分揀壓力，造成資源的不必要重復浪費，同時增加時間成本。第二種情況一方面需要等待一定時間使快件達到一次運輸標準，而同城快件客戶一般對時間有明顯預期，過長時間的等待容易造成客戶流失，倘若優(yōu)先考慮顧客服務時效則容易造成過大的運營成本；另一方面從資源本身而言大范圍的點對點運輸會使車輛運營成本居高不下。此外由于沒有明確的網絡結構劃分容易導致管理運營難度提升，難以在客戶需求激增以及有急切的時間要求的情況下做出即時高效反應。而物流網絡結構優(yōu)化一直是很多快遞公司提升運營效率的方向之一，這同樣適用于同城快遞。通過借鑒全國的軸輻式物流網絡結構提出了同城快遞的集散點網絡運營模式如圖1所示，該模式的特點是將普通快件和同城快件加以區(qū)分，利用現(xiàn)有的網點資源，從中選擇合適的網點成為集散點，搭建同城集散點網絡結構服務同城快件。集散點針對的同城快件規(guī)模相對較小，無需對現(xiàn)有網點做出太大改變，只是在部分網點加入一個小型集散中轉的功能，起到整合分配下屬節(jié)點快件的集散作用。

軸輻式網絡設計問題一般稱為樞紐選址問題，重點是確定樞紐的位置以及給樞紐分配分支節(jié)點，最早由O’Kelly[1,2]提出。他在1986年首次將軸輻式物流網絡結構應用到航空貨運樞紐選址問題上，建立了多種選址模型，并指出該問題屬于NP-hard問題[3]；此后這個問題在學術上引起了廣泛的關注。有些學者研究模型以及分配方式，比如Sohn[4]在文章中同時考慮了無容量約束的單分配和多分配的P-HUB選址問題，對P值固定時的兩種情形建立了有效的模型和方法求解，有些學者研究在基礎問題上進行相關的延伸，例如增加容量約束[5]，非樞紐點的分支流向約束[6]。國內相關的研究較少，而且缺乏應用在同城快遞上的相關研究。

本文依托快遞公司同城配送的實際背景，在現(xiàn)有的單分配樞紐選址研究基礎上研究了帶樞紐點分支流向限制的樞紐選址問題，一定程度上填補了國內相關研究空白。此問題屬于樞紐選址問題范疇，已被證明屬于NP-hard問題[6]，難以用精確算法快速求解，禁忌搜索算法是一種被廣泛應用的啟發(fā)式算法。傅少川[7]等研究了禁忌搜索算法在單分配樞紐選址的應用情況，此外禁忌搜索算法在相關文獻中被證明求解此類問題可以得到較好的解[8,9]，本文設計了相應的禁忌搜索算法對問題進行求解，算法加入了重啟以及新的鄰域搜索機制。最后驗證了算法的有效性，并根據實驗結果提出了管理上的建議。

1 問題描述與模型建立

本文研究的是帶分支流向限制的單分配P樞紐選址問題在同城快遞中的應用，模型的構建是在O’Kelly[10]提到的一般單分配樞紐選址模型的基礎上增加樞紐點分支流向限制。同城快遞網絡可用G=(N,A)表示，其中N為所有節(jié)點的集合N={1,…,n},A為所有邊的集合A={(i,j);i,j∈N,i≠j}；每條邊都有一個非負的長度Dij，且三點之間的關系滿足三角不等式Dij+Djm≥Dim,?i,j,m∈N。模型中Xijkm為兩點之間的路徑段的簡略表示，其中i,j為路徑的起點與終點，k,m分別為i,j所屬的樞紐點，Xijkm所對應的路徑段為Xij,Xkm,Xmj，且當取值均為1時，三個路徑段共同構成了貨物從i運輸?shù)絡的流通路徑，如圖2所示。Cij為兩點之間的單位運輸成本，Cij與Xijkm的乘積為成本與下標對應的路徑段組合的乘積，例如。(Cik+Ckm+Cmj)Xijkm=CikXik+CkmXkm+CmjXmj。在建模過程中不考慮車容量限制，且集散點之間運輸存在折扣率。

圖2 流向示意

1.1 參數(shù)設置

p:hub個數(shù);a:干線運輸?shù)恼劭巯禂?shù);Wij:節(jié)點i與節(jié)點j之間的運量;S:可行路徑集；S={(i,j,k,m):(k=i)∨(k≠i∧k=m=j)∨(k≠i∧k≠j∧m≠i)};Si′j′表示中S(i,j,k,m)中的i,j是固定值i′,j′；Si′j′k′表示S中i,j,k是固定值i′,j′,k′；Si′j′m′表示S中i,j,m是固定值i′j′m′。

1.2 模型設置

帶樞紐點分支流向限制的單分配樞紐選址模型如下：

minZ=∑Wij(Cik+aCkm+Cmj)Xijkm

(1)

(10)

其中目標函數(shù)(1)是運輸成本最小化，成本由快件量和運輸費決定，因為主要是改變網點從屬結構以及定義集散點功能，對整個網絡及網點本身影響較小，故不考慮成為樞紐點的建設費用。成本由支線和干線運輸成本決定，干線運輸折扣率為公司一般規(guī)模效應產生的折扣率0.7；約束(2)表示樞紐點總數(shù)為p；約束(3)表示每個節(jié)點只能和一個樞紐點相連，是單分配樞紐選址的特點；約束(4)保證了只有樞紐點可以擁有下屬節(jié)點；約束(5)和(6)表明了單分配這種結構模式的流向限制，非樞紐節(jié)點只可以和對應的樞紐節(jié)點相連；約束(7)為樞紐點分支流向限制，分支流向限制的主要是成為集散點的節(jié)點，因為普通節(jié)點主要對接節(jié)點只有集散點，而集散點面對的操作是將下屬節(jié)點的快件聚集并根據快件流向進行分揀然后運輸至其他集散點，以及將其他集散點運送過來的快件根據流向分揀后運送至其下屬節(jié)點。當分支流向數(shù)過多的時候，集散點聚集過多快件，分揀時間相應的會增加，在人員有限的情況下，同城快件的時效得不到保證。根據mod動作法測算了分揀時間和流向的關系。單一流向分揀為0.3s，而每增加一個流向，分揀時間會增加0.08s來判斷快件所屬分揀方向，對于分揀員的規(guī)定是一小時處理500件可完成任務，則2.38s到2.4s一個快件，那么分支流向上限為26。又因為節(jié)點成為集散點，為了起到一個集散功能形成規(guī)模效應，下屬節(jié)點數(shù)目大于4。約束(8)為樞紐點數(shù)目的范圍。約束(9)～(10)為0-1變量。

2 優(yōu)化算法

禁忌搜索算法是一種亞啟發(fā)式隨機搜索算法，通過設置禁忌列表避免陷入局部循環(huán)，被成功應用于多種學術問題求解上，在選址問題上也有不錯的表現(xiàn)性能。本文采用禁忌搜索算法對問題進行求解，流程如圖3所示，在處理過程中，通過對比多種算法的實驗結果，以及將算法應用到不同數(shù)據集后，發(fā)現(xiàn)算法具有比較好且穩(wěn)定的表現(xiàn)性能。相較于傳統(tǒng)的禁忌搜索，本文提出的禁忌搜索算法設置了重啟這一操作，會通過重啟重新生成初始解，增加了跳出局部最優(yōu)達到全局最優(yōu)的可能性。優(yōu)化搜索算法框架如下：

圖3 算法框架

2.1 初始解生成

初始解質量的優(yōu)劣對啟發(fā)式算法效率有直接影響。常見的初始解生成方式有隨機生成初始解，即根據約束條件限制，隨機選擇樞紐點，然后將非樞紐點隨機分配給樞紐點，一般可以采用隨機數(shù)，因為完全隨機分配方式隨機性太大，本文采用的禁忌搜索算法是針對一個初始解進行變化的一種啟發(fā)式算法，所以初始解生成對算法表現(xiàn)有一定影響，本文初始解采用了部分隨機的貪婪式生成方式。貪婪式生成方式即隨機選擇滿足數(shù)量限制的樞紐點，這樣可以增加算法重啟時解空間的多樣性，然后隨機選擇開始分配非樞紐節(jié)點的樞紐點編號，將與之相連最近的非樞紐節(jié)點分配給該樞紐節(jié)點，然后依次對其他樞紐點進行相應的操作，直到安排完成所有節(jié)點形成初始解。

2.2 鄰域生成

鄰域生成的方式在算法中起到至關重要的作用，對求解結果也有較大影響。在禁忌搜索算法執(zhí)行時，對當前接受的可行解進行兩種操作，一種是最優(yōu)交換，這種鄰域生成方式借鑒了遍歷的思想，遍歷所有非樞紐點移動至其他樞紐點的操作，以及所有的樞紐點和非樞紐點互換即0-1互換，選擇最優(yōu)移動或者互換執(zhí)行；一種是隨機0-1互換，隨機選取非樞紐節(jié)點，使之和其對應的樞紐點進行互換。在執(zhí)行操作時優(yōu)先第一種鄰域操作，當?shù)谝环N鄰域操作無法產生更好的解，則隨機進行0-1互換，通過接受劣于記錄的解來進行新的鄰域搜索。

2.3 禁忌列表及藐視準則

由于傳統(tǒng)的鄰域搜索算法容易陷入局部最優(yōu)的困境，禁忌搜索算法可以通過禁忌相關的移動來避免陷入局部最優(yōu)。本文禁忌對象為禁忌出現(xiàn)過移動的操作，這里的移動一種是最優(yōu)交換，一種是隨機0-1交換。考慮到禁忌步長對算法的影響，在經過步長測試后，設置禁忌列表長為12。若某次操作出現(xiàn)當前最優(yōu)解但是這次操作的變化點在禁忌列表中，操作也可以被接受，為藐視準則，此時接受這個操作并清空禁忌表。

2.4 評價函數(shù)及解的結構

根據目標函數(shù)，設定了新的評價函數(shù)來評判解的優(yōu)劣。在進行每次操作選擇時，根據操作造成的成本減小值進行衡量操作是否可被接收，優(yōu)先選擇使當前成本減少最大的操作接受，當減少值全為正數(shù)時會選擇隨機0-1交換。在構造算法時，將操作和對操作進行的成本減少的計算分開進行，選定最優(yōu)操作之后才會對解進行變化，這樣的處理方式可以提高算法的效率。在處理過程中對是否是樞紐點進行了判斷和記錄，并且使用另外的數(shù)組對樞紐點下屬非樞紐節(jié)點進行了保存和記錄，解的結構如表1所示，其中ishub記錄節(jié)點是否為樞紐點，非樞紐點標為FALSE，樞紐點標為TRUE。solution記錄解的結構，其中數(shù)組第1列記錄的是樞紐點的標號，樞紐點之后記錄的是樞紐點的下屬非樞紐節(jié)點的標號。這樣記錄的好處是計算時可以清晰的表述以及找到樞紐節(jié)點和下屬的非樞紐節(jié)點。

表1 解的結構

3 算例分析

該部分采用了兩類數(shù)據分別進行實驗，一類是傳統(tǒng)的標準CAB數(shù)據集，CAB標準數(shù)據集是樞紐選址問題的經典測試數(shù)據集，主要包含了美國航空運輸25個節(jié)點城市的流量和單位流量成本矩陣。因為本問題是在傳統(tǒng)的樞紐選址問題中加入了一定條件限制，但是依然屬于樞紐選址問題，所以將所設計的算法用于求解CAB數(shù)據并和已有的標桿結果進行對比來驗證算法求解此類問題的有效性；另一類數(shù)據是采取X公司某地的同城快遞業(yè)務一段時間的實際數(shù)據作為算例，使用設計的禁忌搜索算法以及前人研究中采用的一些算法對問題進行求解與對比。

3.1 經典CAB算例測試

因為傳統(tǒng)的CAB數(shù)據集流量矩陣為上對稱矩陣以及沒有分支約束，和實際背景有一定出入，在對算法進行適當改編后，求解CAB數(shù)據集，結果如下表2所示，其中opt為標桿數(shù)值，TS為本文提出的禁忌搜索算法結果，PSO為找到的對比算法結果,其中PSO算法是由Yarpiz團隊提供的開源算法。我們可以發(fā)現(xiàn)設計的算法可以達到前人研究所給出的標桿結果，具有很好的表現(xiàn)性能。部分結果優(yōu)于標桿結果，比如20-3-1，20- 4- 0.2/0.6/0.8，25-3- 0.2/0.4，25- 4- 0.6，部分結果差于標桿結果，比如20-3- 0.4，20- 4- 0.4/1，25- 4- 0.2/0.4，在經過多次實驗以及和其他已知算法對比，認為是因為計算本身精度原因造成，算法的表現(xiàn)正常。

表2 CAB標準數(shù)據集實驗結果

3.2 基礎對比實驗

通過對比不同初始解生成方式對算法結果的影響以及禁忌表長度選擇對求解速度和結果的影響并進行測算，為下文實際求解提供一定的支撐，測試數(shù)據使用的是樞紐點個數(shù)為10，折扣率為1的基礎情況。全局最大未經優(yōu)化的迭代步數(shù)(重啟次數(shù))為20，局部為1000。

3.2.1 初始解設置

對比隨機生成初始解與貪婪式生成初始解兩種方式對算法的影響來選擇更利于求解的設定，其中隨機生成方式是隨機選取p個樞紐點，將剩余的非樞紐節(jié)點依次分配給樞紐節(jié)點。貪婪式生成方式即按照上文提到的初始解生成方式。表3所示結果為采用不同初始解生成方式下算法的運行結果，通過數(shù)據的對比可以發(fā)現(xiàn)不同的初始解生成方式對算法運行結果有一定影響，但是影響相對較小，在一定意義上采用貪婪式的初始解生成方式可以得到比較好的結果，且算法得到解的穩(wěn)定性相較于隨機生成初始解更好。隨機和貪婪式差別較小也可以說明算法的搜索效率和收斂效率優(yōu)良，可在一定的循環(huán)次數(shù)里采用任意初始解生成方式均可得到較優(yōu)的解。

表3 不同初始解運行結果

3.2.2 禁忌列表步長設置

禁忌表長度對算法效率會有一定的影響，考慮到數(shù)據量和鄰域規(guī)模，對禁忌表長度設置做了相應測試，因為本文存在重啟機制，所以結果展示的是未經重啟的第一次搜索結果，如圖4所示，可以發(fā)現(xiàn)在長度4～22區(qū)間段，求解結果數(shù)值上有一定的區(qū)別，收斂速度也存在一定區(qū)別，圖中最下方的虛線表現(xiàn)更好，說明禁忌表長度對算法的收斂性和搜索效果有一定的影響，在經過更多測試后發(fā)現(xiàn)，表長為12時，所得結果相對更為穩(wěn)定，且在全局而言可以更快的得到質量較好的解，求解質量較好。所以在實驗過程中使用的禁忌表長度取值12。

圖4 禁忌步長測試

3.3 實際算例測試

根據目標函數(shù)的表達式以及相應計算方式可以直觀的體會到樞紐點數(shù)目越多，整個網絡成本越小。在經過基礎實驗后，根據分支流向限制的樞紐選址問題的模型和參數(shù)設置，分別測算了樞紐點個數(shù)在4～15時解的結構模式，為了增加得到更好解的可能性，全局未改善的循環(huán)次數(shù)設為100，局部未改善循環(huán)次數(shù)為1000。在測算過程中發(fā)現(xiàn)當樞紐點數(shù)目為15時，因為分支流向數(shù)目的限制，每個樞紐點的下屬非樞紐節(jié)點數(shù)趨向平均，非樞紐節(jié)點的分配某種意義上是為了滿足其分支流向的限制，求解意義變小，結構如圖5示，可以發(fā)現(xiàn)在樞紐數(shù)每增加一個的前后對比中，部分樞紐點的選擇相對固定，剩下的節(jié)點中因為需要產生新的樞紐點，結構發(fā)生改變，但是網絡結構相對穩(wěn)定。與此同時對比分析了PSO算法的求解結果，參數(shù)設置為1000個算子迭代2000次，慣性權重為1，慣性權重阻尼系數(shù)0.997，個體學習系數(shù)1.5，全局學習系數(shù)2.0，成本對比如表4，通過結果對比可以發(fā)現(xiàn)在本文問題求解上禁忌搜索結果遠好于PSO算法結果。且在運行中PSO算法的求解速度遠慢于禁忌搜索的求解速度。

表4 禁忌搜索和PSO求解結果比較

圖5 樞紐點個數(shù)在4～15之間網絡結構

3.4 實驗結論

測算發(fā)現(xiàn)當不存在樞紐點時，運輸成本為2.21565e+008，雖然運輸成本較小，但是相應的對車輛投入會增加太多，在實際運營之中幾乎不考慮全連通情況，一般若兩點間快遞量足夠時，會采用小車進行兩點之間直通運輸，其余節(jié)點依然是運送至中轉場進行統(tǒng)一轉運。測算當存在一個樞紐點時運輸成本為3.20245e+008，結構如圖6所示，可以發(fā)現(xiàn)樞紐選擇的位置位于整個圖的中心區(qū)，但在實際運營中，樞紐因為面積等客觀因素限制，所處位置幾乎不可能位于中心地段，所以成本遠大于模擬數(shù)值。

圖6 樞紐點個數(shù)為1的網絡

圖7 無折扣分區(qū)

圖8 折扣率為0.7時分區(qū)

通過算例實驗給出不同數(shù)量下的集散點安排方式，且根據網絡結構圖，也可以更科學的對城市劃分片區(qū)進行管理，而不是單純根據區(qū)這一行政單位進行劃分如圖7，8所示，如何對城市網點進行管理也是快遞公司面臨的一大問題，這樣的結構可輔助公司進行決策，進而提升管理效率。

4 總結

本文根據現(xiàn)實需求對城市物流網絡結構進行設計，根據問題特性和學術研究中的樞紐選址問題相結合進行建模并求解，基于現(xiàn)實測算考慮了分支流向約束，設計了高效的求解算法得到高質量的解決方案，并且通過圖形直觀的展示。

根據實驗結果認為將樞紐選址應用于同城快遞網絡結構設計中可以為同城快遞分區(qū)管理提供科學依據。在采用集散點同城快遞模式后，可在城內采取班車制度，定時的對同城快件進行轉運以及配送，可以節(jié)省整個網絡的成本。采用集散點模式后可以提升整個同城快件的時效，實現(xiàn)同城快遞當日達，小時達等。之后可以進行的工作是將車輛路徑問題與此問題相結合，設計相應的行車路線和時間表，將整個同城配送線路進行固化，方便管理，或者根據更具體以及一般化的要求對模型進行進一步的完善，例如加入其他在成本，工作量等更為具體的限制對選址進行進一步確定。