離散泊位分配裝卸量加權(quán)延遲最小化策略

楊 斌，岳宇菲

（上海海事大學(xué)物流研究中心，上海201306）

0 引言

近年來，經(jīng)濟的全球化和貿(mào)易的國際化給港口企業(yè)帶來機遇的同時也帶來了巨大的挑戰(zhàn)。港口企業(yè)為了提高服務(wù)質(zhì)量和顧客滿意度，盡量縮短船舶的作業(yè)時間，使船舶等待作業(yè)的時間最短。然而，由于不同的船型及其裝載量有明顯差別，如果簡單地將船舶總的作業(yè)時間累加，并不能使港口的作業(yè)效率達到最優(yōu)。對于一些大船，因為其日租金較高，在等待過程中消耗的能耗也較大，其延誤一個單位時間所付出的代價要遠遠超過一艘小船在相同時間內(nèi)所付出的代價?；诖耍瑳Q策者在做出決策時，不能將大船和小船視為平級，而要使用大船優(yōu)先策略，通過對所有船舶的作業(yè)延遲時間加權(quán)來對不同船舶的等級進行區(qū)分。

泊位分配問題在國外已有了深入的研究。文獻［1］研究了亞洲商業(yè)港口的靜態(tài)泊位分配問題；文獻［2］在此基礎(chǔ)上進一步研究了港口的動態(tài)泊位分配問題；文獻［3］將離散泊位分配問題構(gòu)建為動態(tài)調(diào)度問題，借用文獻［1－2］所構(gòu)建的模型，設(shè)計了拉格朗日啟發(fā)式算法用在離散的泊位分配問題中，碼頭被分為了幾個有限的泊位，每個泊位每次只能為一艘船服務(wù)。而在連續(xù)的泊位分配問題中，碼頭沒有固定的泊位分配，只要有空余的位置，合適的船舶就可以靠泊［4］。在連續(xù)性泊位分配方面，文獻［5］提出了模擬退火算法；文獻［6］提出了梯度優(yōu)化的方法；文獻［7］考慮了空間上的水深和船長度等因素，提出了遺傳算法，并通過計算得到了很好的解決方案；文獻［8］在文獻［1－2］模型的基礎(chǔ)上提出了以成本最小化為目標(biāo)的泊位分配問題，并鄰域搜索啟發(fā)式算法對該問題進行了求解；文獻［9］研究了動態(tài)泊位的數(shù)學(xué)規(guī)劃問題，并通過計算實驗對不同的情況進行了比較。

而在國內(nèi)的相關(guān)文獻中，文獻［10］考慮到船舶動態(tài)到達的情況，以及實際操作中碼頭裝卸效率對船舶在港作業(yè)時間和船舶優(yōu)先權(quán)的影響，以最小化包括等待時間在內(nèi)的船舶在港停留時間為目標(biāo)，建立了基于船舶優(yōu)先權(quán)的連續(xù)布置泊位分配模型；文獻［11］建立了以最小化船舶在港總停時間為目標(biāo)函數(shù)的數(shù)學(xué)模型，并用遺傳算法進行求解，并指出傳統(tǒng)的先到先服務(wù)的人工分配方式的低效性；文獻［12］考慮了體現(xiàn)碼頭和船公司雙方各自的需求指標(biāo)，使用一種基于禁忌深度局部搜索的模擬退火混合算法，對船舶動態(tài)到達情況下的離散泊位調(diào)度問題進行求解；文獻［13］將泊位問題抽象為二維裝箱問題，建立了同時考慮泊位和橋吊資源的整數(shù)規(guī)劃模型，并給出了求解模型的回溯算法。文獻［14］建立了集裝箱港口集群下多港口多泊位聯(lián)合調(diào)度的多目標(biāo)非線性決策模型，并設(shè)計了改進的遺傳啟發(fā)式算法。文獻［15］充分利用碼頭的岸橋資源，設(shè)計出了一種基于合同網(wǎng)協(xié)議（CNP）協(xié)商機制的岸橋?qū)崟r調(diào)度模型，有效地降低了不確定因素所帶來的影響。

雖然上述文獻在泊位分配問題研究中提出了水深、船長等物流條件的限制，但沒有考慮到在實際運營過程中人為設(shè)置的船舶優(yōu)先權(quán)對泊位分配與港口運作效率的影響。本文在離散泊位的基礎(chǔ)上，引入服務(wù)優(yōu)先權(quán)的思想，根據(jù)船舶的裝卸量賦予不同的權(quán)重，建立以加權(quán)后船舶等待時間最小化為目標(biāo)的泊位分配方案，對比了傳統(tǒng)的僅以最小化船舶等待時間為目標(biāo)的泊位分配方案，并分析了不同的權(quán)重值對泊位分配方案的影響。

1 問題描述

泊位調(diào)度是指在船舶到港前或到港后，根據(jù)各個泊位的空閑情況和物理條件約束對船舶分配合理的?？坎次弧⑦x擇合適的靠泊順序。本文研究的船舶調(diào)度問題目的是確定計劃周期內(nèi)船舶分配的泊位位置及進行裝卸作業(yè)的次序和時間，目標(biāo)是使不同服務(wù)級別船舶總的作業(yè)延遲時間最小。

若不考慮船舶的重要性程度，只是以船舶的作業(yè)時間最小化為目標(biāo)函數(shù)，這樣得到的泊位分配方案沒有太大的意義。不同的船舶由于裝卸量的不同，其對于港口企業(yè)的重要程度也有很大差別。通常來說，裝卸量較小的船舶都是一些小船、非定期常來的船舶，裝卸量較大的船舶往往是大船，跟港口企業(yè)有長期合作的關(guān)系，其日租金也會較高，等待一個單位時間所消耗的成本要比那些小船大。因此，若將不同裝卸量的船視為平級，簡單地相加所有船舶的作業(yè)延遲時間，并將其作為港口泊位分配的目標(biāo)函數(shù)，是不合理的。因此，在實際的泊位分配過程中，港口企業(yè)要對不同裝卸量的船舶區(qū)分開來，對裝卸量較大的船舶實施優(yōu)先調(diào)度策略。要想對不同的船舶進行區(qū)分，就要分別對船舶進行加權(quán)，使每一艘船都有對應(yīng)的權(quán)重值。由于船舶的優(yōu)先權(quán)跟船舶的裝卸量相關(guān)，因此可以根據(jù)船舶的裝卸量建立以下的加權(quán)函數(shù)，并結(jié)合不同的權(quán)值系數(shù)來表示不同程度的重要性，從而得到相應(yīng)船舶的權(quán)重值ωi。

其中，wi為船舶的裝卸量；wmax為船舶集合V中裝卸最大的船舶裝卸量；wmin為船舶集合V中裝卸最小的船舶裝卸量；q為權(quán)重系數(shù)，ωi為在權(quán)重系數(shù)為q的情況下船舶i相對應(yīng)的權(quán)重值，q的取值越大，船舶的優(yōu)先權(quán)越突出。

2 模型的建立

2.1 假設(shè)條件

（Ⅰ）每條船必須被服務(wù)且僅被服務(wù)一次（即不考慮移泊情況）；

（Ⅱ）每個泊位上一次只能?？恳粭l船；

（Ⅲ）船長不超過泊位長；

（Ⅳ）船舶預(yù)計到港時間已知，船舶裝卸作業(yè)開始時間必須晚于船舶到港時間；

（Ⅴ）一艘船從開始裝卸到完成之前，不會離開泊位；

（Ⅵ）船舶的在港時間為船舶在錨地的等待時間加上在泊位上的作業(yè)時間。

假設(shè)條件（Ⅰ）、（Ⅱ）、（Ⅲ）是泊位分配的基本要求，假設(shè)條件（Ⅳ）是船舶到港作業(yè)的必要條件，假設(shè)條件（Ⅴ）是碼頭對船舶裝卸作業(yè)的要求，假設(shè)條件（Ⅵ）是為了在不影響求解結(jié)果的前提下，使建立的模型相對簡單。

2.2 模型建立

基于船舶獲得的優(yōu)先權(quán)，建立如下的泊位分配模型：

此模型中，V為到港船舶的集合，i＝（1，2，…，I）∈V；Q為港口泊位的集合，j＝（1，2，…，J）∈Q；O為船舶服務(wù)順序，k＝（1，2，…，I）∈O；Si為船舶i的長度；Lj為船舶j的長度；ai為船舶i總的裝卸時間；bi為船舶i的到港時間；ωi為船舶i所對應(yīng)的權(quán)重值；zi為船舶i的最長延遲時間；M表示一個足夠大的正數(shù)。xijk為0～1變量，若船在i泊位以k順序開始作業(yè)，xijk＝1，否則xijk＝0；yijk為船舶i在泊位j以k順序開始作業(yè)的時間；σijk為0～1變量，若i船被分配到j(luò)泊位時σijk＝1，否則σijk＝0。

式（2）表示最小化加權(quán)后船舶總的延遲時間定義目標(biāo)函數(shù)；式（3）表示每一艘船舶只能?？吭谝粋€泊位上進行服務(wù)；式（4）表示泊位j上的第k時間段最多只能有一艘船舶?？?；式（5）表示靠泊船舶的長度不能超過泊位的長度；式（6）表示船舶的開始作業(yè)時間必須遲于船舶的到港時間；式（7）表示僅當(dāng)船舶被分配在泊位j上以順序k進行作業(yè)時，才存在開始作業(yè)時間；式（8）是對xijk的限制，保證xijk的取值；式（9）表示船舶i開始作業(yè)時間必須大于0；式（10）表示對船舶作業(yè)延遲時間的限制，即將裝卸量較大的船的延遲時間盡量縮短；式（11）是防止在同一個泊位上的兩條船開始作業(yè)的時間重疊。

3 仿真算例

3.1 參數(shù)設(shè)置

為了驗證模型的有效性，本文根據(jù)港口實際業(yè)務(wù)情況，選取了48 h內(nèi)某港口的作業(yè)計劃作為實例，選擇了5個參與作業(yè)的泊位和10條船舶的參數(shù)數(shù)據(jù)，泊位1～泊位5的泊位長度分別為150 m、160 m、260 m、280 m、220 m，船舶數(shù)據(jù)如表1所示。船舶長度（l）、預(yù)計到港時刻（T）、預(yù)計裝卸時間（t）和船舶裝卸量（Q）是隨機給出的，根據(jù)表1給出的數(shù)據(jù)，可以根據(jù)式（1）計算出在不同權(quán)值系數(shù)的情況下，10條船所對應(yīng)的權(quán)重值。

表1 船舶數(shù)據(jù)

由于泊位數(shù)量的限制，有的船舶到港后并不能立即進行作業(yè)，甚至需要等待很長時間。而船舶的優(yōu)先權(quán)直接決定著船舶的最長延遲時間，上文已根據(jù)船舶的裝卸量和權(quán)重系數(shù)得到了船舶i的權(quán)重，因此，可以引入一個分段函數(shù)式來確定船舶i的最長延遲時間：

式中，zi表示船舶i的最長延遲時間；ωi表示船舶i相對應(yīng)的權(quán)重值；參數(shù)r1、r2、r3、r4表示權(quán)重范圍系數(shù)；s1、s2、s3、s4、s5表示船舶i在相對應(yīng)的權(quán)重范圍內(nèi)的最長延遲時間。本文選取參數(shù)值r1＝1、r2＝2、r3＝3、r4＝4、s1＝24、s2＝12、s3＝6、s4＝3、s5＝1。即可得到10條船在不同權(quán)重下船舶i的最長延遲時間。

分別選取了q＝2、q＝3、q＝4這3種情況，并根據(jù)以上公式得出了相應(yīng)的權(quán)重值和船舶最長延遲時間，如表2所示。

表2 不同權(quán)重系數(shù)下的船舶權(quán)重值ωi及最長延遲時間zi

3.2 結(jié)果分析

3.2.1 加權(quán)對泊位分配的影響

根據(jù)表1給出的數(shù)據(jù)，運用CPLEX軟件進行編程求解，以權(quán)值系數(shù)q＝2，設(shè)計了不考慮船舶優(yōu)先權(quán)（試驗1）和考慮船舶優(yōu)先權(quán)（試驗2）的兩組試驗，見表3。

由于試驗1中沒有權(quán)值系數(shù)及相對應(yīng)的權(quán)重值，因此得不到加權(quán)后的延遲時間這組數(shù)據(jù)。本文考慮把q＝2所對應(yīng)的權(quán)重值ωi與試驗1中所得到的船舶i的延遲時間（t1）分別相乘，并求和得到10條船的總的加權(quán)后的延遲時間，與試驗2進行對比。

表3 泊位分配計劃

從表3中的兩組試驗數(shù)據(jù)對比中可以發(fā)現(xiàn)：若將船舶的總延遲時間最小化作為目標(biāo)，那么不考慮船舶的優(yōu)先權(quán)的情況下，其目標(biāo)函數(shù)值f＝16 h，考慮船舶優(yōu)先權(quán)的情況下，目標(biāo)函數(shù)值f＝44 h。從總的延遲時間上來看，不考慮船舶優(yōu)先權(quán)可能更為有利，然而，船公司所擁有的客戶有大客戶和小客戶之分，其重要性有很大差異，不同的客戶等待一個單位時間所付出的成本是不一樣的。所以在做出決策時，要將不同船舶的權(quán)重值考慮進去，使大客戶的等待時間盡可能少，同時讓一部分小客戶做出犧牲，延長其等待的時間，從而最小化加權(quán)后的總延遲時間。取權(quán)值系數(shù)q＝2，得到考慮船舶優(yōu)先權(quán)時的加權(quán)延遲時間f＝0.682 h，為了便于和加權(quán)后的方案比較，將q＝2時相對應(yīng)的權(quán)重ωi代入到不考慮權(quán)重時得出的方案當(dāng)中，得到目標(biāo)函數(shù)值f＝4.212 h，顯然，不考慮船舶優(yōu)先權(quán)時的加權(quán)延遲時間f遠遠大于考慮優(yōu)先權(quán)時的加權(quán)延遲時間f。

因此，對不同的船區(qū)別對待，在不影響港口整體作業(yè)的前提下，很大程度的提高客戶滿意度，為企業(yè)帶來一定的效益。

3.2.2 不同的權(quán)值系數(shù)對泊位分配的影響

不同船舶的權(quán)重值受到q值的影響，q表示權(quán)值系數(shù)，權(quán)值系數(shù)越大，大船的優(yōu)先程度越高。因此，q值的選取直接影響著泊位分配方案。

本文選取權(quán)值系數(shù)q＝2、q＝3、q＝4進行了3組試驗，分別比較了3種情況下船舶加權(quán)后總的作業(yè)延遲時間，結(jié)果見表4。

表4 船舶在不同權(quán)重下作業(yè)的總延遲時間及加權(quán)后延遲時間

由表4可以發(fā)現(xiàn)：在考慮船舶權(quán)重的情況下，隨著權(quán)值系數(shù)的逐漸增大，船舶總的作業(yè)延遲時間變化不大。然而，由于大船的優(yōu)先程度越來越高，使小船犧牲的利益也越來越大，從而在整體上導(dǎo)致加權(quán)后總的延遲時間逐漸增大。

權(quán)值系數(shù)的選取會對泊位分配產(chǎn)生很大的影響，決策者在制定決策的過程中，要綜合考慮到船舶的重要性程度以及整個港口的作業(yè)效率，不能只是考慮船舶的優(yōu)先權(quán)問題而使整個港口的作業(yè)效率失衡。

4 結(jié)論

本文主要研究了靜態(tài)離散泊位調(diào)度問題，基于船舶的不同裝卸量，引入服務(wù)優(yōu)先權(quán)的思想，否定了把船舶作業(yè)延遲時間簡單相加作為目標(biāo)的泊位分配方式，并在已有的泊位分配模型上進行了相關(guān)改進，建立了考慮船舶優(yōu)先權(quán)的泊位分配模型。通過對不考慮權(quán)重和考慮權(quán)重的兩種泊位分配方式的對比分析，可以看出引入服務(wù)優(yōu)先權(quán)后泊位分配方式的優(yōu)越性，并指出不同權(quán)重系數(shù)對泊位分配方式的影響。該模型和泊位分配策略可以使港口企業(yè)從實際角度對泊位進行合理分配，對不同重要性的船舶區(qū)分對待，為調(diào)度人員提供決策支持，同時有效地提高港口作業(yè)效率和總體客戶服務(wù)水平。

［1］ Ima A，Nagaiwa K，Chan W.Efficient Planning of Berthing Allocation for Container Terminals in Asia［J］.Journal of Advanced Transportation，1997，31：75－94.

［2］ Imai A，Nishimura E，Papadimitriou S.The Dynamic Berth Allocation Problem for a Container Port［J］.Transportation Research Part B，2001，35（4）：401－417.

［3］ Dorigo M，Maniezzo V，Colorni A.Ant System：Optimization by a Colony of Cooperating Agents IEEE Trans［J］.Systems Man Cybernet，1996，26（1）：29－41.

［4］ Lim A.The Berth Planning Problem［J］.Operations Research Letters，1998，25（2／3）：105－110.

［5］ Kim K H，Moon K C.Berth Scheduling by Simulated Annealing［J］.Transportation Research Part B，2003，37（6）：541－560.

［6］ Park K T，Kim K H.Berth Scheduling for Container Terminals by Using a Sub-gradient Optimization Technique［J］.Journalof the Operational Research Society，2002，53（9）：1054－1062.

［7］ Nishimura E，Imai A，Papadimitriou S.Berth Allocation Planning in the Public Berth System by Genetic A lgorithms［J］.European Journal of Operational Research，2001，131（2）：282－292.

［8］ Hansen P，Oguz C，M ladenovic N.Variable Neighborhood Search Form inimum Cost Berth A llocation［J］.European Journal of Operational Research，2008，191（3）：636－649.

［9］ Buhrkal K，Zuglian S，Ropke S，et al.Models for the Discrete Berth Allocation Problem：A Computational Comparison［J］.Transportation Research Part E，2011，47（4）：461－473.

［10］ 童珊.基于船舶優(yōu)先權(quán)的集裝箱港口泊位分配問題［J］.交通運輸工程與信息學(xué)報，2012，10（1）：105－110.

［11］ 王軍，李卓榮.基于遺傳算法的動態(tài)泊位分配問題優(yōu)化研究［J］.中國水運，2011，11（1）：63－65.

［12］ 韓笑樂，陸志強.具有服務(wù)優(yōu)先級別的動態(tài)離散泊位調(diào)度優(yōu)化［J］.上海交通大學(xué)學(xué)報，2009，43（6）：902－905.

［13］ 韓曉龍，丁以中.集裝箱港口泊位配置優(yōu)化［J］.系統(tǒng)工程理論方法應(yīng)用，2006，15（3）：275－278.

［14］ 畢婭，李文鋒.集裝箱港口集群下多港口多泊位聯(lián)合調(diào)度方法［J］.計算機應(yīng)用，2012，32（2）：448－451.

［15］ 孫彬，孫俊清，陳秋雙.基于魯棒反應(yīng)式策略的泊位和岸橋聯(lián)合調(diào)度［J］.系統(tǒng)工程理論與實踐，2013，33（4）：1076－1083.