基于樞紐點(diǎn)流量控制的軸輻式物流網(wǎng)絡(luò)優(yōu)化

馬瑞光

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

引言

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

文獻(xiàn)綜述

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

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

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

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

模型的建立

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

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

表1 a、b的值對(duì)最小總成本的影響

表2 a、b的值對(duì)樞紐點(diǎn)的流量的影響

G：固定成本；

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

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

F(w)=bwa

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

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

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

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

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

wkm：樞紐點(diǎn)k、m之間的流量；

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

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

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

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

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

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

（2）樞紐點(diǎn)之間完全直連，而非樞紐點(diǎn)之間通過(guò)樞紐點(diǎn)連接；

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

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

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

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

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

模型的求解

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

算例分析

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

（一）考慮樞紐點(diǎn)的擁堵對(duì)總成本的影響

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

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

（二）考慮樞紐點(diǎn)的擁堵對(duì)樞紐點(diǎn)流量的影響

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

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

結(jié)論

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

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

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

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

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

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