不规则背包问题仿真开题报告

1. 研究目的与意义（文献综述）

1.1本课题的目的

集装箱运输作为海上运输的主要方式之一，是以集装箱为载体，将货物集合组装成集装单元，在流通领域里完成模块化移动的运输方式。由于集装箱是高度标准化的，所以集装箱运输具有装卸效率高，工人劳动强度低，保证货物运输安全与质量，节省包装费用，降低运输成本，适于不同运输方式之间的联合运输等优势，现已成为世界各国保证国际贸易的最优运输方式。

根据世界航运理事会的数据，现今国际海运贸易总价值的52%是通过集装箱来运输的。2013年，世界集装箱港口的吞吐量达到了6.51亿标准箱（20英尺集装箱），同比增长了5.58%，2012同比增长4.97%，而在2011是8.63%。在2013年，世界排名前20的港口的年吞吐量达到2.99亿标准箱，占世界总量的46%。对于集装化的贸易，全球集装箱贸易量在2006年至2013年间，平均每年增长7.9%，在2013年就增长了1990万标准箱。数据表明，2004年1月时平均每艘集装箱船装载2259个标准箱，在2009年1月达到平均每艘船3161个，而到2014年1月这一数据达到4449个标准箱。现在，世界上最大的集装箱船能够装载19224个标准箱[17]。

集装箱船舶的大型化，提高了船舶运输能力与营运效率，但同时也延长了船舶靠港装卸停滞时间，集装箱船舶大约60%时间停泊在港口，每艘船舶在港口每小时的停泊费用约为1000美元，所以减少大型船舶在港停留时间，提高船舶装卸船效率，是近年来世界港口集装箱码头研究的重大课题，由于在远洋航行路程上集装箱船多能保证适合的航行速度，因此在整个航运周期中，靠港停泊时间长短对于集装箱船运输效率有决定性的影响。

2. 研究的基本内容与方案

2.1研究的基本内容

集装箱贝内配载问题实际上是将集装箱放进船舶的箱位，不过在装载时需要考虑集装箱放置的位置，还有其对船舶的影响。

背包问题是组合优化问题，是指给定一组物品，这些物品都具备体积和质量还有价值，先需要将物品装到一个背包里面，背包的容量和承受的重量有限，在满足其他约束的情况下，怎么使所装物品的价值和最大。

多背包问题（multipleknapsack problem，mkp)是指在一个物品集合{1，2,…，n}中选出一个子集分别装人m 个背包中，m = {l, 2,…，m}，在不超出每个包的限制容量)的条件下，使选出的全部物品的总价值最大。

3. 研究计划与安排

第1-4周：查阅参考文献、资料；外文文献翻译；调研需求；撰写开题报告；

第5-8周：建立问题的数学描述，构建数学模型，并把算法翻译为程序，在算法的层面基本保证正确性；

第9-11周：建立仿真模型，并将算法移植到模型中，设计算例验证算法的有效性；

4. 参考文献（12篇以上）

[1] 段成华, 郭旭. 基于整数规划的单贝多港 (sbmp) 配载模型研究[j]. 计算机辅助工程, 2004, 13(3): 9-13.

[2] 张维英. 集装箱船全航线配载智能优化研究[d]. 大连理工大学, 2005.

[3] 张维英, 林焰, 纪卓尚. 集装箱船全航线 bay 位排箱优化模型[j]. 上海交通大学学报, 2007, 41(2): 199-204.