集裝箱碼頭堆場(chǎng)出口箱堆放位置分配問題

1、集裝箱碼頭堆場(chǎng)出口箱堆放位置分配問題摘要 ：隨著全球化步伐的加快和國(guó)家貿(mào)易的迅猛增長(zhǎng)， 集裝箱運(yùn)輸已成為連接全 球供應(yīng)鏈至關(guān)重要的一環(huán)。 港口作為現(xiàn)代物流系統(tǒng)中的重要節(jié)點(diǎn)， 是海陸運(yùn)輸?shù)?樞紐，愛全球化制造和國(guó)家貿(mào)易中扮演著不可或缺的角色。堆場(chǎng)是集裝箱碼頭的重要資源， 是港口的重要組成部分， 其堆場(chǎng)集裝箱堆位 分配優(yōu)劣直接影響碼頭整體的運(yùn)作效率。 本文著重以集裝箱碼頭堆場(chǎng)出口箱堆位 分配為研究?jī)?nèi)容， 分為出口箱堆場(chǎng)空間場(chǎng)位問題和具體儲(chǔ)存位置分配問題， 運(yùn)用 混合整數(shù)規(guī)劃和混合序列疊加算法兩個(gè)階段進(jìn)行探討和研究。關(guān)鍵詞 ： 集裝箱碼頭 儲(chǔ)位分配 混合整數(shù)模型 啟發(fā)式算法一緒論問題背景隨著全球經(jīng)濟(jì)

2、一體化的迅猛發(fā)展， 一方面企業(yè)的采購(gòu)倉(cāng)儲(chǔ)銷售配送等 協(xié)作關(guān)系日趨復(fù)雜， 全球采購(gòu)全球銷售本土化生產(chǎn)的趨勢(shì)越來越明顯。 國(guó)家 經(jīng)濟(jì)與世界經(jīng)濟(jì)的發(fā)展更加緊密地融合在一起。 這對(duì)于物流服務(wù)的速度以及吞吐 量提出了更高的要求；另一方面，經(jīng)濟(jì)全球化在本國(guó)企業(yè)帶來新的機(jī)遇的同時(shí)， 也帶來了巨大的挑戰(zhàn)。 企業(yè)面臨的競(jìng)爭(zhēng)日益加劇， 如何降低企業(yè)的生產(chǎn)經(jīng)營(yíng)成本 以增強(qiáng)盈利能力擺在所有企業(yè)面前的一道難題， 而如何通過科學(xué)的手段在不影響 物流服務(wù)水平的前提下降低物流成本， 成為了各個(gè)企業(yè)關(guān)注的焦點(diǎn)， 也成為研究 的熱點(diǎn)。集裝箱運(yùn)輸?shù)牟粩喟l(fā)展，一方面導(dǎo)致目前國(guó)內(nèi)許多集裝箱碼頭超負(fù)荷工作， 給集裝箱碼頭運(yùn)用管理人員的日

3、常決策帶來了很多困難。 為緩解集裝箱運(yùn)輸業(yè)發(fā) 展所帶來的壓力， 國(guó)內(nèi)許多港口城市競(jìng)相規(guī)劃和建設(shè)大型集裝箱深水碼頭， 規(guī)模 和投資十分巨大，這些設(shè)施的建設(shè)和投入使用無(wú)疑對(duì)我國(guó)區(qū)域經(jīng)濟(jì)的發(fā)展有著重 要的推動(dòng)作用。 另一方面， 由于集裝箱碼頭企業(yè)管理模式?jīng)]能與時(shí)俱進(jìn)， 因而導(dǎo) 致企業(yè)成本居高不下，通過能力低下，造成生產(chǎn)能力的浪費(fèi)。這些因素的存在， 嚴(yán)重制約集裝箱碼頭企業(yè)競(jìng)爭(zhēng)力的提升。線代集裝箱碼頭高度機(jī)械化的作業(yè)特點(diǎn)決定了其固定設(shè)備的投資是十分巨 大的，作為其經(jīng)營(yíng)主題的碼頭公司必須考慮企業(yè)的生存盈利問題， 因此不可能無(wú) 限制的投入機(jī)械設(shè)備。 同時(shí)，集裝箱碼頭即使規(guī)模再大， 其堆場(chǎng)和泊位等資源也 是有

4、限的。因此，通過注重現(xiàn)有資源的挖掘，逐步提高資源的綜合利用率，成為 提升集裝箱碼頭作業(yè)效率的根本途徑。面對(duì)集裝箱碼頭的大型化和作業(yè)的復(fù)雜化高效化， 傳統(tǒng)的基于人工經(jīng)驗(yàn)的 計(jì)劃方式已經(jīng)越來越難以提供一個(gè)合理優(yōu)化的作業(yè)方案， 因此對(duì)于集裝箱碼頭作 業(yè)效率起著關(guān)鍵作用的碼頭資源優(yōu)化調(diào)度問題， 越來越受到人們的重視， 這對(duì)我 國(guó)正在加速發(fā)展的集裝箱碼頭行業(yè)有重大的意義， 因此開展這方面的研究勢(shì)在必 行。問題提出 在集裝箱計(jì)劃中最重要的目標(biāo)就是保證岸邊作業(yè)效率，減少船舶在港周轉(zhuǎn) 時(shí)間。進(jìn)出口集裝箱的生產(chǎn)作業(yè)流程是不同的， 進(jìn)口箱大批大港， 提箱時(shí)間不可 預(yù)測(cè)。出口箱由于隨機(jī)到港， 所以船方和港口需要根據(jù)

5、箱子目的地和尺寸制定嚴(yán)格的堆存及船舶積載計(jì)劃一確保船舶穩(wěn)性，裝船要求。二正文根據(jù)閱讀相關(guān)集裝箱碼頭堆場(chǎng)問題的學(xué)術(shù)研究， 我們發(fā)現(xiàn)針對(duì)出口箱的堆場(chǎng) 堆存位置分配問題沒有較深入的研究。本文將運(yùn)用系統(tǒng)方法論研究該問題。目的：通過充分利用堆場(chǎng)的存儲(chǔ)空間， 出口箱在堆場(chǎng)和碼頭前沿之間的高效 運(yùn)輸與降低運(yùn)輸距離和倒箱操作量來提高出口箱的裝船效率。2. 問題描述和解決方法問題描述 集裝箱碼頭出口生產(chǎn)作業(yè)流程： 外部集卡道口閘口堆場(chǎng)場(chǎng)橋堆場(chǎng) （具體位置） 場(chǎng)橋集卡岸橋 在船舶抵港前，船方會(huì)根據(jù)集裝箱發(fā)往目的地分類編制粗略的配積載計(jì)劃， 提交給港口和航線經(jīng)營(yíng)人等相關(guān)部門企業(yè)， 港口根據(jù)船方提供的積載計(jì)劃和箱子

6、信息制定詳細(xì)具體的配記載計(jì)劃。 儲(chǔ)存計(jì)劃指定堆場(chǎng)具體位置的集裝箱將要裝載 的船上的具體位置。 制定計(jì)劃時(shí)要滿足船舶的穩(wěn)性要求和減小岸橋和堆場(chǎng)設(shè)備的 使用負(fù)荷。我們知道出口箱被儲(chǔ)存在堆場(chǎng)街區(qū)中 （BLOC）K，每個(gè)街區(qū)有 2030 個(gè)場(chǎng)位（場(chǎng) 貝位）組成，堆垛高度 45 層。每個(gè)場(chǎng)位一般安排并列的六列集裝箱（如圖一） 。 一般情況下出口箱在船舶離港前 34 天集港，為了提高裝船效率集裝箱需要被安 排在最佳的位置。 但是由于集裝箱集港具有隨機(jī)性， 不能保證理想的出口箱的布 局堆放。一種有效的方法是根據(jù)集裝箱的目的地和重量在裝船前在堆場(chǎng)進(jìn)行分組作 業(yè)。此種作業(yè)需要一個(gè)堆場(chǎng)緩沖區(qū)域， 留作集港集裝箱臨

7、時(shí)堆放， 同時(shí)需要更多 的裝卸搬運(yùn)工作量， 通常情況是在保證船舶裝船的前提下利用設(shè)備空閑時(shí)間進(jìn)行 操作作業(yè)。 港方在進(jìn)行港口布局規(guī)劃時(shí)， 因?yàn)殛懹蛎娣e的限制此種方法通常不能 實(shí)現(xiàn)。因此決定堆場(chǎng)中出口箱的合理堆放位置對(duì)于提高港口的生產(chǎn)率， 降低船舶在 港時(shí)間來說是至關(guān)重要的一個(gè)環(huán)節(jié)。圖一解決方法 堆場(chǎng)堆放位置分配問題涉及每艘船舶出口箱的堆放場(chǎng)位空間問題和具體的 堆放位置問題。以上問題通過以下兩個(gè)階段進(jìn)行研究：（1）場(chǎng)位分配：第一階段決定出口集裝箱的場(chǎng)位空間位置和每個(gè)場(chǎng)位數(shù)量以滿 足減少出口作業(yè)時(shí)集卡在堆場(chǎng)和岸橋之間的搬運(yùn)時(shí)間和均衡每個(gè)場(chǎng)位的工作量。（2）具體堆放位置：第二階段在第一階段分配的場(chǎng)位

8、中決定具體的堆放位置， 目的是減少裝船作業(yè)的倒箱操作。以上問題構(gòu)建模型如下。3. 構(gòu)建模型出口箱場(chǎng)位分配該問題運(yùn)用混合整數(shù)規(guī)劃模型 （MIP）。場(chǎng)位和每個(gè)場(chǎng)位位置數(shù)量在計(jì)劃期內(nèi) 決定。假設(shè)條件如下：（1）因?yàn)檠b卸系統(tǒng)的分配問題超出本課題研究范圍，故假定出口箱生產(chǎn)作 業(yè)過程中設(shè)計(jì)的設(shè)備數(shù)量充足。（2）預(yù)計(jì)到港船舶泊位分配已知。（3）假定集裝箱尺寸為同一規(guī)格；場(chǎng)橋的工作量按照處理的集裝箱數(shù)量計(jì) 算；集裝箱堆場(chǎng)堆放原則不同尺寸的集裝箱堆放在不同街區(qū)； 因此我們的研究方 法不受集裝箱的規(guī)格大小的直接影響，不同尺寸的箱子能被分離成獨(dú)立的問題。（4）堆場(chǎng)中進(jìn)出口箱不堆放在同一街區(qū)。（5）通常船舶航線掛靠幾

9、個(gè)港口，不同目的地的出口集裝箱不堆放在同一 場(chǎng)位。因?yàn)橥M的集裝箱會(huì)被裝到船舶的相近位置， 所以該原則能夠減少倒箱操 作。4,5 假設(shè)基于上海港的集裝箱碼頭的真實(shí)情況。符號(hào)定義堆放出口箱的場(chǎng)位總數(shù)S L 計(jì)劃期內(nèi)將裝船的船舶集S 計(jì)劃期內(nèi)的所有船舶集場(chǎng)位 i 1 i B 街區(qū) k 1 kK i 場(chǎng)位 i 占的集裝箱街區(qū)數(shù)D j 船舶 j 掛靠的港口數(shù)量K堆場(chǎng)堆放出口箱的街區(qū)總數(shù)BSA計(jì)劃期內(nèi)應(yīng)該被分配位置的船舶的集合 合SS以前計(jì)劃期已經(jīng)被分配的船舶集合合S=SASLSSij 船舶 j kCi 場(chǎng)位 i 的堆存容量 b 量mj 船舶 j 能夠裝載的最大集裝箱貝位數(shù)量j SAVio計(jì)劃期場(chǎng)位 i

10、 的集裝箱初始數(shù)量 1 i BNj計(jì)劃期內(nèi)裝往船舶 j 的集裝箱到港堆場(chǎng)的預(yù)計(jì)數(shù)量 j SA Bj 船舶 j 已經(jīng)分配的集裝箱堆放場(chǎng)位集合； j SSA 表示來自 SA 不能分配dij 場(chǎng)位 i 與船舶 j 的泊位之間的搬運(yùn)運(yùn)輸距離 決策變量xij 計(jì)劃期內(nèi)堆放在場(chǎng)位 i 中裝往 j 船舶的集裝箱數(shù)量 j SAij 1 如果裝往船舶 j 的集裝箱堆放在場(chǎng)位 i, 為 1，j SA。；否則為 0；對(duì)于 j SSA ，ij 在以前的計(jì)劃期決定。Mj船舶 j 分配的總場(chǎng)位數(shù) j SA ；j SSA ，在以前的計(jì)劃期決定。Vi 場(chǎng)位 i 計(jì)劃期末的總集裝箱數(shù)量W k計(jì)劃期內(nèi) k 街區(qū)的工作量目標(biāo)函數(shù)：

11、約束條件：目標(biāo)函數(shù)和約束條件說明：屬于船舶 j 的出口箱 i 在場(chǎng)位堆放位置與岸橋之間的運(yùn)輸距離取決于每艘船 舶分配的空間位置。 （1）第一個(gè)式子表示總運(yùn)輸距離最??；第二個(gè)式子說明計(jì)劃期內(nèi)每個(gè)場(chǎng)位堆放 的集裝箱數(shù)量不均衡； w1 和 w2 作為調(diào)整兩個(gè)目標(biāo)重要性的權(quán)重 （2）計(jì)劃期末場(chǎng)位中集裝箱的總數(shù)量（3）保證每個(gè)場(chǎng)位的集裝箱數(shù)量在允許的范圍內(nèi)，是每個(gè)場(chǎng)位允許堆放集裝 箱的密度。在實(shí)際生產(chǎn)操作中需要有剩余空間進(jìn)行倒箱操作（ 4）表示裝往 j 船舶的集裝箱占用的場(chǎng)位將在下一個(gè)計(jì)劃期可用， j SL （5）確保計(jì)劃期內(nèi)每個(gè)船舶的空間需求（6）定義變量，（7）保證裝往不同船舶的集裝箱不混合在相同場(chǎng)

12、位（ 8）表示屬于船舶 j 的集裝箱所在場(chǎng)位的數(shù)量（ 9）確保船舶安排的場(chǎng)位數(shù)量大于或等于 Dj（ 10）規(guī)定用于裝往船舶 j 的集裝箱堆場(chǎng)的場(chǎng)位最大數(shù)量， 能避免集裝箱分布于 太大區(qū)域（11）計(jì)劃期內(nèi)安排的場(chǎng)位數(shù)量不能超過碼頭可利用的場(chǎng)位數(shù)量（12）表示計(jì)劃期內(nèi)集裝箱的工作量即處理的集裝箱數(shù)量（13）保證變量無(wú)負(fù)值（ 14）0-1 問題 目標(biāo)函數(shù)不是線性規(guī)劃模型，故采取如下方法進(jìn)行轉(zhuǎn)換： 定義P= Q=目標(biāo)函數(shù)轉(zhuǎn)變?yōu)榧s束條件增加如下：新的線性規(guī)劃模型等價(jià)于原始的規(guī)劃模型。決定出口箱的具體堆存位置 第一階段的模型解決了發(fā)往不同船舶的出口箱的場(chǎng)位分配問題， 該階段研究 的目的是合理在選擇好的場(chǎng)位

13、中安排集裝箱，最終的布局能夠使裝船效率最大 化。問題描述該階段出口箱會(huì)被按集裝箱的重量級(jí)分組， 我們基于上一階段分配的場(chǎng)位提 出一個(gè)方法論來解決具體的場(chǎng)位問題。 目標(biāo)是減少生產(chǎn)作業(yè)時(shí)的倒箱作業(yè)。 假定 在一個(gè)確定場(chǎng)位內(nèi)， 重箱先于輕箱裝船。 對(duì)于不同重量級(jí)的集裝箱生產(chǎn)作業(yè)時(shí)會(huì) 比較復(fù)雜。例如，有的場(chǎng)位的集裝箱裝船時(shí)，輕箱先于重箱裝載。通常情況，重箱更可能先裝船。因此如果重箱堆放在低層時(shí)，將會(huì)產(chǎn)生倒箱操作、序列疊加決定出口集裝箱堆場(chǎng)堆放場(chǎng)位中的具體位置是一個(gè)實(shí)時(shí)決策問題， 很難找到 全局優(yōu)化程序去解決。 序列疊加被廣泛應(yīng)用于實(shí)踐當(dāng)中， 相同重量級(jí)別的箱子被 堆放在同層或堆疊。圖二展示了一個(gè)序列疊

14、加的構(gòu)架。 每個(gè)位置的數(shù)字代表該處集裝箱的重量級(jí) 別，數(shù)字越大，代表的重量級(jí)別越高，垂直堆放考慮 5 個(gè)重量級(jí)，水平堆放考慮 4個(gè)重量級(jí)，圖中空格處是預(yù)留的集裝箱堆放緩沖區(qū)域。由于集裝箱集港的隨機(jī) 性，很難獲得圖二所示的理想貝位模型。在堆放過程中會(huì)發(fā)生大量的倒箱操作。 例如，圖二 a 中的垂直堆放方法， 如果大量重箱先到達(dá)堆場(chǎng)， 卡車通道附近很快 就會(huì)被堆滿， 因此在輕箱到達(dá)時(shí)場(chǎng)橋堆箱移動(dòng)會(huì)變得非常困難。 對(duì)于圖二 b 的水 平堆放，同樣重箱先到，必須將其放入緩沖區(qū)域等輕箱到港才能進(jìn)行堆放在場(chǎng)位。垂直堆放 水平堆放圖二 序列疊加混合序列堆加此部分我們提出混合序列疊加的方法來彌補(bǔ)上述序列疊加的不

15、足， 混合序列 疊加能夠獲得到港集裝箱任意最佳的儲(chǔ)存位置。圖三展示了運(yùn)用混合序列疊加得到的一個(gè)理想的貝位配置模型。 數(shù)字代表與 上述相同，不在過多贅述。 每列集裝箱的重量級(jí)向上依次遞增， 重箱堆放在左上 部分，輕箱在右下的位置。 相同重量級(jí)的集裝箱堆放在不同層或不同列， 此堆放 方法能夠在集裝箱進(jìn)場(chǎng)決定位置時(shí)時(shí)獲得更優(yōu)化的結(jié)果。 方法的另一個(gè)優(yōu)點(diǎn)是裝 船作業(yè)時(shí)左上方取走后會(huì)留下合適的空間便于場(chǎng)橋操作，加快港口生產(chǎn)率。圖三中場(chǎng)位集裝箱重量級(jí)分 9 個(gè)集合，利用協(xié)調(diào)重量級(jí)的方法每個(gè)場(chǎng)位包括 多個(gè)最佳的儲(chǔ)存位置。 例如，重量級(jí)為 6 的集合有 4 處最佳的堆放位置。 該方法 不局限于 9 個(gè)級(jí)別，管

16、理調(diào)度人員可以根據(jù)所在港口集裝箱量， 貨物種類等多方 面考慮合適的連續(xù)重量級(jí)別。圖三 貝位理想配置圖混合序列疊加算法（ HHSA）符號(hào)定義：Wmin,Wmax集裝箱重量范圍 W c 集裝箱 c 的重量Lc集裝箱 c 重量級(jí)別 l 重量級(jí)別 lSl重量級(jí)為 l 的最佳集裝箱位置集合（xl,yl）集合 Sl 位置的幾何中心 （xc,yc） 集裝箱 c 的最佳存儲(chǔ)位置（xcs,y cs）集裝箱 c不屬于集合 Sl, 的可利用儲(chǔ)存位置通過下列式子可以根據(jù)給出的集裝箱 c 的重量來計(jì)算重量級(jí)別 LC ：一般規(guī)則延伸為重箱堆放位置在左上，輕箱的堆放位置在右下。 根據(jù)問題屬性可以得到解決問題的優(yōu)化方案。4. 算例應(yīng)用略5. 結(jié)論集裝箱碼頭堆場(chǎng)堆放位置分配問題直接與生產(chǎn)作業(yè)效率相關(guān)， 集裝箱進(jìn)港的 隨機(jī)性給問題的解決帶來了很大難度。 本文將問題轉(zhuǎn)化為兩個(gè)階段， 第一階段主 要解決出口不