海上散货运输的船舱配载问题研究摘要当今世界在航运路线的研究中，很多的限制条件和规定影响着航运的日常操作。
这些限制条件的影响尚未从运筹学的角度深入研究。
本论文将论述在海运运输中散货货物如何在船舱的有效分配的问题，其主要的问题存在于一系列的复杂的限制条件。
当要解决一个给定的航线对于一个特定的船舶是否可行的问题时，货物在船舱中分配问题显得更为重要。
在此过程中，计算机模拟实验可以有助于评估解决此类实际问题的难度。
可行的规划可以为海运散货运输载重问题的研究提供一个合适的起点。
1 引文货物运输是我们的全球经济学的重要组成部分，海上运输是国际贸易运输的主要渠道。
每年超过7亿美元的货物经海运运输。
正确的路线和班次规划对运输提供者来说有巨大的价值。
即使在这方面航运业落后于其他的运输方式，但在过去的十几年，我们已经积累了很多研究经验。
我们也开发了一些最优决策支持系统，例如，Fagerholt 和Lindstad的支持系统决策描述模型。
在很多的海运散货运输操作中，船舶可能有数十个船舱，同时装载数个不同种类的若干票货物。
尤其是在油产品和化工产品船中更是如此。
对于在这些货类领域经营的航运公司，最重要的规划问题就是安排什么样的船或者哪一个船舱装载某些特定的货物。
我们将这类问题称为船舱分配问题TAP。
当计划装卸任务，航线和时间安排的时候TAP成为一个很重要的的评价可行性的标准。
当是给定的路线例如是班轮运输的路线，这就成为一个单独的问题。
当把不同的货物分配到不同的船舱时，必须满足很多的限制条件，例如装载能力，船的稳定性，危险品管理规则。
再者，不同的货物不能放在同一船舱内。
在给定的一个航线里，在运输单一的一票货物时也需要考虑TAP。
对于一个竞争性强的一个航线，货物的装卸是与港口有联系的。
学术上对海运TAP的研究很少。
Pintens提出综合整合规划模型，是针对一批单一的货物的船舱分配问题提出的，其目的是减少经济成本和测量的结构压力，受制于各种的条件，例如货物爆裂，船的稳性，货物之间的兼容性，以及最大货物量。
在这线性的综合规划中，当计算测量船稳性时，重心的表述常用线性回归表示。
再者，提出的非线性模型也没有使稳性的测量过程得到简化的。
运用计算机实验测试有十个船舱的小型船舶，把GLPK方法运用到线性模型中，把模仿演算法运用到非线性模型中能解决这类测试问题。
最好的结果是从线性方法中得到的。
这方法的得到结构性的计划。
Vouros et al提出了一个针对油产品和化工产品的在船舱中的分配问题的一个发展专家系统的框架，并针对货物装卸操作的进行规划，但只是针对单一的一票货物。
这个框架由3个层面组成，知识层面描述的是货物分配与装卸任务，第二层次涉及到专家装卸系统所需要的知识类别，例如规划者掌握的关于船结构的知识，还有，涉及到的通用程序和解决问题的方法的策略性知识。
最后一个层面是对专家系统的知识的运用。
这种模型框架不能用于任何的实际问题。
Fagerholt and Christiansen研究的是在干散货航运运输中一个联合船的航线以及货物分配问题。
这里，每条船配备一个装货物的货仓，这货仓还可以分成几个小货仓。
除了对于航线的确定外，货仓的分割与货物的分配导致更小的货仓的问题也要考虑。
这问题的解决通过两部方法，第一步选择一些特定的可行的候选航线，包括船上的货仓的的分割以及货物的分配。
第二步，~~~~~Fagerholt and Christiansen进一步阐述了线路的形成以及第一步中的货物分配。
在其他不同类型不同特征的货物的海运运输中，同样存在着装卸和分配的问题。
比如，在集装箱船装卸的时候，货物装卸操作的效率必须要考虑。
当要卸载的一个特定的集装箱，但它被另一个集装箱压在上面，这时候集装箱的移动是必要的。
因此在集装箱船装卸时，目标函数要考虑到要使集装箱最小规模数目的变动。
与散货运输的TAP相比，学界已经对集装箱船装卸的大量研究，例如Wilson，Roach，Kang 和Kim。
在学界中，一些额外相关的装载问题已经被提及。
Shilfer和Naor 已提出了隔离储存问题SSP，即不同种类的谷物必须储存在相隔的船舱中，每个仓库最多存放一种产品。
假设有一种无限容量的外部储存容器用来调节溢出的产品，其目的是使储存费用最低。
Neebe 和Rao模拟的SSP可以看作为一个包装问题，使没有一个船舱是装载超过一种货物的，并且每一种货物都充分的分配好。
Evans 和Cullen提出了一个SSP的交替运输模型。
Dannenbring，Khumawala，Neebe ，Rao，Neebe，Evans，Asubakitan，White 和Francis 都提出了解决SSP的正确方法。
广义的隔离储存问题GSSP是另一个相关的问题，因此，当一种产品分配到一个船舱时，就会再出现另一个限制条件，即与它相矛盾的另一种产品不能放在该产品附近的船舱里。
Barbucha提出了一个具建设性启发建议和两个基于人口的运算来解决GSSP问题。
Yu¨ceer提出了海运运输中货物分配中最多一种产品分配到一个仓库的问题。
其目标是这样做的目的是最大限度地最少的周期的要求,满足所有的产品都是由单一运送到一个或多个目的地。
最优算法来解决这个问题。
Bukchin和Sarin也在考虑同样的问题，但引入了一个不连续的时间策略，使在一个可变的时间周期里交付总量不变。
Cornillier et al提出了一个汽油站订货问题PSRP,包括在一个单一的时间段内共同决定的交付数量，分配产品到船舱里，要求最多一个货物放一个仓，还要包括决定交付到站点的运输路线。
PSRP已分解成货车分配问题和路线问题。
一个正确的运算和截断版本算法可以用作启发。
本文将提出相关的模型以及在海运散货运输中出现的不同货种的TAP。
在本文第2章通过描述一个数学模型来解释TAP。
2 TAP在考虑一个给定的航运路线时，例如在FIG1中的例子。
例子中的船舶总运力是7500，一共有8个不同的仓。
在实际中，可能会有10个仓的情况。
在表一中，每一个船舱都被标上号码和容量。
在航线的每个节点中，有装货的也有卸货的。
每一票具体的货物都给定了一个特定的数量。
货物积载计划问题可以定义为：对于一个给定的船舶航线，设计一个如何在船舱中分配货物的最优的或可行的方案。
在航线每个节点中都要满足最重要的和典型的限制条件：1. 每一票货物必须分配到一个或多个船舱中，这货物的重量，大小，都必须不能超过这些船舱的总容量。
2. 船上的船舱必须有不同的涂层。
货物只能分配到和涂层相容的船舱中。
3. 货物装船后，不能允许在别的船舱中移动。
但这种限制有时不需要严格执行，这种情况会在2.3节中讨论。
4. 在同一船舱中不能混放不同种类的货物。
5. 在同一船舱中不能混放不同批次的货物，即使他们会有同类的货物。
这种规定也可以适当的放松限制，这种情况会在2.3节中讨论。
6. 如果船舱被使用了，必须满足它的最小载重量，以防止在航行期间晃荡。
7. 在一个给定的即时计划中，某些船舱可能被一些还不能卸的货物占用。
8. 在危险品货物规定中，某些特定的货物不能放在相互附近的船舱中。
9. 在危险品货物规定中，某些特定的货物不能同时装船。
10. 在危险品货物规定中，某些特定的货物不能放在同一个货舱中，除非它已经清洗过了~~，或者早就有其他的已经经过几个航次货物在这个船舱里了。
11. 船舶稳性和强度的要求规定了怎样的货物种类混合是禁止的。
这些规定会在2.1节中进一步的解释。
在实际问题中，各种一系列的限制可能是没必要的。
例如，一艘船可能转载的货物中没有相冲的货物。
则危险品货物的规定则不会起作用。
在大多数的情况下，最重要的是要提出一个可行的方案。
任何可行的船舱积载计划都一样的好。
然而，计划是一个动态情况下进行的。
这就意味着船舱分配的问题会影响到是否接受未来客户要求的可能性。
除此之外，如果船舱需要清洁，那就有把相关成本减少到最低的倾向。
图1 是一个可行的方案来简化说明TAP，货物1分配到船舱678货物2分配到船舱12货物3分配到船舱34货物4分配到船舱5678（船舱678中的货物1已经被清空了）。
当船离开节点4的时候，船是满载的。
图1 一条航线的例子2.1 单个即期TAP模型我们现在提出一个模型，它是描述在一次航行中的任何时间点面临的问题，那就是说，在遵守所有限制的条件下，在船舱中完成一票货的配载。
我们这个模型叫作单个即期船舱配载问题(SITAP)。
它假设不是同一票货物不能在同一个船舱中混合装载。
定义几个集合，如下：L-装载的集合T-船舱的集合L L l-与第l票货冲突的那几票货的集合L T t-与第t个船舱兼容的那几票货的集合T L l-与第l票货兼容的船舱的集合T lkt-如果第t个船舱装有第l票货，就不能装载第k票货的船舱的集合S-稳性和力维,比如船舶头尾和左右平稳。
见图2图 2Various dimensions around which stability and strength requirements are formed: (A) roll, (B) trim, and (C) strength.其中所用指标的含义，如下：j,k,l-代表第几票货t,u-代表第几船舱s-代表稳性或力维定义几个变量，如下：x lt-指示变量，当且仅当第l票货被装配到第t船舱时，x lt=1y lt-装配到第t船舱的第l票货的数量或体积所有的参数，如下：v1-第l票货的体积d l-第l票货的密度c t-第t船舱的容量b t-当第t船舱载货时，船舱中的最小容量m s t-关于第t船舱的稳性或力维的瞬时大小m s+-就稳性或力维，在总的时刻中的上限m s--就稳性或力维，在总的时刻中的下限所有的限制条件，如下：∑x lt ≤1 (t ∈T ) (4)∑ ∑x ku ≤M lt (1- x lt ) (l ∈L ，t ∈T L l ) (5)m s-≤∑ ∑m s t d l y lt≤m s+ (s ∈S ) (6)限制条件（1）使得不违背船舱容量得到保证，并且仅当被计划配载到某个指定船舱的那几票货是能够被装载入那个船舱的。
限制条件（2）用于调节在一个船舱中允许的最小体积，如果b t >0，就可以避免在一次航行中船舱里的摇晃效应。
限制条件（3）确保整的一票货物被装载在船上。
只有一票货物能被配载入任何给定的船舱，在限制条件（4）得以明确。
限制条件（5）使得不兼容的几票货不能在相邻的船舱中，因此如果第l 票货被配载入第t 船舱，那么与已被装载第l 票货的第t 船舱相邻的第u 船舱中不能装载与第l 票货不兼容的第k 票货。
不等式的右边系数M lt = max k ∣T lkt ∣，（l ∈L ，t ∈T L l ）限制条件（6）确保在考虑船舶左右和头尾平稳和强度的限制条件下船舶的稳性。
