丁明明

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

1 問題描述

區(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ū)港口及航線示意圖

2 模型建立

2.1 模型假設(shè)

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

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

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

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

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

2.2 符號說明

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

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

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

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

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

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

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

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

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

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

3 實例分析

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

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

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

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

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

3.2 模型求解

表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.