東亞地區(qū)樞紐港選擇模型的建立

丁明明

（上海海事大學(xué)物流研究中心 中國 上海 200135）

1 問題描述

區(qū)域性樞紐航線網(wǎng)絡(luò)中樞紐港的選定，屬于在樞紐航線網(wǎng)絡(luò)設(shè)計(jì)中的無容量限制的多重分配p-樞紐中位問題，簡稱UMApHMP[1]-[5]。

所謂UMApHMP，是指在某個(gè)區(qū)域中，有n個(gè)港口，預(yù)先給出樞紐港的數(shù)量為p，樞紐港之間相互連接構(gòu)成干線網(wǎng)絡(luò)，樞紐港承擔(dān)集裝箱中轉(zhuǎn)的角色，而其他所有港口必須通過樞紐港進(jìn)行中轉(zhuǎn)連接，構(gòu)成支線網(wǎng)絡(luò)。

樞紐航線網(wǎng)絡(luò)優(yōu)化的目標(biāo)是船務(wù)公司的收益最大化。船務(wù)公司收入除了航線網(wǎng)絡(luò)影響因素外，還受到很多其他因素的綜合影響，難以進(jìn)行精確計(jì)算，因此在本模型中以航線網(wǎng)絡(luò)運(yùn)輸總成本最小為目標(biāo)函數(shù)。

本文所考慮的問題是要求從n個(gè)港口中選擇p個(gè)作為樞紐，并確定非樞紐港到樞紐港的分派方式，以控制總運(yùn)輸成本最低。

運(yùn)輸成本中包含三個(gè)部分：起點(diǎn)到樞紐港的運(yùn)輸成本；樞紐港之間的運(yùn)輸成本；樞紐港到終點(diǎn)的運(yùn)輸成本。在干線上（樞紐港之間的航線）的集裝箱單位運(yùn)輸成本存在成本折扣 α（0＜α＜1）。 支線上不存在成本折扣。

為了簡化問題，本文模型中用距離代替運(yùn)輸成本，并假定集裝箱流量不超過港口和航線的容量限制。為了減小問題規(guī)模，節(jié)約計(jì)算時(shí)間，同時(shí)得到合理的求解。

東亞地區(qū)港口及航線的分布現(xiàn)狀如圖1所示。

圖1 東亞地區(qū)港口及航線示意圖

2 模型建立

2.1 模型假設(shè)

任何數(shù)學(xué)模型都是在提出問題假設(shè)的基礎(chǔ)上建立起來的，為了將實(shí)際問題理論化，方便模型構(gòu)建，依據(jù)集裝箱運(yùn)輸?shù)奶卣骱蜅l件，本文中的樞紐港選擇模型的前提假設(shè)如下：

（1）非樞紐港和樞紐港間以及樞紐港之間均為直達(dá)航線；

（2）非樞紐港之間必須通過樞紐港中轉(zhuǎn)；

（3）中轉(zhuǎn)航線中轉(zhuǎn)次數(shù)不超過兩次；

（4）保證所有港口對(duì)間都有航線連接（既可以為直達(dá)也可以為中轉(zhuǎn)）。

2.2 符號(hào)說明

N是n個(gè)候選樞紐港口構(gòu)成的集合 λ是干線上的運(yùn)輸折扣成本，0＜λ＜1

Wij表示從港口i到港口j的集裝箱運(yùn)量 Xik表示從港口i經(jīng)過樞紐港k的集裝箱量

TWi表示源于港口i的集裝箱量，

2.3 構(gòu)建模型[3]

通過以上模型假設(shè)和符號(hào)說明，建模的準(zhǔn)備工作已經(jīng)完成，則根據(jù)問題可構(gòu)建混合0-1整數(shù)規(guī)劃模型。

目標(biāo)函數(shù)中第一部分是集裝箱從起點(diǎn)到樞紐港的運(yùn)輸成本，第二部分是樞紐港間航段的運(yùn)輸成本，第三部分是集裝箱從樞紐港到終點(diǎn)的運(yùn)輸成本。

約束條件（1）表示樞紐港的數(shù)量為p

約束條件（2），（3），（4）是集裝箱流量守恒方程

約束條件（5），（6）是集裝箱流量約束

約束條件（8）規(guī)定決策變量為0-1變量

3 實(shí)例分析

3.1 模型數(shù)據(jù)

東亞地區(qū)八個(gè)主要港口之間的航線距離和集裝箱流量如表1和表2所示。

表1 8個(gè)港口間的航線距離（單位：海里）

表2 2009年8個(gè)港口間的集裝箱流量（單位：萬TEU）

其中青島港的分值與其他7個(gè)港口相比較低，不適宜作為樞紐港，因此在選擇樞紐港時(shí)不予考慮，在進(jìn)行樞紐港選擇時(shí)只需考慮前7個(gè)港口，即

3.2 模型求解

表3 不同成本折扣下的樞紐港選擇方案及成本

本文利用 lingo軟件對(duì)模型編程求解， 當(dāng) p=3、4、5，α=0.6、0.8時(shí)，求得結(jié)果如表3所示。圖2為根據(jù)求解結(jié)果可以設(shè)計(jì)東亞地區(qū)港口樞紐航線網(wǎng)絡(luò)（當(dāng)p=4時(shí)）。樞紐港上海、高雄、香港、新加坡之間相互直接連接，構(gòu)成干線網(wǎng)絡(luò)，釜山、寧波等港口作為區(qū)域集裝箱集散港，與距離最近的樞紐港連接，其余規(guī)模較小的港口與區(qū)域集散港或樞紐港連接，構(gòu)成支線網(wǎng)絡(luò)。干線網(wǎng)絡(luò)和支線網(wǎng)絡(luò)構(gòu)成如圖2所示的樞紐航線網(wǎng)絡(luò)。

圖2 東亞地區(qū)的港口樞紐航線網(wǎng)絡(luò)（p=4）

［1］J.G.Klincewicz.A dual Algorithms for the uncapacitated hub location problem[J].Location Science，1996（04）：173-184.

［2］A.T.Ernst.M.Krishnamoorthy.An exactsolution approach based on shortest-paths for p-hub median problems[J].Informs Journal on Computing，1998（10）：149-162.

［3］柏明國.朱金福.姚韻.樞紐輻射航線網(wǎng)絡(luò)的構(gòu)建方法與應(yīng)用[J].系統(tǒng)工程，2006（24）：29-34.

［4］Campbell J.F.Hub location and the p-hub median problem[J].Operations Research，1996（66）：923-935.

［5］Skorin-Kapov D.Skorin-Kapov J.O’Kelly M.Tight linear programming relaxations of uncapacitated p-hub median problem[J].European Journal of Operational Research，1996（94）：582-593.

［6］柏明國.朱金福.航空公司航線網(wǎng)絡(luò)設(shè)計(jì)的一種三階段法[J].南京航空航天大學(xué)學(xué)報(bào)，2006（38）：181-185.