允許直達的混合軸輻式快遞網絡規劃模型與算法研究

趙 晉，張建軍，嚴蔡華

(1.同濟大學職業技術教育學院，上海 201804；2.同濟大學中德工程學院，上海 201804；3.同濟大學經濟與管理學院，上海 200092)

允許直達的混合軸輻式快遞網絡規劃模型與算法研究

趙 晉1,2，張建軍3，嚴蔡華3

(1.同濟大學職業技術教育學院，上海 201804；2.同濟大學中德工程學院，上海 201804；3.同濟大學經濟與管理學院，上海 200092)

在快遞企業的日常運營中，當兩個城市之間的快遞業務量達到一定規模之后會允許該城市對之間開展直達遞送。但是這一規則通常僅在快遞網絡規劃完成之后由相關子公司提請實施。為彌補這一實際規則的局部最優性缺陷，本論文將直達問題納入網絡規劃決策，基于全局優化的視角構建了允許直達的混合軸幅式快遞網絡規劃決策模型，設計了相應的求解流程，并對其中的指派關系決策構建了遺傳算法。基于國內標桿企業的數值案例計算證明了該決策模型與求解方法的有效性，研究結果還說明，相對于純軸輻式結構，允許直達的混合軸幅式網絡結構有助于降低網絡總成本，同時在直達線路上能夠有效的降低迂回、提高服務時效性和服務水平。

快遞網絡；網絡規劃；直達線路；混合軸幅式網絡；遺傳算法

1 引言

當前，伴隨電子商務、網絡購物發展迅猛，我國快遞服務業已進入高速發展期，2014年我國快遞行業的日均處理量已超過3500萬件，市場規模位居世界第一[1]。在企業界，2012年9月，FedEx和UPS兩大國際快遞巨頭獲得了經營中國國內快遞業務的牌照；2013年5月，阿里巴巴集團宣布建立中國智能骨干物流網；2014年12月，國家郵政局批準雅瑪多、歐西愛司、嘉里大通等物流經營國內包裹快遞業務……從這些事件可以看到，當前，快遞業的機遇與挑戰共存，快遞網絡規劃成為企業關注的焦點。

人們對網絡規劃問題研究的主要熱點有[2-4]：(1)具有混合網絡結構的網絡規劃問題；(2)具有網絡建設固定成本的網絡規劃問題；(3)運輸費用有折扣率的網絡規劃問題；(4)hub處理能力有限的網絡規劃問題；(5)大規模網絡規劃問題的求解算法設計。代表性的研究有：Rodriguez-Martin等[5]研究了包括hub邊緣聯接網絡與環形網絡在兩層網絡的規劃中的作用，并設計了分支切割算法求解；Campbell[6]首次將服務時間作為約束條件納入了與成本最小化為目標的網絡規劃模型，其中服務時間被轉化為以距離的形式表達；作為一個發展，Alumura等[7]針對有時限約束的兩層多式聯運網絡規劃問題構建了一個混合整數規劃模型，其中目標函數為線性函數、決策變量數量為O(n3)。趙宇哲[8]針對航運企業的重組與全球擴張引起的競爭問題,提出了競爭環境下的軸-輻式集裝箱海運網絡設計模型。張建軍等[9]研究中國郵政速遞物流公司的陸路網絡規劃問題，在多時限約束下提出了一個基于個體理性的啟發式算法并構建了相應的決策支持系統等。傅少川等[10]設計了改進的禁忌搜索智能算法來求解無容量限制的單分配多樞紐中位問題模型。倪玲霖和史峰[12]分析了多分配快遞軸輻網絡的節點及連接關系、徑路特征與形式等網絡設計要素，在運輸時間預算約束下以分揀費用、運輸費用、中轉費用之和為目標函數建立了多分配軸輻式快遞網絡樞紐選址與分配優化模型[11]。類似的對多分配結構[12]、逆向物流網絡[13]等的研究。

與前述研究不同的是，我們的研究視角聚焦快遞企業網絡規劃實踐中的一類直達問題：在企業調研中，我們發現，企業管理者通常會有一條判斷規則，即任何兩個網絡節點之間的快遞流量如果達到了一定規模，則在其間開通一條直達運輸線路。這一規則的價值是顯著的，具有易于操作的優點，但是不足之處同樣明顯：它沒有在全局優化的視角下分析其可行性。為此，本論文將允許直達納入到快遞網絡規劃問題中，探討相應的決策模型和求解算法設計問題，為這一類具有重要實踐價值的決策規則提供科學的方法指導。

2 問題描述

本文研究單一指派混合軸輻式網絡結構，每個非樞紐節點指派給特定的樞紐中轉站，同一子網或者不同子網之間的非樞紐節點可以有直達線路，各中轉站之間兩兩直達運輸。網絡的結構圖如圖1。

如一批快件配送需求的發生地為貨運站Si，目的地為貨運站Sj，那么存在三種情況：

(1)直達線路(如果有的話)：貨運站Si→貨運站Sj；

(2)同一區域內：貨運站Si→樞紐中心Hk→貨運站Sj；

換言之，貨運站Si→樞紐中心Hk→樞紐中心Hk→貨運站Sj；

(3)不同區域內：貨運站Si→樞紐中心Hk→樞紐中心Hm→貨運站Sj；

具體問題可以描述為：

(1)非樞紐節點都必須且只能與一個樞紐中心相連接；

(2)每個貨運站只能單一指派給特定的樞紐中心，每個樞紐中心的覆蓋區域內可以有多個貨運站；

(3)網絡中樞紐中心的數量為P；

(4)非樞紐節點之間可以直接相連；

(5)兩個節點之間的流量運輸只能有唯一的路徑，不能將流量分成兩個部分；

(6)樞紐節點之間全連通。

圖1 允許直達的混合軸輻式網絡結構

針對上述情況，需要解決如下幾個決策問題：

(1)選取哪些節點作為樞紐中心點？

(2)每個樞紐節點的覆蓋區域？各不同覆蓋區域中非樞紐節點的貨物運輸路徑？

(3)哪些非樞紐節點之間建立起直達運輸路徑？

3 決策模型構建

考慮一個混合軸輻式網絡的完整集合G=(V,E)，V表示節點(軸或者輻)的集合V={1,2,…,N}，節點V表示的是網絡中的起點和終點(如城市終端)以及可能的樞紐節點。E表示連接弧(軸輻中間的連接路徑)的集合，E(i,j)的屬性包括兩點距離dij和從i運輸到j的貨物流量(體積或者重量)Wij，兩點距離符合三角不等式規律。之前的文獻中提到，任意兩個節點對之間的物流運輸包括通過E(i,k)從起點到hub的集貨，經過hub點之間的轉運E(k,m)，經由E(m,j)配送到終點。本文規定，網絡中任意一個起始終點對之間的正逆物流流量總和超過某一上限，那么就表明這兩個城市節點之間的快遞需求交互頻繁，根據兩點距離符合三角不等式規律，建立直達網絡，而不是通過經過中轉站運輸，從而能夠很好的滿足城市對之間的物流需求的時效性要求。

傳統的模型都是假設hub點之間是全連通的，每對hub點之間的流量運輸都有成本折扣α，這是規模效益的具體體現。但是隨之也帶來一個問題，有時候hub點之間的運輸流量并不比非hub弧上的流量要大，甚至更小。因此本文假設，當非樞紐節點之間滿足建立起直達線路的條件時，規定該節點對之間的流量運輸具有規模效應，折扣因子為β。

由于每個配送路徑中通常包括三個環節：集貨、轉運和配送。本文將成本核算成如下表達形式：

Cij=χdik+αdkm+σdmj當貨物通過轉運中心轉運時；

Cij=βdij當存在非樞紐節點之間的貨物直達運輸時。

通常規定χ=σ=1,0≤α<1,0≤β<1。

以網絡運營成本最小化為目標，建立如下帶有直達線路的混合軸輻式網絡問題的模型：

(1)

約束條件：

(2)

(3)

Xi+δij≤1對于任意的i,j

(4)

δij=δji對于任意的i,j

(5)

Xk∈{0,1}對于任意的k

(6)

Xij∈{0,1}對于任意的i,j

(7)

δij∈{0,1}對于任意的i,j

(8)

參數說明：

α表示樞紐中心之間轉運費用的折扣因子；

β表示直達路徑上運輸費用的折扣因子；

p表示需要建立的樞紐中心數量；

Cij表示節點對之間的單位運輸費用；

Wij表示從起始點i到終點j的貨物流量；

決策變量說明：

Xk為二進制決策變量，用于判斷節點k是否為樞紐中心點；當Xk=1時，表示選擇節點k作為樞紐中心；否則，Xk=0。

Xij為二進制決策變量，用于判斷節點i是否與節點j相連通；當Xij=1時，表示節點i與j相連；否則，Xij=0。

目標函數說明:

約束條件說明：

式(2)限制了最終需要建立的樞紐中心點的個數；

式(3)、(7)保證了非樞紐節點只能與一個樞紐中心點相連；

式(4)、(5)是為了明確非樞紐節點間的直接通路與樞紐節點和非樞紐節點連接路徑的區別；

式(6)、(7)、(8)是對決策變量取值的限制。

4 模型求解算法設計

上述所構建的混合軸輻式網絡規劃模型，在實踐中由于網絡節點數量較大，屬于大規模的混合整數規劃問題，如果采用精確求解的辦法，通常很難或者根本不可能在可以接受的時間內得到問題的有效解。為此我們設計了一個分步啟發式算法進行求解，首先將模型求解問題分成三個部分：樞紐選址問題，非樞紐點的直達路徑構建問題，和非樞紐點的指派問題。我們設計的求解流程如圖2。

4.1 樞紐中心選址

設計用于確定候選樞紐中心節點的求解過程如下：

第一步：計算節點i到其他與其有流量需求發生的節點的總運輸距離和TCi；

第二步：計算節點i到其他各節點間的總流量之和TWi；

第三步：計算各節點的TWi/TCi值；

第四步：對所有節點的TWi/TCi值按從大到小排序，排位越靠前的節點被選中的幾率越大，因為TWi/TCi值越大表明其運輸流量大但運輸總距離較小，體現了配送網絡運營價值的最大化；

圖2 決策模型的求解流程

4.2 非樞紐點的直達路徑構建

設候選樞紐中心點得集合為H，非樞紐中心點的集合為U，則H+U=V，V是所有節點的集合。

最終可以得到，在不同的樞紐中心點選址的情況下，非樞紐點中需要建立直接通路的節點對集合。

4.3 非樞紐點的指派

在前面兩個部分完成之后，接下來就是要對非樞紐節點與相應的候選中心集合中的各個節點進行指派關系的確定。這是決策模型求解的核心部分。我們設計以下遺傳算法，根據前面兩個階段確定的樞紐中心集合H和非樞紐中心集合U，通過算法的遺傳搜索確定集合U中每個節點與集合H中的節點之間的指派關系，最終得到決策模型的解決方案。

(1)初始染色群體的設計

首先，將集合V(元素個數設為v)中的節點指派給距離最近的集合H(元素個數設為h，v+h=n)中的樞紐中心點，每個非樞紐節點只能指派給唯一特定的樞紐中心，若出現貨運站節點到達兩個樞紐中心點的距離相等的情況，則隨機選取其中一個即可。如果將集合V中的v個非樞紐節點到集合H的h個樞紐中心的指派關系作為染色體的一個基因，那么整條染色體的基因個數將是v*h個，即一條染色體中有v段，每一段染色體有h個基因，h個基因的表示方式為二進制，1表示貨運站指派給所在的染色體基因段的樞紐中心，0表示貨運站不指派給所在的染色體基因段的樞紐中心。

例如：v=4，h=8，V=(1,2,3,4)，H=(5,6,7,8,9,10,11,12)

染色體第一段，非樞紐節點到樞紐中心1的指派方式：

56789101112111000000

染色體第二段，非樞紐節點到樞紐中心2的指派方式：

56789101112200110000

染色體第三段，非樞紐節點到樞紐中心3的指派方式：

56789101112300001100

染色體第四段，非樞紐節點到樞紐中心4的指派方式：

56789101112400000011

通過設定染色體中的基因片段的不同的基因值，可以得到不同的染色體，組成初始染色體群。不同的染色體中基因片段和基因值各不相同，即相對應的非樞紐節點與樞紐節點之間的指派方案和整個運營網絡不同，最終得出的運營網絡總成本也不同，總成本最小的方案最優，總成本最大的方案最差。

(2)適應度函數設計

遺傳算法在進化搜索過程中基本不利用外部信息，僅以適應度函數(Fitness Function)作為進化的依據，利用中群眾每個個體的適應度來進行判斷和搜索。適應度函數的選取至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優解。一般而言，適應度函數是由目標函數變換而來的。定義目標函數的方法，對于同一個問題而言，可能不止一種，選擇時要盡量反應問題本身的整體特性，而不是只追求片面的目標。一般來說，適應度函數設計主要滿足以下條件：

1)單值、非負、最大化；

2)合理、一致性。要求適應度函數值反應對應解的優劣程度。

3)計算量小。適應度函數設計要簡單，減少計算時間和復雜性。

4)通用性強。適應度函數對某類問題，應盡可能通用。

運營網絡的總成本可以通過染色體適應度的設定準確的反映出來，可以將染色體的適應度設為與運營網絡總成本成反比例關系的值，即總成本越小，該染色體的適應度越高，反之則相反。為了達到在遺傳選擇過程中選取適應度較大的染色體概率較大和成本最小化的目的，因此適應度函數設定如下：

表1 20個戰略重點城市

Fit(f(x))=M-f(x)

其中M為較大的常量，使得函數值非負。適應度函數將目標函數值轉化成適應度，可以看出適應度越大，表明總成本越小，優化方案越好。

(3)選擇操作設計

我們選用賭盤選擇法進行選擇運算，具體操作如下：

1)計算出群體中每個個體的適應度Fiti；

3)計算出每個個體被遺傳到下一代群體中的概率pi，pi=Fiti/Fitzong

5)在[0,1]內產生一個均勻分布的偽隨機數r；

6)若r≤q1，則選擇個體1；否則，選擇個體k，使得qk-1

7)重復5、6步驟共pop_size次，每次選出一個染色體，最終構成新的種群。

(4)交叉操作設計

我們采用多點交叉的方法來解混合軸輻式網絡規劃問題，主要有以下步驟：

1)設定交叉概率pc，循環次數Nc為：Nc=Chr_gene_size*pop_size*pc/2

其中：Chr_gene_size為每條染色體中基因個數；

2)在每一次的循環過程中，選取隨機配對的染色體對進行基因交叉運算，從而產生新的個體，進而組成新的染色體群體。

(5)變異操作設計

變異過程主要有以下步驟：

1)設定變異概率pm，變異循環次數為Nd：Nd=Chr_gene_size*pop_size*pm

2)在每一次的變異過程中，隨機選取一個染色體，隨機選取該染色體中的任意基因點位進行變異，產生新的個體。

5 求解算法設計與案例計算

我們以國內某標桿快遞公司的長三角區域陸路快遞網絡設計為例對上述決策過程的可適用性進行驗證。

5.1 數據準備

本實例需要準備的基礎數據如下：

1)城市節點數據：節點集合包括樞紐節點和非樞紐節點，如表1；

2)距離和流量數據：距離數據為每個節點對之間的距離，該距離矩陣為對稱矩陣，由百度地圖測得；流量數據為起始站到終點站在統計周期內的平均貨流量，節點對之間的正逆向流量是不一樣的，因企業保密問題，略去展示。

3)遺傳算法基本參數數據：包括染色體種群大小、染色體基因數目、種群的最大進化代數、交叉概率、變異概率、適應度函數中的常量M、迭代次數，如表2。

表2 遺傳算法參數設定

5.2 樞紐中心的確定

表3 確定的樞紐中心

表4 城市節點對的流量

至此，可以將案例中的城市節點分為兩大類：

第一類，樞紐中心點集合：上海、蘇州、杭州、南京；

第二類，非樞紐節點集合：常州、合肥、淮安、嘉興、金華、連云港、南京、南通、寧波、紹興、臺州、溫州、無錫、徐州、鹽城、揚州、鎮江。

5.3 非樞紐節點之間直達路徑的確定

通過數據整理，得到表4。

由表4，根據流量閾值判斷，可以得出7對直達線路：常州——南通、南通——寧波、南通——無錫、鹽城——寧波、鹽城——臺州、鹽城——無錫、揚州——溫州。

5.4 非樞紐節點指派路徑的確定

基于節4.3所設計的遺傳算法，采用Matlab 7.0對網絡節點的指派問題進行了編程，針對本案例的20個節點的問題規模進行求解，最終得出全局近似最優解如表5、6所示。

表5 求解所得的各項成本

表6 各樞紐中心的覆蓋情況

5.5 結果分析

我們同樣計算了不允許直達線路存在的網絡結果，如表7所示。通過表6和表7的對比我們可以發現，在允許直達線路存在時，網絡總成本比不允許情形減少了約0.79%。另一方面，由于減少了迂回，7對直達線路的存在能夠顯著提高它們的服務效率和服務水平。

表7 不允許直達時的成本

6 結語

本文在允許直達的情形下建立了相應的混合軸輻式快遞網絡規劃決策模型和決策流程，在保證時效性要求的前提下，以網絡成本最小化為目標，對帶有直達線路的軸輻式網絡的規劃問題進行了分析和數學描述，并設計了遺傳算法對關鍵問題進行求解。進而，基于實際的企業運營數據的實證研究證明了該決策模型和方法的有效性，并且發現：允許直達時，網絡成本能得到控制，并提高服務效率。

另一方面，本文研究存在以下不足之處尚需后續做進一步研究：

(1)只考慮兩個層級的混合軸輻式網絡設計，如果能夠綜合考慮3個層次甚至更多軸輻式網絡，將更加貼近實際，能夠更好地指導實際應用；

(2)本文初步考慮了以成本為目標的優化模型，并進行了模型求解，可以嘗試采用多目標優化模型，加入相應的時間約束，這方面的研究將是今后進一步探討的重點；

(3)在算法設計中，本文首先確定了樞紐中心的個數和選址，這對成本最小化目標有一定的影響；根據相關文獻，可以從全局最優的角度出發，以成本最小化為目標，讓算法自動求解出相應的樞紐中心個數和選址，從而給出全局最優解，等。

[1] 國家郵政局.國家郵政局公布2014年郵政行業運行情況[EB/OL].[2015-01-15].http://www.spb.gov.cn/dtxx_15079/201501/t20150115_410741.html，2014.

[2] Campbell J F, O'Kelly M E. Twenty-five years of hub location research[J]. Transportation Science, 2012，46(2): 153-169.

[3] Contreras I, Fernández E. General network design: A unified view of combined location and network design problems[J]. European Journal of Operational Research, 2012, 219(3): 680-697.

[4] Alumur S, Kara B Y. Network hub location problems: The state of the art[J]. European Journal of Operational Research, 2008, 190 (1): 1-21.

[5] Rodriguez-Martin I, Salazar-Gonzalez J, Yaman H.A branch-and-cut algorithm for two-level survivable network design problems[J]. Computers & Operations Research, 2016, 67(c):102-112.

[6] Campbell J F. Hub location for time definite transportation[J]. Computers & Operations Research, 2009, 36(12): 3107-3116.

[7] Alumura S A,Yamanb H, Kara B Y. Hierarchical multimodal hub location problem with time-definite deliveries[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(6): 1107-1120.

[8] 趙宇哲.競爭環境下的軸-輻式集裝箱海運網絡設計問題[J].中國管理科學，2015，23(7)：103-112.

[9] Zhang Jianjun, Tang Ou, Zhao Jin, et al.CPEL redesigns its land express network[J]. Interfaces,2013,43(3):221-231.

[10] 傅少川，胡夢飛，唐方成.禁忌搜索算法在單分配多樞紐軸輻式物流網絡中的應用[J].中國管理科學，2012，20(3)：145-151.

[11] 何明珂，程紅晶.快遞企業航空貨運網絡的構建[J].運籌與管理，2013，22(6)：232-242.

[12] 倪玲霖，史峰.多分配快遞軸輻網絡的樞紐選址與分配優化方法[J].系統工程理論與實踐，2012，32(2)：441-448.

[13] 熊中楷，方衍，張聰譽.以舊換新收購方式下的逆向物流網絡優化設計[J].中國管理科學，2011，19(6)：65-72.

Research on Hybrid Hub-spoke Express Network Decision with Point-to-point Direct Shipment

ZHAO Jin1,2, ZHANG Jian-jun3, YAN Cai-hua3

(1.Institute of vocational education, Tongji University, Shanghai 201804, China;2.China-German School of Engineering,Tongji University, Shanghai 201804, China;3.School of Economics and Management, Tongji University, Shanghai 200092, China)

express network; network design; point-to-point direct shipment; hybrid hub-spoke network; genetic algorithm

1003-207(2016)11-0058-08

10.16381/j.cnki.issn1003-207x.2016.11.007

2015-06-06；

2016-02-25

國家自然科學基金資助項目(71102071, 71373180);上海市社科規劃課題(2014BGL025)

張建軍(1978-)，男(漢族)，江西人，同濟大學經濟與管理學院副教授，博士生導師，研究方向：物流與供應鏈管理，E-mail：zhangjianjun@tongji.edu.cn.

F272

A