丁明明
(上海海事大學(xué)物流研究中心 中國 上海 200135)
區(qū)域性樞紐航線網(wǎng)絡(luò)中樞紐港的選定,屬于在樞紐航線網(wǎng)絡(luò)設(shè)計中的無容量限制的多重分配p-樞紐中位問題,簡稱UMApHMP[1]-[5]。
所謂UMApHMP,是指在某個區(qū)域中,有n個港口,預(yù)先給出樞紐港的數(shù)量為p,樞紐港之間相互連接構(gòu)成干線網(wǎng)絡(luò),樞紐港承擔集裝箱中轉(zhuǎn)的角色,而其他所有港口必須通過樞紐港進行中轉(zhuǎn)連接,構(gòu)成支線網(wǎng)絡(luò)。
樞紐航線網(wǎng)絡(luò)優(yōu)化的目標是船務(wù)公司的收益最大化。船務(wù)公司收入除了航線網(wǎng)絡(luò)影響因素外,還受到很多其他因素的綜合影響,難以進行精確計算,因此在本模型中以航線網(wǎng)絡(luò)運輸總成本最小為目標函數(shù)。
本文所考慮的問題是要求從n個港口中選擇p個作為樞紐,并確定非樞紐港到樞紐港的分派方式,以控制總運輸成本最低。
運輸成本中包含三個部分:起點到樞紐港的運輸成本;樞紐港之間的運輸成本;樞紐港到終點的運輸成本。在干線上(樞紐港之間的航線)的集裝箱單位運輸成本存在成本折扣 α(0<α<1)。 支線上不存在成本折扣。
為了簡化問題,本文模型中用距離代替運輸成本,并假定集裝箱流量不超過港口和航線的容量限制。為了減小問題規(guī)模,節(jié)約計算時間,同時得到合理的求解。
東亞地區(qū)港口及航線的分布現(xiàn)狀如圖1所示。
圖1 東亞地區(qū)港口及航線示意圖
任何數(shù)學(xué)模型都是在提出問題假設(shè)的基礎(chǔ)上建立起來的,為了將實際問題理論化,方便模型構(gòu)建,依據(jù)集裝箱運輸?shù)奶卣骱蜅l件,本文中的樞紐港選擇模型的前提假設(shè)如下:
(1)非樞紐港和樞紐港間以及樞紐港之間均為直達航線;
(2)非樞紐港之間必須通過樞紐港中轉(zhuǎn);
(3)中轉(zhuǎn)航線中轉(zhuǎn)次數(shù)不超過兩次;
(4)保證所有港口對間都有航線連接(既可以為直達也可以為中轉(zhuǎn))。
N是n個候選樞紐港口構(gòu)成的集合 λ是干線上的運輸折扣成本,0<λ<1
Wij表示從港口i到港口j的集裝箱運量 Xik表示從港口i經(jīng)過樞紐港k的集裝箱量
TWi表示源于港口i的集裝箱量,
通過以上模型假設(shè)和符號說明,建模的準備工作已經(jīng)完成,則根據(jù)問題可構(gòu)建混合0-1整數(shù)規(guī)劃模型。
目標函數(shù)中第一部分是集裝箱從起點到樞紐港的運輸成本,第二部分是樞紐港間航段的運輸成本,第三部分是集裝箱從樞紐港到終點的運輸成本。
約束條件(1)表示樞紐港的數(shù)量為p
約束條件(2),(3),(4)是集裝箱流量守恒方程
約束條件(5),(6)是集裝箱流量約束
約束條件(8)規(guī)定決策變量為0-1變量
東亞地區(qū)八個主要港口之間的航線距離和集裝箱流量如表1和表2所示。
表1 8個港口間的航線距離(單位:海里)
表2 2009年8個港口間的集裝箱流量(單位:萬TEU)
其中青島港的分值與其他7個港口相比較低,不適宜作為樞紐港,因此在選擇樞紐港時不予考慮,在進行樞紐港選擇時只需考慮前7個港口,即
表3 不同成本折扣下的樞紐港選擇方案及成本
本文利用 lingo軟件對模型編程求解, 當 p=3、4、5,α=0.6、0.8時,求得結(jié)果如表3所示。圖2為根據(jù)求解結(jié)果可以設(shè)計東亞地區(qū)港口樞紐航線網(wǎng)絡(luò)(當p=4時)。樞紐港上海、高雄、香港、新加坡之間相互直接連接,構(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].南京航空航天大學(xué)學(xué)報,2006(38):181-185.