楊 斌，岳宇菲

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

0 引言

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

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

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

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

1 問題描述

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

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

2 模型的建立

2.1 假設(shè)條件

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

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

（Ⅲ）船長(zhǎng)不超過泊位長(zhǎng)；

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

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

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

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

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的長(zhǎng)度；Lj為船舶j的長(zhǎng)度；ai為船舶i總的裝卸時(shí)間；bi為船舶i的到港時(shí)間；ωi為船舶i所對(duì)應(yīng)的權(quán)重值；zi為船舶i的最長(zhǎng)延遲時(shí)間；M表示一個(gè)足夠大的正數(shù)。xijk為0～1變量，若船在i泊位以k順序開始作業(yè)，xijk＝1，否則xijk＝0；yijk為船舶i在泊位j以k順序開始作業(yè)的時(shí)間；σijk為0～1變量，若i船被分配到j(luò)泊位時(shí)σijk＝1，否則σijk＝0。

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

3 仿真算例

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

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

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

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

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

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

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

3.2 結(jié)果分析

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

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

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

表3 泊位分配計(jì)劃

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

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

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

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

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

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

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

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

4 結(jié)論

本文主要研究了靜態(tài)離散泊位調(diào)度問題，基于船舶的不同裝卸量，引入服務(wù)優(yōu)先權(quán)的思想，否定了把船舶作業(yè)延遲時(shí)間簡(jiǎn)單相加作為目標(biāo)的泊位分配方式，并在已有的泊位分配模型上進(jìn)行了相關(guān)改進(jìn)，建立了考慮船舶優(yōu)先權(quán)的泊位分配模型。通過對(duì)不考慮權(quán)重和考慮權(quán)重的兩種泊位分配方式的對(duì)比分析，可以看出引入服務(wù)優(yōu)先權(quán)后泊位分配方式的優(yōu)越性，并指出不同權(quán)重系數(shù)對(duì)泊位分配方式的影響。該模型和泊位分配策略可以使港口企業(yè)從實(shí)際角度對(duì)泊位進(jìn)行合理分配，對(duì)不同重要性的船舶區(qū)分對(duì)待，為調(diào)度人員提供決策支持，同時(shí)有效地提高港口作業(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］.交通運(yùn)輸工程與信息學(xué)報(bào)，2012，10（1）：105－110.

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

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

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

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

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