集装箱翻译.doc

班轮运输的船队规划和网络设计摘要：班轮承运人面临的一个普遍的问题就是其服务网络设计。对于给定的待运输的货物需求及港口，承运人要利用已有资源，尽可能高效的为其船舶设计运输路线。而且，运输路线的利润，取决于运输货物所选择的路线。本论文构建一个整合模型，即混合整数线性规划模型来同时解决船队规划和路径选择问题。这个模型合并了相关约束（比如营运航线的周频率约束）和可能的中转情况（比如两个或两个以上运输路线上的货物中转）。为了解决这个混合整数规划，本文提出一些算法来探索问题的分离性。具体说有贪婪算法、遗传算法和两阶段Benders（班德尔）分解算法，考虑解决问题的效果，各算法的计算效率和计算时间也被考虑在内。提出了一种有效的迭代探索算法来计算船舶规划，并在20多个港口、100多艘船舶中随机生成距离进行计算机仿真试验，最终结果有较高的船舶利用率和有效地中转。关键词：海上运输；班轮运输；Benders（班德尔）分解算法前言海运货物，即船舶运输的货物，它包括除了邮件、人及随身行李等一切经由海运的货物。国际海运承运人，可以是一个人，一个企业或一个能在全球范围内通过海运提供运输服务的组织。货主可以是人，也可以是一个企业，他们是待运货物的提供者或者所有人。在各种运输方式中，海运拥有运费低（十分之一的航空运输费用）、事故少、污染小的优势，因此也被认为是一种经济、安全、环保的运输方式。逐渐发展的全球化和各经济体间相互依赖促进了航运业的蓬勃发展，并使许多国家的国际国内贸易都依赖于此种运输方式。美国是世界上最大的进出口贸易国家，其贸易量占世界贸易量的接近20%，根据美国港务局协会2006年统计，国际货物运输的99%是由海运完成。美国港口和水路每年完成超过25亿吨的贸易货量，且这一数据在未来十五年内能翻一番。世界海运贸易的发展，带动了世界船队的发展。联合国贸发会2006的数据显示，2005年，世界海运贸易装载量增长到71.1亿吨，并以每年3.8%的速度增长，而同时，世界船队增长到9.6亿载重吨，并以每年7.2%的速度增长。尽管船队类型和规模已随着时间改变，但是船舶的高效利用仍是承运人利润的主要决定因素。一艘船舶需要巨大的资本投资，一般都是几百万美元，而且其日常营运成本也有几万美元，因此，最优决策支持系统的发展对于船队有效管理非常必要。海运业已经有很大改变并正在形成新的格局。一个最显著的改变就是集装箱的大量使用。集装箱货物是指，把货物空间上和经济上储存在集装箱里。货物集装箱化减少了港口人力和设备的装卸作业，是航运业的一次改革。集装箱也已经标准化，术语TEU表示20英尺长的集装箱。根据德鲁克航运2001年报告，在十九世纪九十年代初，只有20%的杂货是由集装箱运输的。在2001年这年，这一数据就增加到60%。IBM业务咨询白皮书（作者Naresh Hingorani、Derek Moore、Keld Tornqvist 2005年）显示，集装箱航运市场仍以每年8%-10%的速度增长。趋势详见图1.伴随集装箱化运输的另一个重大改变是集装箱空箱调配。在运输航线上贸易量巨大的不平衡性，承运人需要调配空箱，这也是一笔很大的成本。ROI研究所2002年报告显示，在设备和调配上减少10%的成本，利润就可以增加30%-50%。海运业的发展见证了中转港数量的增多、规模的增大。中转港是指货物从一艘船上，在某港口转运到另一艘船上。通过一系列岸桥的移动，货物从一艘船上直接换装到另一艘船上，或者卸到港口暂时储存再装载到出港船舶上继续运输。集装箱的使用，使得这种中转非常方便并且成本效率高。中转服务为承运人提供了额外的路线选择，减少了中转次数并担当了国际贸易促进者的角色。比如，巴哈马弗理波特（Freeport）的和黄（Hutchinson）集装箱码头已经成为美东海岸、墨西哥湾、加勒比海、南美到欧洲、地中海沿岸、远东和澳大利亚地区的贸易通道。其他重要的国际中转港包括新加坡、马来西亚巴生港和香港。2003年，将近30%的集装箱都需要进行中转，而且这个数字还在增加。美国消费者服务2003年数据表明，在新加坡装卸的所有集装箱的80%都是中转箱。新加坡是世界第二大集装箱码头，按照船舶吨位计算，新加坡则是世界上最繁忙的港口。海上承运人之间的合作也并非新见。早在1875年，承运人就采用协商的方式来抑制竞争控制运费。最近常见的是，承运人形成战略联盟来实现规模经济，通过为客户提供高频率的航班和高速度的中转，扩大其客户基础和增加设备利用率（Song and Panayides 2002）。从1990年海陆联运和马士基率先联盟，并开始在大西洋和太平洋上共享船舶以来，战略联盟变得更为普遍。现在，更小的联盟合作成为更大的联盟，比如伟大联盟和新世界联盟2006年签下合作协议。联合船队和运输路线的趋势需要更好的决策支持系统来控制一定数量的船舶，来解决大规模规划和最优化问题。Christiansen, Fagerholt, and Ronen（2004）详细的将全球航运业划分为三种不同的营运模式，大宗工业物资运输、不定期船运输和班轮运输。在大宗工业物资运输中，货主拥有船舶并追求运输总成本最低。在不定期船运输方式中，承运人与货主签订运输合同，在一定时间内在特定港口见运输干散货。如果市场上还有其他货物，允许根据船队能力加载货物以追求收益最大。在班轮运输方式中，承运人决定一定的航线，向货主提供船期，并按此营运。通俗而言，大宗工业物资运输就好比家有小汽车，不定期运输好比出租车，班轮运输好比有着固定班次和公共路线的公共汽车。本论文讨论的是班轮运输。班轮运输是指在固定航线上有规律的进行集装箱运输。班轮运输有较高的固定的运价和管理费用，比如说不定期船运输。不定期船运输在船舶满载离开港口之前通常需要等待，然而班轮运输则不管船舶是否满载，都需要在预先设定的班期时间离开港口。既定航线上的船舶数量主要是由该航线上所需要的发班频率、船舶运输的距离和船舶航行速度决定的。例如，纽约和汉堡间的周班服务需要四条船舶来确保必要的发班频率。正如Christiansen, Fagerholt and Ronen（2004）所观察的那样，随着全球集装箱货物的增加，班轮运输也高速发展。2003年，由运输网络、集装箱、集装箱码头和信息系统组成的班轮运输完成了全部海运贸易的60%。根据Barry Rogliano Aales AlphaLiner2002年的报告，2000年2月到2006年2月，全球班轮贸易的集装箱能力从515万标箱增加到913.5万标箱，增加了77.4%。班轮运输涉及了战略、战术和运营计划层面的决策。表2给出了在不同层面上所需要制定的决策。在战略决策层面，需要决定船队最优船舶数量和船舶类型。考虑到拥有一艘船舶需要巨大的资本投入（通常是几百万美元）和持有一艘200TEU的船舶的闲置成本是每天22.5万美元，战略层面的决定是极为重要的。在战术计划层面，需要进行航线设计以构建运输网络，也就是说，要考虑既定船队挂靠的码头和这些航线的船舶分配。船舶在整个计划范围内从一个港口到另一个港口循环运输。为了维护客户，为客户提供固定船期，大部分船舶一周至少挂靠一次其运输航线上的每个港口（e.g. a cycle）。这就需要在该循环上营运的船舶数量至少等于完成这个循环所需要的周数。有些循环，比如说连接亚洲和北美的航线可能需要八周才完成，这就意味着承运人需要至少八艘船舶来在这条航线上开辟新业务。承认人设计服务网络的问题可以归结为船队规划问题。在营运计划层面，承运人需要决定接受或拒绝哪票货物、选择哪条航线运输承运的货物。这就是所说的货物路径选择问题。承运人可能选择不运输某些货物，或者因为它利润低或者因为别的港口有其他货物，而这票货更有利可赚。货物运输的开始是从内陆运输到装货港，从内陆由卡车、铁路或者水运运送到装货港的运输网络，被称为支线运输网络。然后货物从装货港运送到卸货港，中途也可能挂靠几个中间港。随后又利用支线运输网络，运送到内陆目的地。货物从装货港运送到卸货港中间挂靠的一些中间港有时候是进行水水换装的中转港。一个层面上的决策也会影响另一个层面上的决策。战略层面的决策为战术和操作层面的决策提供政策和指导。同样，战术层面的决策为运营层面的决策提供能力限制和网络结构。反过来，有了这些决策的系统产生的成本收益的信息又为更高层次的决策提供了必要的反馈。过去的几年里，航运业在采用新的决策系统方面一直是保守的。长期以来，都是有经验的决策者手工计划，而且，一般来说，船队规划涉及很多各种各样的问题。因此，对于有具体约束和目标的具体问题来说，大部分量身定制的模型是可用的。而且，大部分可用的文献也随着行业和不定期船运输的发展而发展（Christiansen, Fagerholt, and Ronen 2004）。由于模型和问题结构本身的不同，现存文献中也很难有比较性。接下来，我们简单的回顾一下有关集装箱和班轮运输的一系列有代表性的文献。为了综合系统的回顾船队规划和路径选择方面的文献，我们推荐Romen1983年完成的论文、Ronen19821992年研究于1993年完成的论文和Christiansen, Fagerholt, and Ronen2004年完成的对于近十年研究的论文。Rana and Vickson（1991）通过为每一艘集装箱船选择最优的挂靠港顺序、为每艘船舶在每组港口中转提供了最优的货物单元数量，提出了非线性整数规划的方法，来解决总利润最大化。他们允许船舶多次的收发货物（pickups and deliveries）。然而，考虑了一个具体的网络结构，即在终港货物的装卸量是有限制的。而且，模型没有考虑中转，即不允许船舶载运的货物不经由装货港或卸货港。这个模型解决三艘船舶20多个港口的船舶规划情况所需要的时间不超过一小时。Fagerholt(1999)将班轮运输问题放在一个特定网络中考虑，这个网络是将一个所有货物从一组出发港口汇聚到一个港口。这个问题通过首先把所有可能的单船航线汇聚到一起，然后再划分的方法解决。但是同样这个模型在转运问题上面具有不可操作性。尽管该模型在运营航线中增加了周频率这样一个约束条件，可行航线最大的航行周期时间也只有一个星期。因此，在任何一个可行航线上单船可以满足每周的频率。文中展示了模型几分钟内解决19条船舶，40个港口的规划问题的实例。最后，Perakis(2002)提供了一个线性回归和整数规划模型，这个模型只考虑了一支拥有不同船型，路线固定，服务频率固定的班轮船队的部署问题，模型目标在于最大程度降低运营成本。如前面所提到的,在一个规划阶段的决策将影响在其他规划阶段的水平。给定一个船队的规模和结构下,服务网络由基于一定运营规划水平的货运航线决策决定。货物决定运营决策，路线决定生成的成本和收入，由此给出服务网络可以产生的盈利能力。这两个问题高度关联，因此，给出他们的整合框架是十分重要的。本文的贡献是双重的。首先,提出了一种新的混合型整数规划(MIP)模型解决船舶综合调度和货物运输集装箱路径问题。由图2所示,我们把这个问题看做船舶和货物同时调度的路径问题。其次,由于该整数规划太大,无法解决经济上的通用混合整规划代码,我们开发的更高效算法解决。我们的模型处理了很多以前的文章中没有提到的约束条件和新的趋势，例如,客户期望承运人保持他们所在航次的至少每周发班的频率。就我们目前所掌握的知识,一般文章中这个约束条件还不能完全形成。但我们成功地给出了基于承运人角度在港每周频率的约束。在通常的集装箱运输问题中,我们允许多个小车和货物抵达船舶。也就是说,我们允许一个集装箱抵达一个或多个目的港。此外,一支船队由具有不同的特征不同 ,并可能随时间改变。我们认为一支船队的船只具有不同大小、成本结构和速度。在文献中,虽然有文献例如,Fagerholt (1999)模型考虑到非统一化的舰队,但大多数模型考虑用相同的服务速度。空箱调运问题是在班轮运输的一个重大的问题。我们的模型经过改进，具有处理空箱调运问题的功能。Shen和Khoong(1995)以及Cheung和Chen(1998)都对空箱调运问题进行了一定研究,然而,这些研究只考虑了在一个特定的网络下的空箱调运。我们模型中的货运航线是多个航次的组合而不仅仅是一个循环性的周期（一些简化假设成本的转运），从而为承运人提供更多的机会。在模型中，集装箱转运的中途港是未知的，这些特性使用我们的模型在设置上具有多样化。到目前为止,最通用的解决船队规划问题的方法如下：Fagerholt(1999)找到了包含非线性、复杂的约束条件的一系列可行的时间表,然后用一套分割问题解决。本文目标在于建立对于船队规划和货物路径选择同时解决的模型并解决大型实际问题。因此，我们设计的算法不再局限于一个最初的航线或详尽地列出所有船只的路线,而是利用问题的分离性构建对船舶和有效路径需求的周期模型。更确切地说, 我们通过贪婪算法、列生成算法和基于Benders分解的两阶段算法，考虑解决问题的效果，各算法的计算效率和计算时间也被考虑在内。提出了一种有效的迭代探索算法来计算船舶规划。计算结果是最优的，并且一些算法在大型问题处理上具有可行性。合并海运其他行业的结果是船队规模扩大，本文通过多达100船只和20个港口的规划问题进行实例验证。文章整体结构如下。下一节介绍了我们的符号,数学公式,以及关于这个问题的复杂性。2讨论了三种不同的算法, 贪婪算法、列生成算法和基于Benders分解的两阶段算法。 第三节提供了各种算法和实现细节。第4节给出了计算和实例验证。最后一节讨论了结论和对今后工作的展望。1.问题描述我们首先介绍符号含义和空间网络，然后向大家展示数学理论公式。表示港口构成的集合，我们要把需求做为一组商品供应的一个积极的起源港和积极的目的地港口需求。每件货物的起始港为O,目的港为d，时间为i,在港可供应时间O,在港最大需求d（单位TEU），D（O,d,i）; 每TEU需求的满意收入R（o,d,i）,我们用（o,d,i）来表示一个具体的需求，表示其构成的集合。在一支船队中通常有几种不同的船型，每一船舶类型通常有不同的能力和速度。我们用来表示船舶种类的集合，a表示其中的一种船舶类型，表示船型a的装载能力（TEU）；对于港口表示一艘船型为a的船舶从港口p航行到港口q所花费的时间（天），表示在给定的船队中船型为a的船舶数量。考虑到时间方面的问题很重要,我们把船舶调度和货运路径问题看做一个带有空间网络约束的MCF问题。此外,我们把空间网络以天为单位，因为一般远洋航线在给定天无法到达一个港口。定义为一个带有变量集合V和边缘点集E的直接空间网络。对于，港口(v)表示一个港口，时间(v)表示一周中的星期。也就是说，对于每个港口，我们在V中制造了7个顶点。为了标记方便起见，我们把顶点表示为：当时，。我们用G来表示，这取决于表达方式。网络G=(V,E).包含3种类型的边缘。第一种是地面边缘(ground edges)。对于每一个船型，我们连接这两个v点并且,同样的连接。对于一个船舶来说，这些边缘展示了一个在港的滞期；对于货物来说，这些边缘展示了货物在港滞期或者滞留在未出港的船上。其次，对于船型和港口，我们构造航行边缘(voyage edges) ,对于,使，去余数(7)。这种航行边缘表示了在一定速度下船舶和货物从一港至另一港的运动。最后，我们创造了一系列虚拟边缘（fictitious edges），对于所有的需求三元向量,一个边缘仅允许货物流量(o,d,i)通过并且使我们掌握货物(o,d,i)在网络中的循环成为可能。我们用Eg表示地面边缘构成的集合，船型a地面边缘构成的集合为，航次边缘Ev,船型a的航次边缘构成集合，所有虚拟边缘Ef。也就是说，。我们同样使用以下符号：inedges(v)表示在变量v下incoming edges 构成的集合，outedges 同理；对于一个边缘e=（u,v），tail(e)表示终止点u,head(e)表示起始点v。图表3表示了一个带有四个港口个、和两个航线的空间网络，C1和C2。港口C作为货物从港口A到港口D的中转港。航次边缘的长度等于船型a的船舶从港口v到港口u所需要的天数。当时，le=1；当时，le=0.一个线路可以承受的能力用TEU表示出来。一个港口的地面线路可能有有限的或者无限的能力，这取决于我们是否愿意给一个港口的货物数量加一个（操作量或存贮量）限制条件。航行线路上的能力取决于该航线上船舶的数量（和他们的能力）。在船舶调度和货物路径上面需要注意到可变成本和固定成本的问题。其中的一些费用是由船舶引起的，其他是由货物引起的。对于与港口相关的费用，我们用表示船型为a的船舶在v港的一次性费用，表示每TEU货物一天在v港的总费用。港口访问成本在不同港口费用不同。类似的，当在航行时，体现了船型a的船舶在路径e上的运营成本，当停泊时，体现了船型a的船舶在港停泊一昼夜的费用。对于货物来说，当时，表示在线路e上每TEU货物在线路e上的船舶成本，当时，表示表示每TEU货物在始发港(e)的仓储费用。虚拟线路相当于0费用。我们要确保港口访问成本在每个港口只发生一次,即使这艘船进行了一夜停泊在港口的行为。为了正确考虑在访问时间扩大的网络下港口费用问题,我们在路面线路e产生的船舶费用上减去船型a的港口访问费用。因此,如果一艘船一整夜呆在一个港口,那么尽管港口访问成本是由于节点增加成了两次费用,但是已经在路面线路的费用中扣除了。船舶在港空载的代价是过夜也同样会收停泊费。货物由于在非目的港滞留而增加其费用。在本文中,我们把星期中的每天作为时间离散化水平；因此,我们假设如果在港个不同航线的船舶同一天出现在港口,转运就可以发生在两个方向(例如,货物可从其中一船舶转移到另一船舶)。通过考虑更精细的离散化的时候,可以采取占较小的时间窗的一个港口,船只在见面并确定转运吧可能只在一个方向(不承担因此持续的费用)。考虑到空间网络的离散化水平是以天为单位,一种商品在第i天到港o可以被描绘成一个供应网络上的顶点， 我们假定供应在每一周的那一固定天出现在在顶点o(目的地d)。由于我们是在考虑一个合理的模型，所以我们给出的供应在给定的某一天出现是合理的。由于承运人的需求是不变的,每周的服务水平也不会发生变化。为此,我们假设给定任何航次,每周频率、使用船型等都保持不变。我们描述港口船期表上的一个航线C,在该周期性循环的航线上访问的港口和时间是固定的,船型也是固定的,航次C每周运营需要的船队数量也是固定的。由于船舶的不可分割性，Lc定义取整。当满足预定规则的船只数量、周期频率以及访问港口时，我们认为这是一个周期。我们把这一系列基于船型a的可行的航线集合定义为。从数学上来说，对于一个cycle ,必要时我们用一组点来代表一个cycle C；对于中C的航线费用由COSTc表示，并且1.1数学模型对于船队规划和货物路径选择问题，我们提出了一个整数规划的理论公式。 这个公式有两套变量。首先,对于任意可行cycle C我们定义其为Xc。当cycle C 能够保持每周的循环频率，Xc = 1；否则Xc=0. 变量Xc是一个二进制,这是因为在同一个星期相同类型的两艘船从一个港口沿着相同的港口调用几乎是不可能的。接下来，我们定义将线路的流量定义为一个负连续变量，对于每个线路和每个triplet ,我们定义在线路e上的(o,d,i)集合为。对于一个虚拟线路e= ,对于货物(o,d,i)一个单向流变量定义为，因为在此条线路上的其他货物流动是不允许的。需要注意的是我们让流程变量是连续的，因为一个非整数的容器不影响我们模型的最优解。在建立模型之前，我们附加了以下假设条件，假设1-3是为了更清晰的展示模型以及保证我们模型的可用性；假设4是最为重要的。假设1：假定ground edges的能力是无线的，也就是说，我们可以在一个港口处理/储存无限的货物。假设2：我们假设所有的货物费用都可以通过线路费用建模；也就是说，我们使假设3：我们假定所有货物可以再相同的1-TEU集装箱中，因此，表示一单从港口d出发并在一周的第i天，到达港口o的货物需要的集装箱数量 。假设4：最后，我们不考虑从一条船转移到另一条船的成本。正如前文所述，货物在任何港口过夜都涉及持有成本。为了正确衡量转运成本，我们需要识别网络中同一边构成的不同航线的容量。如果在所有可变的航线上将边复制，图形将迅速变大。转运成本将难以衡量。如果网络位置，也就说将要运营的航线未被选择。由于我们以同时考虑网络设计和货运线路规划问题为目标，将形成可行航线作为子问题，我们暂时忽略转运成本。在4.4节，我们将以案例研究方式讨论货运航线决策中转运成本的影响，货物运输的船队是给定的。同时的船舶调度和货运航线规划问题可用以下混合整数规划定义：约束条件为：现在我们来解释上述公式。目标函数（1）是使得收益减去运营成本后的净利润最大化。目标函数的第一项表示不同起始港、目的港形成的组合转运货物产生的总收益。第二项包括了设计货物在起始港到目的港的费用。第三项表示在已选航线上运营船舶的总费用。约束（2）是在空间与时间构成的网络上各点的流量平衡限制。它确保了流入点v每种货物（o,d,i）等于同种货物流出的总量。约束（3）和（4）是边的容量限制。约束（3）在航线上某条边的总流量必须小于服务于该边的运营船舶的容量之和。约束（4）表示一种给定的货物，从起始港到目的港的总流量必须小于目的港的需求量。注意，由于假设1，我们没有地面周转的容量限制。约束（5）要求每支船队的类型，我们使用的船舶都不会闲置。注意如果航线Cn被选择，就表明Xc=1，则使用Lc型船舶来维持一个周班航行。最后，（6）表明Xc是二进制变量，（7）表示fe(o,d,i)是非负连续变量。1.2问题的复杂性同时调度船舶和设计货运航线问题从决策上讲，是NP难题。即给定一组运营航线和航线上的货运流，可以由总收入是否超出给定常数K的多项式来判断。我们将利用著名的NP完全问题，0-1背包问题，将一个同时调度船舶和货运线路的问题转化为把一个NP完全问题。0-1背包问题定义如下：给定集合：N=1,2,n，K, Ci, Wi为整数，对iN，总有N子集S满足：。定理1：同时调度船舶和货运航线属于NP完全问题。证明：假设W条同样的船舶，载重均为TTEUs。构建如下的海运网络，对i1,2,n，假设有2个港口，其需求分别为di和CiTEUs，起始港为Oi。让船队中的船舶承担从Oi港到di港Wi/2周期的运输。假设港口之间距离相同，对1ijn，Oi与dj的距离无穷大。这样，wi的船舶必须维持CI的周班航行即Ci=oi-di-oi，1in，所有其他航线均不可行。另T=maxiN Ci，满足任何o-d组的单位需求收益为1。假设不包括运营成本。结果：所有可行的航线都是非连接的。航线Ci需要Wi条船舶维持周班，形成Ci单位收益。如果集合SN，用于运营，的总收益被形成。当给定一组既定S航线K单位或更多利润，0-1背包问题就有一个可行解。这样，0-1背包问题能用SSSCR问题求解。2.解决方法（1）至（7）的线性规划甚至是中等规模的问题中都包含了大量的变量。模型的规模是可行航信的指数结果。而且，每种需求增加成MIP模型的一组可变的变量。但是，一个有趣的实验，如果我们决定各类船型的航线集合，即给定非负值满足船队可用性约束（5）。模型（1）到（7）简化为如下的MCF模型，每个模型量被认为一种不同的货物。注意（8）至（12）是只包括了可变变量fe(o,d,i)，是无整数约束的线性规划。令=v(o,d,i): v(o,d,i)无限制，vV，(o,d,i）,=e,e o, (o,d,i)的变量集合分别满足约束（9）（10）（11）。下面，我们提出三个遗传算法，阐明上述SSSCR问题。首先，我们提供一个简单的贪婪算法，挨个选择满足的航线，再将货物分配给航线。然后，我们列出一组基于遗传算法的数形成满意的航线，从中选择最优航线和网络中的运输线路。最后，我们介绍了包括Benders 分解算法。图4描述了三种算法的流程。2.1贪婪算法令S代表运营航线的集合，即分配船舶维持航线周班。航线C的价值取决于雇佣船舶在C上的货物流动、船舶数量和运营航线C的可变成本。航线C的边际价值也却绝育集合S中的航线。因此，航线的贪婪算法必须被考虑到现存的运营航线和需求(o,d,i)。令Aa,a，代表船型a当前可用的船舶数量。贪婪算法以一组空集开始。为了找到合适的航线，网络Gn=（Vn,En）被创建以便使用MCF问题的解法分担边际成本。Gn用于每条船型a以保证Vn=V, En=EvaUEna 。利用步骤FindCycle（Gn）每条边eEa承担Ce=Cesia+e,每个点，vVa承担成本Ce=Cesia。对每种船型，算法寻求附加网络中最小成本的航线。步骤的细节在第3节介绍。最后，如果可行，最小成本的航线和船舶数量的满意值将被选择以维持周班的频率。步骤会重复到船舶被分配完成。2.2基于列生产的算法尽管贪婪算法简单，能快速提供可行解，但并不是有效解。它是可行航线的小范围解集，一旦可行航线形成，它将在最终解中出现，不再考虑。接下来，我们引入基于列生成算法，为解决线性规划的可行航线集合。列生成算法是一种解决线性规划的有效方法。比起列举所有显示的列，它从解一个用一组可选的列来解决有约束的问题。子问题用形成一系列有效的列来求解，它们随后被增加到子问题中。生产列方法已经成功运用到许多大型优化问题中，请看（Barnhart 1944）求解航线人员分配任务的问题。为解决SSSCR的LP松弛问题，在生产列中的主要问题被生成，通过对于每个需求变量的来限制航线选择变量。在生产列的步骤中，通过寻求每个决策变量的最优值用来解决此主要问题。定价问题在生产列中等同于在辅助网络中为每艘船型确定负成本周期。辅助网络Ga=(Va,Ea)作为每条船型a使得Va=V,Ea=Eav U Eag。主要问题的双变量值被用来分担辅助网络中边和点得成本。每条边eEa,分担成本Ce=Cesia+Tae+(le/7)，每个点vVa分担成本Cv=Cvsia，负成本周期在Ga中对应主要问题的正降低成本。注意由于SSSCR是最大化问题，盈利列代表有效降低成本。FindCycle（Gn）步骤（第3节）被用来确认辅助网络中负的成本航线，相应的列被增加到主要问题中。步骤一直持续到发现新循环。最后，整数约束被添加到航线选择变量，分支-树形框架用来获取SSSCR问题整数解。在分支-树形阶段，新列不再形成。不同的分支方法有不同的优点，可以调整求得整数解。例如，在最大的克星航线上，分支使得许多其他二进制变量也能满足整形约束。但是，我们尽可能用影响求解质量的变量作为分支变量，给上一级分支（Xc=1）优先权。因为这种策略在我们的实验中最优。2.3 双向Benders分解算法港口、船舶和需求的增加导致列生成中的模型（1）至（7）难以求解。约束限制的数量和变量随着港口、船舶和需求的变量增加而增加。因此，问题规模的增加作用分为主要问题和子问题。进一步地，这种分解被用来有效求解LP松弛问题。这种解法用于分支-树形方法中获取一个整数解。Benders分解是一种求解带有连接性约束混合整数规划编程问题的常用方法，这种方法用于主要问题有所有整形变量并且难以作为子问题时。这种解法的流程在整形主要问题和子问题。主要问题传递到子问题的整数变量的值，子问题形成可行和优化的部分重新传递到主要问题上。然而，这种方法已经证实适合许多问题，它有整形主要问题不得不在在每个整数阶段被解决。McDaniel和Devine（1977）引入了这种方法的证明，这种方法的解法有一系列整数规划变成一系列线性规划和若干整数规划。在整数控制问题和子问题（群）之间的求解迭代过程。控制问题将整数价值变量传递给子问题（群）。然后子问题（群）进行筛检（可行性和最优性）然后传递回给控制问题。虽然已经证明这些方法适合于许多问题，但是整数控制问题的每一此迭代都在返回参数时都需要解决，McDaniel和Devine（1997）对这些方法的模型做了改进，即以一系列线性问题和几个整数的序列问题代替整数问题的序列问题。McDaniel和Devine（1997）以及他们的模型已经成功地用来解决许多疑难问题。Florian et al.（1976）运用这个技术解决了工程调度问题，而且Vander Wiel and Sahinidis（1996）也运用其解决了时间旅行推销员问题。近来，这些技术也成功的解决了机车指派、航空路线以及船员调度问题。对于上述这些问题，在整数控制问题中首次成功运用了松弛完整性约束，并且大量的时间缩减以及路径质量上也有很大的进步。在松弛性解决了可接受时间或最优准则之后，完整性约束也被再次引入到控制问题。我们现在也运用Bender分解技术方法来解决SSSC问题。2.3.1 Benders 分解技术 作为早被定义为非负价值系数满足船队约束（5），松弛线性规划模型（1）（7）减到MCF，因为MCF是一个没有完整性约束的问题，而且MCF问题的最优解等于其对偶最优解。MCF问题的对偶问题可以表达为：（DP）： (13)因此 (14) (15) 无约束，v V，（o,d,i） (16) (17) (18) 让D为对偶问题的可行域，而PD和QD分别为D极点和边界极线， D在不独立，而且由于 ，对于对偶子问题的可行解是， ，而且因为，通过强对偶，无论MCF是否可行或者有边界。明显，对于MCF零矢0是一个可行解。这就意味着MCF和DP的原始对偶是可行和右边界的。所以，MCF 和DP的最优解可以仅仅作为DP问题的极点；也就是设PD，可以写成引进一个剩余变量Z，公式（1）（7）能重新表示为下面的BMP（Benders master problem）问题，这个问题有整数变量XC和一个自由连续变量Z：（BMP）： max Z （19）约束表示由于对偶问题有界，所以在Benders控制问题中无可行解。最优性约束（20）保证了Z小于等于约束（20）的右侧，即各种对偶问题的极值点。总的来说，上面的模型包含了比松弛线性约束模型（1）（7）更多的约束，但是大多数约束在最优化时并不活跃。因此，必要时要通过减少或生成更多约束（20）来形成解决约束（19）（23）的自然方法。我们现在提出基本的Benders 算法来解决SSSCR问题的线性松弛问题和最优性问题。然后，完整性约束被引入到解决原始SSSCR问题。我们将BMP （邦德尔控制问题）的线性松弛表示为LPBMP（线性邦德尔控制问题），将包含减少约束（20）的LPBMP问题的松弛性表示为RLPBMP。2.3.2 算法概述 基本邦德尔分解算法是用来解决SSSCR迭代选择好的循环线性规划松弛性，它是通过解决解决船队调度问题的RLPBMP问题，以及为有效解决货物路线问题而解决的MCF问题。MCF问题利用RLPBMP的解来在解决流问题之前给航线分配船舶运力。反过来，在每次迭代过程中，MCF问题的对偶问题的解提供了一个RLPBMP问题最优切割。用t表示迭代次数，PDt表示在第t次迭代式可行域D的极值点的限制。在RLPBMP问题的第t次迭代中，包含了LPBMP问题中以PDt替换约束（20）中的PD。RLPBMP问题在第t次迭代中的解提供了原始LPBMP问题的上界（因为RLPBMP问题比LPBMP问题的约束更少），并用Z表示。.算法1，基本邦德尔分解算法：带有整数约束的原始BMP（或者SSSCR）问题分两个阶段启发式解决。第一阶段，去掉所有的整数约束，并运用基本邦德尔分解算法解出LPBMP的最优解。因为可行性周期的集合可能是指数，RLPBMP在本阶段中列生成设定中解决的。对于阶段1，算法1的解涉及到这个列生成。在第一阶段中保留所有的最优解切割和周期性生成，第二阶段将整数约束放回控制问题。重新开始算法1，然而，在这一阶段RLPBMP问题的第一步被混合整数规划BMP代替，与此同时切割和周期在第一阶段生成。由于对偶问题的多胞性不受被整数约束影响，所有在第一阶段生成的最优性切割都可以被用于第二阶段中的混合整数规划生成反馈切割。额外的最优性切割在每次迭代中都会产生。然而，在第二阶段，算法1中的第一步在每一代中都解决了整数问题。因此，在第二阶段中不会有新的循环产生，而且此解仅仅适用于松弛邦德尔控制问题的分支定界法。利用邦德尔分解算法来解决整数规划问题的两阶段法是由McDaniel and Devine在1997年创立的。其背后的直觉是希望控制问题中的许多必要约束可能在解决线性规划问题是生成更多，而这是为了代替解决计算量大的整数规划问题。在第二阶段中的分支定界数是由通过给上分支确定优先级的深度优先搜索来搜索的，在2.2节中，选择对结果影响最大的变量作为分支变量，记住在BMP中解决混合整数规划问题是计算量非常庞大的步奏，因为任何一个可行整数解都可能被用于生成一个最有切割，混合整数规划BMP问题不需要在在每一次迭代时都解决最优化问题。但是，如果利用启发式方法解决BMP问题，则它在邦德尔迭代中提供的上界可能比真实的上界要小得多，这样可能导致算法的提前结束。最差的情况下，上界可能比下界还小。为了避免算法的提前结束，分支定界搜索只有在获得一个可接受的最优差距的解质量时才允许终止（这个差距在最优整数目标和最有节点剩余目标之间）。利用较小最优差距来搜索分支定界树的解好像是花费了大量计算时间，但是它也貌似在每次邦德尔迭代中提供更好的边界，因而提供了更好的解质量。因此必须选择一个合适的最优差距来避免算法的提前结束，并保持计算的效率性。2.3.3 解决RLPBMP的列生成 邦德尔分解算法的控制（即算法1中的RLPBMP问题）可由列生成设定解决。在列生成中的定价子问题降低识别辅助网络中的负面成本周期，Ga=（Va ,Ea）,对于各种船型a，就像前面，Ga是由Va =V和Ea=EDqEgq，我们接着表示我们将如何在网络Ga的节点和边上计算成本。让（，）和a分别表示对应约束（20）和（21）的对偶变量，循环C所节省的成本公式如下：上式中第二个求和为C循环的边缘航次。由于通过加入松弛条件，陆地边界的能力很大。因此，陆地边界可以算入上述公式中的求和。LP理论中，我们知道如果每个的节省成本并且每个船队类型，那么我们就获得了最优解。也就是说，列生成迭代至对于某些存在一个循环使得对于我网络，我们假设：每个来说成本，对于每个边界成本为。当我们用代替中的时，我们假设成本为。考虑到，如果对于的最有定价都大于0，那么我们需要检查是否存在。如果存在，那我们就建立了一个盈利的循环，如果不存在，或者没有更盈利的循环，或者可盈利的循环只有非常低的负成本（-1）以至于可以忽略。我们使用程序来定义在种的负成本循环。3 算法问题在这部分我们将讨论有关于改进我们的算法是之更有效、可靠的几个问题。3.1 解决定价子问题定价子问题对于列生成以及Benders分解算法都适用，降低了辅助网络中可盈利网络的识别。相似的，在贪婪算法中也需要寻找辅助网络中的可盈利网络。这试图直接解决网络中的最小成本循环问题。然而，将由循环问题的求解结果得到的循环分解转化成简单的循环，并不是实用的。比如，我们最初循环问题的计算结