英语原文共 12 页

动态变化需求和运费下的集装箱船运输网络的设计

赵晨、增青城

摘要：本文重点研究集装箱船运输网络的优化以及在动态变化的货物需求和运费下它的运作方式。

该问题是一个混合整数非线性规划问题（MINP），目的是在三个阶段使平均单位船槽利润最大化。基于一年的一系列需求矩阵，同时考虑了如空集装箱的重新定位，船舶槽分配，船舶大小，集装箱数量配置等问题。为了算出该模型，提出了一种基于双层遗传算法的求解方法。最后通过数值实验验证了提出的模型和算法的有效性。结果表明，所提出的模型能够在需求和运价变化的基础上，为这些问题提供更现实的解决方案，并且比基于平均需求的模型能更有效地安排集装箱运输网络结构和运营优化。

关键词：集装箱航运、船槽分配、空集装箱重新定位、集装箱配置；单位平均舱位利润；优化。

1.导言

随着全球经济的增长，集装箱运输业在国际货物运输中发挥着越来越重要的作用(Jaržemskienė和Jaržemskis 2009；Liu etal.)2009年；SU和Wang，2009年；Paulauskas和Bentzen，2008年；Vasilis Vasiliauskas和Barysienė，2008年；Jaržemskis和Vasilis Vasiliauskas，2007年；Rohaacute;cs和Simongaacute;ti，2007年)。为了适应更大的集装箱货运需求，航运公司正在通过新的超大型集装箱船增加运力。公司也开始特别注意优化集装箱运输网络的设计和运营，以促进更高质量的服务。本文研究了集装箱运输网络结构和运营问题，在处理空位、船槽分配、船舶尺寸和集装箱配置等问题时，考虑了需求和运价的变化。

 集装箱航运网络设计问题(CSNDP)涉及从一组候选端口中选择一组调用端口并确定调用序列。其目标是就以下问题做出最优决策：航程路线、要部署的船舶资产和集装箱的规模、按一定序列在每个呼叫港口分配船舶插槽、在每条航线上装载的集装箱数量以及在往返作业中最大限度地提高舱位利润。

在大多数已有的研究中，CSNDP的求解是基于这样的假设：即货物需求仅由一个需求矩阵作为一组常数给出，该矩阵代表了一组稳定值或一组年需求量平均值。这种假设源自于这样一种信念，即船舶大小可以由给定的需求决定，而航线运输的成本是固定的。它进一步假设运费并不是直接受实际对固定运力需求波动的影响。然而，这一假设与集装箱航运网络设计的实际情况不符合要求。事实上，货物运输需求和运费率是周期性波动的。在这种情况下，当需求低时，航运网络的运营可能会导致较大的运力过剩，而在需求高时则会造成巨大的收入损失。例如，在一年之内，在中日航线上，最高的货物需求和运费是最低的三倍。因此，如何及时、准确地移动或租赁空集装箱，在旺季最大限度地提高船舶的收益，以及如何确定集装箱保质期内集装箱保有量，以及如何确定集装箱保质期集装箱保有量的风险，都是需要解决的问题。这些问题已经成为CSNDP的关键和基本问题，应该主要由集装箱货物分布来解决。

贸易区所有港口之间的分配。由于必须考虑需求变化和运价变化的影响，CSNDP可以分解为一系列子问题，包括船舶路由问题（SRP）、调用排序问题（CSP）、船位分配问题（SAP）、船舶尺寸问题（SSP）和集装箱构成问题（RCCP）。

根据CSNDP的特点和属性，提出了一种综合模型。根据一系列一年的需求矩阵，同时考虑了空集装箱重新定位、船位分配、船舶尺寸和集装箱配置等问题。利用背包问题（KP）、销售员旅行问题（STP）和混合整数非线性问题（MIP）的分析方法和平均收益期望值技术，建立了该问题的数学模型。为了求解该模型，提出了一种基于二级遗传算法的方法。最后，通过数值实验验证了所提出的模型和算法的有效性。

本文的其余部分组织如下：在第2节中，简要回顾了以前的工作。问题的描述见第3节。在第4节中，开发了CSNDP的模型。第5节设计了一种二级遗传算法。数值算例用于测试第6节中计算出的方法的性能。结论见第7节。

2。文献综述

现有的一些研究论文集中在集装箱运输方面。其中较大的一部分可分为两大类，涵盖船舶航线和相关作业。

在集装箱船的航线问题上，现有的文献相当有限。Bodin等人对车辆路径问题进行了全面调查。（1983）、Laporte（1992）和Christiansen等人（2004）。BfFy等人。（1979）开发了一个启发式优化模型和一个交互式决策支持系统，用于在北大西洋航线上调度集装箱船。Rana和Vickson（1988年和1991年）试图为在贸易航线上运营的船队找到最佳的停靠港顺序，以便在确定最佳停靠港顺序的同时最大限度地提高班轮运营利润。他们认为不盈利的港口应该作为航线上的主叫港而被拒绝。他们将问题表述为一个混合整数非线性规划模型，并用拉格朗日松弛法和分解法求解。Perakis和Jaramillo（1991年）以及Jaramillo和Perakis（1991年）为路由策略设计了一个线性规划模型，以最大限度地减少总运营和规划时间范围内的布局成本。他们还研究了根据航运运营成本的实际模型，将现有集装箱船编队分配到一组预定航线（停靠港序列）。Cho和Perakis（1996）提出了船队规模和班轮航线设计的最佳模型，同时考虑了现实情况和未来预测中的未来货物需求。将该问题表述为混合整数线性规划，并通过在模型中设计一个流路关联矩阵来检验不同船舶的若干候选港口来解决。Fagerholt（1999）研究了基于周频率确定最佳车队和班轮航线的问题，将其定义为用分区方法解决的多行程车辆路径问题。Bendall和Stent（2001）提出了一个确定最佳船队配置的模型，同时考虑了在枢纽轮辐集装箱航运网络中应用的船队部署计划。拉姆等。（2007年）使用了一条简单的两港航运路线和两航次作业（TPTV）及其多港多航次扩展（MPMV），以证明近似动态规划方法在寻找空箱分配作业策略方面的有效性。由于在上述方法中采用了平均成本最小化的时间差学习，因此只有两次航程可能不足以代表完整的航线系统运行。徐和祥（2007）建立了一个双目标模型，根据这两种成本之间的权衡，通过同时最小化运输成本和库存成本，确定承运人和托运人的最佳班轮航线、船舶尺寸和航行频率。从承运人和托运人的角度来看，该方法具有一定的实用价值。

在航线作业问题上，对空集装箱重新定位进行了大量的研究。Gavish（1981）开发了一个关于集装箱船队管理的决策系统。在他的研究中，如果空集装箱没有在要求的时间重新定位，系统将根据边际成本标准分配自有和租赁的集装箱以满足需求。应进一步注意的是，额外租用的集装箱影响了班轮运输总成本，而不考虑闲置集装箱的库存。克拉尼奇等人（1993）介绍了一个土地分配和运输系统中空箱搬迁的动态和随机模型。同样，为了解决集装箱租赁和空箱搬迁问题，作者忽略了短期租赁成本和长期租赁成本之间的差异。这似乎不切实际，不符合处理长期租赁集装箱的惯例。Cheung和Chen（1998）也考虑了海运空箱分配问题。本文将动态集装箱分配问题定义为两阶段随机网络模型。该模型有助于班轮运营者分配空集装箱，从而降低租赁成本和停靠港的库存水平。但是，他们的工作没有考虑租赁时间的长短。今井等人。（2009）研究了集装箱运输网络设计的优化问题，提出了解决空集装箱重新定位问题的方法。本文采用惩罚成本因子设计目标函数，同时考虑了港口调用顺序和空集装箱重新定位问题。因此，该问题被整合并表述为两个阶段的问题。在该模型中加入惩罚成本，并在网络结构设计中使用虚拟点，这一思想无疑是有价值的。然而，由于实验中缺乏货物运输需求的波动和港口之间的货物流量分布，各停靠港之间的船位分配存在明显的缺陷。最近，Chang等人（2008）研究了一种启发式方法，以提供降低空集装箱交换成本的最佳解决方案。利用现有的数据，他们测试了计算时间和解决方案质量的有效性。Di Francesco等人（2009）开发了一个多场景、多商品、时间扩展的优化模型来处理空集装箱的重新定位问题。根据航运公司的意见，将一些无法通过历史数据估计的不确定模型参数视为有限值集合。Bandeira等人（2009）创建了一个决策支持系统（DSS），以处理集装箱的满舱和空舱转运操作。通过调整DSS模型中的几个参数，可以确定空容器的重新定位排列。

以上所介绍的研究都没有涉及到本文中遇到的问题和方法：即集装箱运输网络的设计和运行应纳入到一个单一的、协调的问题中，通过考虑基于周期波动的船舶规模和集装箱配置的收益损失风险控制来解决。货物需求和运费。

3问题描述

一般来说，CSNDP的优化应该通过一系列决策过程来完成，这些决策过程包括从贸易区的候选港口中选择合适的呼叫港口，用固定的定期频率服务确定合理的呼叫顺序，并在每个呼叫港口WI处确定合理的船位分配。部署资产的适当规模，包括船舶规模、集装箱数量和网络中的集装箱配置。这些决策过程取决于以下影响因素，也被称为可控因素，主要包括距离和货物运输需求以及贸易区内候选港口之间的运价、船舶和集装箱的投资成本以及公司有关航运市场和投资的政策。在这些可控因素的基础上，决策过程应确定各种因素，包括待调用的最佳端口集、调用顺序的最佳顺序、船舶的最佳尺寸以及每个调用端口船上的最佳船位分配序列。由于船舶规模在规划期间是不可改变的，而需求的波动对船舶规模产生了显著的影响，因此使用一系列的需求矩阵来表示需求的波动，而不是只使用平均需求的矩阵，是更可行的。

集装箱运输网络结构根据其运行特点，一般可分为两种形式。一个是圆形的，另一个是钟摆，如图1所示。从拓扑学的角度来看，它们基本上可以简化为环形路由，因为任何摆锤类型都可以通过添加表示反向端口的虚拟节点和构造一个适当的需求分布矩阵转换为圆形路由。航运网络运营通常由一个船队执行，为呼叫港口分配一系列船位。沿航线航行的船队应分成两组，一组顺时针航行，另一组同时逆时针航行。通过这种方式，任何停靠港的货物运输都可以方便地向不同方向运输到相邻港口。例如，从港口1到港口2的货物运输必须由一组船舶顺时针方向运输，从港口1到港口9的货物运输可以由另一组船舶逆时针方向运输，如图2所示。船舶只需在半航次中按照与船舶相同的方向将集装箱运至其他停靠港。

图1示例：摆锤路径(a)；圆路径的(b)。

此外，由于一些停靠港之间的方向性货物流不平衡，因此从该港口出发的总货物流量与到达该港口的总货物流量必须存在差异。由于在实践中，假设船舶容量有备用槽，甩负荷是不太可能的，班轮运输公司必须决定是重新放置空集装箱还是租用额外集装箱，并将闲置的自有集装箱存放在特定的港口。由于单次航程的成本比较不合理，因此有必要在充分考虑的航程中比较这些平均成本。这些要素必须在公式中表示为机会成本，它们之间存在相互替代关系。

因此，我们将构建的模型应包括上述影响因素和要素。以平均单位船位利润最大化为目标的模型，可以通过设计一个具有适当规模的船舶和集装箱的环形航线的平均封闭航程。在船舶交路中，船舶不必在贸易区内的所有港口停靠，如选择1、2、4、5、7、9港，但放弃3、7、8港，如图2所示。其他假设如下：

（a）作为一个关键影响因素，所有港口之间的货物运输需求波动是由一系列需求矩阵按时间顺序和相关的同质运价表示的，而不是由规划范围内的平均需求矩阵表示的。究其原因，主要是规划范围内实际运输的集装箱数量一旦确定，就应受到可接受船舶尺寸的限制，如图3所示。

（b）根据集装箱运输网络设计，每个停靠港必须配备适当数量的集装箱，与在其处处理的数量相对应。额外的集装箱可以在任何港口租赁，但最终必须归还到原始港口。

（c）部署在网络或航线上的船舶必须与容量和巡航速度相同。

（d）船舶的载重量不得超过在任何航线支腿处装上的货柜总数。

图3货运需求和运价的周期性波动

4。模型公式

如上所述，CSNDP由四个子问题组成。第一个问题是为最优网络或路由选择最佳的呼叫端口组。二是确定所选择的一组停靠港的停靠顺序，以优化航程安排。三是优化每个停靠港的船位分配，在每个停靠港的每个航次上处理一系列集装箱数量，实现单位船位利润最大化。最后一个问题是，根据每个调用端口处理的上述容器数量，确定部署在网络中的合理容器配置。由于这些子问题之间存在相互关系和相互作用，基于背包问题（KP）、销售员旅行问题（STP）以及操作问题（OP）和集装箱配置问题（CCP），可以将CSNDP分三个阶段表述为混合整数非线性规划问题（MINP）。优化模型可开发如下：

第一阶段：

其中：v是从贸易区的一组候选端口n中获取的一组调用端口组合；如果选择了由调用端口k的候选组合构建的路由，则w=1；否则为0；pk是调用端口k的候选组合下的目标函数值。

第2阶段：

在给定一组调用端口的情况下，利用STP和OP构造minp，可以得到一个最优的调用序列，为了找到所描述的决策变量，让wij为二元流变量，xij，yij分别为每个调用端口的满船槽和空船槽分配变量，u–船-尺寸变量和xijg、yijg分别表示满载和空载集装箱的实际数量作为辅助变量，加载在场景g中的一系列货物运输需求dijg。考虑到各停靠港之间货物运输的周期性波动，介绍了单位船位利润在规划范围内的平均航次，该平均航次可能更合理、更有效，可以用一年内总航次的预期收益来表示。因此，如果考虑单艘容量为（U）的船舶的航线运行，则可以通过单位船位利润来计算[minp]年平均航次，总航次如下：

最大化：

tij指船舶从（i）港到（j）港的航行时间；v指以固定巡航速度部署在航线上的

资料编号：[5749]