英语原文共 17 页
轴辐式班轮运输网络设计
Jianfeng Zheng, Qiang Meng, Zhuo Sun
摘要：本文提出了一个轴辐式班轮运输网络设计问题，引入了主港的概念，并考虑了以往研究中很少考虑到的多型集装箱运输情况和运输时间约束。针对所提问题，建立了非凸多线性项的混合整数规划模型。提出了一种基于多级分解的遗传算法求解该模型。通过数值实验验证了模型的有效性和算法的有效性。
关键词：班轮运输网络设计 轴辐式 遗传算法 多级分解方法
- 背景介绍
随着全球贸易的增长，集装箱班轮运输也正高速发展。班轮运输中的多型集装箱有不同的功能或大小，如20英尺当量单位(TEU)集装箱、40英尺当量单位(FEU)集装箱和冷藏集装箱等。集装箱由班轮运输，班轮的运输路线称为航线。一艘大型集装箱船需要数百万美元的巨额资本投资，其日常运营成本可高达数万美元(Christiansen等，2007)。Agarwal和Ergun(2008)的报告称，2003年全球约30%的集装箱运输是在枢纽港中转的，且这一比例将逐年上升。集装箱转运业务发展趋势背后的原因在于班轮运输公司能通过部署大型船舶，从规模经济中获益。因此，大型船舶通常服务于由一些枢纽港组成的主航线，而小型船舶则服务于有若干支线港口的支线航线。例如，全球最大的班轮航运公司马士基航运在2011年订购了20艘大型集装箱船，每艘船的运力为1.8万标准箱，这些大型集装箱船目前在亚欧航线上服务。上述大型船舶部署策略要求班轮航运公司提供轴辐式的航运服务。需要指出的是，使用轴辐式运输网络有一些缺点，如支线港口不能由主要航线上的大型船舶直接提供服务。因此，在轴辐式运输网络中需要许多转运操作。
某一沿海国家执行的海上运输法不允许在另一国家注册的船舶在其国内两个港口之间运输集装箱货物，因此班轮公司无法选择集装箱运输需求量较大的港口作为集装箱转运的枢纽港。如集装箱吞吐量最大的上海港并不是马士基航运的枢纽港。这样的港口在班轮航运业中被称为主港，在实践中也被主要航线上的大型船舶所服务。因此，班轮运输公司在考虑季节性规划范围内的主要港口的同时，利用船队部署来设计其轴辐式航运网络是至关重要的。
-
- 文献综述
传统的货运轴辐式网络设计问题由Goldman(1969)提出，随后是O #39;Kelly (1986a,b, 1987)。货物被合并在轴辐式网络的枢纽节点以享受规模经济。在传统的轴辐式网络设计研究中，规模经济通常表现为两个枢纽节点之间运输成本的固定折现因子 (Alumur和Kara, 2008，及其参考文献)。研究人员还提出并研究了一些反映规模经济的预先确定的与流量相关的成本函数，如O#39;Kelly和Bryan(1998)、Horner 和O #39;Kelly(2001)、Racunicam和Wynter(2005)、Meng和Wang (2011b)。然而，这两种规模经济公式已不再适用于本研究中提出的班轮轴辐式航运网络设计问题。这是因为船舶规模的经济规模是由船舶舰队部署决定的，这是不能预先给出的。
传统的货运轴辐式网络设计通常有两个假设：枢纽节点网络是一个完整的图;支线节点直接连接到枢纽节点，任何两个支线节点之间不存在直接连接(见Alumur和Kara, 2008)。这两个假设在现实中并不适用于班轮运输服务，因为两个枢纽港之间每周的集装箱运输需求通常不够高，不需要只服务于这两个港口的大型船舶，支线上的船舶实际上要停靠多个支线港。此外，在同一支线船路线的两个支线港之间运输集装箱时可能不需要转运作业。在本文中，当集装箱在归属于同一枢纽港的任意两个支线港之间运输时，将采用转运作业或是直接运输作为一个决策变量。虽然上述两种假设是后来才提出的(如O #39;Kelly和Miller, 1994；Campbell等)，但在传统的货运轴辐式网络设计中，当确定枢纽位置和非枢纽分配时，放宽货运路由并不是问题。班轮轴辐式航运网络设计不仅要设计具有船舶机群部署的航线，还要确定有运输需求的每对港口之间的集装箱路径。在传统的货运轴辐式网络中，每个节点只能是枢纽节点或非枢纽节点。如上文所述，班轮运输公司不能直接将运输需求较高的主港作为枢纽港。此外，在传统的轴辐式网络设计研究中很少研究班轮运输公司或承运人的服务水平，即没有考虑起止点间的中转时间限制。
关于班轮轴辐式航运网络设计的研究较少。Fagerholt(1999, 2004)、Sambracos等(2004)和Karlaftis等(2009)研究了具有一个枢纽港(或一个中心仓库)和多个支线港口的支线船舶航线设计问题。Imai等(2006，2009)研究并比较了轴辐式策略与两个区域之间的多端口调用(multi-port-call, MPC)策略：他们假设枢纽港是预先给定的，即每个地区有一个枢纽港。Hsu和Hsieh (2007)开发了一种双目标优化模型来确定最优航线、船舶大小和频率的轴辐式运输网络。Meng和Wang (2011a)引入分段的概念，假定候选航线是预先给定的，提出了考虑空集装箱重新定位的轴辐式与MPC相结合的班轮运输网络设计问题。Gelareh等(2010)提出了一个设计班轮运输网络的竞争枢纽选址问题。Gelareh和Pisinger(2011)利用预先确定的折扣因子来反映船舶规模经济，分析了船队部署对班轮轴辐式航运网络设计的影响。这些关于班轮轴辐式航运网络设计的研究都没有考虑到多类型集装箱运输、运输时间限制或船队部署固有的规模经济。此外，单班轮运输服务设计(Plum等， 2014a)和班轮航线计划设计(Wang和Meng，2012a)考虑了运输时间约束；大型集装箱船的规模经济已经在McLellan(1997)、Gilman(1999)、Cullinane和Khanna(1999, 2000)中得到了探索。
除班轮轴辐式网络设计外，还有许多与班轮网络设计相关的研究。Agarwal和Ergun(2008)提出了一种用于船舶调度和货物路由的混合整数规划模型，其缺点在于没有考虑集装箱转运成本。之后，Agarwal和Ergun(2010)研究了班轮联盟的班轮运输网络设计，计算了联盟内班轮之间共享船舶容量的容量交换成本。Alvarez(2009)提出了一种用于船舶航线和部署联合优化的MIP公式。Shintani等(2007)，Song和Dong(2013)探讨了单一班轮航线设计问题，以及考虑空集装箱的重新定位问题。Wang和Meng(2013)研究了班轮运输网络设计的一个特殊子问题，重点研究了给定班轮运输网络中港口反向旋转的选择。Plum等(2014b)提出了一种基于服务流程的班轮运输网络设计的简洁公式。最近，Brouer等人(2014)提出了一个整数规划模型和一个基准套件，通过提供对数据源的方便访问来设计班轮运输网络。更多关于船舶路由调度的研究，可以参考Ronen (1983, 1993)， Christiansen等(2004,2013)，Meng等(2014)等综述性论文。
-
- 目标和贡献
传统的货运业轴辐式网络设计中使用的二维或四维决策变量建模技术，在班轮轴辐式网络设计时是不适用的。因此，本文针对该问题建立了一个非凸多线性项的混合整数规划模型，并将其分解为三个子问题：枢纽位置和支线分配、航路设计和集装箱流分配，并用一种基于多级分解的遗传算法求解。
本文的贡献有三方面。首先，提出了一个班轮轴辐式航运网络设计问题。其次，针对该问题建立了非凸多线性项的混合整数规划模型。第三，提出了一种基于多阶段分解的遗传算法求解该模型。
本文的其余部分组织如下。第二章给出了符号和假设，并描述了班轮轴辐式航运网络设计；第三章建立了一个非凸多线性项的混合整数规划模型；第四章提供了一个高效的遗传算法，通过一个多阶段分解方法来求解提出的模型；第五章基于亚欧大洋洲班轮运输网络进行了数值实验；第六章给出了总结。
-
符号，假设和问题描述
- 干线与支线
班轮运输公司在一组港口之间提供定期的运输服务，港口集合由P表示，被运输的多型集装箱集合由A表示。其中港口集P被进一步划分为三个不相交子集：P1为候选枢纽港集，P2为主港集，P3为非枢纽港集。设V表示班轮运输公司可用的一组船舶类型，将特定船舶的港口停靠序列称为船舶航线。为简便起见，本文假设每种类型的船舶数量都不受限制。轴辐式航运业务包含两种类型的船舶航线:在主港和（或）枢纽港停靠的主要船舶航线，和为支线港口服务的支线船舶航线。在轴辐式航运操作中，为一组港口服务的所有可能的航线都用一组R表示。在不失一般性的前提下，假设每条航线从实际出发保持每周的服务频率。由于一些物理障碍，如港口吃水受限，并非所有的船型都能部署在特定的航路上，所以令Vr isin;V表示为航路risin;R提供可用的船型集合。
特定航路risin;R的港口调用序列可以表示为：
(1)
其中是第一停靠港。从第i个停靠港到第i 1个停靠港称为航线r的第i个分支。设为航线r的停靠港指标集合。式(1)中的两个不同的表示方式可能指向同一个港口，设为对于一特定港口pisin;P的船舶航路r的停靠港序列。因此，我们应确定从一个港口pisin;P到另一个港口qisin;P的集装箱航路的一段，其起始港和终止港表示为：
(2)
(3)
其中%是数学中的余数运算符。换句话说，停靠在港口的船舶按以下顺序运输集装箱：，，hellip;hellip;，。
-
- 集装箱路径和运输时间的限制
设为具有多类型集装箱需求的起止港口对(o，d)集合，为港口对(o，d)在季节规划周期内每周运输的A型集装箱数量。港口对(o，d)之间的集装箱需求将由连接o港和d港的航线上的船舶负责运输，且航线可能涉及枢纽港的一些集装箱转运操作。这些集装箱从始发港到目的港所经过的路线被称为集装箱路径，它可能是相关船舶路线的组合。不涉及任何集装箱转运操作的路径称为直接运输。本研究假设，支线港间的集装箱不得转运两次以上，且直接运输仅允许在两个枢纽港、两个主港或枢纽与主港之间发生。
为简便起见，船舶在港口对(o，d)之间沿着特定的路径运输所用的时间被称为运输时间。由于OD端口对(o，d)之间有许多集装箱路径，因此最长的集装箱路径运输时间代表了班轮运输公司提供的最低服务水平。班轮运输公司为了在竞争激烈的集装箱运输市场中生存，必须向托运人承诺港口对(o，d)之间的最长运输时间不超过，即：
(4)
运输时间可以在班轮运输公司发布的网站上找到，如www.apl.com；http://www.maerskline.com/appmanager/。
- 模型建立
在这一节中，我们将提出一个具有非凸多线性项的混合整数规划模型来研究班轮轴辐式航运网络设计问题。为了便于表示，将班轮轴辐式航运网络设计问题分解为三个子问题：枢纽位置与支线分配、船舶航线设计与船队部署，集装箱流分配。需要指出的是，划分子问题主要用来清晰地描述我们的问题，但每个子问题并没有自己的目标函数，且每个子问题都不是独立解决的。如第四章所示，我们开发了一种高效的遗传算法，嵌入多阶段分解方法来求解所提出的模型。即第一阶段确定枢纽位置，第二阶段确定支线分配，第三阶段共同解决剩余的子问题。在前两个阶段确定枢纽位置和支线分配后，集装箱运输需求可以分为两组，一组在主航线上交付，另一组在支线航线上交付。然后根据集装箱分装需求设计船舶航线。因此，本文将可行航线集表示为枢纽位置和支线分配解的函数。
-
- 决策变量
枢纽位置和馈线分配子问题的决策变量定义如下：
：如果港口作为枢纽港则取1，否则为0；
：如果非枢纽港挂靠于枢纽港则取1，否则取0。
为了便于表示，这些决策变量被分组到一个向量x中。
给定一个决策变量向量x，我们假设任何未被选为枢纽港的备选枢纽港都将降级为一个主港，从而可以定义枢纽港集P1和主港集P2。枢纽港集服务的特定非枢纽港可用 表示：
(5)
设R为轴辐式航运作业下，给定决策变量向量x下所有可行航路的集合，由船舶舰队部署子问题的航路设计产生的决策变量可以明确定义为：
：如果船舶航线由型船舶提供则取1，否则为0；
：部署在航路上的型船舶的数量。
这些决策变量被分成向量y和n。
给定集合R(x)，我们使用以下基于OD的集装箱流变量来表示集装箱流分配子问题：
：港口对(o，d)的航线中，在第i个港口装载的a型集装箱数量；
：港口对(o，d)的航线中，在第i个港口卸货的a型集装箱数量；
：港口对(o，d)的航线中，在第i段上航行的a型集装箱的数量。
将这些基于OD的集装箱流量变量分为向量z和f，则在枢纽港中转的a型集装箱的总数量可以计算为：
(6)
其中为停靠港口的所有可行航线集合。
-
- 集装箱运输时间
对于特定的航线, 型船舶的往返时间包括运输时间和装卸时间两部分。假设型船舶的平均航速已知，并固定在航路的每条分支上；设为型船舶在航路的第i条分支上的航速。船舶在特定港口的装卸时间取决于在该港口装卸的集装箱总数和每小时在该港口装卸的每种集装箱数。实际上，在一个港口，大型船舶每小时处理的集装箱数量通常比较小型船舶的多，因为港口运营商部署了更多的码头起重机为大型船舶装卸。设为型船舶在港口的每小时装卸a型集装箱的平均数量。
给定一个可行的集装箱流向量z，可以计算型船舶所服务的航线在第i个港口停靠的集装箱装卸时间为：
(7)
用表示型船舶在航路某一段从港口到港口的总时间，
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
