考虑空箱调拨的班轮运输网络设计.doc

考虑空箱调拨的班轮运输网络设计摘要：本文在同时考虑轴辐式-多港挂靠混合模式和空箱调拨下提出班轮运输网络设计问题。本文首先提出了一个新奇的概念“分段（segment）”，并把它定义为一条班轮航线上的一对有序港口，然后针对提出的问题构建了混合整数线性规划模型。基于亚洲-欧洲-大洋洲的实际运营中的大量数值试验证明该模型能够使用CPLEX有效地求解。同时也证明了本文研究的问题比单纯考虑轴辐式或者单纯考虑多港挂靠式，亦或是不考虑空箱调拨在大量节约成本方面有着巨大的潜力。关键词：班轮运输网络设计、轴辐式、多港挂靠式、转运、空箱调拨1 前言集装箱班轮运输公司在一个由若干港口组成的航线上经营一支船队，按照一定的服务频率从一个港口到另外一个港口从事集装箱运输服务。由于货运需求的增长以及班轮集装箱运输业的收购、整合及合并，班轮集装箱运输公司较以往运输量大大增加。因此，集装箱班轮公司在核心港口之间配置大型的船舶以获得规模经济效益。船舶大小的变化和运输需求的增加也导致船舶配置策略从多港挂靠模式向轴辐式-多港挂靠混合模式转变，尤其对于像马士基这样的全球班轮运输公司而言更是如此。轴辐式-多港挂靠混合模式与传统应用于航空和电信网络的轴辐式运营有一些共同之处，大船被配置到主要航线上挂靠核心港口，小船被配置到支线上挂靠喂给港，这些喂给港的箱量通常不能满足直接挂靠的需要，一些集装箱需要被转运到核心港口。然而，轴辐式-多港挂靠混合模式在班轮运输中有两个独特的性质：（a）集装箱转运成本和装卸时间不能够被忽略，因为它们分别构成了运营成本和往返时间的主要部分；（b）在包括喂给港在内的任何两个港口之间都可以进行集装箱的直接运输。这两个独特的性质使得轴辐式-多港挂靠混合模式显著地区别于传统轴辐式运营，这种传统的轴辐式运营是基于现有关于传统的轴辐式网络设计的研究，这些研究不考虑在核心港的转运成本，并且所有在两个分支节点之间的转运必须被转移到相应的核心港。除了从托运人那里运输重箱外，班轮运输公司还要运输由于进出口贸易不均衡引起的空箱。以跨太平洋贸易为例：2007年从亚洲到北美的集装箱量大概是1540万TEU，而回程却只有490万TEU。这种货流不均衡导致空箱在进口主导的区域（北美）增加，而在出口主导的区域（亚洲）短缺。因此，需要将这些空箱从北美调运到亚洲。对于一个特定的集装箱班轮运输公司而言，它在两个港口之间的重箱量经过3-6个月的一段时期会发生变化。例如，从亚洲到欧洲的重箱量通常在第四个季度由于圣诞节而大幅度增加。因此，每3-6个月集装箱班轮运输公司不得不调整其班轮运输网络，根据下一个3-6月时期集装箱运输需求量预测重新部署船舶。这个调整的目的是决定在众多的备选航线选择哪些航线运营，选择什么类型的船舶，在每一个选定的班轮运输航线上配置多少艘船舶，在轴辐式-多港挂靠混合模式下以总运营成本最小为目标运输重箱。这是一个为期3-6个月的决策问题，这个问题就是在轴辐式-多港挂靠混合模式下考虑空箱调拨的班轮运输网络设计问题。本研究的目的就是针对该问题开发一个合适的数学模型，该数学模型能够有效地被各种广泛使用的优化解决方法比如CPLEX解决。1.1 文献综述现在关于船舶运输网络设计问题的研究主要有两种：不定期船舶运输网络设计和班轮运输网络设计。不定期船运输网络设计解决船舶路径和船队配置问题，运输诸如煤炭和铁矿石之类的散货，并且不考虑轴辐式运输经营。这是因为在不定期船运输汇总，起始港和终止港之间的货运量很大，因此没有必要在核心港口进行货物整合。现有关于班轮运输网络设计的问题被分成两类：考虑轴辐式运营和不考虑轴辐式运营，接下来将逐一说明。对于传统轴辐式运营的班轮运输网络设计问题，Fagerholt在一项开创性研究中调查了一个支线航运服务设计问题，该问题针对一个具体的轴辐式运输网络，考虑一个核心港和多个喂给港的情况。他提出了一个设置分区的模型，该模型枚举了所有可能的运输线路并尽可能的把单一运输线路联合成多运输线路，该模型假设所有的船舶都有相同的航行速度。Fagerholt后来扩展了设置分区的模型，用它来解决一个多样化船队问题，针对每一种类型的船舶在给定成本结构、容量和航速的情况下进行研究。Sambracos等人进行了一项有关在航运支线爱琴海上调运集装箱的研究，该研究是从一个端港（比雷埃夫斯）到其他12个港口。他们假设一个均匀的船队以最小的运营成本包括燃油消耗和港口费用来满足集装箱运输需求。这个问题后来被Karlaftis等人推广，考虑集装箱的提取和交付操作，同时还有时间期限的限制，他们把这个扩展问题归为考虑集装箱提取、交付和时间窗的车辆路径问题。以上四篇文章中所提到的支线网路设计问题具有明显的特征，能够显著地区分支线服务网络和总体班轮运输服务网络。最重要的区别就是班轮运输公司在只有一个核心港口的支线服务网络上采取传统的轴辐式运营。这个核心港口可以被视为传统车辆路径问题的仓库。因此，在这些支线运输网络中不存在转运。对于没有轴辐射式操作的班轮运输网络设计问题，Rana和Vickson贡献了一种开创性的方法，他们针对一个单一航线设计问题建立了一个混合整数线性规划模型。他们使用拉格朗日松弛法求解他们的混合整数线性规划模型。在这两种模型中，船舶的挂靠港口顺序是预先设定的，并且不允许货物的转运操作。Shintani等人放松了挂靠港口有优先的假定，并且考虑空箱调拨来设计单一运输路线。他们使用遗传算法来解决他们提出的问题。不过，转运仍被排除在外。为了涵盖货物转运，Agarwal和Ergu针对班轮运输网络设计问题，提出了一个多种商品为基础的时空网络模型。这个模型覆盖了多样化船队，周班和货物转运操作。为了简化时空网络和算法设计，在港口的转运成本在网络设计阶段并没有考虑，并且不管装卸多少集装箱都认为船舶在港口的滞留时间为常量。有一些关于传统轴辐式运营和多港挂靠模式运营下的成本效益对比的文献。Hsu和Hsieh提出了一个两目标优化模型，通过分别使得运输成本和库存成本最小来决定是通过到核心港转运还是直接到卸货港。他们的模型也涵盖了对一个给定运输服务网络的船舶配置，船舶配置包括决定船舶大小和不同类型船舶的组合还有服务频率。Imai等人通过博弈论模型研究百万集装箱船舶的经济可行性。基于这个模型，Imai等人在考虑空箱调度的前提下，比较了传统轴辐式运输网络和多港挂靠式运输网络拓扑结构的效率。这些调查研究中的网络要么是单纯的轴辐式，要么是单纯的多港挂靠式，而不是轴辐式-多港挂靠混合模式。近年来，空箱调度问题受到了广泛的关注。这些关于空箱调拨的研究停留在运营层面，因此需要为集装箱设置更高的优先级，这是由于一般都用船舶的剩余舱位来运输空箱。在班轮运输网络设计问题的战略层考虑，重箱和空箱的运输都应该考虑。否则，若只考虑重箱的话，那么就不能以一种有效节约成本的方式调度空箱。Imai等人的一项假设研究表明，在某些情况下，在不考虑空箱调拨的情况下，传统的轴辐式运营是一个最优的解决方案，然而当考虑到空箱问题的时候，多港挂靠模式操作起着主导作用。这就表明空箱调拨对于班轮运输网络设计具有重要的影响。为了确保班轮运输网络设计的整体最优，当进行集装箱班轮运输网络设计的时候，重箱和空箱都应该考虑。1.2 目的与贡献根据以上的文献回顾，可以得出结论，那就是现有的关于班轮运输网络设计的文献并没有考虑轴辐式-多港挂靠混合模式，虽然这种模式已经被班轮集装箱运输业采用。在进行集装箱班轮运输网络设计的时候，空箱调拨作为另一个具有重要实际意义的约束很少受到关注。也就是说，本文所提出的考虑空箱调拨的轴辐式-多港挂靠混合模式的班轮运输网络设计问题是一个新的研究问题，该问题在实践中已经存在。为了应对考虑空箱调度的轴辐式-多港挂靠混合模式所引起的建模困难，本文首先根据航程中的港口挂靠次序为每一个港口编码。这样的一个编码方案使得我们引入一个叫做“段”的新概念，所谓“段”就是一对有序的港口，如果两个港口至少在一条航线上。重箱转运过程可以用“基于分段”的集装箱流很好地表征。与重箱相反，在港口剩余空箱没有固定的目的地。因此，空箱是在每一个航段上检查。根据重箱的段流和空箱的航段流，本文针对班轮运输服务网络设计问题开发了一个混合整数线性规划模型。这个模型能够有效地被广泛使用的优化软件比如CEPLE求解。本文对于理论研究的贡献可以被概括为三个方面。首先也是最重要的一方面，本文是在考虑轴辐式-多港挂靠混合模式，空箱调拨，定期航运服务频率，集装箱装卸时间和转运成本等班轮运输服务网络设计问题实际运营中所面对的一系列问题的基础上进行研究的。分段概念的引进使得我们能够开发一个混合整数线性规划模型，并且该模型能够被CPLEX有效地求解。第二，本文的贡献还在于通过集成轴辐式-多港挂靠混合模式来比较单纯轴辐式网络和多港挂靠式网络的成本效益。结合单纯轴辐式和单纯多港挂靠式网络，混合模式有最低的运营成本。第三，与以往把空箱调度问题作为操作层进行处理不同，本文把空箱调度问题上升为战术层问题。数值结果表明在网络设计阶段考虑空箱调拨问题能够大幅度降低成本。本文的其余部分组织如下。除了介绍必要的符号和假设，第二部分还分析了集装箱班轮运输的业务特点。第三部分对于研究的问题构建了一个混合整数线性规划模型。第四部分在全球班轮运输公司在亚-欧-大洋洲班轮运输服务基础上进行了数值试验，检测了模型的结果和实际意义。第五部分得出结论以及将来的研究方向。2参数、假设和模型在阐述了在实际的班轮运输业务之前，为了方便阅读本研究的主要假设是列在附录A。让我们考虑一个供定期航运服务的班轮公司挂靠的港口集合，用P表示。这些港口被分为两个相互排斥的子集：其中核心港用PH表示和喂给港用PF表示，即有：，；我们假设每个喂给港是都由且仅由一个核心港来服务，集装箱能够从喂给港p转运到它的核心港。如果它的目的港也是一个喂给港，那么可以到它的目的港的核心港再转运。进一步假设，从一个核心港到另一个核心港的集装箱运输通过一条运输航线无需转运。例如，亚洲欧洲大洋洲运输网络服务是由一个全球性的班轮船舶公司提供的，如图1所示，由6个核心港和40个喂给港组成。核心港为上海，香港，新加坡，斯里兰卡，塞拉莱和南安普顿。每一个核心港服务于单个区域内的喂给港，图1中各矩形中的内容说明了这一点。假定有一组连接港口集合P中港口的预定的备选航线，表示为集合R，来满足给定的集装箱运输需求。每个候选的航线服务频率为一周一班。每3-6个月，班轮运输公司通常会根据变化的集装箱运输需求来改变他们现有的运输网络的。他们决定航线的删除，是否要删除或添加一个挂靠港口，或改变航线上港口的挂靠顺序。他们还会根据他们的经验和判断设计了一条新的航线（港口挂靠顺序）并决定哪条航线投入运营。在实践中，一个班轮运输网络是很少从头开始设计的，除了当一个新班轮船舶公司成立或为一个新的地区（例如，美国南部）提供服务。如果网络设计从零开始，许多商业和业务的因素都要考虑，如一个港口的集装箱装卸效率，集装箱起运地和运达地腹地的货物分配，航海的访问（海上通行权），燃油价格，转运成本和时间，以及多式联运（Fleming，2003；Notteboom，2006）。港口挂靠顺序是NP难问题（Agarwal和Ergun，2008），是本研究的范围之外。图1 亚洲欧洲大洋洲运输网络一个候选的运输航线能够通过其挂靠港的顺序（或路线）来表示： （1）式中，Nr是指航线上的挂靠的港口的数量。式（1）表明运输航线是根据预先设定好挂靠港口顺序的循环。一个港口在一个往返的航线中可以挂靠多次。例如，图2描述了一个从釜山港到新加坡港的不对称的航线，其包含于图1所示的服务网络中。一艘船舶在该航线安排的挂靠的港口顺序为釜山（BS），上海（SH），盐田（YT），香港（香港），新加坡（SG），盐田（YT），并返回到釜山（BS）。根据式（1），可以表示为的港口的挂靠顺序：（2）在一个航线中的两个连续的港口被称为一个航段。为了用公式说明一条航线形成一个回路这种特点，我们引入函数定义为： （3）其中“mod”运算是用除以Nr只取余数为返回值。因此有，。有了这个公式，航线中的两个连续的港口和被称为航段，表示为有序港口对。在式子（2）中展示的航线有6段航段，他们分别是航段1，航段2，航段3，航段4，航段5和航段6。图2 全球航运公司的一条航线对于每一条备选航线，由于一些物理障碍比如港口吃水限制导致不能为其配置所有的类型的船舶。集装箱班轮运输公司一份儿适用于航线的船舶类型清单，表示为集合，所有船型被分成不同的子集： （4）已知备选航线集，在同一航线上的一对有序港口被称为一个分段。所有分段都可以很容易被确认，将他们定义为一个集合S，即 （5）我们进一步定义作为航线上分段的集合，即 （6）我们注意到任何一段航段都是一个分段，与此同时，任何一个分段可能包括许多航段。我们用一个包括七个港口和三条航线作为例子（如图3）来阐述分段的概念。在图3中，那对有序的港口不是分段，因为这三航线都不穿过它。是分段因为1号航线经过雅加达港和香港港口（通过新加坡港）。如果我们定义了香港作为第一个停靠港，这段分段包括了航线1的航段和航段；为了指出航段和分段的关系，定义了： （7）因此有且航线1和航线2均穿过分段，因此有且，换句话说，超过一条航线穿过某一个分段是有可能的定义（TEUs/周）为从港口运输到港口在中期规划中的重箱量，如果从港口到港口没有集装箱货物运输的需求则。由于全球贸易的不平衡，除了要运载重箱以外，集装箱班轮公司不得不调拨散布港口集P中各个挂靠港的空箱。为了反映空箱调运，港口集合P可以被分成为三个子集：有剩余空箱的港口定义为，空箱不足的港口定义为和进出箱量平衡的港口定义为，即 （8）我们把、和分别称为富余港、赤字港和平衡港，定义（TEUs/周）为港口进口箱和出口箱之间的差额。 （9）从等式（9）看出，当为正的时候表示有空箱供给，当为负的时候表示有空箱需求。图3 全球航运公司的部分航线网络2.1集装箱货运的装载计划采用H&S和MPC混合模式的班轮运输业有两个独特的特点：（a）集装箱转运成本和处理时间是不可忽略的因为他们分别构成运营成本和往返时间的很大一部分；（b）如果有航线通过这两个港口，那么这两个港口之间的直达运输是允许的。这两个特征使轴辐式和多港挂靠混合模式不同于在航空业和电信业上轴辐式运营模式。第一个特征考虑到高成本使得我们确保重箱从出发地到目的地过程中不能被转运超过两次。第二个特点为我们提供了更多的灵活性来运输重箱和空箱调运。换句话说，会有一个以上的替代运输方案从起运港到目的港来运输重箱，这是被称为重箱运载计划（LCSP）。一个重箱运载计划是一个基于分段的路径以确定某一O-D对集装箱中转港。我们使用重箱运载计划和基于分段的路径交替以后。关于重箱运载计划的概念在以下内容中阐述。回忆一下我们作出的以下三个假设：重载集装箱不能转运超过2次；重箱和空箱都只能在与出发喂给港和目的喂给港相对应的核心港进行转运；只有在两个核心港之间有直达运输。根据这三个假设，假定且p1，p2和p都分配到同一个核心港，即有，对于7种类型的O-D港口对的所有可能的重箱运输方案集合如表1所示。因此，每个分段式路径是由一个，两个或三个分段组成的。如果他们被分配到相同的核心港中最多有两个可能重箱运载计划从一个喂给港到另一个喂给港；如果两个喂给港同属于一个核心港那么这两个港口之间的重箱运输方案最多有两种可能；从一个核心港到另一个核心港的喂给港或相反也只有两种可能的重箱运输方案；直达运输只存在于两个核心港之间或者喂给港与其核心港之间。（从一个核心港到另一个核心港的重箱运载计划是对于直达运输，以及从一个喂给港给它的核心港是唯一的，或反之亦然）。请注意，直达运输只是意味着集装箱在旅途中不经过转船，而运载集装箱的船舶可以挂靠起运港和目的地之间的中转港。每个OD港口对的重箱运输方案数不超过四。表1 重箱调运计划的所有可能O-D特征可能的基于分段的路径核心港-核心港喂给港-分配的核心港分配的核心港-喂给港喂给港-其他核心港其他核心港-喂给港p-q喂给港-喂给港（不同核心港之间的）喂给港-喂给港（相同核心港的）定义为备选航线集合R中从港口到港口的重箱运载计划集合。对于给定的航线集合R，很容易得出分段式路线集合。例如在图3给出的航运运服务网络中，从雅加达（JK）到香港（HK）有两个重箱运载计划：一种方式是重箱可以通过航线1来运输；另一种方式是先通过航线1从雅加达（JK）运到新加坡（SG），然后在新加坡转运，从航线2运至香港（HK）。换而言之，从雅加达（JK）到香港（HK）的基于分段的路径有两条，即应该注意到表1给出了重箱运载的所有可能方案。在给定的航线集合R中，有些方案可能包含了一些不能被服务的航线，例如，在图3中，只有一条从雅加达（JK）到金奈（CN）分段式路径，即2.2空箱调拨问题我们已经在文献综述部分的分析，以往的关于集装箱空箱调运的研究大多都基于操作层面。如果空箱的网络设计不是在战术层面上的，设计的网络可能无法调拨所有的空箱。例如，图4显示了一个有三个港口和一条航线的运输服务网络。在中期规划范围内，我们假设每周从港口2到港口3的重箱运输需求为5000TEUs/周，从港口3到港口1为1000TEUs/周，且在其他港口对之间没有货运需求。根据式（9），可以发现分别有1000TEUs/周和4000TEUs/周剩余空箱在港口1和港口3产生，而港口2则短缺5000 TEUs/周。假设一条5000TEU的集装箱船配置在该航线上以每周一班的发班频率。假设由于从港口1到港口2有水深的限制在该航段上一艘 5000TEU集装箱船舶最大只能运输4000TEU。因此在航段上航行的一艘 5000TEU的集装箱船产能剩余成为4000 TEU，因此它不能容纳在港口1和港口3产生的5000TEU/周的空箱剩余量。换句话说，在这个例子中这些空箱不能由产能剩余的船舶来调运。上面的例子表明，在中期规划范围内，设计集装箱班轮服务网络及船舶配置时，应同时考虑重箱运输和空箱调拨问题。在经济性的前提下，可以允许空集装箱在核心港转运超过两次。空箱调运问题比重箱运输路线的设计要困难，因为在剩余港产生的空箱可以分配到任何一个不足港。这对我们制定的空箱调运提出了挑战。图4 产能富余的集装箱空箱调运运输网络2.3具体航线的船舶配置可行方案船型的船舶在航线往返时间运输的时间包括海上航行时间和港口花费时间。因为型船在航线各个航段上航行速度是已知的，所以海上航行时间可以事先确定，用表示。在一个特定港口船舶所花费的时间由两部分组成：到达和离开港口的备用时间包括拖船、引航和可能的等待时间，以及进行重空箱装卸的港口泊位占用时间。假设第一部分时间是固定的。因此，让表示型船在航线的往返航次中花费的海上航行时间和在航线所挂靠的港口的备用时间。不过，第二部分时间取决于在这些港口集装箱的数量和装卸效率。注意在一个港口对于一艘大船平均每TEU的装卸时间为是小于一艘较小的船舶，因为有更多的码头起重机为大船服务。为了维持航线船型每周的发班频率，配置的集装箱船舶数量的最小值和最大值的分别定义为和，计算如下： （12） （13）其中表示不大于x的最大整数，是v型船舶的集装箱装载量，分母168是一个星期中的小时总数和（TEUs/h）对于v型船在港口每小时可以装或卸的集装箱数量。式（12）表示在该航线上的任何港口没有集装箱的装卸；式（13）表示在每个港口满载的船舶卸空后又装满集装箱。航线的每周一班的约束条件大体上可以通过配置船型为的m艘集装箱船来实现，这称为一个可行的船舶配置方案（SDP）定义为。很明显，和是满足每周一次服务的船舶数量的最松散约束。事实上，在班轮公司根据船舶的营运经验会利用两个更严格的约束，用和表示，即： （14） （15）对在航线上配置船型以保证每周的服务所需要的船舶数量可能取值集合指定如下： （16）船舶配置方案的总的运营成本可以被分为两部分：固定营运成本（美元/周）和可变营运成本。固定成本主要包括燃油消耗的成本，运河费和在港口停靠固定成本。请注意，对于班轮经营者来说一条集装箱船舶的阻力基本上是相同，即使是在不同的装载条件下，由于船舶不可能一直处于压载的状态。此外，运河费和港口停靠固定成本主要是由船舶的尺寸确定。因此，这是合理的假设，是恒定的和独立的。可变成本是总和的泊位占用的花费综合，这主要取决于在每个港口泊位占用时间和总的集装箱装卸费用。3 班轮运输网络设计的数学模型3.1 班轮运输网络设计问题在一个中期规划周期内，已知备选运输航线集合R，重箱货物需求和空箱的不均衡分布，班轮运输网络设计问题的目标函数是以满足货运需求和空箱调拨的情况下服从轴辐式和多港挂靠混合运营模式的总运营成本最小化，决策目的是航线选择、制定航线配船计划和船舶在各航段重箱运输量以及空箱调拨计划。该问题的决策变量如下：在选定航线 上配备艘型船舶的船舶配置方案的数量，其中；：每周从港到港的分段式路径上的重箱运输量（TEUs/周）；：在船舶配置方案中，航线中分段上从港口k装船在港口l卸船的每周重箱运输量（TEUs/周）；：在船舶配置方案中，航线的航段上的每周空箱调拨量（TEUs/周）；：在船舶配置方案中，在航线的第i个停靠港的每周空箱装船数量（TEUs/周）；：在船舶配置方案中，在航线的第i个停靠港的每周空箱卸船数量（TEUs/周）。决策变量可以取任何非负整数值反映实际实施过程中的船舶配置。表示拒绝船舶配置方案。表示在备选航线r上配备m艘v型船以周班频率发船。换句话说，这m艘船在每周的的同一天挂靠航线的上的同一个港口，即每周的周一、周二、周三、周四、周五、周六、周日。决策变量表示集装箱班轮运输公司为航线配备m组船舶，每组包括艘v型船。每一组的这艘可以被视为一艘大船并且他们每周挂靠一个港口。将一条航线上多个小船组成大船的想法来自实际操作经验。例如，一条航线包括两个港口这两个港口之间的集装箱运输需求量为每周2000TEU，并且一艘船就可以维持每周一班的发班频率。如果这两个港口中的一个由于吃水限制只能停靠1000TEU的船舶，那么集装箱班轮运输公司不得不采用两艘1000TEU型船舶联合运输。让我们来考虑另一种情况，那就是集装箱班轮运输公司只有两种类型的船：1000TEU和5000TEU。如果班轮公司不使用1000TEU型船的话，就只能调用5000TEU型船。但是，一艘5000TEU型船的运行费用可能会超过两艘1000TEU型船舶。因此，一般会选择调用两艘1000TEU型船。决策变量取值为连续非负值。尽管集装箱的数量一定是整数值，但是这个整数值通常是几百的数量级。因此中期规划周期内，把路径流量模拟为连续变化是合理的。从表1可知，每一对港口对p和q之间最多有四条分段式路径，其集装箱总运输量等于集装箱需求量。路径流量跟船舶配置放方案中重箱分段流量有关，且一条路径包括一个、两个或三个分段。例如，图3中路径和都包含分段。因此，包含分段的所有路径上的重箱总运输量应该等于所有船舶配置方案中分段流量总和。空箱没有具体的出发港和目的港，因此可以从任何一个空箱剩余港运输到任何一个空箱不足港。所以，航段运输量变化特别大。为了克服这个困难，我们用空箱航段流表示而不是分段流，因为航段流的数值变化要小很多。分段流量其隐含定义了装货港和卸货港，与之相反需增加空箱装卸变量（分别和）来表示航段流流量。3.2 混合整数线性规划模型根据v型船在港口p每小时集装箱装船数量和（或）卸船数量的平均值，每标准箱的重箱或空箱在港口的的装船或卸船时间（h/TEU）可以表示为： （17）设（美元/TEU）表示已知的重箱或空箱在港口的每标准箱装卸成本，（美元/TEU）表示已知的v型船在港口p的泊位占用费。在装卸过程中发生的操作费用和v型船舶在港口p停靠的每标准箱的泊位占用费可以表示如下： （18）设u表示所有决策变量组成的决策向量，定义为： （19）关于向量u的总运营成本函数表示为：（20）式（20）中求和的的第一项是备选航线的固定运营成本，第二项是与重箱运输量相关的可变成本，最后一项是相应的空箱调拨的可变成本。本文提出的班轮运输航线服务网络设计问题可以表述为一个混合整数线性规划模型：（21）s.t. （22） （23） （24）（25）（26）（27） （28） （29） （30） （31） （32） （33） （34） （35） （36）其中，表示从p港到q港包含分段的分段式路径集合，；表示包含分段的备选航线的集合，；表示连接港口p的备选航线集合，；表示航线r上港口p的编码指数集合，因为p港可能被航线两次挂靠，即 （37）在上述模型构建中，目标函数（21）为求最小总运营成本。约束（22）要求对于每一对OD对港口，其路径所有航段上的运输的标准集装箱量之和等于集装箱需求量。约束（23）表明航段上的总的重箱运输量等于船舶配置方案中为该航段提供的重箱运输量。约束（24）确保满足所有的空箱调拨任务。约束（25）强调了在每一个挂靠港的空箱流守恒。对于航线r上的任何一种船舶配置方案，在港口，从港运来的空箱量加上那些在本港装走的空箱量之和等于从该港运往港的空箱量和在该港卸下的空箱量之和。约束（26）是所有船舶配置方案中每条航段上的船舶容量限制约束。式（26）的左边第一项是航段的重箱运输量总量。空箱运输量仅仅取决于重箱运输量。第二项是空箱运输量。式（26）的右边是船舶配置方案提供的运能。约束（27）强调了每个船舶配置方案不得超出最大泊位占用时间。式子的左边是重空箱装卸过程中产生的泊位占用时间。在航段运输一个重箱的时间包括在k港的装船时间和在l港的卸船时间。空箱的泊位占用时间与装船量和卸船量直接相关。式子的右边是船舶配置方案的总的最大泊位占用时间，其中每m艘船，泊位占用时间最长为往返时间168h减去海上航行时间总和跟在挂靠港的闲置时间。约束（28）强制约束在船舶配置方案中每一个港口要至少被一艘船舶挂靠，因为任何一个港口要么是出发港要么是目的港或二者都是。约束（29）要求在空箱不足和中空箱平衡的港口没有空箱装船。约束（30）要求在空箱剩余和中空箱平衡的港口没有空箱卸船，约束（31）（35）为各个决策变量的非负约束。约束（36）表示为一个非负整数值，其中Z+表示正整数集合。4 数值模拟算例4.1 测试实例为了评估被提出的混合整数线性模型的计算效率并调查其实际含义，我们使用上面提到的由46个港口组成的亚-欧-大洋洲航运服务网来生成24个实例，如图1所示。在此所用的所有参数都来源于全球班轮航运公司的实际数据（由于商业机密而有所修改）。我们从三个方面生成这24个实例：从一个港口到另一个港口的所要求的备选航线的集合，船型的集合和载运集装箱运输的集合。对于这些实例，集合的上下限由公式（16）表示，和定义如下： （38） （39）式中参数30%和40%反应了总泊位占用时间百分比的两种极端情况，这两种情况都将往返时间考虑在内。我们首先生成两个备选航线的集合。第一个集合有40条航线，第二个集合有60条航线。第一个集合是通过考虑了在第二个集合中的前40条航线而推导出来的。这些航线包括了那些现下由全球班轮航运公司运作和那些由评估模型的航运专家所设计的。为了确定船型数量的影响，我们测试了船型的三个层次：四种船型（1500TEU，3000TEU，5000TEU和10，000TEU），六种船型（外加500TEU，4000TEU），和八种船型（外加2000TEU和1000TEU）。我们假设根据往返运距，确定某种船型的能否在60条备选航线的其中一条航线上航行。例如，5000TEU船型的备选航线就是所有往返运距在10,000到20,000海里的海运航线。两种船型的往返运距区间可以重叠，并且第一个集合的四种船型已经包含了所有60条备选航线的往返运距。事实上，不是所有港口对都有集装箱运输需求。因此，基于实际数据我们生成了一个包含600 个集装箱运输需求非零的OD港口对的实例，然后又筛选出三个分别包含50个 OD对，100个 OD对和200 个OD对的实例，这三个实例分别筛选的前50，100和200 OD对。这3个层面的结合生成了24个实例。每一个实例都由备选航线数量（R），船型数量（S）以及O-D对数量（D）所描述的。例如，一个有着40条备选航线，4种船型和50 O-D对的实例用R40S4D40来表示。在配有3.2GHz双核和4GB内存的电脑上，可用CPLEX-12.1通过默认参数设置来解决所有这些24个实例。4.2 结果分析表格2显示了24个实例的结果。“船只部署计划数”一栏表示的是船只部署计划总数。“重箱运输计划数”表示了重箱计划总数。“时间”一栏罗列了测试每一个实例的CPU运行时间。“Obj”一栏表示最有总运营成本（百万美元/周）。表格2 也显示了重箱和空箱的处理结果，包括了被运输（“容量”一栏）的总容量和在港装载总数量（TEUs）。重箱的数量比被运输的集装箱的数量多，因为一些集装箱转船了（至少装载了一次）。我们首先分析了模型的计算性能。船只部署计划的数量是由备选航线和船型所决定的。船只部署计划的数量是随着备选航线和船型的数量增长而增长的。重箱运输计划的数量和备选航线和O-D港口对相联系的。我们注意到每一个O-D港口对最多有四个重箱运输计划。CPU计算R60组实例的时间比计算那些有着相同船型数和O-D对数量的R40组要长，因为R60组有更多的船只部署计划。CPU计算时间一般随着船型数和O-D对数量增长而增长的，因为新的船型和新的O-D对将会引进新的变量。但是，也有例外，特别是D600组的CPU计算时间基本上随着船型数增长而减少，而且计算整个D200组比D600组需要更多的时间。我们推测这个结果是因为相关问题的特殊结构。这24个问题实例所需的平均CPU计算时间是六分钟。因此我们有信心做出结论，这个被提出的模型可以应用于解决实际问题。表2 24个测试的结果接着，我们为班轮公司测试了管理影响。正如我们所预期的，在相同备选航线和船型的条件下，总的运营成本是随着O-D港口对数量的增加而增加的，因为需要运输更多的集装箱。我们也观察到了对于相同的集装箱运输需求，总的运营成本随着船型数和备选航线数的增加而减少。这可以解释为班轮公司可以有更多的运营选择。因此，我们可以通过设计更多的备选航线来减少运营成本。然而，如果设计不当，增加备选航线可能不会提升解决方案。例如，R40S6D200和R60S6D200的总的运营成本是一样的，这意味着在第二个集合中增加的20条备选航线在优化方案中没被使用。而且，为了减少总的运营成本而纳入更多的备选航线是要耗费更长的计算时间的。班轮公司必须在方案质量和计算时间之间找到平衡点。在所有的停靠港装走的集装箱总量等于卸下的总量，而且它比要被运输的集装箱量要大。换句话说，一些重箱和空箱不止装载过一次（转运）。从表格2中得出如下结论，首先，我们观察到大量的空箱是由于贸易不平衡而造成的。24个实例中运输的集装箱总量中平均有32.4%为空箱。同时，在港装船的集装箱平均有25.6%是空箱。这意味着空箱要比重箱转运的频率要少。这可以解释为由于空箱有着灵活的目的港口。因此，这个模型就可以尝试着通过转运空箱数最少的原则匹配出发港港和目的港。最后，我们注意到平均有35.0%的在港重箱是转运集装箱。这强调了在模型发展中要考虑转运这一方面的重要性。4.3 与纯轴辐式和纯多港挂靠式的比较为了评估考虑轴辐式和多港挂靠混合模式的重要性，我们将它与纯多港挂靠模式和纯轴辐式网络进行比较。在纯多港挂靠式网络中，集装箱直接从起始地到目的地中途没有转运。在纯轴辐式网络中，从一个喂给港到另一个喂给港的集装箱必须经其相应的核心港口转运。因为纯多港挂靠式网络中一些O-D对港口之间没有备选航线，我们假设班轮公司可以租用其他公司的箱位。为了简化问题，这里我们并不考虑空箱。我们测试了