趙 晉,張建軍,嚴蔡華
(1.同濟大學職業(yè)技術教育學院,上海 201804;2.同濟大學中德工程學院,上海 201804;3.同濟大學經(jīng)濟與管理學院,上海 200092)
允許直達的混合軸輻式快遞網(wǎng)絡規(guī)劃模型與算法研究
趙 晉1,2,張建軍3,嚴蔡華3
(1.同濟大學職業(yè)技術教育學院,上海 201804;2.同濟大學中德工程學院,上海 201804;3.同濟大學經(jīng)濟與管理學院,上海 200092)
在快遞企業(yè)的日常運營中,當兩個城市之間的快遞業(yè)務量達到一定規(guī)模之后會允許該城市對之間開展直達遞送。但是這一規(guī)則通常僅在快遞網(wǎng)絡規(guī)劃完成之后由相關子公司提請實施。為彌補這一實際規(guī)則的局部最優(yōu)性缺陷,本論文將直達問題納入網(wǎng)絡規(guī)劃決策,基于全局優(yōu)化的視角構建了允許直達的混合軸幅式快遞網(wǎng)絡規(guī)劃決策模型,設計了相應的求解流程,并對其中的指派關系決策構建了遺傳算法?;趪鴥葮藯U企業(yè)的數(shù)值案例計算證明了該決策模型與求解方法的有效性,研究結果還說明,相對于純軸輻式結構,允許直達的混合軸幅式網(wǎng)絡結構有助于降低網(wǎng)絡總成本,同時在直達線路上能夠有效的降低迂回、提高服務時效性和服務水平。
快遞網(wǎng)絡;網(wǎng)絡規(guī)劃;直達線路;混合軸幅式網(wǎng)絡;遺傳算法
當前,伴隨電子商務、網(wǎng)絡購物發(fā)展迅猛,我國快遞服務業(yè)已進入高速發(fā)展期,2014年我國快遞行業(yè)的日均處理量已超過3500萬件,市場規(guī)模位居世界第一[1]。在企業(yè)界,2012年9月,F(xiàn)edEx和UPS兩大國際快遞巨頭獲得了經(jīng)營中國國內快遞業(yè)務的牌照;2013年5月,阿里巴巴集團宣布建立中國智能骨干物流網(wǎng);2014年12月,國家郵政局批準雅瑪多、歐西愛司、嘉里大通等物流經(jīng)營國內包裹快遞業(yè)務……從這些事件可以看到,當前,快遞業(yè)的機遇與挑戰(zhàn)共存,快遞網(wǎng)絡規(guī)劃成為企業(yè)關注的焦點。
人們對網(wǎng)絡規(guī)劃問題研究的主要熱點有[2-4]:(1)具有混合網(wǎng)絡結構的網(wǎng)絡規(guī)劃問題;(2)具有網(wǎng)絡建設固定成本的網(wǎng)絡規(guī)劃問題;(3)運輸費用有折扣率的網(wǎng)絡規(guī)劃問題;(4)hub處理能力有限的網(wǎng)絡規(guī)劃問題;(5)大規(guī)模網(wǎng)絡規(guī)劃問題的求解算法設計。代表性的研究有:Rodriguez-Martin等[5]研究了包括hub邊緣聯(lián)接網(wǎng)絡與環(huán)形網(wǎng)絡在兩層網(wǎng)絡的規(guī)劃中的作用,并設計了分支切割算法求解;Campbell[6]首次將服務時間作為約束條件納入了與成本最小化為目標的網(wǎng)絡規(guī)劃模型,其中服務時間被轉化為以距離的形式表達;作為一個發(fā)展,Alumura等[7]針對有時限約束的兩層多式聯(lián)運網(wǎng)絡規(guī)劃問題構建了一個混合整數(shù)規(guī)劃模型,其中目標函數(shù)為線性函數(shù)、決策變量數(shù)量為O(n3)。趙宇哲[8]針對航運企業(yè)的重組與全球擴張引起的競爭問題,提出了競爭環(huán)境下的軸-輻式集裝箱海運網(wǎng)絡設計模型。張建軍等[9]研究中國郵政速遞物流公司的陸路網(wǎng)絡規(guī)劃問題,在多時限約束下提出了一個基于個體理性的啟發(fā)式算法并構建了相應的決策支持系統(tǒng)等。傅少川等[10]設計了改進的禁忌搜索智能算法來求解無容量限制的單分配多樞紐中位問題模型。倪玲霖和史峰[12]分析了多分配快遞軸輻網(wǎng)絡的節(jié)點及連接關系、徑路特征與形式等網(wǎng)絡設計要素,在運輸時間預算約束下以分揀費用、運輸費用、中轉費用之和為目標函數(shù)建立了多分配軸輻式快遞網(wǎng)絡樞紐選址與分配優(yōu)化模型[11]。類似的對多分配結構[12]、逆向物流網(wǎng)絡[13]等的研究。
與前述研究不同的是,我們的研究視角聚焦快遞企業(yè)網(wǎng)絡規(guī)劃實踐中的一類直達問題:在企業(yè)調研中,我們發(fā)現(xiàn),企業(yè)管理者通常會有一條判斷規(guī)則,即任何兩個網(wǎng)絡節(jié)點之間的快遞流量如果達到了一定規(guī)模,則在其間開通一條直達運輸線路。這一規(guī)則的價值是顯著的,具有易于操作的優(yōu)點,但是不足之處同樣明顯:它沒有在全局優(yōu)化的視角下分析其可行性。為此,本論文將允許直達納入到快遞網(wǎng)絡規(guī)劃問題中,探討相應的決策模型和求解算法設計問題,為這一類具有重要實踐價值的決策規(guī)則提供科學的方法指導。
本文研究單一指派混合軸輻式網(wǎng)絡結構,每個非樞紐節(jié)點指派給特定的樞紐中轉站,同一子網(wǎng)或者不同子網(wǎng)之間的非樞紐節(jié)點可以有直達線路,各中轉站之間兩兩直達運輸。網(wǎng)絡的結構圖如圖1。
如一批快件配送需求的發(fā)生地為貨運站Si,目的地為貨運站Sj,那么存在三種情況:
(1)直達線路(如果有的話):貨運站Si→貨運站Sj;
(2)同一區(qū)域內:貨運站Si→樞紐中心Hk→貨運站Sj;
換言之,貨運站Si→樞紐中心Hk→樞紐中心Hk→貨運站Sj;
(3)不同區(qū)域內:貨運站Si→樞紐中心Hk→樞紐中心Hm→貨運站Sj;
具體問題可以描述為:
(1)非樞紐節(jié)點都必須且只能與一個樞紐中心相連接;
(2)每個貨運站只能單一指派給特定的樞紐中心,每個樞紐中心的覆蓋區(qū)域內可以有多個貨運站;
(3)網(wǎng)絡中樞紐中心的數(shù)量為P;
(4)非樞紐節(jié)點之間可以直接相連;
(5)兩個節(jié)點之間的流量運輸只能有唯一的路徑,不能將流量分成兩個部分;
(6)樞紐節(jié)點之間全連通。
圖1 允許直達的混合軸輻式網(wǎng)絡結構
針對上述情況,需要解決如下幾個決策問題:
(1)選取哪些節(jié)點作為樞紐中心點?
(2)每個樞紐節(jié)點的覆蓋區(qū)域?各不同覆蓋區(qū)域中非樞紐節(jié)點的貨物運輸路徑?
(3)哪些非樞紐節(jié)點之間建立起直達運輸路徑?
考慮一個混合軸輻式網(wǎng)絡的完整集合G=(V,E),V表示節(jié)點(軸或者輻)的集合V={1,2,…,N},節(jié)點V表示的是網(wǎng)絡中的起點和終點(如城市終端)以及可能的樞紐節(jié)點。E表示連接弧(軸輻中間的連接路徑)的集合,E(i,j)的屬性包括兩點距離dij和從i運輸?shù)絡的貨物流量(體積或者重量)Wij,兩點距離符合三角不等式規(guī)律。之前的文獻中提到,任意兩個節(jié)點對之間的物流運輸包括通過E(i,k)從起點到hub的集貨,經(jīng)過hub點之間的轉運E(k,m),經(jīng)由E(m,j)配送到終點。本文規(guī)定,網(wǎng)絡中任意一個起始終點對之間的正逆物流流量總和超過某一上限,那么就表明這兩個城市節(jié)點之間的快遞需求交互頻繁,根據(jù)兩點距離符合三角不等式規(guī)律,建立直達網(wǎng)絡,而不是通過經(jīng)過中轉站運輸,從而能夠很好的滿足城市對之間的物流需求的時效性要求。
傳統(tǒng)的模型都是假設hub點之間是全連通的,每對hub點之間的流量運輸都有成本折扣α,這是規(guī)模效益的具體體現(xiàn)。但是隨之也帶來一個問題,有時候hub點之間的運輸流量并不比非hub弧上的流量要大,甚至更小。因此本文假設,當非樞紐節(jié)點之間滿足建立起直達線路的條件時,規(guī)定該節(jié)點對之間的流量運輸具有規(guī)模效應,折扣因子為β。
由于每個配送路徑中通常包括三個環(huán)節(jié):集貨、轉運和配送。本文將成本核算成如下表達形式:
Cij=χdik+αdkm+σdmj當貨物通過轉運中心轉運時;
Cij=βdij當存在非樞紐節(jié)點之間的貨物直達運輸時。
通常規(guī)定χ=σ=1,0≤α<1,0≤β<1。
以網(wǎng)絡運營成本最小化為目標,建立如下帶有直達線路的混合軸輻式網(wǎng)絡問題的模型:
(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)
參數(shù)說明:
α表示樞紐中心之間轉運費用的折扣因子;
β表示直達路徑上運輸費用的折扣因子;
p表示需要建立的樞紐中心數(shù)量;
Cij表示節(jié)點對之間的單位運輸費用;
Wij表示從起始點i到終點j的貨物流量;
決策變量說明:
Xk為二進制決策變量,用于判斷節(jié)點k是否為樞紐中心點;當Xk=1時,表示選擇節(jié)點k作為樞紐中心;否則,Xk=0。
Xij為二進制決策變量,用于判斷節(jié)點i是否與節(jié)點j相連通;當Xij=1時,表示節(jié)點i與j相連;否則,Xij=0。
目標函數(shù)說明:
約束條件說明:
式(2)限制了最終需要建立的樞紐中心點的個數(shù);
式(3)、(7)保證了非樞紐節(jié)點只能與一個樞紐中心點相連;
式(4)、(5)是為了明確非樞紐節(jié)點間的直接通路與樞紐節(jié)點和非樞紐節(jié)點連接路徑的區(qū)別;
式(6)、(7)、(8)是對決策變量取值的限制。
上述所構建的混合軸輻式網(wǎng)絡規(guī)劃模型,在實踐中由于網(wǎng)絡節(jié)點數(shù)量較大,屬于大規(guī)模的混合整數(shù)規(guī)劃問題,如果采用精確求解的辦法,通常很難或者根本不可能在可以接受的時間內得到問題的有效解。為此我們設計了一個分步啟發(fā)式算法進行求解,首先將模型求解問題分成三個部分:樞紐選址問題,非樞紐點的直達路徑構建問題,和非樞紐點的指派問題。我們設計的求解流程如圖2。
4.1 樞紐中心選址
設計用于確定候選樞紐中心節(jié)點的求解過程如下:
第一步:計算節(jié)點i到其他與其有流量需求發(fā)生的節(jié)點的總運輸距離和TCi;
第二步:計算節(jié)點i到其他各節(jié)點間的總流量之和TWi;
第三步:計算各節(jié)點的TWi/TCi值;
第四步:對所有節(jié)點的TWi/TCi值按從大到小排序,排位越靠前的節(jié)點被選中的幾率越大,因為TWi/TCi值越大表明其運輸流量大但運輸總距離較小,體現(xiàn)了配送網(wǎng)絡運營價值的最大化;
圖2 決策模型的求解流程
4.2 非樞紐點的直達路徑構建
設候選樞紐中心點得集合為H,非樞紐中心點的集合為U,則H+U=V,V是所有節(jié)點的集合。
最終可以得到,在不同的樞紐中心點選址的情況下,非樞紐點中需要建立直接通路的節(jié)點對集合。
4.3 非樞紐點的指派
在前面兩個部分完成之后,接下來就是要對非樞紐節(jié)點與相應的候選中心集合中的各個節(jié)點進行指派關系的確定。這是決策模型求解的核心部分。我們設計以下遺傳算法,根據(jù)前面兩個階段確定的樞紐中心集合H和非樞紐中心集合U,通過算法的遺傳搜索確定集合U中每個節(jié)點與集合H中的節(jié)點之間的指派關系,最終得到?jīng)Q策模型的解決方案。
(1)初始染色群體的設計
首先,將集合V(元素個數(shù)設為v)中的節(jié)點指派給距離最近的集合H(元素個數(shù)設為h,v+h=n)中的樞紐中心點,每個非樞紐節(jié)點只能指派給唯一特定的樞紐中心,若出現(xiàn)貨運站節(jié)點到達兩個樞紐中心點的距離相等的情況,則隨機選取其中一個即可。如果將集合V中的v個非樞紐節(jié)點到集合H的h個樞紐中心的指派關系作為染色體的一個基因,那么整條染色體的基因個數(shù)將是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)
染色體第一段,非樞紐節(jié)點到樞紐中心1的指派方式:
56789101112111000000
染色體第二段,非樞紐節(jié)點到樞紐中心2的指派方式:
56789101112200110000
染色體第三段,非樞紐節(jié)點到樞紐中心3的指派方式:
56789101112300001100
染色體第四段,非樞紐節(jié)點到樞紐中心4的指派方式:
56789101112400000011
通過設定染色體中的基因片段的不同的基因值,可以得到不同的染色體,組成初始染色體群。不同的染色體中基因片段和基因值各不相同,即相對應的非樞紐節(jié)點與樞紐節(jié)點之間的指派方案和整個運營網(wǎng)絡不同,最終得出的運營網(wǎng)絡總成本也不同,總成本最小的方案最優(yōu),總成本最大的方案最差。
(2)適應度函數(shù)設計
遺傳算法在進化搜索過程中基本不利用外部信息,僅以適應度函數(shù)(Fitness Function)作為進化的依據(jù),利用中群眾每個個體的適應度來進行判斷和搜索。適應度函數(shù)的選取至關重要,直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言,適應度函數(shù)是由目標函數(shù)變換而來的。定義目標函數(shù)的方法,對于同一個問題而言,可能不止一種,選擇時要盡量反應問題本身的整體特性,而不是只追求片面的目標。一般來說,適應度函數(shù)設計主要滿足以下條件:
1)單值、非負、最大化;
2)合理、一致性。要求適應度函數(shù)值反應對應解的優(yōu)劣程度。
3)計算量小。適應度函數(shù)設計要簡單,減少計算時間和復雜性。
4)通用性強。適應度函數(shù)對某類問題,應盡可能通用。
運營網(wǎng)絡的總成本可以通過染色體適應度的設定準確的反映出來,可以將染色體的適應度設為與運營網(wǎng)絡總成本成反比例關系的值,即總成本越小,該染色體的適應度越高,反之則相反。為了達到在遺傳選擇過程中選取適應度較大的染色體概率較大和成本最小化的目的,因此適應度函數(shù)設定如下:
表1 20個戰(zhàn)略重點城市
Fit(f(x))=M-f(x)
其中M為較大的常量,使得函數(shù)值非負。適應度函數(shù)將目標函數(shù)值轉化成適應度,可以看出適應度越大,表明總成本越小,優(yōu)化方案越好。
(3)選擇操作設計
我們選用賭盤選擇法進行選擇運算,具體操作如下:
1)計算出群體中每個個體的適應度Fiti;
3)計算出每個個體被遺傳到下一代群體中的概率pi,pi=Fiti/Fitzong
5)在[0,1]內產(chǎn)生一個均勻分布的偽隨機數(shù)r;
6)若r≤q1,則選擇個體1;否則,選擇個體k,使得qk-1 7)重復5、6步驟共pop_size次,每次選出一個染色體,最終構成新的種群。 (4)交叉操作設計 我們采用多點交叉的方法來解混合軸輻式網(wǎng)絡規(guī)劃問題,主要有以下步驟: 1)設定交叉概率pc,循環(huán)次數(shù)Nc為:Nc=Chr_gene_size*pop_size*pc/2 其中:Chr_gene_size為每條染色體中基因個數(shù); 2)在每一次的循環(huán)過程中,選取隨機配對的染色體對進行基因交叉運算,從而產(chǎn)生新的個體,進而組成新的染色體群體。 (5)變異操作設計 變異過程主要有以下步驟: 1)設定變異概率pm,變異循環(huán)次數(shù)為Nd:Nd=Chr_gene_size*pop_size*pm 2)在每一次的變異過程中,隨機選取一個染色體,隨機選取該染色體中的任意基因點位進行變異,產(chǎn)生新的個體。 我們以國內某標桿快遞公司的長三角區(qū)域陸路快遞網(wǎng)絡設計為例對上述決策過程的可適用性進行驗證。 5.1 數(shù)據(jù)準備 本實例需要準備的基礎數(shù)據(jù)如下: 1)城市節(jié)點數(shù)據(jù):節(jié)點集合包括樞紐節(jié)點和非樞紐節(jié)點,如表1; 2)距離和流量數(shù)據(jù):距離數(shù)據(jù)為每個節(jié)點對之間的距離,該距離矩陣為對稱矩陣,由百度地圖測得;流量數(shù)據(jù)為起始站到終點站在統(tǒng)計周期內的平均貨流量,節(jié)點對之間的正逆向流量是不一樣的,因企業(yè)保密問題,略去展示。 3)遺傳算法基本參數(shù)數(shù)據(jù):包括染色體種群大小、染色體基因數(shù)目、種群的最大進化代數(shù)、交叉概率、變異概率、適應度函數(shù)中的常量M、迭代次數(shù),如表2。 表2 遺傳算法參數(shù)設定 5.2 樞紐中心的確定 表3 確定的樞紐中心 表4 城市節(jié)點對的流量 至此,可以將案例中的城市節(jié)點分為兩大類: 第一類,樞紐中心點集合:上海、蘇州、杭州、南京; 第二類,非樞紐節(jié)點集合:常州、合肥、淮安、嘉興、金華、連云港、南京、南通、寧波、紹興、臺州、溫州、無錫、徐州、鹽城、揚州、鎮(zhèn)江。 5.3 非樞紐節(jié)點之間直達路徑的確定 通過數(shù)據(jù)整理,得到表4。 由表4,根據(jù)流量閾值判斷,可以得出7對直達線路:常州——南通、南通——寧波、南通——無錫、鹽城——寧波、鹽城——臺州、鹽城——無錫、揚州——溫州。 5.4 非樞紐節(jié)點指派路徑的確定 基于節(jié)4.3所設計的遺傳算法,采用Matlab 7.0對網(wǎng)絡節(jié)點的指派問題進行了編程,針對本案例的20個節(jié)點的問題規(guī)模進行求解,最終得出全局近似最優(yōu)解如表5、6所示。 表5 求解所得的各項成本 表6 各樞紐中心的覆蓋情況 5.5 結果分析 我們同樣計算了不允許直達線路存在的網(wǎng)絡結果,如表7所示。通過表6和表7的對比我們可以發(fā)現(xiàn),在允許直達線路存在時,網(wǎng)絡總成本比不允許情形減少了約0.79%。另一方面,由于減少了迂回,7對直達線路的存在能夠顯著提高它們的服務效率和服務水平。 表7 不允許直達時的成本 本文在允許直達的情形下建立了相應的混合軸輻式快遞網(wǎng)絡規(guī)劃決策模型和決策流程,在保證時效性要求的前提下,以網(wǎng)絡成本最小化為目標,對帶有直達線路的軸輻式網(wǎng)絡的規(guī)劃問題進行了分析和數(shù)學描述,并設計了遺傳算法對關鍵問題進行求解。進而,基于實際的企業(yè)運營數(shù)據(jù)的實證研究證明了該決策模型和方法的有效性,并且發(fā)現(xiàn):允許直達時,網(wǎng)絡成本能得到控制,并提高服務效率。 另一方面,本文研究存在以下不足之處尚需后續(xù)做進一步研究: (1)只考慮兩個層級的混合軸輻式網(wǎng)絡設計,如果能夠綜合考慮3個層次甚至更多軸輻式網(wǎng)絡,將更加貼近實際,能夠更好地指導實際應用; (2)本文初步考慮了以成本為目標的優(yōu)化模型,并進行了模型求解,可以嘗試采用多目標優(yōu)化模型,加入相應的時間約束,這方面的研究將是今后進一步探討的重點; (3)在算法設計中,本文首先確定了樞紐中心的個數(shù)和選址,這對成本最小化目標有一定的影響;根據(jù)相關文獻,可以從全局最優(yōu)的角度出發(fā),以成本最小化為目標,讓算法自動求解出相應的樞紐中心個數(shù)和選址,從而給出全局最優(yōu)解,等。 [1] 國家郵政局.國家郵政局公布2014年郵政行業(yè)運行情況[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] 趙宇哲.競爭環(huán)境下的軸-輻式集裝箱海運網(wǎng)絡設計問題[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] 傅少川,胡夢飛,唐方成.禁忌搜索算法在單分配多樞紐軸輻式物流網(wǎng)絡中的應用[J].中國管理科學,2012,20(3):145-151. [11] 何明珂,程紅晶.快遞企業(yè)航空貨運網(wǎng)絡的構建[J].運籌與管理,2013,22(6):232-242. [12] 倪玲霖,史峰.多分配快遞軸輻網(wǎng)絡的樞紐選址與分配優(yōu)化方法[J].系統(tǒng)工程理論與實踐,2012,32(2):441-448. [13] 熊中楷,方衍,張聰譽.以舊換新收購方式下的逆向物流網(wǎng)絡優(yōu)化設計[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);上海市社科規(guī)劃課題(2014BGL025) 張建軍(1978-),男(漢族),江西人,同濟大學經(jīng)濟與管理學院副教授,博士生導師,研究方向:物流與供應鏈管理,E-mail:zhangjianjun@#edu.cn. F272 A5 求解算法設計與案例計算
6 結語