海上散貨運(yùn)輸?shù)拇撆漭d問題研究

1、海上散貨運(yùn)輸?shù)拇撆漭d問題研究摘要當(dāng)今世界在航運(yùn)路線的研究中，很多的限制條件和規(guī)定影響著航運(yùn)的日常操作。這些限制條件的影響尚未從運(yùn)籌學(xué)的角度深入研究。本論文將論述在海運(yùn)運(yùn)輸中散貨貨物如何在船艙的有效分配的問題，其主要的問題存在于一系列的復(fù)雜的限制條件。當(dāng)要解決一個(gè)給定的航線對(duì)于一個(gè)特定的船舶是否可行的問題時(shí)，貨物在船艙中分配問題顯得更為重要。在此過程中，計(jì)算機(jī)模擬實(shí)驗(yàn)可以有助于評(píng)估解決此類實(shí)際問題的難度?？尚械囊?guī)劃可以為海運(yùn)散貨運(yùn)輸載重問題的研究提供一個(gè)合適的起點(diǎn)。1 引文貨物運(yùn)輸是我們的全球經(jīng)濟(jì)學(xué)的重要組成部分，海上運(yùn)輸是國際貿(mào)易運(yùn)輸?shù)闹饕?。每年超過7億美元的貨物經(jīng)海運(yùn)運(yùn)輸。正確的路線和

2、班次規(guī)劃對(duì)運(yùn)輸提供者來說有巨大的價(jià)值。即使在這方面航運(yùn)業(yè)落后于其他的運(yùn)輸方式，但在過去的十幾年，我們已經(jīng)積累了很多研究經(jīng)驗(yàn)。 我們也開發(fā)了一些最優(yōu)決策支持系統(tǒng)，例如，F(xiàn)agerholt 和Lindstad的支持系統(tǒng)決策描述模型。在很多的海運(yùn)散貨運(yùn)輸操作中，船舶可能有數(shù)十個(gè)船艙，同時(shí)裝載數(shù)個(gè)不同種類的若干票貨物。尤其是在油產(chǎn)品和化工產(chǎn)品船中更是如此。 對(duì)于在這些貨類領(lǐng)域經(jīng)營的航運(yùn)公司，最重要的規(guī)劃問題就是安排什么樣的船或者哪一個(gè)船艙裝載某些特定的貨物。我們將這類問題稱為船艙分配問題TAP。當(dāng)計(jì)劃裝卸任務(wù)，航線和時(shí)間安排的時(shí)候 TAP成為一個(gè)很重要的的評(píng)價(jià)可行性的標(biāo)準(zhǔn)。當(dāng)是給定的路線例如是班輪運(yùn)輸

3、的路線，這就成為一個(gè)單獨(dú)的問題。當(dāng)把不同的貨物分配到不同的船艙時(shí)，必須滿足很多的限制條件，例如 裝載能力，船的穩(wěn)定性，危險(xiǎn)品管理規(guī)則。再者，不同的貨物不能放在同一船艙內(nèi)。在給定的一個(gè)航線里，在運(yùn)輸單一的一票貨物時(shí)也需要考慮TAP。對(duì)于一個(gè)競爭性強(qiáng)的一個(gè)航線，貨物的裝卸是與港口有聯(lián)系的。學(xué)術(shù)上對(duì)海運(yùn)TAP的研究很少。Pintens提出綜合整合規(guī)劃模型，是針對(duì)一批單一的貨物的船艙分配問題提出的，其目的是減少經(jīng)濟(jì)成本和測量的結(jié)構(gòu)壓力，受制于各種的條件，例如貨物爆裂，船的穩(wěn)性，貨物之間的兼容性，以及最大貨物量。在這線性的綜合規(guī)劃中，當(dāng)計(jì)算測量船穩(wěn)性時(shí)，重心的表述常用線性回歸表示。再者，提出的非線性模型

4、也沒有使穩(wěn)性的測量過程得到簡化的。運(yùn)用計(jì)算機(jī)實(shí)驗(yàn)測試有十個(gè)船艙的小型船舶，把GLPK方法運(yùn)用到線性模型中，把模仿演算法運(yùn)用到非線性模型中能解決這類測試問題。最好的結(jié)果是從線性方法中得到的。這方法的得到結(jié)構(gòu)性的計(jì)劃。Vouros et al提出了一個(gè)針對(duì)油產(chǎn)品和化工產(chǎn)品的在船艙中的分配問題的一個(gè)發(fā)展專家系統(tǒng)的框架，并針對(duì)貨物裝卸操作的進(jìn)行規(guī)劃，但只是針對(duì)單一的一票貨物。這個(gè)框架由3個(gè)層面組成，知識(shí)層面描述的是貨物分配與裝卸任務(wù)，第二層次涉及到專家裝卸系統(tǒng)所需要的知識(shí)類別，例如規(guī)劃者掌握的關(guān)于船結(jié)構(gòu)的知識(shí)，還有，涉及到的通用程序和解決問題的方法的策略性知識(shí)。最后一個(gè)層面是對(duì)專家系統(tǒng)的知識(shí)的運(yùn)用。這

5、種模型框架不能用于任何的實(shí)際問題。Fagerholt and Christiansen研究的是在干散貨航運(yùn)運(yùn)輸中一個(gè)聯(lián)合船的航線以及貨物分配問題。這里，每條船配備一個(gè)裝貨物的貨倉，這貨倉還可以分成幾個(gè)小貨倉。除了對(duì)于航線的確定外，貨倉的分割與貨物的分配導(dǎo)致更小的貨倉的問題也要考慮。這問題的解決通過兩部方法，第一步選擇一些特定的可行的候選航線，包括船上的貨倉的的分割以及貨物的分配。第二步，F(xiàn)agerholt and Christiansen進(jìn)一步闡述了線路的形成以及第一步中的貨物分配。在其他不同類型不同特征的貨物的海運(yùn)運(yùn)輸中，同樣存在著裝卸和分配的問題。比如，在集裝箱船裝卸的時(shí)候，貨物裝卸操作的

6、效率必須要考慮。當(dāng)要卸載的一個(gè)特定的集裝箱，但它被另一個(gè)集裝箱壓在上面，這時(shí)候集裝箱的移動(dòng)是必要的。因此在集裝箱船裝卸時(shí)，目標(biāo)函數(shù)要考慮到要使集裝箱最小規(guī)模數(shù)目的變動(dòng)。與散貨運(yùn)輸?shù)腡AP相比，學(xué)界已經(jīng)對(duì)集裝箱船裝卸的大量研究，例如 Wilson， Roach，Kang 和 Kim。在學(xué)界中，一些額外相關(guān)的裝載問題已經(jīng)被提及。Shilfer和 Naor 已提出了隔離儲(chǔ)存問題SSP，即不同種類的谷物必須儲(chǔ)存在相隔的船艙中，每個(gè)倉庫最多存放一種產(chǎn)品。假設(shè)有一種無限容量的外部儲(chǔ)存容器用來調(diào)節(jié)溢出的產(chǎn)品，其目的是使儲(chǔ)存費(fèi)用最低。Neebe 和Rao模擬的SSP可以看作為一個(gè)包裝問題，使沒有一個(gè)船艙是裝載

7、超過一種貨物的，并且每一種貨物都充分的分配好。Evans 和Cullen提出了一個(gè)SSP的交替運(yùn)輸模型。Dannenbring，Khumawala，Neebe ，Rao，Neebe，Evans，Asubakitan，White 和 Francis都提出了解決SSP的正確方法。廣義的隔離儲(chǔ)存問題GSSP是另一個(gè)相關(guān)的問題，因此，當(dāng)一種產(chǎn)品分配到一個(gè)船艙時(shí)，就會(huì)再出現(xiàn)另一個(gè)限制條件，即與它相矛盾的另一種產(chǎn)品不能放在該產(chǎn)品附近的船艙里。Barbucha提出了一個(gè)具建設(shè)性啟發(fā)建議和兩個(gè)基于人口的運(yùn)算來解決GSSP問題。Yuceer提出了海運(yùn)運(yùn)輸中貨物分配中最多一種產(chǎn)品分配到一個(gè)倉庫的問題。其目標(biāo)是這樣

8、做的目的是最大限度地最少的周期的要求,滿足所有的產(chǎn)品都是由單一運(yùn)送到一個(gè)或多個(gè)目的地。最優(yōu)算法來解決這個(gè)問題。Bukchin和 Sarin也在考慮同樣的問題，但引入了一個(gè)不連續(xù)的時(shí)間策略，使在一個(gè)可變的時(shí)間周期里交付總量不變。Cornillier et al提出了一個(gè)汽油站訂貨問題PSRP,包括在一個(gè)單一的時(shí)間段內(nèi)共同決定的交付數(shù)量，分配產(chǎn)品到船艙里，要求最多一個(gè)貨物放一個(gè)倉，還要包括決定交付到站點(diǎn)的運(yùn)輸路線。PSRP已分解成貨車分配問題和路線問題。一個(gè)正確的運(yùn)算和截?cái)喟姹舅惴梢杂米鲉l(fā)。本文將提出相關(guān)的模型以及在海運(yùn)散貨運(yùn)輸中出現(xiàn)的不同貨種的TAP。在本文第2章通過描述一個(gè)數(shù)學(xué)模型來解釋T

9、AP。2 TAP在考慮一個(gè)給定的航運(yùn)路線時(shí)，例如在FIG1中的例子。例子中的船舶總運(yùn)力是7500， 一共有8個(gè)不同的倉。在實(shí)際中，可能會(huì)有10個(gè)倉的情況。在表一中，每一個(gè)船艙都被標(biāo)上號(hào)碼和容量。在航線的每個(gè)節(jié)點(diǎn)中，有裝貨的也有卸貨的。每一票具體的貨物都給定了一個(gè)特定的數(shù)量。貨物積載計(jì)劃問題可以定義為：對(duì)于一個(gè)給定的船舶航線，設(shè)計(jì)一個(gè)如何在船艙中分配貨物的最優(yōu)的或可行的方案。在航線每個(gè)節(jié)點(diǎn)中都要滿足最重要的和典型的限制條件：1. 每一票貨物必須分配到一個(gè)或多個(gè)船艙中，這貨物的重量，大小，都必須不能超過這些船艙的總?cè)萘俊?. 船上的船艙必須有不同的涂層。貨物只能分配到和涂層相容的船艙中。3. 貨物

10、裝船后，不能允許在別的船艙中移動(dòng)。但這種限制有時(shí)不需要嚴(yán)格執(zhí)行，這種情況會(huì)在2.3節(jié)中討論。4. 在同一船艙中不能混放不同種類的貨物。5. 在同一船艙中不能混放不同批次的貨物，即使他們會(huì)有同類的貨物。這種規(guī)定也可以適當(dāng)?shù)姆潘上拗?，這種情況會(huì)在2.3節(jié)中討論。6. 如果船艙被使用了，必須滿足它的最小載重量，以防止在航行期間晃蕩。7. 在一個(gè)給定的即時(shí)計(jì)劃中，某些船艙可能被一些還不能卸的貨物占用。8. 在危險(xiǎn)品貨物規(guī)定中，某些特定的貨物不能放在相互附近的船艙中。9. 在危險(xiǎn)品貨物規(guī)定中，某些特定的貨物不能同時(shí)裝船。10. 在危險(xiǎn)品貨物規(guī)定中，某些特定的貨物不能放在同一個(gè)貨艙中，除非它已經(jīng)清洗過了，

11、或者早就有其他的已經(jīng)經(jīng)過幾個(gè)航次貨物在這個(gè)船艙里了。11. 船舶穩(wěn)性和強(qiáng)度的要求規(guī)定了怎樣的貨物種類混合是禁止的。這些規(guī)定會(huì)在2.1節(jié)中進(jìn)一步的解釋。在實(shí)際問題中，各種一系列的限制可能是沒必要的。例如，一艘船可能轉(zhuǎn)載的貨物中沒有相沖的貨物。則危險(xiǎn)品貨物的規(guī)定則不會(huì)起作用。在大多數(shù)的情況下，最重要的是要提出一個(gè)可行的方案。任何可行的船艙積載計(jì)劃都一樣的好。然而，計(jì)劃是一個(gè)動(dòng)態(tài)情況下進(jìn)行的。這就意味著船艙分配的問題會(huì)影響到是否接受未來客戶要求的可能性。除此之外，如果船艙需要清潔，那就有把相關(guān)成本減少到最低的傾向。圖1 是一個(gè)可行的方案來簡化說明TAP，貨物1分配到船艙678貨物2分配到船艙12貨物

12、3分配到船艙34貨物4分配到船艙5678（船艙678中的貨物1已經(jīng)被清空了）。當(dāng)船離開節(jié)點(diǎn)4的時(shí)候，船是滿載的。圖 1 一條航線的例子2.1 單個(gè)即期TAP模型我們現(xiàn)在提出一個(gè)模型，它是描述在一次航行中的任何時(shí)間點(diǎn)面臨的問題，那就是說，在遵守所有限制的條件下，在船艙中完成一票貨的配載。我們這個(gè)模型叫作單個(gè)即期船艙配載問題(SITAP)。它假設(shè)不是同一票貨物不能在同一個(gè)船艙中混合裝載。定義幾個(gè)集合，如下：L-裝載的集合T-船艙的集合LLl-與第l票貨沖突的那幾票貨的集合LTt-與第t個(gè)船艙兼容的那幾票貨的集合TLl-與第l票貨兼容的船艙的集合Tlkt-如果第t個(gè)船艙裝有第l票貨，就不能裝載第k票

13、貨的船艙的集合S-穩(wěn)性和力維,比如船舶頭尾和左右平穩(wěn)。見圖2圖 2 Various dimensions around which stability and strength requirements are formed: (A) roll, (B) trim, and (C) strength.其中所用指標(biāo)的含義，如下：j,k,l-代表第幾票貨t,u-代表第幾船艙s-代表穩(wěn)性或力維定義幾個(gè)變量，如下：xlt-指示變量，當(dāng)且僅當(dāng)?shù)趌票貨被裝配到第t船艙時(shí)，xlt=1ylt-裝配到第t船艙的第l票貨的數(shù)量或體積所有的參數(shù)，如下：v1-第l票貨的體積dl-第l票貨的密度ct-第t船艙的容量bt

14、-當(dāng)?shù)趖船艙載貨時(shí)，船艙中的最小容量mst-關(guān)于第t船艙的穩(wěn)性或力維的瞬時(shí)大小ms+-就穩(wěn)性或力維，在總的時(shí)刻中的上限ms-就穩(wěn)性或力維，在總的時(shí)刻中的下限所有的限制條件，如下：lLTtxlt 1 (tT) (4)kLLl xkuMlt(1- xlt) (lL，tTLl) (5)uTlkt tTLllLms- mstdlyltms+ (sS) (6)限制條件（1）使得不違背船艙容量得到保證，并且僅當(dāng)被計(jì)劃配載到某個(gè)指定船艙的那幾票貨是能夠被裝載入那個(gè)船艙的。限制條件（2）用于調(diào)節(jié)在一個(gè)船艙中允許的最小體積，如果bt0，就可以避免在一次航行中船艙里的搖晃效應(yīng)。限制條件（3）確保整的一票貨物被裝載

15、在船上。只有一票貨物能被配載入任何給定的船艙，在限制條件（4）得以明確。限制條件（5）使得不兼容的幾票貨不能在相鄰的船艙中，因此如果第l票貨被配載入第t船艙，那么與已被裝載第l票貨的第t船艙相鄰的第u船艙中不能裝載與第l票貨不兼容的第k票貨。不等式的右邊系數(shù)Mlt = maxkTlkt，（l L，t TLl）限制條件（6）確保在考慮船舶左右和頭尾平穩(wěn)和強(qiáng)度的限制條件下船舶的穩(wěn)性。注意到與屈從于非線性表達(dá)的總的計(jì)算作對(duì)比，這些限制條件得以簡化。因此，存在一些證據(jù)表明來自于簡化的損失是較小的。SITAP模型可以被考慮為帶有一些附加限制條件的SSP模型。正如Yuceer所指出的，SSP模型是一種劃分

16、問題的類型，模型中在假定TL的情況下，將所有的T個(gè)船艙劃分配載入所有的L票貨。這樣劃分的數(shù)量是由第二張訂單的數(shù)量決定的，即S(T,L)=(1/L!)k=0L(-1)L-kLkkT。因?yàn)槊總€(gè)船艙都能裝載一票貨物，所以把所有貨物指派到所有船艙的方法的數(shù)量是由L！S(T,L)給出的。舉個(gè)例子來說，如果T=8，L=5，那么指派的數(shù)量=5！S（8,5）=1201050=126000。 我們至今尚未提出任何目標(biāo)函數(shù)，并且將推遲關(guān)于合適的目標(biāo)函數(shù)的討論，直到第二個(gè)模型被提出以后。2.2 TAP模型我們現(xiàn)在將問題轉(zhuǎn)向完整的TAP，在這個(gè)模型中，貨物通過機(jī)械動(dòng)力完成裝和卸，與港口的要求一致。我們假定一旦被裝上船

17、貨物就不能被從一個(gè)船艙移動(dòng)到另一個(gè)船艙。在某種意義上說，我們只對(duì)裝載上船的貨物感興趣（如圖Fig.1，在問題的描述中被標(biāo)記了“+”的節(jié)點(diǎn)），和對(duì)還沒有被卸下船的貨物感興趣。因此，我們不必特地地考慮卸貨（在問題描述中被標(biāo)記了“”的節(jié)點(diǎn)），除了當(dāng)船舶離開港口后，考慮對(duì)穩(wěn)性和強(qiáng)度限制時(shí)。在SITAP模型中使用的注釋仍然保留，此外再有幾個(gè)附加注釋，如下：定義幾個(gè)集合：Nl-在第l票貨裝船后，將要立即裝船的那幾票貨物。Pl-在裝裝載第l票貨之前，已經(jīng)完成裝船的那幾票貨物。Q-在符合要求將貨物裝船后的那個(gè)滿足船舶左右和頭尾平穩(wěn)限制的時(shí)刻的每個(gè)集合的組合。R-用于總和的那幾票貨的集合。定義一個(gè)變量：zlt-

18、指示變量，當(dāng)且僅當(dāng)在裝載入第l票貨之前，第t船艙清洗時(shí)，zlt =1。定義一個(gè)參數(shù)：hlkt-如果第t船艙已經(jīng)被儲(chǔ)藏了與第l票貨沖突的第k票貨，則在第l票貨被裝載入第t船艙之前，一種兼容的貨物必須被裝載入第t船艙的最小數(shù)量。 所有的限制條件，如下：（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）現(xiàn)在是用來保證在船舶航行過程中的任何

19、時(shí)刻，只有一票貨被配載入任何一個(gè)船艙。限制條件（10）沒有任何相鄰的船艙中裝載著不兼容的貨物。限制條件（11）在整個(gè)航行過程中，控制船舶的穩(wěn)性和強(qiáng)度是被要求。這個(gè)模型是通過一個(gè)限制建立的，這個(gè)限制是每一票貨的裝載必須保證穩(wěn)性和強(qiáng)度的限制，那就是說每個(gè)RQ。因此每個(gè)RQ在離港或到港的時(shí)刻與裝載的貨物符合。最后，新的限制條件（12）需要一些解釋。這些限制條件確保第l票貨在與之不兼容的第k票貨已經(jīng)被裝載去第t船艙時(shí)，不能再被配載入第t船艙。然而，有兩種例外情況：如果船艙已經(jīng)在中間被清洗過，那么這個(gè)船艙就可以被用于裝載第l票貨?；蛘?，如果自從第k票貨之后，有充足數(shù)量hlkt的另外貨物已經(jīng)裝載入了這個(gè)船

20、艙。舉例來說，考慮一票給定的貨物l，一個(gè)與第l票貨兼容的船艙t,和與第l票貨沖突但可以被裝載入第t船艙的第k票貨。集合R=PlPkk代表的是那些在第k票貨之后但在第l票貨之前裝船的貨物?？梢宰⒁馊绻趌票貨不被配載去第t船艙，則限制條件（12）不等式的左邊將很可能等于0（因?yàn)閤lt=0）,而右邊是非負(fù)。如果第l票貨被配載入第t船艙，則限制條件（12）的左邊將很可能等于hlkt（因?yàn)閤lt=1）?，F(xiàn)在，如果第k票貨也不被配載入第t船艙，則右邊一定等于hlkt（因?yàn)閤kt=0）。然而，如果第k票貨被配載入第t船艙，則右邊等于0（因?yàn)閤kt=1）。存在三種使得左邊遵從的方法：要么這個(gè)船艙在裝載第l票

21、貨之前被清洗了（這時(shí)zlt=1）,要么這個(gè)船艙在被第k票貨使用之后在第l票貨使用之前的某個(gè)j時(shí)間點(diǎn)上被清洗了（這時(shí)zjt=1）。要么一定數(shù)量hlkt的其他貨物在中間已經(jīng)被裝載入第t船艙（這時(shí)xjt=1）。還有一些限制條件沒有被考慮入模型，因?yàn)樗鼈冊(cè)陬A(yù)備階段可以被簡單地測算出來。這些適用于一些貨物不能同時(shí)存在于船上，并且在任何時(shí)候裝載的總重量必須低于一些門檻（船舶的載重噸）。2.2.1 目標(biāo)函數(shù)就這個(gè)問題有許多可能的目標(biāo)函數(shù)?？紤]燃料價(jià)格和日常運(yùn)營成本，對(duì)船公司來說最關(guān)心的是制定好的航運(yùn)決策。策略決策的成本，諸如在哪里航行和裝載什么貨物，遠(yuǎn)遠(yuǎn)大于運(yùn)營成本，諸如船艙配載。在許多現(xiàn)實(shí)世界的情況中，配

22、載計(jì)劃只有存在可行性時(shí)才有興趣去做。認(rèn)為所有的可行配載計(jì)劃是相同的是適當(dāng)?shù)?，通過使用一個(gè)常量作為目標(biāo)函數(shù)：min0 （14）就其它船舶運(yùn)營而言，根據(jù)花費(fèi)在清洗上的時(shí)間和金錢，洗艙還表一種不便。下面的目標(biāo)函數(shù)最小化了洗艙的不方便：lL t TLl當(dāng)考慮關(guān)于未來貨物（現(xiàn)在未知的）的靈活性時(shí)，其它的目標(biāo)函數(shù)是適當(dāng)?shù)?。基于有許多空艙能使得后面的時(shí)刻容納附加的貨物變得更容易的觀察，下面的目標(biāo)函數(shù)最大化了船舶航行期間的空艙平均載重量：lL t TLlkNl2.3 問題的變形正如當(dāng)前所說，在SITAP模型中的限制條件（4）用來確保每個(gè)船艙被至多一票貨物使用。這個(gè)限制條件在某些情況下顯得太嚴(yán)格了。舉了例子，如

23、果這幾票貨物是同種同質(zhì)的產(chǎn)品，并且基于精確地測量，船舶允許給定的數(shù)量能夠被裝卸。如果在這種情況下，我們能引入下面的附加注釋：wt-指示變量，當(dāng)且僅當(dāng)?shù)趖船艙被至少一票貨物使用時(shí)，wt=1那么，通過以下限制條件替換限制條件（2）和（4），我們能夠允許不止一票貨被配載到每個(gè)船艙。lLTtlLTtlLTt限制條件（17）確保配載入船艙的總?cè)萘坎怀^它的容量。任何搖晃效果通過限制條件（18）被調(diào)節(jié)。并且限制條件（19）現(xiàn)在允許不止一票貨被配載入每個(gè)船艙。與第t船艙兼容的幾票貨物的數(shù)量，在后面的限制條件能夠被變緊，如果能夠被混合在一個(gè)船艙的最大化數(shù)量的貨物是有限的。為了TAP模型，這些可供選擇的限制條件

24、很容易被擴(kuò)展，雖然我們?cè)谶@兒沒有列出所有的限制條件。為了允許在第t船艙里混合第l票貨和第k票貨，我們必須要有兩個(gè)條件：（1）k LlL 或者t Tlkt 和（2）l LkL 或者t Tklt ,因?yàn)榉駝t混合將被限制條件（5）限制。因此，限制條件（5）使得模型能夠獲得當(dāng)一些貨一點(diǎn)都不能混合時(shí)，一些貨能夠在一些特定的船艙被混合，但不能在其它的船艙混合。TAP模型的另一個(gè)假設(shè)，一旦那幾票貨物已經(jīng)被儲(chǔ)存在船上，它們不能在船艙間被移動(dòng)。在散貨運(yùn)輸可能的現(xiàn)實(shí)情況中這個(gè)限制條件不能被保證。最合適的解決不同貨物能夠在船艙中移動(dòng)情況的方法能夠被可論證地更改模型，通過在變量中引進(jìn)時(shí)間指標(biāo)，引入變量xlti代表第l

25、票貨是否在i 時(shí)刻被配載入第t船艙。然而，我們希望指出這種情況能夠被處理，通過使用存在的模型。舉個(gè)例子，如果不考慮洗艙，那么關(guān)于移動(dòng)貨物的問題能夠被解決，通過在每一段航程中解決一系列SITAP實(shí)例。存在許多其它能夠被想象的問題的變形，舉個(gè)例子通過放寬要么限制條件（5）要么限制條件（6）。此外，正如前面章節(jié)所論述的，存在著許多可能的目標(biāo)函數(shù)。提出模型的幾個(gè)變形的主要原因是為了傳達(dá)真實(shí)的海上運(yùn)輸問題出現(xiàn)了無數(shù)的變形，并且每個(gè)船公司都有必須遵守的他們自己的限制條件和程序。我們已經(jīng)提出了TAP模型作為我們的主要模型，因?yàn)槲覀冋J(rèn)為它已經(jīng)足夠容納各種各樣可能發(fā)生的真實(shí)世界的配載情況，并且該模型為海上散貨運(yùn)

26、輸配載問題的研究可能形成一個(gè)合適的起點(diǎn)。2.4 復(fù)雜性分析TAP在計(jì)算上是棘手的，在某種意義上說，找到解決問題的可行的方法就是NP-Complete。事實(shí)上，一個(gè)SITAP模型的簡化變形就是NP-Complete，使用一個(gè)與Barbucha關(guān)于SSP的論文中相似的論據(jù)來得以證明。不正式地說，TAP是SITAP的一個(gè)一般形式，并且SITAP是SSP的一個(gè)一般形式。因此找到解決SSP的可行的方法是NP-Complete，則就等于找到解決要么TAP要么SITAP的可行的方法也是NP-Complete。在下面我們給出了一個(gè)證明解決SITAP的可行方法是NP-Complete的正式的論據(jù)，通過對(duì)已知的N

27、P-Complete劃分問題(PP)的簡化。定義，由n個(gè)數(shù)組成的集合A=a1,a2,an,PP是決定是否存在A的一個(gè)劃分，由此而得兩個(gè)子集合A1和A2，滿足jA1 aj=jA2aj定理2.1 讓單一即期船艙配載可行性問題（SITAFP）代表找到解決SITAP可行的方法的問題。SITAFP就是NP-Complete。論證，容易看到SITAFP的解決方法能在多項(xiàng)式時(shí)間中被證實(shí)，因此SITAFP就是在NP中。在多項(xiàng)式時(shí)間中PP能被簡化為SITAFP，也就是說SITAFP就是NP-Complete。仍然能表示任何PP的實(shí)例能怎樣被轉(zhuǎn)化成SITAFP的實(shí)例，也就是說當(dāng)且僅當(dāng)存在一個(gè)解決SITAFP實(shí)例的

28、方法時(shí)，存在一個(gè)解決PP實(shí)例的可行方法。通過由n個(gè)數(shù)組成的集合A=a1,a2,an,拿任何PP的實(shí)例來具體說明。用n個(gè)船艙，T=1,2 ,n和兩票貨物L(fēng)=1,2來建立一個(gè)SITAFP實(shí)例。設(shè)置每票貨的容量vl=0.5jA aj,并設(shè)置船艙的容量等于集合A中的每個(gè)數(shù)的大小，ct=at。讓TLl=T因?yàn)閘L并讓LTt=L因?yàn)閠T。現(xiàn)在在A1和A2中考慮一個(gè)解決PP可行的方法。一個(gè)與SITAFP一致的可行的解決方法能夠通過如果atAl并且ylt=0使得ylt=at而找到?，F(xiàn)在考慮存在一個(gè)解決SITAFP實(shí)例的方法。在那種情況下，一個(gè)PP的解決方法能通過當(dāng)且僅當(dāng)ylt=at時(shí)在Al增加at來被找到?？?/p>

29、以注意到不存在0yltat，因?yàn)橐凰掖目側(cè)萘康扔谳d貨的總體積，并且在一個(gè)船艙中混合兩票貨物是不被允許的。3 計(jì)算研究在第二節(jié)我們介紹了TAP和它的幾個(gè)變形。這一節(jié)的重點(diǎn)是(1)(3),(7)(8)的主要結(jié)構(gòu)，（14）（15）（16）的運(yùn)用，目的是創(chuàng)造出各種不同的Tap的現(xiàn)實(shí)樣品，這些現(xiàn)實(shí)樣品可以被用來計(jì)算研究，以便于獲得解決由海運(yùn)散貨航運(yùn)公司面臨TAP方案的評(píng)估難度。3.1節(jié)描述了樣品的生產(chǎn)，計(jì)算研究的結(jié)果3.2節(jié)給出。3.1 樣品產(chǎn)生由于TAP是一個(gè)一般的模型，這就允許更多類型的樣品可以在一個(gè)單一的計(jì)算研究被探討。因此，這里產(chǎn)生的樣品受制于一下參數(shù)。圖3說明了兩只油船的結(jié)構(gòu)配置，樣品是依據(jù)

30、這些為基礎(chǔ)的。一個(gè)是一個(gè)相對(duì)小的船，能裝載1000m3（8000自重噸）分布在24個(gè)貨艙。另一個(gè)是一個(gè)相對(duì)較大的船，45000m3的容積（39000自重噸）和38個(gè)貨艙。依據(jù)每艘船貨艙的配置可以計(jì)算穩(wěn)定性限制。有兩種類型的貨艙,一架采用不銹鋼,另一種是用鋅硅酸鹽涂料,后者彩色灰色圖3。簡單來說，我們假設(shè)負(fù)載可以分三類：第一類負(fù)載分配至任何貨艙而不是與其他貨載沖突；第二類負(fù)載分配至任何貨艙但是與第三類負(fù)載沖突；第三類負(fù)載只能分配在有鋅硅酸鹽涂料的貨艙并與在第二類第三類的負(fù)載沖突。在負(fù)載l和負(fù)載k沖突的情況下，我們將（Tlkt-如果第t個(gè)船艙裝有第l票貨，就不能裝載第k票貨的船艙集合）Tlkt 為

31、貨艙的一部分在t的一旁。見圖3。對(duì)于每個(gè)樣品，10負(fù)載將被考慮到固定的地方，也就是，他們形成這艘船過去的歷史，影響哪個(gè)貨艙是干凈的哪個(gè)貨艙將被使用。為了產(chǎn)生各種各樣的樣品，不同的值考慮以下五參數(shù): 貨艙的數(shù)量取決于船舶的選擇，T24（小船）和T38（大船）的設(shè)置標(biāo)簽。 負(fù)載的數(shù)量（包括10個(gè)固定的負(fù)載），給20負(fù)載、30負(fù)載、40負(fù)載分別設(shè)置標(biāo)簽L20、L30和L40。 對(duì)各種負(fù)載的可能分布，標(biāo)記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%的負(fù)載來源于第一類負(fù)載，40%來源于第二類負(fù)載，0%來源

32、于第三類。 最低（最大）艙容利用率在裝貨（卸貨）之前就會(huì)出現(xiàn)，標(biāo)記F1（0.65,0.35）,F2(0.75,0.25)和F3(0.85,0.15)，這就是，用F1產(chǎn)生的路線上，船將會(huì)開始去提取貨物的地點(diǎn)提貨直到船舶總負(fù)載超過船舶容量的65%，然后去交貨地點(diǎn)直到船上總負(fù)載低于船舶容量的35%，然后再去提取貨物的地點(diǎn)。這些限制進(jìn)而影響交貨和取貨順序是怎么樣被混雜的在路線生成的情況下。圖4是對(duì)F1生成樣品TAP_T24L20C3F1S3_01的說明。 負(fù)載大小的分配，標(biāo)記S3（1000-5000m3）,S6（3000-9000 m3）和S12（8000-16000 m3）。在S3的情況下，意味著負(fù)

33、載的大小遵循均與分布，在1000-5000 m3之間。有兩艘船的設(shè)計(jì)（不是規(guī)模）用于產(chǎn)生測試樣品，上方是一個(gè)24個(gè)油艙和容積10000m3的小船，下方是一個(gè)38個(gè)油艙和容積45000 m3 的大船。樣品被隨機(jī)地生成為每個(gè)這些情況的組合設(shè)置，除了T24、S12的組合（船太小不能考慮負(fù)載）和T38、S3的組合。每組設(shè)置生成5個(gè)樣品，144組設(shè)置共720個(gè)樣品。在樣品生成期間，用3.2章節(jié)描述的方法證明，結(jié)果表明可行性解存在。表1部分顯示了TAP_T24L20C3F1S3_01樣品，給出了裝貨和卸貨的順序，每次負(fù)載的種類和體積，另外貨艙的分配以及部分樣品的貨艙分配。解決這個(gè)樣品相當(dāng)于填寫表格右下部分

34、的數(shù)據(jù)，說明每個(gè)負(fù)載怎樣被分配到可行的貨艙中，這樣所有限制問題也不會(huì)被違反。樣品和樣品生成器可以從作者的要求中獲得。3.2 結(jié)果盡管TAP是非完全多項(xiàng)式而因此從理論角度是難以計(jì)算的，實(shí)際大小樣品能否在實(shí)踐中高效的被解決這個(gè)問題仍沒有答案。計(jì)算研究已經(jīng)進(jìn)行了正如3.1章節(jié)描述的用720個(gè)樣品。這里出現(xiàn)的主要結(jié)果是通過商業(yè)上可行的整數(shù)規(guī)劃求解模型CPLEX v.11在Intel2.66GHz處理器上運(yùn)行得出的。有一些實(shí)驗(yàn)室用來評(píng)估各種的求解設(shè)置。第一步，我們運(yùn)用目標(biāo)函數(shù)（15）作為我們的主要目標(biāo)函數(shù)，并檢查標(biāo)準(zhǔn)設(shè)置和是否集中證明最優(yōu)或找出第一個(gè)可行辦法的不同。第二步，當(dāng)我們用CPLEX試圖找出可行

35、解的時(shí)候我們分別運(yùn)用函數(shù)（14）-（16）進(jìn)行比較。第三步，我們看看通過CPLEX跨過標(biāo)準(zhǔn)的選擇改變個(gè)人變量的分支的優(yōu)先選擇。四個(gè)選擇測試：（1）所有變量的平等優(yōu)先（標(biāo)準(zhǔn)優(yōu)先）；（2）xlt比xkt if |TLl|TLk|更高級(jí)優(yōu)先（艙容優(yōu)先）；（3）xlt比xkt （如果 l 裝載k的前面）更高級(jí)（時(shí)間優(yōu)先）；（4）z變量的更高級(jí)優(yōu)先（清潔優(yōu)先）。研究主要是運(yùn)用CPLEX集中找出TAP的可行辦法。然而，如果可行解是有針對(duì)性的，基于限制變成的求解方法有潛在的好處。作為一種測試假設(shè)的方法，樣品通常被運(yùn)用約束求解的模型MINION建模和解決。MINION 是一個(gè)通用的約束求解方法，被當(dāng)做一個(gè)黑盒

36、用。我們注意到當(dāng)大多數(shù)的TAP用MINION輸入語言建模時(shí)很容易的時(shí)候，y變量肯定是離散的。當(dāng)檢查實(shí)際大小的樣品是否能通過CPLEX和MINION高效處理的時(shí)候，我們旨在建立哪一個(gè)問題的維度有助于創(chuàng)建實(shí)踐中難以解決的樣品。表2總結(jié)了第一個(gè)測試的結(jié)果。CPLEX被分配了600秒的時(shí)間來解決這720個(gè)樣品中的每個(gè)樣品。圖表的結(jié)果來自三次運(yùn)營，每次都是運(yùn)用目標(biāo)函數(shù)（15）：一個(gè)是標(biāo)準(zhǔn)值；一個(gè)是找出一個(gè)可行解，第三個(gè)是證明方案的最優(yōu)化。所有的樣品一起給出了平均結(jié)果。因此，L20子集包括所有的樣品，這些樣品包括20負(fù)荷（其中的10負(fù)荷認(rèn)為是固定的，剩下的10個(gè)要求規(guī)劃）。我們認(rèn)為函數(shù)（15）是主要的目標(biāo)

37、函數(shù)，因?yàn)殛P(guān)于清潔貨艙有一個(gè)直接的可衡量的不便。對(duì)于每個(gè)求解設(shè)置和樣品子集，我們報(bào)告了能求出可行解的樣品，能證明最優(yōu)的樣品以及找出第一個(gè)可行解所用的平均時(shí)間。 在第一次測試中我們發(fā)現(xiàn)在發(fā)現(xiàn)可行解的數(shù)量上沒有大的不同：當(dāng)計(jì)算可行解或最優(yōu)解得時(shí)候，有4-12組的情況是沒有解得在600秒內(nèi)。然而，找到可行解的平均的時(shí)間將會(huì)是兩倍以上如果沒有一個(gè)明確專注于可行性分析。被證明最優(yōu)解答的數(shù)量稍低了一點(diǎn)當(dāng)有一個(gè)最優(yōu)焦點(diǎn)而不是標(biāo)準(zhǔn)設(shè)置的時(shí)候，但是預(yù)期會(huì)更低如果有可行性焦點(diǎn)。因?yàn)榭尚行允强紤]的一個(gè)主要因素，在余下的測試中我們主要是找出可行解。我們可以通過表2哪些因素加大了尋找可行解的難度。很容易看出來，隨著負(fù)載

38、的增加，這些事例變得更加困難，在600秒內(nèi)發(fā)現(xiàn)可行解和最優(yōu)解的數(shù)量都在減少，而找到第一個(gè)可行解的時(shí)間在增加，隨著三種貨物數(shù)量的增加，會(huì)導(dǎo)致更多的貨物與其他的貨物產(chǎn)生沖突的機(jī)會(huì)增加，并且找到可行解的時(shí)間也增加了，可以被證明的可行解的數(shù)量也減少了。F1-F3包含了各種記載利用率的例子，F(xiàn)1看起來好像給出的比其他兩種簡單，但是對(duì)于其他結(jié)果的解釋不是太明顯。最后，這些建立在24艙船的實(shí)例比38艙船的要簡單，裝載小的要比裝載量大的難，這些主要是由于不同船的配置結(jié)構(gòu)不同，而并非單是船艙個(gè)數(shù)或體積造成的。第二個(gè)測試說明了在優(yōu)化船艙配載時(shí)不同的目標(biāo)函數(shù)所產(chǎn)生的影響，表格3給出了（14）-（16）這三種目標(biāo)函數(shù)的運(yùn)行結(jié)果。這個(gè)表