海上散货运输的船舱配载问题研究

1、海上散货运输的船舱配载问题研究摘要当今世界在航运路线的研究中，很多的限制条件和规定影响着航运的日常操作。这些限制条件的影响尚未从运筹学的角度深入研究。本论文将论述在海运运输中散货货物如何在船舱的有效分配的问题，其主要的问题存在于一系列的复杂的限制条件。当要解决一个给定的航线对于一个特定的船舶是否可行的问题时，货物在船舱中分配问题显得更为重要。在此过程中，计算机模拟实验可以有助于评估解决此类实际问题的难度。可行的规划可以为海运散货运输载重问题的研究提供一个合适的起点。1 引文货物运输是我们的全球经济学的重要组成部分，海上运输是国际贸易运输的主要渠道。每年超过7亿美元的货物经海运运输。正确的路线和

2、班次规划对运输提供者来说有巨大的价值。即使在这方面航运业落后于其他的运输方式，但在过去的十几年，我们已经积累了很多研究经验。 我们也开发了一些最优决策支持系统，例如，Fagerholt 和Lindstad的支持系统决策描述模型。在很多的海运散货运输操作中，船舶可能有数十个船舱，同时装载数个不同种类的若干票货物。尤其是在油产品和化工产品船中更是如此。 对于在这些货类领域经营的航运公司，最重要的规划问题就是安排什么样的船或者哪一个船舱装载某些特定的货物。我们将这类问题称为船舱分配问题TAP。当计划装卸任务，航线和时间安排的时候 TAP成为一个很重要的的评价可行性的标准。当是给定的路线例如是班轮运输

3、的路线，这就成为一个单独的问题。当把不同的货物分配到不同的船舱时，必须满足很多的限制条件，例如 装载能力，船的稳定性，危险品管理规则。再者，不同的货物不能放在同一船舱内。在给定的一个航线里，在运输单一的一票货物时也需要考虑TAP。对于一个竞争性强的一个航线，货物的装卸是与港口有联系的。学术上对海运TAP的研究很少。Pintens提出综合整合规划模型，是针对一批单一的货物的船舱分配问题提出的，其目的是减少经济成本和测量的结构压力，受制于各种的条件，例如货物爆裂，船的稳性，货物之间的兼容性，以及最大货物量。在这线性的综合规划中，当计算测量船稳性时，重心的表述常用线性回归表示。再者，提出的非线性模型

4、也没有使稳性的测量过程得到简化的。运用计算机实验测试有十个船舱的小型船舶，把GLPK方法运用到线性模型中，把模仿演算法运用到非线性模型中能解决这类测试问题。最好的结果是从线性方法中得到的。这方法的得到结构性的计划。Vouros et al提出了一个针对油产品和化工产品的在船舱中的分配问题的一个发展专家系统的框架，并针对货物装卸操作的进行规划，但只是针对单一的一票货物。这个框架由3个层面组成，知识层面描述的是货物分配与装卸任务，第二层次涉及到专家装卸系统所需要的知识类别，例如规划者掌握的关于船结构的知识，还有，涉及到的通用程序和解决问题的方法的策略性知识。最后一个层面是对专家系统的知识的运用。这

5、种模型框架不能用于任何的实际问题。Fagerholt and Christiansen研究的是在干散货航运运输中一个联合船的航线以及货物分配问题。这里，每条船配备一个装货物的货仓，这货仓还可以分成几个小货仓。除了对于航线的确定外，货仓的分割与货物的分配导致更小的货仓的问题也要考虑。这问题的解决通过两部方法，第一步选择一些特定的可行的候选航线，包括船上的货仓的的分割以及货物的分配。第二步，Fagerholt and Christiansen进一步阐述了线路的形成以及第一步中的货物分配。在其他不同类型不同特征的货物的海运运输中，同样存在着装卸和分配的问题。比如，在集装箱船装卸的时候，货物装卸操作的

6、效率必须要考虑。当要卸载的一个特定的集装箱，但它被另一个集装箱压在上面，这时候集装箱的移动是必要的。因此在集装箱船装卸时，目标函数要考虑到要使集装箱最小规模数目的变动。与散货运输的TAP相比，学界已经对集装箱船装卸的大量研究，例如 Wilson， Roach，Kang 和 Kim。在学界中，一些额外相关的装载问题已经被提及。Shilfer和 Naor 已提出了隔离储存问题SSP，即不同种类的谷物必须储存在相隔的船舱中，每个仓库最多存放一种产品。假设有一种无限容量的外部储存容器用来调节溢出的产品，其目的是使储存费用最低。Neebe 和Rao模拟的SSP可以看作为一个包装问题，使没有一个船舱是装载

7、超过一种货物的，并且每一种货物都充分的分配好。Evans 和Cullen提出了一个SSP的交替运输模型。Dannenbring，Khumawala，Neebe ，Rao，Neebe，Evans，Asubakitan，White 和 Francis都提出了解决SSP的正确方法。广义的隔离储存问题GSSP是另一个相关的问题，因此，当一种产品分配到一个船舱时，就会再出现另一个限制条件，即与它相矛盾的另一种产品不能放在该产品附近的船舱里。Barbucha提出了一个具建设性启发建议和两个基于人口的运算来解决GSSP问题。Yuceer提出了海运运输中货物分配中最多一种产品分配到一个仓库的问题。其目标是这样

8、做的目的是最大限度地最少的周期的要求,满足所有的产品都是由单一运送到一个或多个目的地。最优算法来解决这个问题。Bukchin和 Sarin也在考虑同样的问题，但引入了一个不连续的时间策略，使在一个可变的时间周期里交付总量不变。Cornillier et al提出了一个汽油站订货问题PSRP,包括在一个单一的时间段内共同决定的交付数量，分配产品到船舱里，要求最多一个货物放一个仓，还要包括决定交付到站点的运输路线。PSRP已分解成货车分配问题和路线问题。一个正确的运算和截断版本算法可以用作启发。本文将提出相关的模型以及在海运散货运输中出现的不同货种的TAP。在本文第2章通过描述一个数学模型来解释T

9、AP。2 TAP在考虑一个给定的航运路线时，例如在FIG1中的例子。例子中的船舶总运力是7500， 一共有8个不同的仓。在实际中，可能会有10个仓的情况。在表一中，每一个船舱都被标上号码和容量。在航线的每个节点中，有装货的也有卸货的。每一票具体的货物都给定了一个特定的数量。货物积载计划问题可以定义为：对于一个给定的船舶航线，设计一个如何在船舱中分配货物的最优的或可行的方案。在航线每个节点中都要满足最重要的和典型的限制条件：1. 每一票货物必须分配到一个或多个船舱中，这货物的重量，大小，都必须不能超过这些船舱的总容量。2. 船上的船舱必须有不同的涂层。货物只能分配到和涂层相容的船舱中。3. 货物

10、装船后，不能允许在别的船舱中移动。但这种限制有时不需要严格执行，这种情况会在2.3节中讨论。4. 在同一船舱中不能混放不同种类的货物。5. 在同一船舱中不能混放不同批次的货物，即使他们会有同类的货物。这种规定也可以适当的放松限制，这种情况会在2.3节中讨论。6. 如果船舱被使用了，必须满足它的最小载重量，以防止在航行期间晃荡。7. 在一个给定的即时计划中，某些船舱可能被一些还不能卸的货物占用。8. 在危险品货物规定中，某些特定的货物不能放在相互附近的船舱中。9. 在危险品货物规定中，某些特定的货物不能同时装船。10. 在危险品货物规定中，某些特定的货物不能放在同一个货舱中，除非它已经清洗过了，

11、或者早就有其他的已经经过几个航次货物在这个船舱里了。11. 船舶稳性和强度的要求规定了怎样的货物种类混合是禁止的。这些规定会在2.1节中进一步的解释。在实际问题中，各种一系列的限制可能是没必要的。例如，一艘船可能转载的货物中没有相冲的货物。则危险品货物的规定则不会起作用。在大多数的情况下，最重要的是要提出一个可行的方案。任何可行的船舱积载计划都一样的好。然而，计划是一个动态情况下进行的。这就意味着船舱分配的问题会影响到是否接受未来客户要求的可能性。除此之外，如果船舱需要清洁，那就有把相关成本减少到最低的倾向。图1 是一个可行的方案来简化说明TAP，货物1分配到船舱678货物2分配到船舱12货物

12、3分配到船舱34货物4分配到船舱5678（船舱678中的货物1已经被清空了）。当船离开节点4的时候，船是满载的。图 1 一条航线的例子2.1 单个即期TAP模型我们现在提出一个模型，它是描述在一次航行中的任何时间点面临的问题，那就是说，在遵守所有限制的条件下，在船舱中完成一票货的配载。我们这个模型叫作单个即期船舱配载问题(SITAP)。它假设不是同一票货物不能在同一个船舱中混合装载。定义几个集合，如下：L-装载的集合T-船舱的集合LLl-与第l票货冲突的那几票货的集合LTt-与第t个船舱兼容的那几票货的集合TLl-与第l票货兼容的船舱的集合Tlkt-如果第t个船舱装有第l票货，就不能装载第k票

13、货的船舱的集合S-稳性和力维,比如船舶头尾和左右平稳。见图2图 2 Various dimensions around which stability and strength requirements are formed: (A) roll, (B) trim, and (C) strength.其中所用指标的含义，如下：j,k,l-代表第几票货t,u-代表第几船舱s-代表稳性或力维定义几个变量，如下：xlt-指示变量，当且仅当第l票货被装配到第t船舱时，xlt=1ylt-装配到第t船舱的第l票货的数量或体积所有的参数，如下：v1-第l票货的体积dl-第l票货的密度ct-第t船舱的容量bt

14、-当第t船舱载货时，船舱中的最小容量mst-关于第t船舱的稳性或力维的瞬时大小ms+-就稳性或力维，在总的时刻中的上限ms-就稳性或力维，在总的时刻中的下限所有的限制条件，如下：lLTtxlt 1 (tT) (4)kLLl xkuMlt(1- xlt) (lL，tTLl) (5)uTlkt tTLllLms- mstdlyltms+ (sS) (6)限制条件（1）使得不违背船舱容量得到保证，并且仅当被计划配载到某个指定船舱的那几票货是能够被装载入那个船舱的。限制条件（2）用于调节在一个船舱中允许的最小体积，如果bt0，就可以避免在一次航行中船舱里的摇晃效应。限制条件（3）确保整的一票货物被装载

15、在船上。只有一票货物能被配载入任何给定的船舱，在限制条件（4）得以明确。限制条件（5）使得不兼容的几票货不能在相邻的船舱中，因此如果第l票货被配载入第t船舱，那么与已被装载第l票货的第t船舱相邻的第u船舱中不能装载与第l票货不兼容的第k票货。不等式的右边系数Mlt = maxkTlkt，（l L，t TLl）限制条件（6）确保在考虑船舶左右和头尾平稳和强度的限制条件下船舶的稳性。注意到与屈从于非线性表达的总的计算作对比，这些限制条件得以简化。因此，存在一些证据表明来自于简化的损失是较小的。SITAP模型可以被考虑为带有一些附加限制条件的SSP模型。正如Yuceer所指出的，SSP模型是一种划分

16、问题的类型，模型中在假定TL的情况下，将所有的T个船舱划分配载入所有的L票货。这样划分的数量是由第二张订单的数量决定的，即S(T,L)=(1/L!)k=0L(-1)L-kLkkT。因为每个船舱都能装载一票货物，所以把所有货物指派到所有船舱的方法的数量是由L！S(T,L)给出的。举个例子来说，如果T=8，L=5，那么指派的数量=5！S（8,5）=1201050=126000。 我们至今尚未提出任何目标函数，并且将推迟关于合适的目标函数的讨论，直到第二个模型被提出以后。2.2 TAP模型我们现在将问题转向完整的TAP，在这个模型中，货物通过机械动力完成装和卸，与港口的要求一致。我们假定一旦被装上船

17、货物就不能被从一个船舱移动到另一个船舱。在某种意义上说，我们只对装载上船的货物感兴趣（如图Fig.1，在问题的描述中被标记了“+”的节点），和对还没有被卸下船的货物感兴趣。因此，我们不必特地地考虑卸货（在问题描述中被标记了“”的节点），除了当船舶离开港口后，考虑对稳性和强度限制时。在SITAP模型中使用的注释仍然保留，此外再有几个附加注释，如下：定义几个集合：Nl-在第l票货装船后，将要立即装船的那几票货物。Pl-在装装载第l票货之前，已经完成装船的那几票货物。Q-在符合要求将货物装船后的那个满足船舶左右和头尾平稳限制的时刻的每个集合的组合。R-用于总和的那几票货的集合。定义一个变量：zlt-

18、指示变量，当且仅当在装载入第l票货之前，第t船舱清洗时，zlt =1。定义一个参数：hlkt-如果第t船舱已经被储藏了与第l票货冲突的第k票货，则在第l票货被装载入第t船舱之前，一种兼容的货物必须被装载入第t船舱的最小数量。 所有的限制条件，如下：（1） （3）kLTtNtxlt 1 (lL，tT) （9）uTlktkLTtNt xku Mlt(1- xlt) (lL，tTLl) (10)tTLllRms-mstdlyltms+ (RQ，sS) (11) jR （7）（8）限制条件（1）（3）仍然是用来确保所有货物被装上船后，船舱容量不被违背。限制条件（9）现在是用来保证在船舶航行过程中的任何

19、时刻，只有一票货被配载入任何一个船舱。限制条件（10）没有任何相邻的船舱中装载着不兼容的货物。限制条件（11）在整个航行过程中，控制船舶的稳性和强度是被要求。这个模型是通过一个限制建立的，这个限制是每一票货的装载必须保证稳性和强度的限制，那就是说每个RQ。因此每个RQ在离港或到港的时刻与装载的货物符合。最后，新的限制条件（12）需要一些解释。这些限制条件确保第l票货在与之不兼容的第k票货已经被装载去第t船舱时，不能再被配载入第t船舱。然而，有两种例外情况：如果船舱已经在中间被清洗过，那么这个船舱就可以被用于装载第l票货。或者，如果自从第k票货之后，有充足数量hlkt的另外货物已经装载入了这个船

20、舱。举例来说，考虑一票给定的货物l，一个与第l票货兼容的船舱t,和与第l票货冲突但可以被装载入第t船舱的第k票货。集合R=PlPkk代表的是那些在第k票货之后但在第l票货之前装船的货物。可以注意如果第l票货不被配载去第t船舱，则限制条件（12）不等式的左边将很可能等于0（因为xlt=0）,而右边是非负。如果第l票货被配载入第t船舱，则限制条件（12）的左边将很可能等于hlkt（因为xlt=1）。现在，如果第k票货也不被配载入第t船舱，则右边一定等于hlkt（因为xkt=0）。然而，如果第k票货被配载入第t船舱，则右边等于0（因为xkt=1）。存在三种使得左边遵从的方法：要么这个船舱在装载第l票

21、货之前被清洗了（这时zlt=1）,要么这个船舱在被第k票货使用之后在第l票货使用之前的某个j时间点上被清洗了（这时zjt=1）。要么一定数量hlkt的其他货物在中间已经被装载入第t船舱（这时xjt=1）。还有一些限制条件没有被考虑入模型，因为它们在预备阶段可以被简单地测算出来。这些适用于一些货物不能同时存在于船上，并且在任何时候装载的总重量必须低于一些门槛（船舶的载重吨）。2.2.1 目标函数就这个问题有许多可能的目标函数。考虑燃料价格和日常运营成本，对船公司来说最关心的是制定好的航运决策。策略决策的成本，诸如在哪里航行和装载什么货物，远远大于运营成本，诸如船舱配载。在许多现实世界的情况中，配

22、载计划只有存在可行性时才有兴趣去做。认为所有的可行配载计划是相同的是适当的，通过使用一个常量作为目标函数：min0 （14）就其它船舶运营而言，根据花费在清洗上的时间和金钱，洗舱还表一种不便。下面的目标函数最小化了洗舱的不方便：lL t TLl当考虑关于未来货物（现在未知的）的灵活性时，其它的目标函数是适当的。基于有许多空舱能使得后面的时刻容纳附加的货物变得更容易的观察，下面的目标函数最大化了船舶航行期间的空舱平均载重量：lL t TLlkNl2.3 问题的变形正如当前所说，在SITAP模型中的限制条件（4）用来确保每个船舱被至多一票货物使用。这个限制条件在某些情况下显得太严格了。举了例子，如

23、果这几票货物是同种同质的产品，并且基于精确地测量，船舶允许给定的数量能够被装卸。如果在这种情况下，我们能引入下面的附加注释：wt-指示变量，当且仅当第t船舱被至少一票货物使用时，wt=1那么，通过以下限制条件替换限制条件（2）和（4），我们能够允许不止一票货被配载到每个船舱。lLTtlLTtlLTt限制条件（17）确保配载入船舱的总容量不超过它的容量。任何摇晃效果通过限制条件（18）被调节。并且限制条件（19）现在允许不止一票货被配载入每个船舱。与第t船舱兼容的几票货物的数量，在后面的限制条件能够被变紧，如果能够被混合在一个船舱的最大化数量的货物是有限的。为了TAP模型，这些可供选择的限制条件

24、很容易被扩展，虽然我们在这儿没有列出所有的限制条件。为了允许在第t船舱里混合第l票货和第k票货，我们必须要有两个条件：（1）k LlL 或者t Tlkt 和（2）l LkL 或者t Tklt ,因为否则混合将被限制条件（5）限制。因此，限制条件（5）使得模型能够获得当一些货一点都不能混合时，一些货能够在一些特定的船舱被混合，但不能在其它的船舱混合。TAP模型的另一个假设，一旦那几票货物已经被储存在船上，它们不能在船舱间被移动。在散货运输可能的现实情况中这个限制条件不能被保证。最合适的解决不同货物能够在船舱中移动情况的方法能够被可论证地更改模型，通过在变量中引进时间指标，引入变量xlti代表第l

25、票货是否在i 时刻被配载入第t船舱。然而，我们希望指出这种情况能够被处理，通过使用存在的模型。举个例子，如果不考虑洗舱，那么关于移动货物的问题能够被解决，通过在每一段航程中解决一系列SITAP实例。存在许多其它能够被想象的问题的变形，举个例子通过放宽要么限制条件（5）要么限制条件（6）。此外，正如前面章节所论述的，存在着许多可能的目标函数。提出模型的几个变形的主要原因是为了传达真实的海上运输问题出现了无数的变形，并且每个船公司都有必须遵守的他们自己的限制条件和程序。我们已经提出了TAP模型作为我们的主要模型，因为我们认为它已经足够容纳各种各样可能发生的真实世界的配载情况，并且该模型为海上散货运

26、输配载问题的研究可能形成一个合适的起点。2.4 复杂性分析TAP在计算上是棘手的，在某种意义上说，找到解决问题的可行的方法就是NP-Complete。事实上，一个SITAP模型的简化变形就是NP-Complete，使用一个与Barbucha关于SSP的论文中相似的论据来得以证明。不正式地说，TAP是SITAP的一个一般形式，并且SITAP是SSP的一个一般形式。因此找到解决SSP的可行的方法是NP-Complete，则就等于找到解决要么TAP要么SITAP的可行的方法也是NP-Complete。在下面我们给出了一个证明解决SITAP的可行方法是NP-Complete的正式的论据，通过对已知的N

27、P-Complete划分问题(PP)的简化。定义，由n个数组成的集合A=a1,a2,an,PP是决定是否存在A的一个划分，由此而得两个子集合A1和A2，满足jA1 aj=jA2aj定理2.1 让单一即期船舱配载可行性问题（SITAFP）代表找到解决SITAP可行的方法的问题。SITAFP就是NP-Complete。论证，容易看到SITAFP的解决方法能在多项式时间中被证实，因此SITAFP就是在NP中。在多项式时间中PP能被简化为SITAFP，也就是说SITAFP就是NP-Complete。仍然能表示任何PP的实例能怎样被转化成SITAFP的实例，也就是说当且仅当存在一个解决SITAFP实例的

28、方法时，存在一个解决PP实例的可行方法。通过由n个数组成的集合A=a1,a2,an,拿任何PP的实例来具体说明。用n个船舱，T=1,2 ,n和两票货物L=1,2来建立一个SITAFP实例。设置每票货的容量vl=0.5jA aj,并设置船舱的容量等于集合A中的每个数的大小，ct=at。让TLl=T因为lL并让LTt=L因为tT。现在在A1和A2中考虑一个解决PP可行的方法。一个与SITAFP一致的可行的解决方法能够通过如果atAl并且ylt=0使得ylt=at而找到。现在考虑存在一个解决SITAFP实例的方法。在那种情况下，一个PP的解决方法能通过当且仅当ylt=at时在Al增加at来被找到。可

29、以注意到不存在0yltat，因为一艘船的总容量等于载货的总体积，并且在一个船舱中混合两票货物是不被允许的。3 计算研究在第二节我们介绍了TAP和它的几个变形。这一节的重点是(1)(3),(7)(8)的主要结构，（14）（15）（16）的运用，目的是创造出各种不同的Tap的现实样品，这些现实样品可以被用来计算研究，以便于获得解决由海运散货航运公司面临TAP方案的评估难度。3.1节描述了样品的生产，计算研究的结果3.2节给出。3.1 样品产生由于TAP是一个一般的模型，这就允许更多类型的样品可以在一个单一的计算研究被探讨。因此，这里产生的样品受制于一下参数。图3说明了两只油船的结构配置，样品是依据

30、这些为基础的。一个是一个相对小的船，能装载1000m3（8000自重吨）分布在24个货舱。另一个是一个相对较大的船，45000m3的容积（39000自重吨）和38个货舱。依据每艘船货舱的配置可以计算稳定性限制。有两种类型的货舱,一架采用不锈钢,另一种是用锌硅酸盐涂料,后者彩色灰色图3。简单来说，我们假设负载可以分三类：第一类负载分配至任何货舱而不是与其他货载冲突；第二类负载分配至任何货舱但是与第三类负载冲突；第三类负载只能分配在有锌硅酸盐涂料的货舱并与在第二类第三类的负载冲突。在负载l和负载k冲突的情况下，我们将（Tlkt-如果第t个船舱装有第l票货，就不能装载第k票货的船舱集合）Tlkt 为

31、货舱的一部分在t的一旁。见图3。对于每个样品，10负载将被考虑到固定的地方，也就是，他们形成这艘船过去的历史，影响哪个货舱是干净的哪个货舱将被使用。为了产生各种各样的样品，不同的值考虑以下五参数: 货舱的数量取决于船舶的选择，T24（小船）和T38（大船）的设置标签。 负载的数量（包括10个固定的负载），给20负载、30负载、40负载分别设置标签L20、L30和L40。 对各种负载的可能分布，标记C1（0.6,0.4,0.0）C2(0.5,0.4,0.1) C3(0.4,0.4,0.2)和C4(0.3,0.4,0.3)。C1的意思是60%的负载来源于第一类负载，40%来源于第二类负载，0%来源

32、于第三类。 最低（最大）舱容利用率在装货（卸货）之前就会出现，标记F1（0.65,0.35）,F2(0.75,0.25)和F3(0.85,0.15)，这就是，用F1产生的路线上，船将会开始去提取货物的地点提货直到船舶总负载超过船舶容量的65%，然后去交货地点直到船上总负载低于船舶容量的35%，然后再去提取货物的地点。这些限制进而影响交货和取货顺序是怎么样被混杂的在路线生成的情况下。图4是对F1生成样品TAP_T24L20C3F1S3_01的说明。 负载大小的分配，标记S3（1000-5000m3）,S6（3000-9000 m3）和S12（8000-16000 m3）。在S3的情况下，意味着负

33、载的大小遵循均与分布，在1000-5000 m3之间。有两艘船的设计（不是规模）用于产生测试样品，上方是一个24个油舱和容积10000m3的小船，下方是一个38个油舱和容积45000 m3 的大船。样品被随机地生成为每个这些情况的组合设置，除了T24、S12的组合（船太小不能考虑负载）和T38、S3的组合。每组设置生成5个样品，144组设置共720个样品。在样品生成期间，用3.2章节描述的方法证明，结果表明可行性解存在。表1部分显示了TAP_T24L20C3F1S3_01样品，给出了装货和卸货的顺序，每次负载的种类和体积，另外货舱的分配以及部分样品的货舱分配。解决这个样品相当于填写表格右下部分

34、的数据，说明每个负载怎样被分配到可行的货舱中，这样所有限制问题也不会被违反。样品和样品生成器可以从作者的要求中获得。3.2 结果尽管TAP是非完全多项式而因此从理论角度是难以计算的，实际大小样品能否在实践中高效的被解决这个问题仍没有答案。计算研究已经进行了正如3.1章节描述的用720个样品。这里出现的主要结果是通过商业上可行的整数规划求解模型CPLEX v.11在Intel2.66GHz处理器上运行得出的。有一些实验室用来评估各种的求解设置。第一步，我们运用目标函数（15）作为我们的主要目标函数，并检查标准设置和是否集中证明最优或找出第一个可行办法的不同。第二步，当我们用CPLEX试图找出可行

35、解的时候我们分别运用函数（14）-（16）进行比较。第三步，我们看看通过CPLEX跨过标准的选择改变个人变量的分支的优先选择。四个选择测试：（1）所有变量的平等优先（标准优先）；（2）xlt比xkt if |TLl|TLk|更高级优先（舱容优先）；（3）xlt比xkt （如果 l 装载k的前面）更高级（时间优先）；（4）z变量的更高级优先（清洁优先）。研究主要是运用CPLEX集中找出TAP的可行办法。然而，如果可行解是有针对性的，基于限制变成的求解方法有潜在的好处。作为一种测试假设的方法，样品通常被运用约束求解的模型MINION建模和解决。MINION 是一个通用的约束求解方法，被当做一个黑盒

36、用。我们注意到当大多数的TAP用MINION输入语言建模时很容易的时候，y变量肯定是离散的。当检查实际大小的样品是否能通过CPLEX和MINION高效处理的时候，我们旨在建立哪一个问题的维度有助于创建实践中难以解决的样品。表2总结了第一个测试的结果。CPLEX被分配了600秒的时间来解决这720个样品中的每个样品。图表的结果来自三次运营，每次都是运用目标函数（15）：一个是标准值；一个是找出一个可行解，第三个是证明方案的最优化。所有的样品一起给出了平均结果。因此，L20子集包括所有的样品，这些样品包括20负荷（其中的10负荷认为是固定的，剩下的10个要求规划）。我们认为函数（15）是主要的目标

37、函数，因为关于清洁货舱有一个直接的可衡量的不便。对于每个求解设置和样品子集，我们报告了能求出可行解的样品，能证明最优的样品以及找出第一个可行解所用的平均时间。 在第一次测试中我们发现在发现可行解的数量上没有大的不同：当计算可行解或最优解得时候，有4-12组的情况是没有解得在600秒内。然而，找到可行解的平均的时间将会是两倍以上如果没有一个明确专注于可行性分析。被证明最优解答的数量稍低了一点当有一个最优焦点而不是标准设置的时候，但是预期会更低如果有可行性焦点。因为可行性是考虑的一个主要因素，在余下的测试中我们主要是找出可行解。我们可以通过表2哪些因素加大了寻找可行解的难度。很容易看出来，随着负载

38、的增加，这些事例变得更加困难，在600秒内发现可行解和最优解的数量都在减少，而找到第一个可行解的时间在增加，随着三种货物数量的增加，会导致更多的货物与其他的货物产生冲突的机会增加，并且找到可行解的时间也增加了，可以被证明的可行解的数量也减少了。F1-F3包含了各种记载利用率的例子，F1看起来好像给出的比其他两种简单，但是对于其他结果的解释不是太明显。最后，这些建立在24舱船的实例比38舱船的要简单，装载小的要比装载量大的难，这些主要是由于不同船的配置结构不同，而并非单是船舱个数或体积造成的。第二个测试说明了在优化船舱配载时不同的目标函数所产生的影响，表格3给出了（14）-（16）这三种目标函数的运行结果。这个表