啟運(yùn)港退稅的航線網(wǎng)絡(luò)魯棒優(yōu)化

楊芊+林國(guó)龍+信曉雷

【摘 要】 為解決未來(lái)啟運(yùn)港退稅政策擴(kuò)圍后啟運(yùn)港的選擇和運(yùn)輸網(wǎng)絡(luò)優(yōu)化問(wèn)題，基于港口容量限制和未來(lái)運(yùn)輸需求的不確定性，通過(guò)將啟運(yùn)港的因素考慮到內(nèi)支線集裝箱運(yùn)輸網(wǎng)絡(luò)的優(yōu)化中，分析支線間的多式聯(lián)運(yùn)問(wèn)題，建立魯棒優(yōu)化模型，并使用情景分析法對(duì)不確定性參數(shù)進(jìn)行描述。論證得出：魯棒優(yōu)化模型可有效降低支線網(wǎng)絡(luò)中啟運(yùn)港的選擇風(fēng)險(xiǎn)；使用粒子群-蟻群算法對(duì)魯棒優(yōu)化模型的求解及仿真證明該算法和魯棒優(yōu)化模型的有效性。

【關(guān)鍵詞】 啟運(yùn)港退稅；魯棒優(yōu)化；粒子群-蟻群算法

0 引 言

啟運(yùn)港退稅政策指的是從啟運(yùn)港發(fā)往洋山保稅港區(qū)中轉(zhuǎn)至境外的出口貨物，一經(jīng)確認(rèn)離開啟運(yùn)港口即被視同出口并可辦理退稅。與傳統(tǒng)的船舶抵達(dá)后再辦理退稅相比，啟運(yùn)港退稅不僅使企業(yè)的資金周轉(zhuǎn)效率更高，還能增強(qiáng)洋山港區(qū)的集聚輻射作用，助推上海國(guó)際航運(yùn)中心建設(shè)。當(dāng)啟運(yùn)港退稅政策惠及到國(guó)內(nèi)其他沿海中轉(zhuǎn)港、內(nèi)陸港以及無(wú)水港時(shí)，選擇合適的啟運(yùn)港和合理的航線，才能使整個(gè)航線運(yùn)輸網(wǎng)絡(luò)的物流成本降到最低。從這個(gè)角度來(lái)看，啟運(yùn)港的選擇問(wèn)題與樞紐港的選址有所相似。

網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)模型由確定型、隨機(jī)型和魯棒優(yōu)化型等3種組成。運(yùn)用確定型和隨機(jī)型網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)模型都需要能夠準(zhǔn)確預(yù)測(cè)網(wǎng)絡(luò)設(shè)計(jì)的參數(shù)或分布。由于參數(shù)值和概率分布很難預(yù)測(cè)和獲取，網(wǎng)絡(luò)優(yōu)化多用魯棒優(yōu)化理論進(jìn)行。啟運(yùn)港的確定，不僅要考慮集裝箱港口所輻射區(qū)域的集裝箱出口量，還要考慮多式聯(lián)運(yùn)的方便性和成本的節(jié)約性。

1 模型的建立

模型建立基礎(chǔ)條件有：（1）一個(gè)支線港需要出口的集裝箱只能通過(guò)一種運(yùn)輸方式運(yùn)到啟運(yùn)港，且只能運(yùn)到一個(gè)啟運(yùn)港；（2）啟運(yùn)港有集裝箱最大吞吐量限制；（3）啟運(yùn)港之間和啟運(yùn)港與目的港之間具有一個(gè)運(yùn)輸成本折扣d （0

情景s下的魯棒優(yōu)化模型為

式中：N為所有的節(jié)點(diǎn)集合（支線港、目的港及潛在的啟運(yùn)港）；L為候選路線集合；S為狀態(tài)情景集合；K為運(yùn)輸需求的港口；€%R€%o為運(yùn)輸方式的集合；c為單位集裝箱資金的單位時(shí)間占用成本；n為流量資金的占用天數(shù)；為在狀態(tài)情景s下運(yùn)輸需求港口k的集裝箱運(yùn)輸量； 為在情景狀態(tài)s下，支線港建設(shè)成啟運(yùn)港的固定成本；為在運(yùn)輸路線（i，j）上每單位流量的運(yùn)輸成本；為在狀態(tài)情景s下，運(yùn)輸需求港口k在線路（i，j）上的運(yùn)輸成本；為在狀態(tài)情景s下，在港口節(jié)點(diǎn)k處，運(yùn)輸方式由€%o1轉(zhuǎn)為€%o2的中轉(zhuǎn)費(fèi)用；p為啟運(yùn)港的個(gè)數(shù)；qs為狀態(tài)情景s可能出現(xiàn)的概率；為狀態(tài)情景s的最佳狀態(tài)；為各港口的吞吐量；Zi為二元決策變量，為“1”則港口i設(shè)為啟運(yùn)港，為“0”則不設(shè)；Xij為二元決策變量，為“1”則路線（i，j）被選中，為“0”則不選；為二元決策變量，為“1”則運(yùn)輸方式在節(jié)點(diǎn)k由€%o1變?yōu)閫%o2，為“0”則不變；為在狀態(tài)情景s中，港口k的集裝箱經(jīng)過(guò)啟運(yùn)港i和j中轉(zhuǎn)的比例（當(dāng)i=j時(shí)，表示僅經(jīng)過(guò)一個(gè)啟運(yùn)港中轉(zhuǎn)；當(dāng)i≠j時(shí)，表示經(jīng)過(guò)了兩次中轉(zhuǎn)）；為在狀態(tài)情景s中，啟運(yùn)港i的集裝箱直接運(yùn)到樞紐港的比例。

式（1）為目標(biāo)函數(shù)，表示運(yùn)輸成本、啟運(yùn)港的設(shè)置成本、運(yùn)輸方式的轉(zhuǎn)換成本和資金占用成本的總和最小。式（2）～式（14）為約束條件：式（2）保證從每個(gè)支線港運(yùn)出的集裝箱只能有一條路線；式（3）保證在每一個(gè)場(chǎng)景狀態(tài)s中，啟運(yùn)港i的集裝箱可以運(yùn)輸?shù)綐屑~港或其他啟運(yùn)港；式（4）保證從啟運(yùn)港i運(yùn)輸?shù)募b箱量等于從其他港口運(yùn)到啟運(yùn)港i的集裝箱量與啟運(yùn)港i自有的集裝箱量之和；式（5）保證在每個(gè)場(chǎng)景狀態(tài)s中，支線港i的集裝箱運(yùn)輸量都必須被完全滿足；式（6）保證啟運(yùn)港i的集裝箱吞吐量不大于其最大集裝箱吞吐量；式（7）限定了啟運(yùn)港的個(gè)數(shù)；式（8）保證有集裝箱運(yùn)量的運(yùn)輸路線（i，j）必須是開放的；式（9）保證假如支線港i被選為啟運(yùn)港的話，其能夠?yàn)槠渌Ь€港服務(wù)；式（10）保證集裝箱運(yùn)輸路線為單向，即只能從支線港到啟運(yùn)港或啟運(yùn)港到樞紐港，不能從啟運(yùn)港到支線港或從樞紐港到其他港口；式（11）限定了p-魯棒的狀態(tài)，每個(gè)場(chǎng)景狀態(tài)中的相對(duì)遺憾值不能大于一個(gè)常數(shù)值（p>0），即該情景s的解決方案的成本與最優(yōu)成本之間的相對(duì)距離必須在p以內(nèi)，因此，該模型中的每個(gè)場(chǎng)景的目標(biāo)函數(shù)不能大于（1+ p）；式（12）規(guī)定了啟運(yùn)港的數(shù)量；式（13）和式（14）規(guī)定了約束變量的類型。

2 算法設(shè)計(jì)

本文設(shè)計(jì)了兩級(jí)的混合智能啟發(fā)式優(yōu)化算法求解魯棒優(yōu)化模型。主級(jí)使用粒子群優(yōu)化算法（PSO）求解啟運(yùn)港的選擇問(wèn)題；從級(jí)使用蟻群優(yōu)化算法求解支線港集運(yùn)路線以及集運(yùn)方式的選擇。

2.1 PSO優(yōu)化設(shè)計(jì)

設(shè)搜索空間為D維，粒子數(shù)為u，第h個(gè)粒子的位置向量Xh=（xh1，xh2，xh3，…，xhd），速度向量Vh=（vh1，vh2，vh3，…，vhd），其中：h=1，2，3，…，u；d=1，2，3，…，D。Ph=（ph1，ph2，ph3，…，phd）為適應(yīng)值最優(yōu)的位置向量，Pr=（pr1，pr2，pr3，…，prd）為全局最優(yōu)位置向量。各粒子按下式更新位置

vhd=wvrd + c1r1（phd-xhd） + c2h2（pgd-xgd）（15）

xhd=xhd + vhd（16）

式中：w是慣性因子；c1，c2是學(xué)習(xí)因子；r1，r2為[0，1]之間的隨機(jī)數(shù)。

粒子的初始位置和初始速度都是隨機(jī)產(chǎn)生的，然后按式（15）和式（16）的方法進(jìn)行迭代，直至找到最優(yōu)解，迭代結(jié)束。

根據(jù)以上模型的求解特點(diǎn)，按照整個(gè)運(yùn)輸網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)n構(gòu)造粒子h為一維向量且包含n個(gè)元素，這n個(gè)元素分別對(duì)應(yīng)著網(wǎng)絡(luò)中的n個(gè)節(jié)點(diǎn)，以此來(lái)表示對(duì)應(yīng)的節(jié)點(diǎn)在解碼時(shí)的先后等級(jí)。

2.2 蟻群算法優(yōu)化設(shè)計(jì)

將m只螞蟻放在n個(gè)港口上（1≤n≤m），設(shè)定如下規(guī)則：（l）每只螞蟻可以釋放對(duì)其他螞蟻選擇路徑帶來(lái)影響的信息素；（2）在與當(dāng)前節(jié)點(diǎn)相連接的多個(gè)路徑上，每只螞蟻可以根據(jù)其不同的信息素濃度來(lái)選擇通過(guò)哪條路徑進(jìn)入下一個(gè)節(jié)點(diǎn)；（3）每只螞蟻選擇路徑的依據(jù)是信息素濃度，濃度越高，選擇此條路徑的概率越大；（4）螞蟻通過(guò)信息素尋找食物，而且在尋找過(guò)程中會(huì)同時(shí)釋放出信息素；（5）根據(jù)每條航線的營(yíng)收收益大小釋放與之相應(yīng)濃度的信息素，且隨著時(shí)間推移其濃度會(huì)變小。

本文利用可行的航線方案表示螞蟻群體探索并走過(guò)的路徑，并將每只螞蟻所走的路線看作一個(gè)方案可行解。優(yōu)化設(shè)計(jì)如下：

（1）若第k只螞蟻在第i個(gè)港口節(jié)點(diǎn)上，按照隨機(jī)比例的規(guī)則，其選擇下一個(gè)港口節(jié)點(diǎn)j的概率為

=（17）

式中：Ak為螞蟻k下一步允許選擇的港口節(jié)點(diǎn)的集合；€%mij為航線路徑（i，j）上的信息素量軌跡強(qiáng)度的大??；€%`ij為航線（i，j）的可見度，表示從港口節(jié)點(diǎn)i到節(jié)點(diǎn)j的啟發(fā)程度。

在路徑選擇過(guò)程中，螞蟻并不是僅選擇概率最大的路徑，而是結(jié)合賭輪法，以較大的概率選擇概率最大的路徑，但不排除選其他路徑的可能，從而保證搜索的全面。

（2）螞蟻在構(gòu)造路徑的同時(shí)，按式（18）及時(shí)更新局部信息素，減少相應(yīng)的信息素，更符合螞蟻搜索過(guò)程，且可以有效避免螞蟻收斂到同一路徑。

€%m（i，j）=（1-€%l） €%m（i，j） + €%l€HU€%m（i，j）（18）式中： €%l∈（0，1）為信息揮發(fā)因子。

（3）每只螞蟻完成循環(huán)后，在加強(qiáng)最優(yōu)螞蟻的信息素的同時(shí)減弱最差螞蟻的信息素，通過(guò)增大最優(yōu)與最差路徑上信息素的差異，使最優(yōu)路徑的搜索更加快捷。

2.3 粒子群-蟻群算法步驟

步驟1 設(shè)置蟻群算法的相關(guān)參數(shù)，螞蟻的位置均處于隨機(jī)狀態(tài)。

（1）按照式（17）為每只螞蟻的初始路徑進(jìn)行概率選擇；

（2）每只螞蟻生成自己的航線路徑，并按照式（18）進(jìn)行信息素的局部更新；

（3）循環(huán)（1）―（2）兩步，直至所有的螞蟻都形成完整的航線路徑；

（4）將螞蟻的目標(biāo)函數(shù)值進(jìn)行記錄，并根據(jù)數(shù)值進(jìn)行評(píng)定；

（5）在迭代完成后，將選出的最優(yōu)螞蟻（目標(biāo)函數(shù)值最大）的路徑按下式進(jìn)行全局信息素的更新；

€%m（i，j）=（1-€%j） €%m（i，j） + €%j€HU€%m（i，j）（19）

式中： €%j表示路徑中信息素持久性的因子；1-€%j表示路徑中信息素的衰減度因子； €%j∈（0，1），表示螞蟻個(gè)體之間相互影響的強(qiáng)弱程度。

（6）將最差螞蟻（目標(biāo)函數(shù)值最?。┑穆窂桨聪率礁氯中畔⑺?；

€%m（i，j）=（1-€%j） €%m（i，j） + €%^ （20）

（7）重復(fù)步驟（1）―（6），直到滿足結(jié)束條件，依據(jù)最后各航線網(wǎng)絡(luò)節(jié)點(diǎn)的選擇狀態(tài)得出最佳網(wǎng)絡(luò)模型。

步驟2 利用蟻群算法得到每個(gè)粒子的適應(yīng)度值，并更新歷史最優(yōu)粒子位置向量和全局最優(yōu)粒子位置向量Pg。

步驟3 按式（15）、式（16）對(duì)粒子的速度向量和位置向量進(jìn)行更新。

步驟4 重復(fù)步驟2―步驟4，直至滿足結(jié)束條件，利用蟻群算法求解出最優(yōu)解。

步驟5 計(jì)算結(jié)束。

3 算例分析

本文采用小規(guī)模算例對(duì)算法進(jìn)行分析和驗(yàn)證。選取10個(gè)國(guó)內(nèi)港口（包括未來(lái)的無(wú)水港），分別標(biāo)號(hào)A，B，C，D，E，F(xiàn)，G，H，I，J，其中港口A為出口目的港?，F(xiàn)在目標(biāo)函數(shù)和約束條件下，從其他9個(gè)港口中選取啟運(yùn)港。10個(gè)港口之間的距離見表1。

從表5可以看出，魯棒優(yōu)化后的計(jì)算時(shí)間明顯小于魯棒優(yōu)化前的計(jì)算時(shí)間，這也證明了算法的有效性。當(dāng)p=2，€%Z=0.6或€%Z=0.8時(shí)，魯棒優(yōu)化前后的啟運(yùn)港是一樣的；但當(dāng)p=3，€%Z=0.8時(shí)，啟運(yùn)港的選擇有兩組。從中可以看出，隨著啟運(yùn)港數(shù)目的增加，由于折扣因子的增加，意味著支線港到啟運(yùn)港和啟運(yùn)港之間、啟運(yùn)港與目的港之間的運(yùn)輸效益差正在減小，導(dǎo)致了魯棒最優(yōu)解的增加。

p=2和p=3時(shí)的運(yùn)輸路線和運(yùn)輸方式分別見圖1和圖2，圖3。

4 結(jié) 語(yǔ)

本文將啟運(yùn)港退稅政策引入集裝箱運(yùn)輸網(wǎng)絡(luò)，不僅考慮了各港口集裝箱運(yùn)輸量增加的不確定性，而且將啟運(yùn)港的因素考慮到內(nèi)支線集裝箱運(yùn)輸網(wǎng)絡(luò)的優(yōu)化中，并分析了支線間的多式聯(lián)運(yùn)問(wèn)題，建立魯棒優(yōu)化模型，利用一組已知概率的離散情景來(lái)表示未來(lái)支線港口可能的運(yùn)量。用粒子群-蟻群雙層優(yōu)化算法求解魯棒優(yōu)化模型并進(jìn)行仿真，證明了算法的有效性，也證明了魯棒優(yōu)化模型可以降低支線網(wǎng)絡(luò)中啟運(yùn)港的選擇風(fēng)險(xiǎn)。