集卡調(diào)度中的關(guān)鍵問題

顏銀慧

【摘 要】 為提高集裝箱碼頭集卡調(diào)度的有效性，通過分析其現(xiàn)有的研究成果，結(jié)合碼頭實(shí)際作業(yè)需求，提出集卡調(diào)度中的關(guān)鍵問題并給出解決方法，并從精細(xì)化管理的角度出發(fā)，首次提出集卡運(yùn)行總成本的評(píng)價(jià)指標(biāo)，用以評(píng)價(jià)集卡調(diào)度的有效性。

【關(guān)鍵詞】 集卡；調(diào)度；重載率；評(píng)價(jià)指標(biāo)

0 引 言

隨著港口競(jìng)爭(zhēng)的不斷加劇，如何提高碼頭作業(yè)設(shè)備利用率，降低作業(yè)成本已經(jīng)成為碼頭公司提高服務(wù)水平、提升自身競(jìng)爭(zhēng)力的重要研究課題。船舶在碼頭的停留時(shí)間和完成裝卸作業(yè)的時(shí)間是衡量碼頭作業(yè)水平的重要指標(biāo)，而該指標(biāo)與碼頭作業(yè)設(shè)備的作業(yè)效率息息相關(guān)。集裝箱卡車（簡(jiǎn)稱集卡）作為連接碼頭水平運(yùn)輸和垂直運(yùn)輸?shù)臉蛄?，其作業(yè)效率對(duì)整個(gè)碼頭的作業(yè)效率有著至關(guān)重要的影響。因此，集裝箱碼頭的集卡調(diào)度問題已經(jīng)成為國內(nèi)外研究熱點(diǎn)之一。

NG等[1]以集卡總體作業(yè)耗時(shí)最小化為目標(biāo)，將集卡調(diào)度問題轉(zhuǎn)化為混合整數(shù)規(guī)劃MIP問題，采用遺傳算法進(jìn)行求解；XUE等[2]從碼頭的實(shí)際作業(yè)出發(fā)，考慮裝卸船作業(yè)的先后順序，通過建立混合整數(shù)規(guī)劃模型，運(yùn)用兩階段算法即蟻群算法（Ant Colony Optimization）和貪婪算法（Greedy Algorithm），為集卡分配作業(yè)指令；BISH等[3]基于碼頭的作業(yè)規(guī)則，采用啟發(fā)式算法動(dòng)態(tài)地給集卡指派作業(yè)任務(wù)。

集卡調(diào)度問題屬于NP難問題，而窮舉法過于耗時(shí)，因此許多學(xué)者提出各種近似的方法來求解集卡調(diào)度問題，以不斷提升調(diào)度算法的性能和優(yōu)化效果。

1 集卡調(diào)度中的關(guān)鍵問題

集裝箱碼頭的常規(guī)作業(yè)主要包括裝船、卸船、堆場(chǎng)移箱作業(yè)和進(jìn)提箱作業(yè)。碼頭作業(yè)的常用設(shè)備包括岸橋、場(chǎng)橋和集卡等。卸船作業(yè)的基本流程為：岸橋?qū)⒓b箱從船上卸到岸邊的集卡上，然后集卡將該集裝箱運(yùn)至堆場(chǎng)指定位置，再由堆場(chǎng)的場(chǎng)橋從集卡上將集裝箱吊起放至堆場(chǎng)指定位置。裝船作業(yè)流程則與卸船作業(yè)流程相反。

在傳統(tǒng)的調(diào)度模式下，碼頭調(diào)度人員為單個(gè)工作點(diǎn)（如對(duì)應(yīng)一輛岸橋）固定分配一批集卡，通常為5～7輛，并獨(dú)享該工作點(diǎn)下的所有集卡資源。但在這種調(diào)度模式下，各個(gè)工作點(diǎn)忙閑程度不一，需要集卡的工作點(diǎn)得不到集卡資源，容易出現(xiàn)集卡載著集裝箱從堆場(chǎng)到岸邊，最后空車返回堆場(chǎng)，造成集卡空載率（距離）較高（約為50%），利用率較低。

現(xiàn)有的調(diào)度算法很難在生產(chǎn)環(huán)境中得到應(yīng)用，主要有以下原因：（1）算法耗時(shí)過長(zhǎng)，往往超過1 min（以30輛集卡為例），很難滿足碼頭作業(yè)的實(shí)時(shí)性要求；（2）調(diào)度的首要目標(biāo)是保證船舶作業(yè)按時(shí)完成，實(shí)現(xiàn)船舶按時(shí)離泊，碼頭的作業(yè)能否按時(shí)完成，取決于岸橋的作業(yè)效率和岸橋、場(chǎng)橋以及集卡的協(xié)同作業(yè)，而現(xiàn)有的調(diào)度算法通常假設(shè)岸橋/場(chǎng)橋數(shù)量足夠，完全能夠滿足集卡的作業(yè)需求，即集卡在岸橋/場(chǎng)橋下不需要等待。

集卡調(diào)度問題可以簡(jiǎn)化為傳統(tǒng)的配對(duì)問題，即合理地為集卡與指令進(jìn)行配對(duì)。據(jù)了解，基于運(yùn)用成本最小原則，集卡指令配對(duì)模型已為業(yè)界一些領(lǐng)先的集裝箱碼頭操作管理系統(tǒng)供應(yīng)商所采用。本文基于集卡指令配對(duì)模型，從碼頭的實(shí)際需求出發(fā)，探討集卡調(diào)度中的一些關(guān)鍵問題：

（1）由于碼頭作業(yè)的復(fù)雜性，在實(shí)際作業(yè)場(chǎng)景中，設(shè)備的作業(yè)時(shí)間和狀態(tài)變化較大，要求調(diào)度算法必須根據(jù)實(shí)際作業(yè)情況的變化，動(dòng)態(tài)地為集卡分配指令。

（2）調(diào)度算法的實(shí)時(shí)性。在碼頭的實(shí)際作業(yè)過程中，要求調(diào)度算法實(shí)時(shí)地為集卡分配指令，通常分配時(shí)間（計(jì)算周期）應(yīng)小于2 s。在設(shè)計(jì)調(diào)度算法時(shí)，可以充分利用相鄰兩次計(jì)算的相似性，即當(dāng)次計(jì)算可以利用上一次計(jì)算信息，縮短算法的計(jì)算時(shí)間，滿足實(shí)時(shí)性需求。針對(duì)集卡調(diào)度，可采用改進(jìn)的Dynamic Hungarian Algorithm算法。

（3）在集卡指令配對(duì)模型中，集卡完成作業(yè)指令的代價(jià)計(jì)算是調(diào)度算法的核心部分。如果僅僅考慮集卡參與作業(yè)所需要行使的路程，往往導(dǎo)致工作點(diǎn)距離作業(yè)箱區(qū)較近的岸橋分配的集卡較多，甚至出現(xiàn)擁堵，從而出現(xiàn)岸橋忙閑不一，造成集卡資源浪費(fèi)。為此，需要考慮岸橋/場(chǎng)橋是否需要集卡，即集卡能否準(zhǔn)時(shí)到達(dá)岸橋/場(chǎng)橋下，盡量使需要集卡的岸橋/場(chǎng)橋能夠得到集卡。

針對(duì)集卡完成作業(yè)指令的3種場(chǎng)景進(jìn)行相應(yīng)的分析，結(jié)果如表1所示。

通過對(duì)以上3種場(chǎng)景的分析來看，集卡完成作業(yè)指令最為合適的代價(jià)計(jì)算應(yīng)是集卡運(yùn)輸時(shí)間、集卡早到時(shí)間和集卡晚到時(shí)間三者的加權(quán)總和，即 €%[ €準(zhǔn)ㄐ惺皇奔洌？€%d €準(zhǔn)ㄔ緄絞奔洌？€%e €準(zhǔn)ㄍ淼絞奔洌渲？€%[， €%d， €%e為權(quán)重參數(shù)。為了減少集卡早到和晚到情形的出現(xiàn)， €%d和 €%e應(yīng)滿足 €%d>€%[和 €%e>€%[。在實(shí)際碼頭應(yīng)用中，需要結(jié)合碼頭的實(shí)際情況不斷摸索和總結(jié)，設(shè)置合理的參數(shù)，以達(dá)到最優(yōu)的調(diào)度效果。

2 集卡調(diào)度的評(píng)估

為評(píng)估集卡調(diào)度的有效性，業(yè)界有些專家提出以下評(píng)價(jià)指標(biāo)：重載率（時(shí)間維度）、重載率（距離維度）、重來重去率。各指標(biāo)的定義如下：

重載率（時(shí)間）=重載時(shí)間/集卡運(yùn)行時(shí)間

重載率（距離）=重載距離/集卡行駛距離

重來重去率=集卡背重箱次數(shù)/集卡背箱總次數(shù)

事實(shí)上，集卡重車在堆場(chǎng)或者岸邊等待可提高集卡重載率（時(shí)間），但重載率高不一定能夠反映集卡調(diào)度效果好。在岸邊完成裝船作業(yè)的集卡通過等待直至獲得卸船作業(yè)任務(wù)，以此提高重來重去率，但也有可能導(dǎo)致岸邊集卡過多，造成交通擁堵。

基于精細(xì)化管理角度，應(yīng)從集卡本身出發(fā)，以集卡成本來評(píng)估集卡調(diào)度的優(yōu)劣。在碼頭作業(yè)中，集卡運(yùn)行成本由以下部分構(gòu)成：集卡空車運(yùn)行成本、集卡空車等待成本、集卡重車運(yùn)行成本和集卡重車等待成本等。通過無線射頻識(shí)別（RFID）技術(shù)或者集卡司機(jī)按鍵確認(rèn)到達(dá)等手段，碼頭可以記錄集卡到達(dá)目標(biāo)作業(yè)的時(shí)間，統(tǒng)計(jì)出集卡空車運(yùn)行時(shí)間（T空運(yùn)）、集卡空車等待時(shí)間（T空等）、集卡重車運(yùn)行時(shí)間（T重運(yùn)）和集卡重車等待時(shí)間（T重等）；根據(jù)歷史經(jīng)驗(yàn)數(shù)據(jù)和集卡行業(yè)相關(guān)信息，碼頭可獲得單位時(shí)間內(nèi)集卡空車運(yùn)行油耗（C空運(yùn)）、集卡空車等待油耗（C空等）、集卡重車運(yùn)行油耗（C重運(yùn)）和集卡重車等待油耗（C重等）。因此，碼頭集卡運(yùn)行的總成本M總=T空運(yùn)€證空運(yùn)+T空等€證空等+T重運(yùn)€證重運(yùn)+T重等€證重等。在作業(yè)任務(wù)一定的條件下，同時(shí)確保岸橋作業(yè)效率，集卡運(yùn)行的總成本可以用來衡量集卡調(diào)度的優(yōu)劣。

3 結(jié) 語

集卡調(diào)度是碼頭作業(yè)設(shè)備調(diào)度的核心問題之一。如何評(píng)估集卡調(diào)度的有效性，需要建立科學(xué)的評(píng)估指標(biāo)。當(dāng)前業(yè)界評(píng)估指標(biāo)存在缺陷，因此，從精細(xì)化管理角度出發(fā)，本文首次提出集卡運(yùn)行總成本的評(píng)估指標(biāo)，并給出相應(yīng)的計(jì)算公式，而對(duì)于設(shè)計(jì)合理的集卡調(diào)度系統(tǒng)及運(yùn)用本文提出的集卡調(diào)度評(píng)估指標(biāo)來不斷優(yōu)化系統(tǒng)將是下一步研究方向。

參考文獻(xiàn)：

[1] NG W C，MAK K L，ZHANG Y X.Scheduling trucks in container terminals using a genetic algorithm [J].Engineering Optimization，2007，39（1）：33-37.

[2] XUE Z J，ZHANG C R，MIAO L X，et al.An ant colony algorithm for yard truck scheduling and yard location assignment problems with precedence constraints [J].Journal of Systems Science and Systems Engineering，2013，22（1）：21-37.

[3] BISH E K，CHEN F Y，LEONG Y T，et al.Container terminal and cargo systems [M].Berlin：Springer Berlin Herdelberg，2007.