集装箱和封条管理程序

第一篇：集装箱和封条管理程序

集装箱和封条管理程序

1.0 目的

为了加强对本公司货物和货柜的运输安全，符合海关与C-TPAT安全标准要求，防止装运、运输过程中丢失货物或遭受非法入侵，避免恐怖威胁、走私及其他犯罪行为，确保货物准确按时的到达目的地，制订本程序。2.0 范围

集装箱和封条检查与监督人员。3.0职责

3.1外贸部负责封条的发放、保管、监管以及与当地海关的沟通； 3.2货物安全代表（成品仓主管）负责封条的使用、记录，检查货柜安全、货物物理安全、负责装柜货物质量监控、拍照及监督装柜过程；

3.3保安负责装柜过程安全的监控以及与当地公安机关的沟通；

3.4船务部要对封条的使用全过程进行文字性的跟踪记录； 3.5装箱完毕后，在进行封箱时及封箱后成品仓主管在保安的监督下要对封条进行再检查、拍照记录；

3.6上封条时仓库主管要在保安、报关员、船务等相关人员的监督下进行 4.0相关要求 4.1集装箱封条作为重要物件，必须符合一般PAS、ISO、17712标准高度保安技术要求，装柜结束上封条等由工厂报关员保安货仓主管监督处置；

4.2确保封条状况良好； 4.2封条用一般手力无法打开； 4.3装货人员须保持如下记录； 4.3.1订箱/仓位编号； 4.3.2封条字码及转船代码； 4.3.3船公司提单号码；

4.4船务员记录相关信息，已确保货物安全顺利的到达指定地点； 4.4.1集装箱离开工厂时间； 4.4.2途中位置的报告； 4.4.3到达指定地点的时间。

第二篇：集装箱总结

集装箱学习总结

学期总结：

一个学期即将结束了，没有目标就没有动力。只有有深刻的总结报告才能进一步了解到这一学期你学到了什么？为今后的学习做好计划，更好的掌握总结所学习的知识。回顾本学期所学的知识，这本《集装箱运输及多式联运方式》书系统地介绍了集装箱运输与多式联运的理论和实务，但是我们这学期主要是学习集装箱运输方面的知识。下面将我这学期所学的《集装箱运输及多式联运方式》知识总结如下：

集装箱

集装箱是一个容器，它装载货物的数量是比较多的，而且是在封闭的情况下进行运送的，所以需要在使用集装箱之前要检查好是否存在安全隐患，是对货物安全运输的基本条件之一。

集装箱多式联运概述

集装箱作为现代最先进的一种运输工具，首先了解国际标准化组织对集装箱的定义：集装箱是一种运输设备，具有足够的强度，可长期反复使用；适于一种或多种运输方式的运送，途中转运使箱内货物不需换装；具有快速装卸和搬运的装置，特别便于从一种运输方式转移到另一种运输方式；便于货物装满和卸空；具有1立方米及1立方米以上的内容积。

随着集装箱运输的发展，为了适应装载不同种类货物的需要，出现了不同种类的集装箱适合装载各种不同的货物来分：

一、按货物的性质分，有普通货物、典型货物、特殊货物；

二、按货物是否适合装箱分：最适合于集装箱的货物、适合于集装箱的货物、临界于集装箱的货物、不适合于集装箱的货物。

在运输过程中防止货物的损失，保护货物，避免在装载过程中可能出现的危险。安全装箱基于以下的因素：运输货物的特点；包装方法；货物的结构、生产特性；保护措施；所使用的包装和包装材料的类型；为了保护安全装载所选用的材料；所选的货物运输装置；运输方式的路线。所以在装箱时需要注意安全装箱，在集装箱装箱之前需要对集装箱做准备的工作，外部检查：检查集装箱的结构承受能力；集装箱侧壁、底、顶状态良好，无严重损害；如果使用盖布，需要确保其质量，并要用绳子加以固定，绳子的质量也要有保证。内部检查：货物运输单元应保持干燥、干净、无残渣、无残留气味；货物运输单元应无重大损害，底板无损害，无诸如钉子、螺丝之类的突起物；货物运输单元要能耐风雨，若之前已有过修复，则更要检查集装箱有无漏缝。

注意问题

集装箱适于装运多种品类的货物，但不是所有的货物都能混合装载，如果装箱前没有根据货物的性质、特点、规格等加以合理挑选组合，运输过程就容易发生货运事故。为了确保集装箱货运质量，必须注意集装箱货物的合理装载和固定，集装箱货物的装载应满足以下的基本要求：重量的合理分配，装载时要使货物的重量在箱底上面形成均匀分布；货物的必要衬垫：装载货物时，要根据包装的强度来决定对其进行必要的衬垫；货物的合理固定：支撑，用方形木条等支柱使货物固定；塞紧，货物与集装箱侧壁之间用木条等；系紧，用绳索、带子等索具或网具等捆绑货物。

装箱的禁止事项：禁止将食物与有毒物体放在一起；装箱时，不要是整个货物单位的重心偏离中心；禁止将重件货物与易碎的货物放在一起，等。

装箱前的准备：1.在装载前要考虑货物运输单元是装载在拖车、卡车、支撑物、有轨车、驳船、还是海船之上。2.要确保装箱过程在平的、坚固的场地上或拖车上进行。

装箱后期的注意事项：确保集装箱干净、干燥、结构合理；确保所有货物已经经过检验，无损害；所有桶装货物应直立堆放等。

通过本学期所学的集装箱知识我认为集装箱的基础知识是最基本的也是必须要掌握的。也使我认知和理解集装箱运输与多式联运的基本理论和应用必要的技能方法，让我锻炼自己的分析能力和增强自己未来的就业竞争力相信本学期所学的知识在今后物流工作中一定能运用得上。

在此，我也感谢我的XXX老师这学期的悉心指导以及帮助过的我的同学。

第三篇：集装箱复习资料

名词解释：

空箱调运：空箱调运是指航运公司向海关进行申报从而进行箱体转移的一种操作，其根本原因在于货运需求与运力供给之间的不平衡。

近洋航线与远洋航线：近洋航线是指本国各港口至邻近国家港口间的海上运输航线的统称；远洋航线是指航程距离较远，船舶航行跨越大洋的运输航线。

公路运输生产率：是指所产出的运输产品数量与生产过程中所耗费的资源的数量之比。

铁路集装箱货运单证：铁路货物运单是铁路与托运人之间为完成货物运输而填制的具有运输合同性质的一种运送单据。

规模效益：所谓规模经济效益是指一定的生产规模与平均收益之间的关系。

简答题：

一、铁路集装箱节点站的主要功能和作用？

答：铁路集装箱节点站具有以下功能：

1、具有编发、接解成列集装箱的能力：

2、对周边地区集装箱运输具有较强的辐射作用，是区域内集装箱的集散中心；

3、具有很强的集装箱装卸储备能力和空箱调配能力；

4、设有功能齐全的集装箱检修、清洗设施；

5、具有办理国际集装箱运输的相关功能。铁路集装箱节点站具有以下作用：

1、是面向客户、受理集装箱托运交付作业的重要窗口之一。

2、是办理门到门运输中，铁路与公路集装箱运输的衔接点。

3、担当集装箱班列编组、解体功能，是集装箱车流的集结、产生、消失地；是集装箱运输相关信息发送、接收、交换处理中心；集装箱、车辆在此进出、停留，其位置、状态等信息应能及时、正确地得到反映。

4、是集装箱统计数据的来源地。

5、是集装箱维修场所。

6、是集装箱装卸作业的指挥、实施场所。

7、为客户及线路内其他环节提供集装箱信息。

二、影响集装箱船舶规模经济效益的因素？

答：

1、装箱运输的适箱货源

2、港口条件

3、航路条件

4、航程因素

5、装卸效率

三、国际多式联运应具备的条件？

答：

1、建立国际多式联运线路与集装箱货运站

2、建立国内外联运网点

3、制定多式联运单一费率

4、制定国际多式联运单据

5、建立科学的组织管理制度

四、国际集装箱多式联运的计费方式？

答：

1、按单一运费制计算运费。单一运费制是指集装箱从托运到交付，所有运输段均按照一个相同的运费率计算运费。

2、按分段运费制计算运费。分段运费制是指按照组成多式联运的各运辖区段，分别计算海运、陆运（铁路、汽车）、空运及港站等各项费用，然后合计为多式联运的全程运费，由多式联运经营人向货主一次计收。

五、多式联运单据的内容？

答：

1、货物名称、种类、件数、重量、尺寸、外表状况、包装形式；

2、集装箱箱号、箱型、数量、封志号；

3、危险货物、冷冻货物等特种货物应载明其特性、注意事项；

4、多式联运经营人名称和主营业所；

5、托运人名称；

6、多式联运单据表明的收货人；

7、接收货物的日期、地点；

8、交付货物的地点和约定的日期；

9、多式联运经营人或其授权人的签字及单据的签发日期、地点；

10、交接方式、运费的支付、约定的运达期限、货物中转地点；

11、在不违背我国有关法律、法规的前提下，双方同意列入的其他事项。

第四篇：集装箱买卖合同

集装箱买卖合同4篇

集装箱买卖合同1

合同编号：

签订日期：

签订地点：

经供方：需方：充分协商，签订本合同。

在执行中，任何一方不履行合同，应承担违约责任。

1.商品

品名规格单位数量单价金额备注

货款共计人民币(大写)：

2.商品质量：

3.作价办法：

4.交货时间：

5.包装要求及费用负担：

6.质量检验及验收方式：

7.结算方式：

8.运输办法：

9.供方违约责任：

(1)产品品种、规格、质量不符合规定，需方同意收货的，按质论价;需方不同意收货的，由供方负责处理，并承担因此造成的损失。

(2)未按合同规定的数量交货，而需方仍有需要的，应照数补交，按延期交货处理。完不成合同任务，不能交货的，应偿付需方应交货总值%的违约金。

(3)包装不符合规定，必须返修或重新包装，应承担支付的费用和损失;需方不要求返修或重新包装，要求赔偿损失的应予赔偿损失。

(4)未按合同规定时间交货，每延期交货一个月，应偿付需方以延期交货部分货款总额的违约金。

(5)不符合同规定的'产品，在需方代保管期内，应偿付需方实际支付的保管、保养费。

(6)产品错发到货地点或接货单位，除按合同规定负责运达到货地点或接货单位外，并承担因而多付的运杂费和造成延期交货的责任。

10.需方违约责任：

(1)变更产品品种、规格、质量或包装规格给供方造成损失时，应赔偿供方实际损失。

(2)中途无故退货，应偿付供方以退货部分货款总值%的违约金。

(3)自提产品未按规定日期提货，每延期一天，按照银行延期付款规定，偿付供方违约金。

(4)未按合同规定的验收办法和时间验收，应偿付供方因延期验收造成的损失;无故延期验收超过三个月即按中途退货处理。

(5)未按合同规定日期付款，每延期一天，按照银行延期付款规定偿付供方违约金。

(6)实行送货或代运的产品无故拒绝接货，应承担因此造成的损失和运输相关部门的罚金。

11.风险的承担

12.争议解决的办法

13.供需双方由于人力不可抗拒和非企业本身造成的原因而不能履行合同时，应当立即通知对方，经双方协商或合同管理机关查实证明，可免予承担经济责任。

14.上述条款如有未尽事宜，应以书面补充，作为附件。

有效日期自年月日起至年月日止。

供方：

代表：

地址：

电话：

开户银行：

帐号：需方：

代表：

地址：

电话：

开户银行：

帐号：

集装箱买卖合同2

出卖人： （以下简称甲方）

住所地：

买受人：（以下简称乙方）国家海洋局第一海洋研究所

住所地：山东省青岛市高科园仙霞岭路6号

甲、乙双方根据《中华人民共和国合同法》等有关法律规定，在平等、自愿的基础上，经充分协商，就乙方购买甲方集装箱达成以下买卖合同条款。

一、产品名称、型号、数量：1*40GP

二、产品质量

1、质量标准：符合国际海运过程中要求的各种标准，适用于正常存货。

2、乙方对产品质量的特殊要求：无

3、乙方对产品包装的特殊要求：无

三、产品价款

产品的单价：人民币2元

运费：人民币20xx元

总价：人民币24000

四、产品交付

甲方产品交付方式为：甲方送货

产品交付地点为甲方所在地，交货时间为合同生效后 7 天，若乙方对甲方产品有特殊要求的，甲方应当在乙方提供相关确认文件后 7 天内交货。但乙方未能按约定付款甲方有权拒绝交货，乙方未能及时提供相应文件的，甲方有权延期交货。

在合同约定期限内甲方违约未能及时交货的，产品的灭失、毁损的风险由甲方承担；产品交付后或乙方违约致使甲方拒绝交货、延期交货的，产品的.灭失、毁损的风险由乙方承担。

五、价款结算

乙方应在本合同书签订7 日内向甲方支付货款 24000 元，甲方在收到货款当日或次日须将集装箱安全及时送达乙方所在地。若因甲方延迟送货，由此给乙方产生不必要的损失，损失由甲方承担。

六、合同的解除与终止

双方协商一致的，可以终止合同的履行。一方根本性违约的，另一方有权解除合同，但应当及时书面通知到对方。

七、商业秘密

乙方在签订和履行本合同中知悉的甲方的全部信息（包括技术信息和经营信息等）均为甲方的商业秘密。

无论何种原因终止、解除本合同的，乙方同意对在签订和履行本合同中知悉的甲方的商业秘密承担保密义务。非经甲方书面同意或为履行本合同义务之需要，乙方不得使用、披露甲方的商业秘密。

八、不可抗力

因火灾、战争、罢工、自然灾害等不可抗力因素而致本合同不能履行的，双方终止合同的履行，各自的损失各自承担。不可抗力因素消失后，双方需要继续履行合同的，由双方另行协商。

因不可抗力终止合同履行的一方，应当于事件发生后 2 日内向对方提供有权部门出具的发生不可抗力事件的证明文件并及时通知对方。未履行通知义务而致损失扩大的，过错方应当承担赔偿责任。

十、其他约定事项

1、乙方联系人或授权代表在履行合同过程中对甲方所作的任何承诺、通知等，都对乙方具有约束力，具有不可撤销性。

2、签订或履行合同过程中，非经甲方书面同意或确认，乙方对甲方任何人员的个人借款，均不构成乙方对甲方的预付款或已付款款项。

3、乙方联系地址、电话等发生变化的，应当及时通知到甲方，在乙方通知到甲方前，甲方按本合同列明的联系方式无法与乙方联系的，由乙方承担相应的责任。

4、本合同未约定的事项，由双方另行签订补充协议，补充协议与本合同书具有同等法律效力。

5、乙方应当在签订合同时向甲方提供其合法经营的证明文件。

6、签订本合同时，双方确认的合同附件为本合同不可分割的组成部分，与本合同具有同，同等法律效力。

十一、争议解决

本合同履行过程中产生争议的，双方可协商解决。协商不成的，应向甲方所在地人民法院提起诉讼解决。

十二、明示条款：

甲、乙双方对本合同的条款已充分阅读，完全理解每一条款的真实意思表示，愿意签订并遵守本合同的全部约定。

十三、本合同经双方盖章或授权代表签字后生效。

十四、本合同书一式四份，双方各执二份。

集装箱买卖合同3

出卖人：（以下简称甲方）

住所地：

授权代表：

联系电话：

买受人：（以下简称乙方）

住所地：

授权代表：

联系电话：

甲、乙双方根据《_____》等有关法律规定，在平等、自愿的基础上，经充分协商，就乙方购买甲方集装箱达成以下买卖合同条款。

一、产品基本情况

产品名称：

型号：

数量：

二、产品质量

1、质量标准：符合国际海运过程中要求的各种标准，适用于正常存货。

2、乙方对产品质量的特殊要求：________________。

3、乙方对产品包装的特殊要求：_______________。

三、产品价款

产品的单价：人民币_______元。

运费：人民币___________元。

总价：人民币___________元。

四、产品交付

1、甲方产品交付方式为：甲方送货。

2、产品交付地点为：甲方所在地。

3、交货时间为：合同生效后7天。

4、若乙方对甲方产品有特殊要求的，甲方应当在乙方提供相关确认文件后7天内交货。但乙方未能按约定付款甲方有权拒绝交货，乙方未能及时提供相应文件的，甲方有权延期交货。

5、在合同约定期限内甲方违约未能及时交货的，产品的灭失、毁损的风险由甲方承担；产品交付后或乙方违约致使甲方拒绝交货、延期交货的，产品的灭失、毁损的风险由乙方承担。

五、价款结算

乙方应在本合同书签订7日内向甲方支付货款______元，甲方在收到货款当日或次日须将集装箱安全及时送达乙方所在地。若因甲方延迟送货，由此给乙方产生不必要的损失，损失由甲方承担。

六、合同的解除

双方协商一致的，可以终止合同的履行。一方根本性违约的，另一方有权解除合同，但应当及时书面通知到对方。

七、商业秘密

1、乙方在签订和履行本合同中知悉的甲方的全部信息（包括技术信息和经营信息等）均为甲方的商业秘密。

2、无论何种原因终止、解除本合同的，乙方同意对在签订和履行本合同中知悉的甲方的商业秘密承担保密义务。非经甲方书面同意或为履行本合同义务之需要，乙方不得使用、披露甲方的商业秘密。

八、不可抗力

因火灾、战争、_____、自然灾害等不可抗力因素而致本合同不能履行的，双方终止合同的履行，各自的损失各自承担。不可抗力因素消失后，双方需要继续履行合同的'，由双方另行协商。

因不可抗力终止合同履行的一方，应当于事件发生后2日内向对方提供有权部门出具的发生不可抗力事件的证明文件并及时通知对方。未履行通知义务而致损失扩大的，过错方应当承担赔偿责任。

九、违约

本合同签订后，任何一方违约，都应当承担违约金____________元。若违约金不足以弥补守约方损失的，违约方应当赔偿给守约方造成的一切损失（包括直接损失、可得利益损失及主张权利的费用等）。

十、争议解决

本合同履行过程中产生争议的，双方可协商解决。协商不成的，应向甲方所在地人民法院提起诉讼解决。

十一、本合同经双方盖章或授权代表签字后生效。

十二、本合同书一式____份，双方各执_____份。

甲方（盖章）：

授权代表（签字）：

_____年____月____日

乙方（盖章）：

授权代表（签字）：

_____年____月____日

集装箱买卖合同4

出卖人：__________

住所地：_______________

买受人：__________

住所地：_______________

甲、乙双方根据《中华人民共和国民法典》等有关法律规定，在平等、自愿的基础上，经充分协商，就乙方购买甲方集装箱达成以下买卖合同条款。

一、产品名称、型号、数量：_____________

二、产品质量

1、质量标准：符合国际海运过程中要求的各种标准，适用于正常存货。

2、乙方对产品质量的特殊要求：_______________

3、乙方对产品包装的特殊要求：_______________

三、产品价款

产品的单价：人民币________元

运费：人民币________________元

总价：人民币__________元

四、产品交付

甲方产品交付方式为：甲方送货

产品交付地点为甲方所在地，交货时间为合同生效后_____天，若乙方对甲方产品有特殊要求的，甲方应当在乙方提供相关确认文件后7天内交货。但乙方未能按约定付款甲方有权拒绝交货，乙方未能及时提供相应文件的，甲方有权延期交货。

在合同约定期限内甲方违约未能及时交货的，产品的灭失、毁损的`风险由甲方承担产品交付后或乙方违约致使甲方拒绝交货、延期交货的，产品的灭失、毁损的风险由乙方承担。

五、价款结算

乙方应在本合同书签订_______日内向甲方支付货款__________元，甲方在收到货款当日或次日须将集装箱安全及时送达乙方所在地。若因甲方延迟送货，由此给乙方产生不必要的损失，损失由甲方承担。

六、合同的解除与终止

双方协商一致的，可以终止合同的履行。一方根本性违约的，另一方有权解除合同，但应当及时书面通知到对方。

七、商业秘密

乙方在签订和履行本合同中知悉的甲方的全部信息均为甲方的商业秘密。

无论何种原因终止、解除本合同的，乙方同意对在签订和履行本合同中知悉的甲方的商业秘密承担保密义务。非经甲方书面同意或为履行本合同义务之需要，乙方不得使用、披露甲方的商业秘密。

八、不可抗力

因火灾、战争、罢工、自然灾害等不可抗力因素而致本合同不能履行的，双方终止合同的履行，各自的损失各自承担。不可抗力因素消失后，双方需要继续履行合同的，由双方另行协商。

因不可抗力终止合同履行的一方，应当于事件发生后___向对方提供有权部门出具的发生不可抗力事件的证明文件并及时通知对方。未履行通知义务而致损失扩大的，过错方应当承担赔偿责任。

十、其他约定事项

1、乙方联系人或授权代表在履行合同过程中对甲方所作的任何承诺、通知等，都对乙方具有约束力，具有不可撤销性。

2、签订或履行合同过程中，非经甲方书面同意或确认，乙方对甲方任何人员的个人借款，均不构成乙方对甲方的预付款或已付款款项。

3、乙方联系地址、电话等发生变化的，应当及时通知到甲方，在乙方通知到甲方前，甲方按本合同列明的联系方式无法与乙方联系的，由乙方承担相应的责任。

4、本合同未约定的事项，由双方另行签订补充协议，补充协议与本合同书具有同等法律效力。

5、乙方应当在签订合同时向甲方提供其合法经营的证明文件。

6、签订本合同时，双方确认的合同附件为本合同不可分割的组成部分，与本合同具有同，同等法律效力。

十一、争议解决

本合同履行过程中产生争议的，双方可协商解决。协商不成的，应向甲方所在地人民法院提起诉讼解决。

十二、明示条款：

甲、乙双方对本合同的条款已充分阅读，完全理解每一条款的真实意思表示，愿意签订并遵守本合同的全部约定。

十三、本合同经双方盖章或授权代表签字后生效。

十四、本合同书一式_____份，双方各执_____份。

甲方：__________乙方：__________

第五篇：集装箱翻译

班轮运输的船队规划和网络设计

摘要：班轮承运人面临的一个普遍的问题就是其服务网络设计。对于给定的待运输的货物需求及港口，承运人要利用已有资源，尽可能高效的为其船舶设计运输路线。而且，运输路线的利润，取决于运输货物所选择的路线。本论文构建一个整合模型，即混合整数线性规划模型来同时解决船队规划和路径选择问题。这个模型合并了相关约束（比如营运航线的周频率约束）和可能的中转情况（比如两个或两个以上运输路线上的货物中转）。为了解决这个混合整数规划，本文提出一些算法来探索问题的分离性。具体说有贪婪算法、遗传算法和两阶段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的船舶的闲置成本是每天2——2.5万美元，战略层面的决定是极为重要的。

在战术计划层面，需要进行航线设计以构建运输网络，也就是说，要考虑既定船队挂靠的码头和这些航线的船舶分配。船舶在整个计划范围内从一个港口到另一个港口循环运输。为了维护客户，为客户提供固定船期，大部分船舶一周至少挂靠一次其运输航线上的每个港口（e.g.a cycle）。这就需要在该循环上营运的船舶数量至少等于完成这个循环所需要的周数。有些循环，比如说连接亚洲和北美的航线可能需要八周才完成，这就意味着承运人需要至少八艘船舶来在这条航线上开辟新业务。承认人设计服务网络的问题可以归结为船队规划问题。

在营运计划层面，承运人需要决定接受或拒绝哪票货物、选择哪条航线运输承运的货物。这就是所说的货物路径选择问题。承运人可能选择不运输某些货物，或者因为它利润低或者因为别的港口有其他货物，而这票货更有利可赚。货物运输的开始是从内陆运输到装货港，从内陆由卡车、铁路或者水运运送到装货港的运输网络，被称为支线运输网络。然后货物从装货港运送到卸货港，中途也可能挂靠几个中间港。随后又利用支线运输网络，运送到内陆目的地。货物从装货港运送到卸货港中间挂靠的一些中间港有时候是进行水水换装的中转港。

一个层面上的决策也会影响另一个层面上的决策。战略层面的决策为战术和操作层面的决策提供政策和指导。同样，战术层面的决策为运营层面的决策提供能力限制和网络结构。反过来，有了这些决策的系统产生的成本收益的信息又为更高层次的决策提供了必要的反馈。

过去的几年里，航运业在采用新的决策系统方面一直是保守的。长期以来，都是有经验的决策者手工计划，而且，一般来说，船队规划涉及很多各种各样的问题。因此，对于有具体约束和目标的具体问题来说，大部分量身定制的模型是可用的。而且，大部分可用的文献也随着行业和不定期船运输的发展而发展（Christiansen, Fagerholt, and Ronen 2004）。由于模型和问题结构本身的不同，现存文献中也很难有比较性。

接下来，我们简单的回顾一下有关集装箱和班轮运输的一系列有代表性的文献。为了综合系统的回顾船队规划和路径选择方面的文献，我们推荐Romen1983年完成的论文、Ronen1982~1992年研究于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所花费的时间（天），考虑到时间方面的问题很重要,我们把船舶调度和货运路径问题看做一个带有空间网络约束的MCF问题。此外,我们把空间网络以天为单位，因为一般远洋航线在给定天无法到达一个港口。定义为一个带有变量集合V和边缘点集E的直接空间网络。对于，港口(v)表示一个港口，时间(v)表示一周中的星期。也就是说，对于每个港口，我们在V中制造了7个顶点。为了标记表示在给定的船队中船型为a的船舶数量。

方便起见，我们把顶点表示为：当

时，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的中转港。

航次边缘的长度港口v到港口u所需要的天数。当

等于船型a的船舶从时，le=1；当

时，le=0.一个线路可以承受的能力用TEU表示出来。一个港口的地面线路可能有有限的或者无限的能力，这取决于我们是否愿意给一个港口的货物数量加一个（操作量或存贮量）限制条件。航行线路上的能力取决于该航线上船舶的数量（和他们的能力）。

在船舶调度和货物路径上面需要注意到可变成本和固定成本的问题。其中的一些费用是由船舶引起的，其他是由货物引起的。对于

与港口相关的费用，我们用用，表示船型为a的船舶在v港的一次性费表示每TEU货物一天在v港的总费用。港口访问成本在不同港，体现了船型a的船口费用不同。类似的，当在航行时舶在路径e上的运营成本，当停泊时港停泊一昼夜的费用。对于货物来说，当e上每TEU货物在线路e上的船舶成本，当，体现了船型a的船舶在时，时，表示在线路表示表示每TEU货物在始发港(e)的仓储费用。虚拟线路相当于0费用。

我们要确保港口访问成本在每个港口只发生一次,即使这艘船进行了一夜停泊在港口的行为。为了正确考虑在访问时间扩大的网络下港口费用问题,我们在路面线路e产生的船舶费用

上减去船型a的港口访问费用。因此,如果一艘船一整夜呆在一个港口,那么尽管港口访问成本是由于节点增加成了两次费用,但是已经在路面线路的费用中扣除了。船舶在港空载的代价是过夜也同样会收停泊费。货物由于在非目的港滞留而增加其费用。在本文中,我们把星期中的每天作为时间离散化水平；因此,我们假设如果在港个不同航线的船舶同一天出现在港口,转运就可以发生在两个方向(例如,货物可从其中一船舶转移到另一船舶)。通过考虑更精细的离散化的时候,可以采取占较小的时间窗的一个港口,船只在见面并确定转运吧可能只在一个方向(不承担因此持续的费用)。

考虑到空间网络的离散化水平是以天为单位,一种商品在第i天到港o可以被描绘成一个供应网络上的顶点，我们假定供应在每一周的那一固定天出现在在顶点o(目的地d)。由于我们是在考虑一

个合理的模型，所以我们给出的供应在给定的某一天出现是合理的。由于承运人的需求是不变的,每周的服务水平也不会发生变化。为此,我们假设给定任何航次,每周频率、使用船型等都保持不变。我们描述港口船期表上的一个航线C,在该周期性循环的航线上访问的港口和时间是固定的,船型也是固定的,航次C每周运营需要的船队数量也是固定的。由于船舶的不可分割性，Lc定义取整。当满足预定规则的船只数量、周期频率以及访问港口时，我们认为这是一个周期。我们把这一系列基于船型a的可行的航线集合定义为对于一个cycle 点来代表一个cycle C；对于并且1.1数学模型

对于船队规划和货物路径选择问题，我们提出了一个整数规划的理论公式。这个公式有两套变量。首先,对于任意可行cycle C我们定义其为Xc。当cycle C 能够保持每周的循环频率，Xc = 1；否则Xc=0.变量Xc是一个二进制,这是因为在同一个星期相同类型的两艘船从一个港口沿着相同的港口调用几乎是不可能的。

接下来，我们定义将线路的流量定义为一个负连续变量，对于每个线路

和每个triplet ,我们定义在。从数学上来说，,必要时我们用一组

中C的航线费用由COSTc表示，线路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）要求每支船队的类型，我们使用的船舶都不会闲置。注意如果航线C∈ψn被选择，就表明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为整数，对i∈N，总有N子集S满足：。

定理1：同时调度船舶和货运航线属于NP完全问题。

证明：假设W条同样的船舶，载重均为TTEUs。构建如下的海运网络，对i∈{1,2,…,n}，假设有2个港口，其需求分别为di和CiTEUs，起始港为Oi。让船队中的船舶承担从Oi港到di港Wi/2周期的运输。假设港口之间距离相同，对γ1≤i≠j≤n，Oi与dj的距离无穷大。这样，wi的船舶必须维持CI的周班航行即Ci=oi-di-oi，1≤i≤n，所有其他航线均不可行。另T=maxi∈N Ci，满足任何o-d组的单位需求收益为1。假设不包括运营成本。

结果：所有可行的航线都是非连接的。航线Ci需要Wi条船舶维持周班，形成Ci单位收益。

如果集合SСN，用于运营，成。

当给定一组既定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)无限制，γv∈V，γ(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）每条边e∈Ea承担Ce=Cesia+λe,每个点，v∈Va承担成本Ce=Cesia。对每种船型，算法寻求附加网络中最小成本的航线。步骤的细节在第3节介绍。最后，如果可行，最小成本的航线和船舶数量的满意值将被选择以维持周班的频率。步骤会重复到船舶被分配完成。2.2基于列生产的算法

尽管贪婪算法简单，能快速提供可行解，但并不是有效解。它是可行航线的小范围解集，一旦可行航线形成，它将在最终解中出现，不再考虑。接下来，我们引入基于列生成算法，为解决线性规划的可行航线集合。

列生成算法是一种解决线性规划的有效方法。比起列举所有显示的列，它从解一个用一组可选的列来解决有约束的问题。子问题用形成一系列有效的列来求解，它们随后被增加到子问题中。生产列方法已经成功运用到许多大型优化问题中，请看（Barnhart 1944）求解航线人员分配任务的问题。

为解决SSSCR的LP松弛问题，在生产列中的主要问题被生成，通过对于每个需求变量的来限制航线选择变量。在生产列的步骤中，通过寻求每个决策变量的最优值用来解决此主要问题。定价问题在生产列中等同于在辅助网络中为每艘船型确定负成本周期。辅助网络Ga=(Va,Ea)作为每条船型a使得Va=V,Ea=Eav U Eag。主要问题的双变

量值被用来分担辅助网络中边和点得成本。每条边e∈Ea,分担成本Ce=Cesia+Taλe+(le/7)，每个点v∈Va分担成本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）：因此

(14)

(15)(13)无约束，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=EDq∪Egq，我们接着表示我们将如何在网络Ga的节点和边上计算成本。

让∏（λ，ω）和σa分别表示对应约束（20）和（21）的对偶变量，循环C所节省的成本

公式如下：

上式中第二个求和为C循环的边缘航次。由于通过加入松弛条件，陆地边界的能力很大。因此，陆地边界可以算入上述公式中的求和。LP理论中，我们知道如果每个且每个船队类型迭代至对于某些的节省成本

并，那么我们就获得了最优解。也就是说，列生成存在一个循环

使得

对于我网络每个，我们假设：，对于每个边界

。当我们用替果对于中的时，我们假设成本为

。考虑到

成本为

代，如来说成本的最有定价都大于0，那么我们需要检查是否存在。如果存在，那我们就建立了一个盈利的循环，如果不存在，或者没有更盈利的循环，或者可盈利的循环只有非常低的负成本（>-1）以至于可以忽略。我们使用程序负成本循环。

来定义在种的3 算法问题

在这部分我们将讨论有关于改进我们的算法是之更有效、可靠的几个问题。

3.1 解决定价子问题

定价子问题对于列生成以及Benders分解算法都适用，降低了辅助网络中可盈利网络的识别。相似的，在贪婪算法中也需要寻找

中的最小成本循辅助网络中的可盈利网络。这试图直接解决网络环问题。然而，将由循环问题的求解结果得到的循环分解转化成简单 的循环，并不是实用的。比如，我们最初循环问题的计算结果表明这种方式下大部分的循环，太长，需要大量船舶才能保证班轮的频率。因此，首先我们讨论班轮公司的实际原则，以确定循环是可行的。接着，迭代算法，程序Find Cycle（G）用来求得负的成本循环的有效性，保证在一个给定网络既定的可行性条件。

3.1.1 定义可行航线

为了解决定价子问题的最优化，必须要将所有的港口序列看做是可能盈利的航线。然而，在无约束方式下负面成本航线的搜索，它通过生产能够产生不良影响的航线，例如大的整数差距，而不仅仅是使算法更低效率，而且它产生的航线在实际中永远都不可能实现。因此我们设定一个约束，那就是一条航线必须满足可行性。

全球承运人分布在不同地区，例如，东方海外货柜航运公司主要经营北美、欧洲和亚洲市场，以及迎合不同市场的需求，例如跨大西洋、跨太平洋、亚洲内部，和亚欧贸易航线。图表5显示了OOCL公司的一条亚欧航线。对于一个承运人来说，同时开发跨区间间和区域内市场很重要，然而有些跨区间间市场，例如，跨太平洋航线就是最有利可图的航线。有些内部区域市场，例如，环亚洲市场，形成了国际海运的骨干。

我们把OOCL和APL在2005年公布出来的跨太平洋和环亚洲贸易航线当做是定义分布在两个区域可行航线的指南，记为ri和rj 1 航线上所挂靠的港口的数量不能太多。当前在跨太平洋航线上大部分挂靠10到15个港口，而在环亚洲航线上挂靠7到10个港口。用R

（ri，rj）表示区域ri和rj之间允许挂靠港口数量的最大值。航线的周期长度必须是一个恰当的数值；也就是说一个具体航线里的船舶数量是有限制的。大多数的环太平洋航线周期长达15个周，大多数的亚洲航线周期长达6个周。设L ri rj是围绕ri和rj航区内航行所需的最长时间。在多个地区航行的航线，每个航区只能进出一次；也就是说，在地区之间的循环是不允许的。然而，1-2个内部的循环是可以的。每个航线在起始港和目的港之间直接有货物需求。没有货物需求的航线是完全不建议采纳的。

3.1.2 寻找负成本航线

导致航线的可行性转化为循环问题的约束条件合并即简化为NP-hard问题。此外，按照上述规则计算的航线数目退化为大量的航线数目。对于分布在两个地区的港口来说，对于有30个货物需求，10个港口分布的地区，有多达10000条航线；对于有50个货物需求问题，15个港口的地区，有多达10万条航线；对于有80个货物需求，20个港口的地区，有多达100万条航线。

我们描述用于寻找放弃好的计算结果的不好的航线的迭代算法。本质上，这个算法利用了Lemma(1)，通过忽略路径中的正的成本来修理搜索树。这种整理有助于算法保持时间和空间上的有效性。Ahuja, Orlin, and Sharma通过使用Lemma(1)来开发一个简单的算法来检测分散的不好的航线。

我们现在为分布在r1和r2区域里的港口提出一个循环算法。请注意，这些观点可以被容易的用于有港口分布的两个以上的地区。在介绍算法之前，我们先定义一些符号。对于每个直航的航线P，由以下条件约束：head p和tail p分别代表航线p的最后一个节点和第一个节点。Cost p代表p航线的成本。NRr1 p和NRr2 p 分别代表从r1区域到r2区域的港口数目，ER p代表地区内线路的数量，1p代表路径p的长度。航线网络的每个边界是相同区域的两个节点之间或者是不同区域的两个节点之间，集合 NRr1 p NRr2 p ER p 完全代表路径P到达的地区。对于路径p，我们令集合head p tail p ER p 为D Set p.如果D Set p = D Set q 并且 Cost p < Cost q 我们则认为航线p 支配航线q。

通过连接一个路径的终点我们可以获得一个循环。Lemma(1)表明发现消极成本循环已足够考虑路径的消极成本。进一步来说，上述定义表明在具有相同D Set航线之间只有最低成本的航线需要进一步探索。如果航线p具有消极成本并且该航线可以扩展为可行的循环，那么这个航线可行。Pk代表不具有统治地位的集合，有k个节点的可行的路径。

对于每个船型a来说，算法（2）来检测辅助网络中由各种成本构成的负成本航线。算法（2）通过构造从Pk到 Pk+1的集合来实现。对于每一个包含于Pk的路径p来说，如果增加一个线路构成路径p‘，那么p‘也是可行的。根据3.1.1中的要求，程序if_feasible_path(p)通过检测路径p所到达的地区，以及对于一个船型a来说所有航行的周期都不会超过Na周，来确定路径p的可行性。通过使用程序if _dominated(p’, Pk+1)来检测路径的优势，并且如果是不具有优势的路径就被添加到Pk+1。对于航线C来说，使用程序if_fessible_cycle 来检测航线C是否可行。

对于一个路径p来说，时间范围限定在O（1）中。例如，对于EP（p’），我们假设所有地区内的线路为0以及地区之间的线路为1.因此当属于PK的路径p增加一个线路变为属于PK+1的路径时，EP（p’）可以通过在EP（p）中增加新增线路的值获得。因为我们保有所有路径所访问地区的信息，所以路径和航线的可行性检测可以再一个常量时间内完成。为了检测属于PK的路径p的优势，我们首先应该检查一下是否存在属于PK的路径q使得D Set(p)=D Set(q)。我们使用散列技术标准来有效地检测具有相同D Set的路径。一旦发现这样的路径，O(1)时间限制的优势就凸显出来了。注意到，在所给的任意时间内，集合PK就只有一个具有特殊D Set值得路径，即没有统治航线。算法（2）通过预先确定最佳航线的数目来修定，而不是保存最消极的航线C*。

3.2 选定份额的初始集

尽管Benders分解算法（1）的初始集可能取极限值空集，初始集的选择会影响它的收敛。我们的实验中，增加几个份额会提高算法（1）的可靠性。

是可行的，但是不是DP的极端解决点。可用来获得固定份额

上述公式等同于增加了约束条件，最优解一定会减少或者等于所有需求-所有航次费用所获得的收益。

相类似

是DP 的可行解。

算法（2）一个检测消极航线的有约束的迭代算法： 寻找航线的程序（Ga）

3.3 列生成效率

当生成列队时，对于纯列队生成的算法—SSSCR和用于解决RLPBMP的Benders分解算法，我们在每次迭代时增加多于一个有利列。在算法的迭代循环中，我们在基本没有额外费用的情况下保有一个5-10收益最佳航线的集合，而不是保有最消极的航线。这有利的减少了算法中列生成的迭代次数而不增加每次迭代的时间。

在一个典型的列队生成中，由于主要问题的列一直增加而导致问题一直增多。为保持列队数量的控制，我们经常的删除那些成本降低很消极的非基本的列。这些明显的减少了每个算法的时间，尽管在一些情况下这样稍微增加了算法的数量。另一种方式是加快列队生成进程，如果在一个船型的算法里没有删除新的航次，那么这个船型的列队就要运行2-5个算法。

4计算试验

在这个部分，我们将展示我们计算的生成试验的模型的结果。首先我们在贪婪启发式算法和列队启发式算法的基础上建立了Benders分解算法。接着我们深入分析了该算法。最后，我们讨论了通过我们的算法所获得的解决方法中的有趣的趋势，结果显示符合近来在海运货物运输行业的趋势。我们所有的算法都是在Unix环境下使用C++实现的，并且我们广泛使用了CPLEX9.0。所有的计算实验都是在Sun280R工作站用UltraSparc-III处理器完成。所用的报告时间以分钟计。4.1数据生成

我们在港口分布的两个地区的网络上模拟我们的计算机实验。区域内的港口任意的以相等的概率分布在任意一个地区中，并且在港口间的航行距离代表着亚洲和北美两地分布的港口之间的距离。我们以OOCL（2005）和APL（2005）的服务航线可知亚洲到北美俩个航区内的航行时间大约为2-30天，而航区之间的航行时间大约为14到42天。

起始港-目的港，港口对可以自由的从港口群中进行选择。在起始港的货源的生成日假定为每个星期的同一天，自由的从一个星期7天中进行选择。需求大小可以是可用最大船舶容量的0.1到1.0倍之间的任何一个数。Fagerholt（1999）使用了相似的比例，用这个比例代表班轮船公司的需求大小。为满足需求而产生的收入, 通过一个给定的需求三维模型（0,d,i）与港口o和港口d之间的距离成正比；也就是说，为满足亚洲港口对北美港口的需求而获得的收入与为满足北美地区两个港口之间所产生的需求而获得的收入相比更多。比例系数

通常在[100,200]之间选择。

因为承运人的船队通常是由不同船型的船舶构成，我们假设我们的船队由三种不同船型构成。这三种船型载箱量分别为2,000TEU，4,000TEU和8,000TEU。Bendall 和 Stent(1999)以及Imai 等(2006)建议当前使用载箱量为2,000TEU和4,000TEU的船舶。根据OOCL（2005），OOCL拥有载箱量从2,500TEU到9,063TEU的各种船型的船舶。近来年，关于更大船型的可能性研究越来越多，这些著作指出大型船舶的使用在增长，Bendall 和 Stent(1999)提出大于8,000TEU载箱量的船舶正在设计中。

海运货物的成本包括固定成本和可变成本。在Christiansen 和 Nygreen（1998）中，我们不考虑每天营运成本，包括资本成本，船员费用，保险等。因为这些费用是计划期内的固定成本。然而，我们认为各种各样的操作费用影响承运人的关于挂靠那个港口以及运营什么航线的决策。对于每个船型来说，对于所有的港口来说，我们假设船型a的船舶在港口v作业就会产生港口使费。在港口p, 港口使费按照船舶吨位的比例征收；也就是说，一个载重量为8,000TEU的船舶要比载重量为2,000TEU的船舶港口使费更高。

在每一个港口，我们假定每天每单位货物的存储费用。这个费用的产生是因为单位货物在港口停留一天所导致的，并且假定对于所有类型的货物取相同的值。在一个港口，货物每单元的存储费用与船舶到港使费相比小很多。对于每个船型，和每对港口来说，{u,v}, 我们假定船舶从港口u到港口v的操作费用。这个费用的

确定依据航行的船型和港口之间的距离的比例来确定。

利用上述模型，我们通过定义不同距离的等级来确定算法的鲁棒性。等级通过确定港口（p）的数量，船舶数量(s), 和货物需求（D）来规定。以6个港口，30艘船和18个货物需求为例，将这描述为P6S30D18。我们在网络上用6,10,15和20个被服务港口来检测我们的算法。在每个检测级别中，20%到30%的港口对被认为是成对的起始和目的港。计划使得船队规模达到100艘船。Grand Alliance世界上最大的联盟，拥有船数达到100艘船的船队。APL（2005）拥有超过80条集装箱船的船队。对于每个测试的等级，这部分所得到的结果可以通过随机生成5个例子然后取平均值来获得。

我们使用以下缩写并以表格的形式展示我们计算所得的结果： G：代表贪婪算法

C: 代表基于算法所产生的纯序列

B： 双向Benders分解算法，在这里生成列被用于解决I的主要问题。

F：循环生成算法是基于循环问题的流量分解的 I：循环生成算法的基础是迭代搜索算法

上述这些的结合被用来作为整个算法的测试。例如，循环生成的两阶段基于Bender分解算法和迭代搜索算法用BI来表示。4.2 算法的有效性

我们将基于Benders分解的算法与所提出的其他算法进行比较。当用纯列生成算法解决问题时，LP松弛变量首先达到最、最优，同时

也通过分支定界法求得整数解。然而，当用两阶段的基于Benders分解的算法时，在第一阶段，当由Benders松弛主问题提供的上界与子问题提供的下界之间的差异小于1%或者第一阶段benders的迭代次数小于200时，才会产生分支。当其中一个准则实现时第一阶段就会终止。由纯列生成算法得到的线性规划的解被用来作为上界来估计最终的整数解的质量。

表1显示了贪婪算法、纯列生成算法、Benders分解算法之间的比较。它也对基于流量分解的循环生成算法以及迭代搜索算法在循环生成方面进行了比较。表1的第2和第三列表示了所生成的周期的数和采用迭代搜索算法的贪婪算法进行计算所花费的CPU的时间。第四和第五列表示的是迭代循环生成的纯列生成算法的统计信息。接下来的四列分别表示了Bender分解算法以及F算法和I算法的相应的统计特征。最后三列分别表示了GI和BI算法，CI和BI算法，BF和BI算法所得到的值的相对偏差之间的差距。3.2节中所的描述的最初的分支被用在了Benders分解算法中。同时，成本降低少于1000000的列在每10次迭代后被删除，在算法C的列生成阶段以及算法B的第一阶段求解主问题时。正如2.3.2小节末所讨论的，我们必须关注Benders分解算法的第二阶段的混整数规划问题的终止条件的设定。在我们的计算试验中，当在小样本情况下达到1%的最优差距以及在大样本情况下达到3%-5% 的差距并在计算时间和计算质量之间实现一种很好的平衡时停止MIP。这些参数是在最初的计算实验结束后进行设定的。具体的，在6个港口的情况下，当最优差距从1%降低到0.1%时，方案的质量仅仅提

高了0.04%，但是计算时间却增加了55%。因此我们相信，如果最优差距选择的适当，过早的终止Benders算法对于启发式的解决MIPs并没有明显的影响。同时，在我们的计算中，当采用上述的最优差距作为结束准则时，由MIP得到的上界永远不小于Benders的下界。对于CI、BF和BI算法，循环的列上的数字表示了证书规划中的循环的次数。值得注意的是，在列生成的过程中产生了大量的循环，当解决线性规划问题时，但是如果他们对于降低成本有极大地负面影响则他们会被删除。

我们测验的结果显示贪婪算法与其他两个算法所得到的方案的质量有非常明显的差异。尽管贪婪算法的速度很快，它适用于非常小的周期集并且他挑选他所产生的周期不需要任何进一步的考虑。纯列生成算法所产生的方案的质量与Benders分解算法所产生的方案的质量差不多。然而，它花费了比较长的计算时间，而且随着问题规模的增加这种差异也会增加。尽管传递到纯列算法中的整数规划中的循环的数量不是很高，与BI算法的第一阶段结束时的循环的数量相比，但是计算的时间非常大。这可以归结于随着问题的规模的增大，列生成算法的变量的数量和约束条件的数量也增加。然而，在Benders分解

算法中，问题规模增大的影响被分布在主问题和子问题。

尽管BI算法要优于BF算法，但是这些算法所得到的方案质量之间的差异小于6%，然而，BF算法所花费的时间要比BI算法所花费的时间多4至5倍。这可以归结于在BF算法中，在解决循环问题时产生了许多不可行的问题并且在Benders分解算法的第一阶段中分解了它的流量。对于一个6-10个港口的问题，BF算法的第一阶段产生了65%的不可行的循环。尽管在第一阶段结束的时候产生了更多的循环，分支定界所花费的时间远少于CI算法中分支定界所花费的时间，因为BF算法所产生的大部分循环对于整数规划来讲是不可行的，并且在分支定界的一开始就被删除了。此外，在CI算法中，大部分的时间被花费在解决线性规划的松弛问题通过列生成。

表1给出了多达10个港口存在的情况下的测试结果因为纯列生成算法以及易于流量分解的循环生成算法的计算非常昂贵，使得CI和BF变得无效。同时，贪婪算法的方案质量更加降低，与Benders分解算法相比。表1 建立了方案的优越性，从CPU时间以及所产生的收益，又两阶段的Benders分解算法与迭代循环算法所得到的。因此我们用这种算法来完成所有的接下来的实验。4.3 基于Benders分解的算法的分析

接下来所进行的实验对于基于Benders分解的算法进行了深度的分析。结果如表2所示。在这些试验中，我们应用来最初的分支并且在Benders分解算法的第一阶段每进行10次迭代我们即将那些对于降低成本具有显著负作用的列移除。表2中的第二列代表了Benders算法 的第一阶段所进行的迭代的次数。第3、4、5列代表的是在解决LPBMP过程中的不同结算所花费的时间。第6列表示的是为了得到整数解而花费的额外时间。最后一列表示的是由CI算法所得到的上界与BI算法所得到的整数方案值的相对偏差之间的差距。为了使计算时间在控制之内，在第二阶段只进行了2~3次迭代。

表2显示，随着需求数量的增加所需要的计算时间也增加，这主要是因为每一个需求线代表是一个不同的商品；因此，随着需求三重线数量的增加，多商品流量问题或者子问题的复杂性会明显增加。值得注意的是，需求数量的增加会导致解决主问题所需要的时间的增加。这主要是因为增加了所产生的循环的可能性。随着港口数量或者船舶数量或者需求的增加总的计算时间也增加。

对于相同数量的港口，随着船舶数量的增加，差距显著减少，这表明，在第一阶段所产生的循环的次数的设定对于第二阶段是有益 的，而且给定足够数量的船舶，差距可以进一步减少。对于6个港口的小规模的测试，我们发现通过我们的算法得到的整数解与许多案例中的最优解很接近，并且基于线性规划的所得出的上界不是很紧。很容易发现，完整性差距非常大。考虑一种两个港口一条船的情况，船舶在两个港口之间的航行时间为一周。一种线性规划的方案是每一边分配半条船，但是整数解就会出现 零利润，就会产生100%的完整性差距。然而，给定足够数量的船舶则上述极端的情况就很难会出现。

接下来我们所设定的实验研究了使用3.2和3.3节中所描述的改进的影响。使用两阶段方法我们解决每一个实例，首先不考虑初始的分支，也不移除迭代时所产生的列，最后通过合并最初的分支并且移除迭代过程中产生的列，只保留一个子集。选择参数以使方案的质量不受这些refinements的影响。然而，计算时间明显减少了。表3表示了循环的产生、迭代的进行一级每一个案例所花费的时间。同时也显示了找到一个整数解所需要的总的CPU时间。

表3显示了多达10个港口的网络的结果，因为在Benders算法中的两个阶段所花费的时间变得非常的高当网络的港口数量大于10个时，如果我们删除最初的分支或者不移除对降低成本所产生明显负作用的列。值得注意的是移除那些对于降低成本少于1000000的列对六个港口的情况来说并不会显著减少循环的次数，因为对于这样一个小的网络来讲，不是许多循环都对降低成本具有负作用。然而，相同的改进减少了10个港口情况下约一半的循环的次数，这表明这种改进必须根据问题的规模进行调整以适当地控制线性规划中的列的数量。

表3中显示了在Benders分解算法中的第一阶段的CPU时间和迭代的次数通过引入最初的分支而减少。然而，时间上的更显著的减少是通过移除那些对于降低成本具有明显负作用的列而实现的。移除对降低成本有明显负作用的列对于第一阶段所花费的时间的减少并没有显著的影响，但是第二阶段整数规划所使用的列明显减少了，因此第二阶段所使用的时间明显减少了。

最后，我们研究了在一个船队中只有一个船型时对方案质量的影响。表4显示了一个具有特定船舶的船队，船舶的大小为4000TEU。对于每一个要测试的类别，我，给出了Benders算法第一阶段和第二阶段所使用的时间，以及所产生的循环的总数，和最有差距。在这个案例中，算法的第二阶段也进行了2至3次迭代。

表4显示在所有的测试中如果所有的船只都是相同的,最优的差距进一步减少。因为所以的船只都是相同的，在第二阶段使用船舶服务航线类似保持每周一次的频率变得更容易操作。表2对比表4显示花费的时间也减少了。花费在每一代循环过程的时间减少的非常明显，因为现在只需要解决一种类型的船舶循环在每次迭代的时候。因此，用在主要问题上的时间减少了。而且产生了更少的循环。因而花费在第二阶段的时间明显降低了。结果就是，整体时间减少了。4.4 分析解决问题

在本节中,我们仔细研究解决Benders decomposition-based算法和它的含意。同时,我们进行初步实验来探讨影响货物运送的成本。

表5中的第二列报告周期或服务路线的编号，在挑选最终的解决方案。服务路线的数量随著船只和港口的数量增加。接下来的两列在表5报告平均百分比的能力，在网络的边缘利用和转运货物的百分比。这些是我们不考虑转运成本的情况，也就是说,当成本的转运是0，边缘上的产能利用率计算是，边缘的总流量除以总容量的边缘。记录那些定义为边缘船舶的数量或容量。通过我们的这些问题，我们的算法不断地指出高达平均比例(70%--90%)容量利用率。也指出服务路线的数量越多，可能的货物路线的数量就越多。因此,转运货物的百分比随着问题规模增长而增长。这种趋势通过我们的计算研究观察到的，转运货物数量增对于6个港口问题的19% 增加到对于10个港口问题的30%.接下来,我们执行初步的实验研究转运成本对货物路线的影响。根据所选择的服务路线，我们构建了一个新的网络。在新的网络，每一个港口，其中两个或两个以上的周期达到一个新的节点构造每一个周期。新节点通过边缘连接到原来的港口节点。这些充当加载/卸载的边缘，并有相应的与之相关的成本。例如，在图3为代表的网络，由图6给出了新的网络。在港口p，cpu和cpi分别代表装载和卸载的成

本，运送成本就是cpu+cpi。因此，转运发生在中间的港口货物卸载和再装载。在图6中，货物通过c港的转运从b港口运送到d港口。他使用了卸载边缘从周期c1到港口c，和装载边缘从c港到周期c2.为了进行试验，我们构建新的网络选择在年底的第二阶段的基于Benders分解算法的周期。货物运送的问题是为新的和旧的网络共同解决的。货物转运成本对货物路线决策的影响是通过观察满足在原有网络的需求（在转运成本的情况下）和新的网络需求（在场的转运费用）之间的百分比差异。我们还计算的总发运的货物中转运货物的百分比。这两个统计在表5表示为三个不同的场景：转运成本=20个单位，每单位的货物；转运成本=100单位每单位货物和转运成本=1 000个单位每单位货物。回想一下在港口的持有成本，选择从随机<110和选择满足需求所产生的收入是成正比的出发和目的港口之间的距离（比例常数被随机选择100 <200）。请注意，如选择港口之间的距离从2-42天，产生的收入从200-8 000选择。因此，第一个场景代表的是转运成本低，相当于在港口的持有成本。第三种情况代表的是当转运成本是非常高，相当于满足需求所产生的收入。如此高的转运费用是极不可能;然而，我们讨论这种情况下，提出一个极端的例子。

我们的计算产生的是在当转运的成本是在一个港口的持有成本，或满足需求所产生的收入比较低，在这两个网络的路线决策是类似的。然而，随着转运成本增加，路线决策也改变。具体来说，随着转运成本从20个单元增加到1000单元，满足需求的量也从0％增加到36％。我们注意到，随着转运变得越来越昂贵，货物转运的百分比下

降。发生异常的比例在第一行的最后一栏表5转运货物从12.84％提高到15.17％时的转运成本从100个单位增加到1000个单位。这是因为随着转运成本的增加，不仅转运减少，在许多情况下，满足的需求也减少因为路线的选择被限制。因此，最后一列的分子以及分母减小。P6S186在类的实例，分母减小速度比分子快，因为这一类的实例我们很少与需求对，一般很小选择周期。

5结束语和未来的研究

在本文中,我们提出了一种新的数学模型来研究在班轮运输中船舶调度以及集装箱货运船运输路径问题。该模型抓住了运输公司面临的每周频率约束的重要性和给出了转运货物的好处。这模型结构容易分解，因此这个模型有高效率的算法。船的有效航线船选择了一篇专栏文章中设置一个迭代搜索算法（iterative search algorithm）。最后, 通过各种测试提出了解决方法。考虑到初步试验结果，我们相信,这个解决方法可以帮助规划者为一支舰队的100的船只开发出更好的路线。设计者们加入他们的预定服务航线的模型，就好像设置一组初始周期。通过解决过程中的一部分获得解决方法。这是一个用户的,而不是一个计算机给出的解决方案。在最后的解决方案中我们的结果显示船容量的高比率的利用率和转运中大量有效的数据。

我们的目标是本文提出一个船舶调度和货运航线一个基本框架。所提出的模型和求解策略的方法可以从不同的方式提高。

其次,提出了今后的研究方向。该模型提出货物的转运是从一艘

船到另一个艘船。最后在4.4我们提出了货物航线中的转运成本。然而,该模型不需要考虑转运费用同时设计路线。需要进一步的研究来扩展或者修改模型包括转运成本。这方面的将增加模型的复杂性解决程序明显需要提高。

在本文中,我们只研究一个船舶类型来维持服务的航线上的每周频率。这样提供了在每周里节点上船舶的相同容量，当承运人每周面临同样的需求这样做有用的。然而，这样是不可能的，因为需求结构在每周都是不一样的。进一步的研究必须允许在服务航线上有多种船型。需求每一周到每一周变化的合并将会扩大这个计划的边界。然后，在模型中多船类型的循环需要改变。

从解决的方法来看in the pure column generation algorithm and the Benders decomposition-based algorithm（算法）,没有新的阶来解决整数规划。New columns可以由编程求解整数规划分支和价格（branch-and-price）的框架。Branch-and-price的结构框架有可以改进解决方案程序的质量。然而,有很多重要的富有挑战性的课题必须解决，而发展一个成功的branch-and-price算法是必要的。具体地说, 一个好的branch规则需要被设计。标准分支周期或者创造一个沿着分支（branch）的变量被设定为零.x C=0意味着c周期将要被排除。然而,它是可能的,下次解决定价问题是有利可图的，当然在这个分支周期,最理想的方案正是周期C。因此第二个最好的循环被考虑是必要的。此外,在深度或者是在ranchand-price树可能需要构建最好的周期。注意,一个成功的branch-andprice算法问题,需要定价

问题被非常有效的解决。就好像这个问题经常被提到一样。明确排除特定周期的定价问题中计算量大的缺陷。因为商业软件如CPLEX數学所做不到处理branch-and-price框架问题、给管理搜索树有效实施带来了许多挑战,如决定哪一个节点分支上,搜索技术(例如,第一次宽度搜索,深度优先搜索等等)。