集裝箱倒箱問題的模型與啟發(fā)式算法研究

郭瑞智,史瑪君,林昊堃

(1.武漢大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,湖北武漢 430072)(2.中國地質(zhì)大學(xué)(武漢)環(huán)境學(xué)院,湖北武漢 430074)

集裝箱倒箱問題的模型與啟發(fā)式算法研究

郭瑞智1,史瑪君1,林昊堃2

(1.武漢大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,湖北武漢 430072)(2.中國地質(zhì)大學(xué)(武漢)環(huán)境學(xué)院,湖北武漢 430074)

本文研究了集裝箱堆場中集裝箱搬運(yùn)的優(yōu)化問題.利用以7個倒箱落位步驟為核心的啟發(fā)式算法,建立軌道式龍門機(jī)取箱作業(yè)的數(shù)學(xué)模型,獲得了最小化倒箱量的方法.推廣了大規(guī)模倒箱問題的結(jié)果,具有較好的實際意義.

軌道式龍門機(jī);大規(guī)模倒箱;倒箱量;啟發(fā)式算法

1 引言

隨著經(jīng)濟(jì)全球化的不斷深入,我國的進(jìn)出口貿(mào)易不斷增長,隨之帶來港口集裝箱吞吐量的急劇增長,尤其在上海、廣州、重慶等這樣的大港,業(yè)務(wù)量更是幾年前的好幾倍.然而由于整體規(guī)劃以及資金的考量,集裝箱堆場碼頭的面積和工作區(qū)域并沒有明顯的擴(kuò)大.如何在有限的條件下提高碼頭的運(yùn)作效率,便成為了當(dāng)務(wù)之急.

在過去十幾年,集裝箱吞吐量并不大的時候,碼頭多采用輪胎式龍門機(jī)作為調(diào)運(yùn)集裝箱的起重機(jī).該起重機(jī)起重量、跨距均較小,移動速度快,方便靈活,很適合中小碼頭的運(yùn)作.隨著科技的發(fā)展以及集裝箱吞吐量的增長,輪胎式龍門機(jī)的弊端也顯現(xiàn)出來：無法滿足大貝位垛堆集裝箱的移動,運(yùn)行成本、維修成本較高,軌道式龍門機(jī)應(yīng)運(yùn)而生.比起輪胎式龍門機(jī)跨中只能堆放6列集裝箱,軌道式龍門機(jī)場地利用率更高,跨中一般可堆放8-15列集裝箱.因此越來越多的碼頭開始采用該起重機(jī)作為調(diào)運(yùn)集裝箱的工具.

為了提高碼頭的運(yùn)作效率,除了采用更為先進(jìn)的設(shè)備外,減少提箱過程中集裝箱倒箱次數(shù)也是一個重要的因素.在集裝箱堆場中,豎直擺放的一列集裝箱叫作一個棧,并排擺放的幾列棧稱為一個貝.若將要提出發(fā)箱的集裝箱不在棧的最高層,必須先把積壓在其上的所有集裝箱移動到其他棧,此移動的過程稱為倒箱.許多實例表明,貝位內(nèi)集裝箱數(shù)量越多,倒箱就越多.倒箱給提取集裝箱裝船帶來了很多不必要的工作,浪費(fèi)了大量的時間和金錢精力.為了解決這一困擾碼頭工作人員許久的難題,不少學(xué)者開始研究它.

1997年Kim[1]提出倒箱量估計方法,研究了碼頭進(jìn)口箱區(qū)堆存高度與倒箱量之間的關(guān)系,并針對不同進(jìn)口箱到達(dá)模式,建立了最小化期望倒箱量為目標(biāo)的數(shù)學(xué)模型;2006年Kim和Hong[2]利用分支定界和啟發(fā)式算法研究了提箱過程中翻到集裝箱落箱位置的確定問題;范磊[3]建立了輪胎式龍門機(jī)取箱作業(yè)數(shù)學(xué)模型,基于6條倒箱落位原則,以倒箱量最少為目標(biāo),運(yùn)用啟發(fā)式算法對模型進(jìn)行求解;徐亞[4]對阻塞箱落箱位置的確定問題以及如何減少二次倒箱進(jìn)行了研究,提出了一種啟發(fā)式算法H及其改進(jìn)算法IH;金鵬[5]以最小化翻箱總次數(shù)為優(yōu)化目標(biāo),運(yùn)用多人爬山算法進(jìn)行求解.

本文研究了貝位內(nèi)的取箱作業(yè)問題,給每一個箱子賦予一個優(yōu)先級別,數(shù)字越小的集裝箱越優(yōu)先被提取出貝位.在設(shè)計啟發(fā)式算法步驟時,創(chuàng)新地引入阻塞箱與棧內(nèi)優(yōu)先級最高的箱子的差的絕對值這一概念,并且將空棧單獨(dú)列出作為考量.通過大規(guī)模算例驗證,算法具有較好的可行解和時效性.

2 問題描述

貝位的初始狀態(tài)和各集裝箱的發(fā)箱順序已知,數(shù)字越小說明發(fā)箱優(yōu)先級越高,如順序為1的集裝箱是最先發(fā)箱的.問題轉(zhuǎn)化為按照各箱子發(fā)箱的優(yōu)先級別依次取箱,如何使得整個發(fā)箱過程倒箱量最少.

根據(jù)文獻(xiàn)[8]中所提到的重慶寸灘港每一個貝位有20棧(2棧作為倒箱緩沖,實際裝箱為18棧),5層,因此本文算例為20棧,6層,稍大于實際規(guī)模.貝位初始狀態(tài)見表1,其中數(shù)字表示集裝箱發(fā)箱順序.

表1：貝位初始狀態(tài)

3 取箱作業(yè)數(shù)學(xué)模型

3.1 模型假設(shè)

(1)貝位初始狀態(tài)和集裝箱發(fā)箱順序已知;

(2)倒箱過程只在一個貝位內(nèi)進(jìn)行,且僅對待提箱上方的阻塞箱進(jìn)行倒箱操作;

(3)不允許有新的集裝箱進(jìn)入貝位;

(4)層數(shù)為m時,貝位內(nèi)至少有m-1個空位留作倒箱使用.

3.2 符號說明

(i,j)：貝內(nèi)第i層第j棧箱位,i=1,2,···,m;j=1,2,···,n,貝位由m層n棧的集裝箱組成,最上層為第1層,最左棧為第1棧,以此類推;Bm×n：箱子優(yōu)先級矩陣.矩陣中各元素代表該位置上箱子被取出的優(yōu)先級,特別地,0元素表示空位;b(k,i,j)：第k次搬移箱子前,位于貝內(nèi)第i層和第j棧的箱子的優(yōu)先級,k=1,2,···,K;i=1,2,···,m;j=1,2,···,n.b(k,i,j)=0表示空位;

3.3 模型的建立

3.3.1 模型的建立

式(3.1)表示倒箱數(shù)量最少.

3.3.2 約束條件

式(3.2)表示每次搬移,僅有一個箱子被移動,要么一個箱子被提出,要么一個箱子被放入;式(3.3)表示第k次搬移前箱位(i,j)上有箱子而(i-1,j)上無箱子,第k次才可能將箱子搬移到(i-1,j);式(3.4)表示第k次搬移前箱位(i,j)上有箱子而(i-1,j)上無箱子,第k次才可能將(i,j)箱位的箱子提出發(fā)箱;式(3.5)表示箱子搬移總次數(shù)為K;式(3.6)表示所有箱子均被發(fā)箱;式(3.7)表示變量屬性.

4 啟發(fā)式算法

步驟1挑選其余棧中未到額定層數(shù)的空箱位作為翻出阻塞箱的堆存箱位.

步驟2步驟1成立時,若空箱位所在棧內(nèi)現(xiàn)有箱子優(yōu)先級比預(yù)移入阻塞箱的都低,則該空箱位可作為翻出箱的堆存箱位.若這樣的空箱位不唯一,則計算阻塞箱與棧內(nèi)優(yōu)先級最高的箱子的差的絕對值,選取絕對值最小的那一棧的空箱位作為翻出箱的堆存箱位.

步驟3步驟1成立但步驟2不成立時,若空箱位所在棧內(nèi)優(yōu)先級最高的箱子上方無阻塞箱,則該空箱位為翻出箱的堆存箱位.若這樣的空箱位不唯一,則計算阻塞箱與棧內(nèi)優(yōu)先級最高的箱子的差的絕對值,選取絕對值最小的那一棧的空箱位作為翻出箱的堆存箱位.

步驟4步驟1成立但步驟2和3不成立時,若空箱位所在棧內(nèi)優(yōu)先級最高的箱子上方只有1個阻塞箱,則該空箱位為翻出箱的堆存箱位.若這樣的空箱位不唯一,則計算阻塞箱與棧內(nèi)優(yōu)先級最高的箱子的差的絕對值,選取絕對值最小的那一棧的空箱位作為翻出箱的堆存箱位.

步驟5只有步驟1成立時,若空箱位所在棧內(nèi)優(yōu)先級最高的箱子上方有2個阻塞箱,則該空箱位為翻出箱的堆存箱位.若這樣的空箱位不唯一,則計算阻塞箱與棧內(nèi)優(yōu)先級最高的箱子的差的絕對值,選取絕對值最小的那一棧的空箱位作為翻出箱的堆存箱位.

步驟6只有步驟1成立時,若空箱位所在棧內(nèi)優(yōu)先級最高的箱子上方有3個阻塞箱,則該空箱位為翻出箱的堆存箱位.若這樣的空箱位不唯一,則計算阻塞箱與棧內(nèi)優(yōu)先級最高的箱子的差的絕對值,選取絕對值最小的那一棧的空箱位作為翻出箱的堆存箱位.

步驟7只有步驟1成立時,若空箱位所在棧內(nèi)優(yōu)先級最高的箱子上方有4個阻塞箱,則該空箱位為翻出箱的堆存箱位.若這樣的空箱位不唯一,則計算阻塞箱與棧內(nèi)優(yōu)先級最高的箱子的差的絕對值,選取絕對值最小的那一棧的空箱位作為翻出箱的堆存箱位.

對于空棧的處理：在執(zhí)行上述任何一步時,若出現(xiàn)空棧,則選定目前非空棧中最上層箱子優(yōu)先級最低的那一個.若該箱子不是該棧優(yōu)先級最高的,則將其移入空棧中,再繼續(xù)執(zhí)行上述7個步驟;否則,把將要移動的阻塞箱放入空棧中,再繼續(xù)執(zhí)行上述7個步驟.

5 算例與結(jié)果分析

運(yùn)用上述啟發(fā)式算法,根據(jù)表1的初始貝位狀態(tài),對該20棧、6層的較大規(guī)模的集裝箱堆場進(jìn)行倒箱操作,可以得到倒箱優(yōu)化方案,見表2.

表2：20*6集裝箱堆場倒箱優(yōu)化方案

倒箱次數(shù)27 28 29 30 31 32 33 34 35 36 37 38 39阻塞箱順序63 96 71 76 81 99 67 86 91 39 60 92 74倒箱前位置4層6棧2層17棧3層17棧4層17棧5層17棧3層14棧1層9棧1層19棧2層20棧3層20棧4層20棧2層10棧3層10棧倒箱后位置4層3棧5層6棧4層6棧3層6棧3層3棧6層17棧2層6棧5層17棧4層17棧3層14棧2層3棧1層6棧3層17棧

倒箱次數(shù)40 41 42 43 44 45 46 47 48 49 50 51 52阻塞箱順序94 90 38 82 65 57 97 64 31 92 85 45 52倒箱前位置1層18棧2層18棧3層18棧4層18棧3層2棧5層2棧2層13棧4層4棧5層4棧1層6棧3層12棧3層9棧4層9棧倒箱后位置2層17棧1層3棧2層14棧5層20棧1層17棧4層16棧6層2棧5層2棧5層1棧6層4棧5層4棧4層12棧4層10棧

倒箱次數(shù)53 54 55 56 57 58 59 60 61 62 63 64 65阻塞箱順序83 59 72 90 89 82 41 80 75 56 88 51 77倒箱前位置3層19棧4層19棧5層19棧1層3棧3層15棧5層20棧4層11棧4層15棧5層15棧4層8棧2層7棧3層5棧4層5棧倒箱后位置4層4棧4層2棧3層4棧6層1棧6層9棧6層19棧2層5棧5層19棧4層19棧3層16棧6層15棧3層10棧5層15棧

倒箱次數(shù)66 67 68 69 70 71 72 73 74 75 76 77阻塞箱順序70 78 61 84 62 87 81 94 73 76 91 96倒箱前位置5層5棧5層14棧5層12棧4層13棧5層10棧5層16棧3層3棧2層17棧5層3棧3層6棧4層17棧5層6棧倒箱后位置2層4棧6層5棧1層6棧6層12棧5層11棧6層10棧6層14棧6層16棧2層17棧4層15棧5層4棧5層2棧

總倒箱次數(shù)為77,算法耗時0.037s.為了進(jìn)一步驗證上述啟發(fā)式算法的高效性,對文獻(xiàn)[3]中的算例進(jìn)行計算,貝位初始狀態(tài)見表3,計算結(jié)果見表4.

表3：6層6棧的貝位初始狀態(tài)

表4：6*6集裝箱堆場倒箱優(yōu)化方案

總倒箱次數(shù)為11,與文獻(xiàn)[3]結(jié)果一樣,但是系統(tǒng)記錄運(yùn)行時間為0.018s,比文獻(xiàn)[3]的0.094s快了幾倍,因此本文的啟發(fā)式算法耗時更短,時效性更好.

6 結(jié)論

本文以軌道式龍門機(jī)在貝位內(nèi)取箱作業(yè)過程中倒箱量最少為目標(biāo),建立了取箱作業(yè)的數(shù)學(xué)模型,運(yùn)用MATLAB編譯的啟發(fā)式算法對模型進(jìn)行求解.相比于同類文章只研究了小規(guī)模的集裝箱倒箱問題,本文研究的是20棧、6層的大規(guī)模問題,更加貼近實際,具有較好的現(xiàn)實意義;單獨(dú)將空棧拿出來考慮,有利于減少二次、三次倒箱數(shù)量,對于減少總倒箱量有很大幫助;針對啟發(fā)式算法步驟中出現(xiàn)候選棧不唯一的情況,本文多增加了一個約束條件,從而確保候選棧的唯一性,大大減少了運(yùn)算量和隨機(jī)性.本文通過兩個規(guī)模不同的算例對算法進(jìn)行了驗證,均給出了具體的倒箱較優(yōu)方案.算例1的結(jié)果對于生產(chǎn)實際中大港口的取箱作業(yè)有較好的幫助,算例2的結(jié)果表明本文算法在時間上具有很大優(yōu)勢.事實上,由于假設(shè)2的存在,集裝箱倒箱實際上是一個NP-hard問題,本文提出的啟發(fā)式算法屬于貪心算法范疇,求得的解可能不是全局最優(yōu)解,下一步的研究重點將放到非限制變量上.

[1]Kim K H.Evaluation of the number of rehandles in container yards[J].Comput.Indus.Engin.(S0360-8352),1997,32(4)：701-711.

[2]Kim K H,Gyu-Pyo Hong.A heuristic rule for relocating blocks[J].Comp.Oper.Res.,2006,33(4)：940-954.

[3]范磊,梁承姬.堆場取箱作業(yè)中倒箱問題的啟發(fā)式算法研究[J].重慶交通大學(xué)學(xué)報(自然科學(xué)版),2014,33(1)：133-138.

[4]徐亞,陳秋雙,龍磊等.集裝箱倒箱問題的啟發(fā)式算法研[J].系統(tǒng)仿真學(xué)報,2008,20(14)：3666-3670.

[5]金鵬,黃有方,嚴(yán)偉.位內(nèi)集裝箱翻箱操作的啟發(fā)式優(yōu)化[J].上海海事大學(xué)學(xué)報,2009,30(4)：13-17.

[6]張維英,林焰,紀(jì)卓尚,吳毅剛.出口集裝箱堆場取箱作業(yè)優(yōu)化模型研究[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2006,30(2)：314-317.

[7]張德文,謝琛,陳麗昕.軌道式集裝箱門式起重機(jī)的技術(shù)分析[J].水運(yùn)科學(xué)研究,2006,6(2)：35-41.

RESEARCH ON THE MODEL AND HEURISTIC ALGORITHM OF CONTAINER RELOCATION PROBLEM

GUO Rui-zhi1,SHI Ma-jun1,LIN Hao-kun2
(1.School of Mathematics and Statistics,Wuhan University,Wuhan 430072,China)(2.School of Environmental Studies,China University of Geosciences,Wuhan 430074,China)

In this paper,we study the optimization of container handling in container yard.Based on the heuristic algorithm with seven choosing locations steps,a mathematical model for railroad gantry crane’s retrieving operation is established,and the method of minimizing the relocation numbers is obtained.This paper promotes the result of large-scale relocation problem which has good practical signi fi cance.

railroad gantry crane;large-scale relocation;relocation number;heuristic algorithm

on：03H05

O29

A

0255-7797(2017)04-0805-06

2016-12-21接收日期：2017-02-27

郭瑞智(1992-),男,湖南衡陽,碩士,主要研究方向：最優(yōu)化理論、算法及其應(yīng)用.