东亚地区枢纽港选择模型的建立

丁明明

（上海海事大学物流研究中心 中国 上海 200135）

1 问题描述

区域性枢纽航线网络中枢纽港的选定，属于在枢纽航线网络设计中的无容量限制的多重分配p-枢纽中位问题，简称UMApHMP[1]-[5]。

所谓UMApHMP，是指在某个区域中，有n个港口，预先给出枢纽港的数量为p，枢纽港之间相互连接构成干线网络，枢纽港承担集装箱中转的角色，而其他所有港口必须通过枢纽港进行中转连接，构成支线网络。

枢纽航线网络优化的目标是船务公司的收益最大化。船务公司收入除了航线网络影响因素外，还受到很多其他因素的综合影响，难以进行精确计算，因此在本模型中以航线网络运输总成本最小为目标函数。

本文所考虑的问题是要求从n个港口中选择p个作为枢纽，并确定非枢纽港到枢纽港的分派方式，以控制总运输成本最低。

运输成本中包含三个部分：起点到枢纽港的运输成本；枢纽港之间的运输成本；枢纽港到终点的运输成本。在干线上（枢纽港之间的航线）的集装箱单位运输成本存在成本折扣 α（0＜α＜1）。 支线上不存在成本折扣。

为了简化问题，本文模型中用距离代替运输成本，并假定集装箱流量不超过港口和航线的容量限制。为了减小问题规模，节约计算时间，同时得到合理的求解。

东亚地区港口及航线的分布现状如图1所示。

图1 东亚地区港口及航线示意图

2 模型建立

2.1 模型假设

任何数学模型都是在提出问题假设的基础上建立起来的，为了将实际问题理论化，方便模型构建，依据集装箱运输的特征和条件，本文中的枢纽港选择模型的前提假设如下：

（1）非枢纽港和枢纽港间以及枢纽港之间均为直达航线；

（2）非枢纽港之间必须通过枢纽港中转；

（3）中转航线中转次数不超过两次；

（4）保证所有港口对间都有航线连接（既可以为直达也可以为中转）。

2.2 符号说明

N是n个候选枢纽港口构成的集合 λ是干线上的运输折扣成本，0＜λ＜1

Wij表示从港口i到港口j的集装箱运量 Xik表示从港口i经过枢纽港k的集装箱量

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

2.3 构建模型[3]

通过以上模型假设和符号说明，建模的准备工作已经完成，则根据问题可构建混合0-1整数规划模型。

目标函数中第一部分是集装箱从起点到枢纽港的运输成本，第二部分是枢纽港间航段的运输成本，第三部分是集装箱从枢纽港到终点的运输成本。

约束条件（1）表示枢纽港的数量为p

约束条件（2），（3），（4）是集装箱流量守恒方程

约束条件（5），（6）是集装箱流量约束

约束条件（8）规定决策变量为0-1变量

3 实例分析

3.1 模型数据

东亚地区八个主要港口之间的航线距离和集装箱流量如表1和表2所示。

表1 8个港口间的航线距离（单位：海里）

表2 2009年8个港口间的集装箱流量（单位：万TEU）

其中青岛港的分值与其他7个港口相比较低，不适宜作为枢纽港，因此在选择枢纽港时不予考虑，在进行枢纽港选择时只需考虑前7个港口，即

3.2 模型求解

表3 不同成本折扣下的枢纽港选择方案及成本

本文利用 lingo软件对模型编程求解， 当 p=3、4、5，α=0.6、0.8时，求得结果如表3所示。图2为根据求解结果可以设计东亚地区港口枢纽航线网络（当p=4时）。枢纽港上海、高雄、香港、新加坡之间相互直接连接，构成干线网络，釜山、宁波等港口作为区域集装箱集散港，与距离最近的枢纽港连接，其余规模较小的港口与区域集散港或枢纽港连接，构成支线网络。干线网络和支线网络构成如图2所示的枢纽航线网络。

图2 东亚地区的港口枢纽航线网络（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］柏明国.朱金福.姚韵.枢纽辐射航线网络的构建方法与应用[J].系统工程，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］柏明国.朱金福.航空公司航线网络设计的一种三阶段法[J].南京航空航天大学学报，2006（38）：181-185.