馬瑞光

（深圳市逸馬商業(yè)科技有限公司 廣東深圳 518000）

引言

軸輻式網(wǎng)絡(luò)（Hub-and-spoke network）的概念起源于航空網(wǎng)絡(luò)規(guī)劃，其指的是將一個或者幾個機(jī)場作為樞紐點（hub），通過樞紐點進(jìn)行中轉(zhuǎn)銜接完成航空布局，同時機(jī)場周邊較小的城市不通航，即為非樞紐點（Spoke）。目前，軸輻式網(wǎng)絡(luò)結(jié)構(gòu)已經(jīng)廣泛應(yīng)用于軍事、郵政、通訊、旅游等行業(yè)中，實踐證明，軸輻式網(wǎng)絡(luò)具有優(yōu)化資源配置、提高運輸效率、產(chǎn)生規(guī)模經(jīng)濟(jì)等作用。在軸輻式網(wǎng)絡(luò)中，非樞紐點上的流量首先要匯集到樞紐點，然后再由樞紐點分配到網(wǎng)絡(luò)上的其他點。由于樞紐點匯集了其他非樞紐點的流量，因此其產(chǎn)生了規(guī)模效益，降低了物流成本。但是在實際情況中，每個樞紐點都存在最大的流量處理能力，如果集中到樞紐點的貨流量超出了樞紐點的最大流量處理能力，那么就會導(dǎo)致樞紐點出現(xiàn)擁堵，這就影響了貨物的正常運輸，增加了成本，降低了邊際效益。所以要結(jié)合樞紐地的流量處理能力，考慮樞紐點數(shù)量以及位置，即考慮樞紐點的流量限制下進(jìn)行軸輻式網(wǎng)絡(luò)優(yōu)化是很有必要的。

文獻(xiàn)綜述

目前，在軸輻式網(wǎng)絡(luò)的擁堵研究和軸輻式網(wǎng)絡(luò)模型的算法方面，國內(nèi)外學(xué)者進(jìn)行了相關(guān)研究。在軸輻式網(wǎng)絡(luò)的擁堵研究方面，楊斌，鄧志慧，胡志華（2016）在考慮了Hub擁堵成本的情況下，構(gòu)建了最小化運輸成本、建設(shè)成本和擁堵成本的非線性規(guī)劃模型，并以此進(jìn)行了驗證；林天倚，盧春霞（2013）綜合考慮了海運網(wǎng)絡(luò)樞紐港的流量負(fù)擔(dān)和成本，構(gòu)建了基于擁堵控制的軸輻式海運網(wǎng)絡(luò)樞紐模型，并使用拉格朗日松弛算法對模型進(jìn)行求解；王卉（2013）首先把混沌粒子群算法應(yīng)用在無容量限制的軸輻式航空網(wǎng)絡(luò)設(shè)計中，然后加以調(diào)整，考慮了樞紐點流量上的擁堵成本，最后結(jié)合航空運輸需求不確定性的特點，建立了需求不確定的樞紐航線網(wǎng)絡(luò)優(yōu)化模型；翁克瑞（2012）考慮了軸輻式網(wǎng)絡(luò)中的固定軸線成本，建立了該問題的混合整數(shù)規(guī)劃模型，并考慮了O-D流的繞道約束問題；Campbell（2009）對p樞紐中位問題、無容量限制的樞紐位置問題、樞紐覆蓋問題以及p樞紐中心問題進(jìn)行建模分析，并在樞紐中位問題中考慮了航線的軸線容量限制、樞紐節(jié)點限制以及航線的開辟成本等。在此基礎(chǔ)上，其他學(xué)者對軸輻式模型進(jìn)行了擴(kuò)展，O’Kelly、Skorin-Kapov、Bryan（1996）探討了當(dāng)樞紐建設(shè)成本以及軸線運輸成本折扣發(fā)生變化時，單分配和多分配的P樞紐中位問題的相應(yīng)變化規(guī)律；S.A.ALUMUR（2012）研究了交通運輸方式不確定性的情況下的樞紐網(wǎng)絡(luò)設(shè)計問題；R.C.LEACHMAN（2011）基于排隊理論預(yù)測了港口樞紐的流量和擁堵時間之間的關(guān)系，建立了基于貨量、人員和裝備的模型，并以中美之間的集裝箱運輸數(shù)據(jù)進(jìn)行實證研究；L.FAN（2012）建立了多式聯(lián)運網(wǎng)絡(luò)，對集裝箱運輸?shù)呢浟恳约皳矶铝窟M(jìn)行了研究；CHEN G（2013）提出了船舶時間窗口的概念，并利用該概念處理口岸擁堵的問題。

圖1 不同a值時的變動成本函數(shù)圖像

在軸輻式網(wǎng)絡(luò)模型的算法方面，傅少川（2012）對軸輻式網(wǎng)絡(luò)進(jìn)行了優(yōu)化，建立了單分配多樞紐中位問題模型，并利用改進(jìn)的禁忌搜索算法進(jìn)行求解；柏明國（2008）在多重分配多樞紐中位問題中利用禁忌搜索算法的啟發(fā)式算法來進(jìn)行求解；熊焱，王靜慧（2012）利用混合遺傳算法來求解貨運軸輻式網(wǎng)絡(luò)模型；付江月，陳剛（2015）針對軸輻式城市物流網(wǎng)絡(luò)模型設(shè)計了帶精英策略的自適應(yīng)遺傳算法；Marcos 和Cunba（2009）利用多初始解的禁忌搜索算法來求解單分配樞紐問題；Iwasa， Saito 和Matsui（2009）利用確定型迭代算法和隨機(jī)型迭代算法來解決單分配問題；Klincewicz（1992）使用貪婪隨機(jī)搜索算法和禁忌搜索算法來求解P-樞紐中位問題。

考慮到樞紐點的流量控制，本文首先考慮了基于流量控制可能會出現(xiàn)的變動成本，然后建立了優(yōu)化后的軸輻式物流網(wǎng)絡(luò)模型，并采用禁忌搜索算法進(jìn)行求解，最后通過算例來比較優(yōu)化后模型的合理性和有效性。

模型的建立

（一）樞紐點容量限制的成本函數(shù)

在軸輻式網(wǎng)絡(luò)中，非樞紐點需要通過樞紐點進(jìn)行連通，雖然軸輻式網(wǎng)絡(luò)可以形成規(guī)模經(jīng)濟(jì)，但這也意味著會有大量的流量通過樞紐點，考慮到樞紐點流量控制的情況，可以用基于流量的樞紐點的成本函數(shù)來表示樞紐點的容量限制情況。樞紐點的成本函數(shù)包括固定成本和變動成本。固定成本是指建設(shè)樞紐點之初所進(jìn)行的固定投入，例如設(shè)備、人工、機(jī)械等；變動成本是指隨著經(jīng)過樞紐點的流量而不斷增加的費用，變動費用和經(jīng)過樞紐的流量成正比。當(dāng)較多流量匯集在樞紐點時，會直接導(dǎo)致變動成本的顯著增加。則成本函數(shù)的參數(shù)設(shè)置如下：

表1 a、b的值對最小總成本的影響

表2 a、b的值對樞紐點的流量的影響

G：固定成本；

w：流經(jīng)樞紐點的流量。

變動成本隨著樞紐點之間的流量的增加而增加。當(dāng)樞紐點的流量小于安全值時，變動成本小幅緩慢上升；當(dāng)樞紐點的流量超過安全值時，變動成本急劇上升。故呈現(xiàn)指數(shù)變化的情況，變動成本和流量之間的關(guān)系可以用以下冪函數(shù)來表示：

F(w)=bwa

f（w）表示樞紐點的變動成本，在這種情況下，a為大于0的數(shù)，當(dāng)b=1時，a取不同的值時的變動成本如圖1所示，其中y軸是變動成本，x軸是樞紐點流量。

由于樞紐點的建設(shè)存在固定成本，則樞紐點的成本函數(shù)為：

F(w)=f(w)+G=bwa+G

（二）考慮到樞紐點成本的軸輻式網(wǎng)絡(luò)模型

在考慮到樞紐點成本的情況下，軸輻式網(wǎng)絡(luò)模型優(yōu)化的目標(biāo)是確定樞紐點的位置，降低總成本，并優(yōu)化軸輻式網(wǎng)絡(luò)中的流量。該優(yōu)化模型建立在一個具有N個節(jié)點的軸輻式網(wǎng)絡(luò)中，有P個樞紐點，k、m為樞紐點，i、j為非樞紐點，具體參數(shù)設(shè)置如下：

wkm：樞紐點k、m之間的流量；

wijkm：從i點出發(fā)，經(jīng)過k、m到達(dá)j點的流量；

Oi：流出節(jié)點i的流量；

Di：流入節(jié)點i的流量；

cik：節(jié)點i和節(jié)點k之間的標(biāo)準(zhǔn)單位運輸成本。

該優(yōu)化模型的假設(shè)條件如下：

（1）在軸輻式網(wǎng)絡(luò)中具有N個節(jié)點，其中樞紐點為P；

（2）樞紐點之間完全直連，而非樞紐點之間通過樞紐點連接；

（3）單個非樞紐點可以多個樞紐點進(jìn)行連接；

（4）樞紐點之間的單位運輸成本折扣系數(shù)為α，0＜α＜1。

在滿足上述假設(shè)條件的情況下，模型的目標(biāo)是使得軸輻式網(wǎng)絡(luò)中的總運輸成本和樞紐點之間的運輸成本最少。則建立模型如下：

在此模型中，目標(biāo)函數(shù)表示從非樞紐點i到樞紐點k、從樞紐點k到樞紐點m、從樞紐點m到樞紐點j以及樞紐點的固定建設(shè)費用最少。約束條件（1）表明選取P個樞紐點；約束條件（2）表示非樞紐點之間必須通過樞紐點才能夠連接；約束條件（3）表示軸輻式網(wǎng)絡(luò)中的節(jié)點只能作為軸點或者輻點存在，不能單獨存在；約束條件（4）（5）表示只有當(dāng)k、m點為樞紐點時，從非樞紐點出發(fā)的流量才經(jīng)過k、m點；約束條件（6）表示只有i點的流量平衡約束。在目標(biāo)函數(shù)中，樞紐點的成本可以用經(jīng)過樞紐點的冪函數(shù)來表示，則目標(biāo)函數(shù)可以表示為：

由于此模型屬于非線性規(guī)劃問題，故采用禁忌搜索智能算法進(jìn)行求解。

模型的求解

本文采用禁忌算法求解。禁忌搜索算法的介紹。禁忌搜索算法屬于一種智能算法，智能算法改變了傳統(tǒng)的啟發(fā)式算法依賴問題性質(zhì)的搜索方法，其根據(jù)一定的規(guī)則來進(jìn)行搜索，從而擴(kuò)大了搜索的廣度和深度，進(jìn)而能夠?qū)ふ胰肿顑?yōu)解的目標(biāo)。禁忌搜索算法的求解步驟包括初始解的選擇、鄰域的構(gòu)建、禁忌表和禁忌長度、解的評價函數(shù)、特赦準(zhǔn)則和停止準(zhǔn)則。

算例分析

為了驗證上述考慮到樞紐點容量限制的模型的合理性和有效性，本文使用算例進(jìn)行研究，數(shù)據(jù)選擇2012年中國十五城市的客流量以及航段距離，并使用禁忌搜索算法，通過JAVA編程進(jìn)行求解。

（一）考慮樞紐點的擁堵對總成本的影響

通過JAVA編程，現(xiàn)通過改變a、b的值來確定樞紐點，以及分析樞紐點的總成本的變化，分析當(dāng)樞紐點確定時的總成本的變化，在這種情況下，確定p=3，折扣系數(shù)α=0.6，在這種情況下模型運行結(jié)果如表1所示。

通過分析可知，當(dāng)a、b取不同的值時，隨著a的值增加，其最小總成本也在增大，說明樞紐點之間的流量成本增加了總成本；隨著b值的增加，其總成本也增大，但增大幅度小于a增加時總成本增加的幅度，這說明相比于b，a的值對總成本的影響較大。

（二）考慮樞紐點的擁堵對樞紐點流量的影響

在已知樞紐點的個數(shù)和折扣系數(shù)的情況下，樞紐點的個數(shù)為3，折扣系數(shù)α為0.6，通過取不同的a和b的值，來分析a、b的取值對樞紐點的流量的影響，具體如表2所示。

通過分析可知，當(dāng)a、b取不同的值時，隨著a的值增加，樞紐點的最大流量和最小流量的比例逐漸變小，說明當(dāng)考慮了樞紐點的流量控制時，一部分流量被進(jìn)行了分流，從一個樞紐點分到了另外的樞紐點，從而使得整體的貨流之間比較平衡。兩個表經(jīng)分析可知，當(dāng)考慮了樞紐點的流量控制時，會導(dǎo)致總體的運輸成本升高，但對整體網(wǎng)絡(luò)的有益之處就是可以平衡樞紐點之間的流量。

結(jié)論

本文基于流量控制的角度，建立了軸輻式網(wǎng)絡(luò)的優(yōu)化模型，并利用禁忌搜索算法進(jìn)行了求解，從而得到了以下結(jié)論。

第一，從流量控制的角度來看，軸輻式網(wǎng)絡(luò)中的樞紐點的成本包括固定成本變動成本，固定成本指的是在樞紐點建設(shè)交通、物流設(shè)施等所做的固定投入。變動成本則隨著流量的增加而不斷增大，為流量的函數(shù)。

第二，軸輻式網(wǎng)絡(luò)的成本，不僅包括非樞紐點和樞紐點之間的運輸成本，還包括了樞紐點之間的固定成本和變動成本。軸輻式網(wǎng)絡(luò)的規(guī)模經(jīng)濟(jì)體現(xiàn)在樞紐點的構(gòu)建以及樞紐點之間的折扣系數(shù)，受限于樞紐點的流量處理能力，當(dāng)樞紐點的流量增多時，軸輻式網(wǎng)絡(luò)的總體成本增加。

第三，在建立優(yōu)化的軸輻式網(wǎng)絡(luò)時，要綜合考慮樞紐點的規(guī)模經(jīng)濟(jì)和成本，選取二者的平衡點作為模型的最優(yōu)目標(biāo)。

第四，可用禁忌搜索算法對優(yōu)化后的軸輻式網(wǎng)絡(luò)模型進(jìn)行求解，結(jié)合算例進(jìn)行分析可知，樞紐點的擁堵成本增加了最小總成本，但在平衡貨流的方面效果明顯。

綜上所述，考慮了流量控制的軸輻式網(wǎng)絡(luò)模型雖然增加了總成本，但是能夠平衡貨流，因此其具有一定的現(xiàn)實意義，在后續(xù)的研究過程中可以深入對不同樞紐點的流量成本函數(shù)進(jìn)行研究，以進(jìn)一步貼近現(xiàn)實。