吳云強(qiáng),張 戎
同濟(jì)大學(xué) 城市交通研究院 道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室 上海市軌道交通結(jié)構(gòu)耐久與系統(tǒng)安全重點(diǎn)實(shí)驗(yàn)室,上海201804
隨著海上運(yùn)輸業(yè)的迅猛發(fā)展,集裝箱港口在全球貨運(yùn)體系中的地位逐漸提高。港口中泊位與航道等核心作業(yè)資源的分配或調(diào)度直接影響其服務(wù)水平,并關(guān)乎整個(gè)港口的運(yùn)營(yíng)成本。然而,進(jìn)出港時(shí)間的限制以及泊位與航道復(fù)雜的協(xié)作關(guān)系使得二者集成優(yōu)化變得格外復(fù)雜。因此,如何根據(jù)現(xiàn)實(shí)情況,快速制定考慮航道資源的船舶調(diào)度方案與泊位分配計(jì)劃,成為集裝箱港口領(lǐng)域研究的熱點(diǎn)問題之一。
在考慮航道資源的船舶調(diào)度研究方面,現(xiàn)有文獻(xiàn)主要關(guān)于單向、雙向以及復(fù)式航道。針對(duì)單向航道,徐國(guó)裕等[1]考慮船舶優(yōu)先級(jí),以船舶載重噸、吃水深度等因素為指標(biāo),通過工作排序方法獲得船舶進(jìn)出港次序。鄔惠國(guó)等[2]基于多目標(biāo)格序決策理論,構(gòu)建通航方案評(píng)價(jià)指標(biāo)體系,并采取熵值法計(jì)算各個(gè)指標(biāo)的權(quán)重,從而選取最佳船舶進(jìn)出港方案。鄭紅星等[3]考慮安全行駛距離與大型船舶需要在潮汐時(shí)段進(jìn)出港口的作業(yè)規(guī)則,以所有船舶作業(yè)等待時(shí)間之和最小為優(yōu)化目標(biāo),并采用改進(jìn)和聲搜索算法來(lái)求解。對(duì)于雙向航道,Eduardo等[4]考慮碳排放和潮汐等因素,以所有船舶等待時(shí)間之和最小為目標(biāo)函數(shù),構(gòu)建了混合整數(shù)規(guī)劃模型,并設(shè)計(jì)了模擬退火算法,且通過多組算例來(lái)驗(yàn)證其求解效率。張新宇等[5]考慮單向通航與雙向通航之間的轉(zhuǎn)換問題,保證船舶在航道安全和高效行駛,以降低停留時(shí)間與調(diào)度時(shí)間為目標(biāo),構(gòu)建了混合整數(shù)線性規(guī)劃模型,且采用改進(jìn)遺傳算法來(lái)求解問題。對(duì)于復(fù)式航道,陳向[6]考慮船舶類型與在港航行速度的影響,基于文獻(xiàn)[5]來(lái)建立混合整數(shù)規(guī)劃模型,并結(jié)合問題特征,采用相應(yīng)啟發(fā)式算法進(jìn)行求解,得到最佳泊位分配與船舶調(diào)度方案。這些研究大多關(guān)于單向航道,有關(guān)雙向和復(fù)式航道研究較少,但由于單向航道中進(jìn)出港時(shí)段交替進(jìn)行,單向航道下的船舶調(diào)度問題比雙向航道更為復(fù)雜,且單向航道是復(fù)式航道的基礎(chǔ)。絕大多數(shù)文獻(xiàn)考慮船舶優(yōu)先級(jí)和潮汐等因素,以港口實(shí)際作業(yè)情況為約束條件,采取方案評(píng)價(jià)法或優(yōu)化算法來(lái)獲取最佳船舶進(jìn)出港方案,但幾乎沒有文獻(xiàn)考慮進(jìn)出港時(shí)段對(duì)船舶調(diào)度的影響。
泊位分配問題基于泊位類型可分為離散泊位分配與連續(xù)泊位分配,且考慮計(jì)劃期開始時(shí)刻船舶是否已經(jīng)??吭阱^地,可分為靜態(tài)泊位分配問題與動(dòng)態(tài)泊位分配問題。依據(jù)兩兩組合原理,泊位分配問題可分為四類,其中動(dòng)態(tài)連續(xù)泊位分配問題最為復(fù)雜,另外三類問題已有國(guó)內(nèi)外眾多學(xué)者開展了大量的研究[7-14]。針對(duì)動(dòng)態(tài)連續(xù)泊位分配問題,秦天保等[15]基于約束規(guī)劃理論,以所有船舶在港停留時(shí)間之和最小為目標(biāo)函數(shù),構(gòu)建了混合整數(shù)規(guī)劃模型,并利用CPLEX來(lái)解決此問題,且通過算例實(shí)驗(yàn)來(lái)分析算法求解效率。曾慶成等[16]針對(duì)港口作業(yè)中的不確定性因素,分別以延誤時(shí)間之和最小與魯棒性指標(biāo)最大為第一、二階段目標(biāo)函數(shù),最后設(shè)計(jì)了改進(jìn)拉格朗日松弛算法。Ursavas[17]考慮船舶服務(wù)的優(yōu)先級(jí),通過動(dòng)態(tài)離散事件仿真模型來(lái)建立泊位分配決策支持系統(tǒng),并嵌入優(yōu)化算法確定各船舶的優(yōu)先級(jí),從而幫助港口制定戰(zhàn)略層與戰(zhàn)術(shù)層的決策。Liu等[18]考慮作業(yè)環(huán)境的不確定性,以最差條件下的運(yùn)營(yíng)成本最小為目標(biāo)函數(shù),構(gòu)建了相應(yīng)的兩階段數(shù)學(xué)模型,并通過啟發(fā)式算法來(lái)解決大規(guī)模調(diào)度問題。從上可知,現(xiàn)有學(xué)者對(duì)于動(dòng)態(tài)連續(xù)泊位分配的研究主要考慮船舶到港時(shí)間或者優(yōu)先級(jí),以計(jì)劃期內(nèi)船舶在港停留時(shí)間之和最小為目標(biāo)函數(shù),構(gòu)建相應(yīng)的數(shù)學(xué)規(guī)劃模型,并通過啟發(fā)式算法或精確算法進(jìn)行求解,但少有文獻(xiàn)涉及潮汐因素對(duì)泊位分配的影響。
在泊位分配與船舶調(diào)度集成優(yōu)化研究方面,以船舶待停靠泊位已知為前提,Zhang 等[19]根據(jù)港口不同區(qū)域交通流,以在港等待時(shí)間最小為目標(biāo)函數(shù),構(gòu)建了相應(yīng)數(shù)學(xué)規(guī)劃模型,結(jié)合模擬退火算法的相關(guān)原理來(lái)構(gòu)造求解算法。Jia等[20]考慮內(nèi)錨地影響,以到港船舶時(shí)間懲罰成本之和最小為目標(biāo)函數(shù),構(gòu)建了混合整數(shù)規(guī)劃模型,并結(jié)合拉格朗日松弛來(lái)求解此問題。以船舶待??坎次晃粗獮榍疤幔嵓t星等[21]考慮泊位類型的差異化,以計(jì)劃期內(nèi)船舶成本之和最小為目標(biāo)函數(shù),構(gòu)建了混合整數(shù)線性規(guī)劃模型,并采用改進(jìn)聲搜索算法來(lái)求解。上述文獻(xiàn)主要是在船舶待??坎次灰阎那闆r下,根據(jù)離散泊位作業(yè)情況,以降低船舶在港停留時(shí)間為目標(biāo),研究泊位分配與船舶調(diào)度協(xié)同優(yōu)化,罕有學(xué)者考慮連續(xù)泊位對(duì)集成優(yōu)化的影響和采用精確算法求解。
綜上,現(xiàn)有文獻(xiàn)關(guān)于船舶調(diào)度方面較多,動(dòng)態(tài)連續(xù)泊位分配次之,泊位分配與船舶調(diào)度集成優(yōu)化最少,后者為港口調(diào)度領(lǐng)域關(guān)鍵問題之一。然而,針對(duì)泊位分配與船舶調(diào)度集成優(yōu)化問題,大部分研究都假設(shè)船舶待??坎次灰阎?,只是得到船舶進(jìn)出港的最佳時(shí)刻,此時(shí)已有泊位分配方案未必最佳,實(shí)際上應(yīng)根據(jù)船舶調(diào)度與泊位分配交互影響來(lái)制定最佳泊位分配方案與船舶進(jìn)出港時(shí)刻表;同時(shí),現(xiàn)如今大多數(shù)港口的泊位為連續(xù)泊位,連續(xù)泊位分配是一個(gè)以時(shí)間與岸線為維度的二維裝箱問題,當(dāng)其與船舶調(diào)度問題結(jié)合時(shí),由于后到港船舶可能因船長(zhǎng)因素而先進(jìn)港,從而改變進(jìn)出港次序,進(jìn)而改變前到港船舶靠泊位置,使問題變得尤為復(fù)雜,增加了求解難度;除此之外,現(xiàn)有文獻(xiàn)大都基于啟發(fā)式算法或仿真方法來(lái)解決二者集成優(yōu)化問題,罕有采用具有較強(qiáng)理論支撐的優(yōu)化理論和精確算法。
因此,本文研究動(dòng)態(tài)連續(xù)泊位分配與船舶調(diào)度集成優(yōu)化問題,從降低港口成本的視角出發(fā),重點(diǎn)考慮潮汐與進(jìn)出港時(shí)段對(duì)集成優(yōu)化的影響,兼顧單向航道的作業(yè)特點(diǎn),并設(shè)計(jì)效果較好的精確算法進(jìn)行求解,最終制定固定計(jì)劃期內(nèi)各艘船舶最佳泊位分配方案和進(jìn)出港時(shí)序。
在預(yù)知船舶抵港計(jì)劃、配載計(jì)劃后,港口會(huì)為其制定靠泊計(jì)劃與作業(yè)計(jì)劃。當(dāng)船舶抵達(dá)港口后,其將停靠在錨地,直至得到VTS 中心允許起錨指令后,船舶通過航道行駛至對(duì)應(yīng)泊位,并在此完成裝船或者卸船作業(yè);當(dāng)船舶提出離港申請(qǐng)后,港口會(huì)把此艘船舶的船名、靠泊位置等信息發(fā)送到VTS 中心審核,直到船舶得到可以離港的通知后,才可通過航道行駛出港口。從中可知,航道與泊位對(duì)港口作業(yè)效率有非常大的影響。
其中,考慮航道資源的船舶調(diào)度目的是在遵循航道管理的前提下,讓船舶盡快通過航道,降低在港停留時(shí)間。現(xiàn)如今大多數(shù)港口受到航道寬度的限制,只能單向通過,異向行駛的船舶無(wú)法同時(shí)通行,即航道類型為單向航道。若不制定合適次序,將導(dǎo)致進(jìn)港船舶一直??吭阱^地、出港船舶停泊在港池內(nèi),容易發(fā)生碰撞。同時(shí),整個(gè)計(jì)劃期可分為多個(gè)進(jìn)港時(shí)段與出港時(shí)段,且時(shí)段交替進(jìn)行,即船舶只能在進(jìn)港時(shí)段完成進(jìn)港過程,出港時(shí)段完成出港過程;此外,船舶在航行時(shí)前后之間須保持安全距離,以免發(fā)生追尾,且某些大型船舶需乘潮進(jìn)出港口。
動(dòng)態(tài)連續(xù)泊位分配指船舶不是計(jì)劃期開始時(shí)就已??吭阱^地,而是在計(jì)劃期內(nèi)動(dòng)態(tài)到達(dá)港口,且船舶的船頭可選擇岸線任意位置來(lái)停靠。同時(shí),不同船舶靠泊位置與時(shí)間段不能同時(shí)存在重疊。泊位一般與港口后方堆場(chǎng)某些箱區(qū)匹配,即??看瞬次坏拇岸际峭ㄟ^上述箱區(qū)來(lái)裝卸貨物,從而產(chǎn)生偏好泊位。若船舶靠泊位置偏離偏好泊位,將會(huì)增加此艘船舶與堆存箱區(qū)間的距離,導(dǎo)致港口作業(yè)成本增加,被稱為泊位偏離成本。此外,若船舶實(shí)際開始離港時(shí)刻晚于預(yù)計(jì)離港時(shí)刻,且這是由于港口作業(yè)安排造成的,則港口需要給船舶一定經(jīng)濟(jì)補(bǔ)償,被稱為船舶滯期成本。
因此,本文問題可描述為,針對(duì)單向航道的連續(xù)泊位集裝箱港口,已知船舶預(yù)計(jì)到港時(shí)刻等信息,重點(diǎn)關(guān)注大型船舶需乘潮進(jìn)出港口與進(jìn)出港時(shí)段交替的作業(yè)現(xiàn)實(shí),兼顧船舶靠泊的時(shí)空約束與航行時(shí)需保持安全距離的要求,以船舶滯期成本與泊位偏離成本之和最小為目標(biāo)函數(shù),確定每艘船舶的進(jìn)港時(shí)刻、出港時(shí)刻與靠泊位置。
(1)船舶的船頭均朝向岸線刻度為0的方向;(2)船舶進(jìn)出港過程只能分別發(fā)生在進(jìn)港時(shí)段與出港時(shí)段;(3)不涉及船舶具體裝卸過程。
模型所涉及到的參數(shù)、中間變量與決策變量如表1。
表1 符號(hào)說明Table 1 Symbol description
(1)目標(biāo)函數(shù)
其中,mi×ci為泊位偏離成本;ui×wi為滯期成本,目標(biāo)函數(shù)為所有船舶上述成本之和最小。
(2)約束條件
其中,式(1)表示各艘船舶選取的靠泊位置不能重合;式(2)、(3)表示船舶在航道航行時(shí)需保持安全距離;式(4)定義了變量xxit;式(5)定義了變量yyit;式(6)表示每艘船舶的船頭需選擇一個(gè)靠泊位置;式(7)表示每艘船舶靠泊位置不能超過岸線長(zhǎng)度;式(8)定義了變量qqi;式(9)~(11)表示船舶開始進(jìn)港時(shí)刻的相關(guān)約束;式(12)~(14)表示船舶開始離港時(shí)刻的相關(guān)約束;式(15)、(16)定義了變量ui;式(17)、(18)定義了變量;式(19)~(21)定義了變量;式(22)~(23)定義了變量;式(24)~(26)定義了變量;式(27)、(28)定義了變量zijt;式(29)表示每艘船舶需選擇一個(gè)進(jìn)港時(shí)段進(jìn)行進(jìn)港過程;式(30)、(31)表示船舶進(jìn)港開始時(shí)刻與進(jìn)港完成時(shí)刻需在時(shí)段范圍內(nèi);式(32)表示每艘船舶需選擇一個(gè)出港時(shí)段進(jìn)行出港過程;式(33)、(34)表示船舶出港開始時(shí)刻與出港完成時(shí)刻需在時(shí)段范圍內(nèi);式(35)表示乘潮船舶須選一個(gè)潮汐時(shí)段來(lái)完成進(jìn)港;式(36)~(40)表示乘潮船舶進(jìn)出港開始時(shí)刻與進(jìn)出港完成時(shí)刻需滿足的時(shí)間約束;式(41)、(42)定義了變量mi;式(43)表示變量取值范圍。
通過觀察上述混合整數(shù)線性規(guī)劃模型,可知式(1)~(3)為耦合約束,其余約束具有對(duì)角分塊結(jié)構(gòu),可針對(duì)每一艘船舶單獨(dú)求解。因此,通過Dantzig-Wolfe 分解方法把上述數(shù)學(xué)模型分成一個(gè)主問題與子問題,每艘船舶對(duì)應(yīng)一個(gè)子問題,且通過求解新模型得到的最優(yōu)解為原問題最優(yōu)解[22]。
為便于描述主問題,定義如表2所示符號(hào)。主問題模型如下所示:
表2 主模型符號(hào)Table 1 Master model symbol
式(44)為目標(biāo)函數(shù),表示所有方案泊位偏離成本與滯期成本之和最?。皇剑?5)表示所有方案中的船舶不能在同一時(shí)刻占用相同岸線位置;式(46)、(47)表示所有方案中的船舶在航道航行時(shí)需保持安全距離;式(48)表示任意一艘船舶需選擇一個(gè)方案;式(49)表示變量sri的取值范圍。由于可選的船舶調(diào)度方案數(shù)量較多,本文通過列生成算法求解主問題的松弛問題。在松弛掉0-1變量相關(guān)約束之后,即約束(49),其余的約束與目標(biāo)函數(shù)構(gòu)成列生成算法用到的主問題模型。
分別以π、μ、α、β當(dāng)作約束(45)~(48)的對(duì)偶變量,則主問題檢驗(yàn)數(shù)的表達(dá)式為:
在列生成迭代過程中,子問題是尋找檢驗(yàn)數(shù)小于0的列,并把它添加到主問題模型中,子模型為:
子問題約束條件為式(4)~(43)。
在每個(gè)子問題中,角標(biāo)i不變,表示相應(yīng)船舶,共有船舶數(shù)量個(gè)子問題。每個(gè)子問題對(duì)應(yīng)一個(gè)船舶調(diào)度方案,其需滿足靠泊位置與進(jìn)出港時(shí)刻有關(guān)約束,且只有目標(biāo)函數(shù)值小于0 的解對(duì)應(yīng)的列才能加入主模型中迭代求解,如果沒有滿足條件的列,則已找到主問題松弛問題最優(yōu)解。同時(shí),根據(jù)對(duì)偶性質(zhì)可知,對(duì)偶變量π、μ、α小于0,當(dāng)β小于等于0時(shí),主問題檢驗(yàn)數(shù)大于等于0,此時(shí)不存在檢驗(yàn)數(shù)小于0的列,則可不必對(duì)子問題進(jìn)行求解。
由于列生成只能得到原問題松弛問題的最優(yōu)解,不能確保這個(gè)解為整數(shù),因此將其與分支定界相結(jié)合,通過分支定價(jià)算法來(lái)求解此問題,如圖1。對(duì)于根節(jié)點(diǎn)(原問題),根據(jù)初始解生成規(guī)則生成初始列加入主問題中,從而得到受限主問題,接著迭代求解主問題和子問題,獲得松弛問題最優(yōu)解。若此解滿足整數(shù)約束,其是原問題最優(yōu)解,否則,需分支。對(duì)于每個(gè)分支(子節(jié)點(diǎn)),通過列生成算法進(jìn)行求解,直到找到原問題可行最優(yōu)解。
圖1 算法流程圖Fig.1 Algorithm flow chart
考慮到進(jìn)出港時(shí)段交替,且船舶靠泊位置同之前進(jìn)港船舶靠泊位置有關(guān),因此本文針對(duì)每一艘船舶,根據(jù)進(jìn)出港時(shí)段、有無(wú)偏好泊位,基于滯期成本與偏離成本之和最小的貪婪策略生成初始解。
步驟1若某船為乘潮船舶,比較預(yù)計(jì)到港時(shí)刻與潮汐時(shí)段,確定乘潮船預(yù)計(jì)最早進(jìn)港時(shí)刻,且非乘潮船預(yù)計(jì)最早進(jìn)港時(shí)刻為預(yù)計(jì)到港時(shí)刻。根據(jù)預(yù)計(jì)最早進(jìn)港時(shí)刻從早到晚對(duì)船舶重新進(jìn)行排序,從而得到初始船舶進(jìn)港次序。
步驟2i表示進(jìn)港次序的序號(hào),t表示進(jìn)出港時(shí)段,令i=1,t=1。
步驟3若t為進(jìn)港時(shí)段,則轉(zhuǎn)到步驟4,否則轉(zhuǎn)到步驟5。
步驟4從序號(hào)i對(duì)應(yīng)的船舶開始分配泊位:若某船沒有偏好泊位且滿足進(jìn)港時(shí)間約束,則隨機(jī)選擇某位置為靠泊泊位;若此船有偏好靠泊位置、靠泊區(qū)間不與其他船重疊且滿足進(jìn)港時(shí)間約束,則靠泊泊位為偏好靠泊位置,否則為此艘船滯期成本與偏離成本之和最小時(shí)的岸線位置,若此時(shí)船舶進(jìn)港完成時(shí)刻大于此時(shí)段結(jié)束時(shí)刻,則更新此船舶預(yù)計(jì)最早進(jìn)港時(shí)刻,且重新生成包括此船在內(nèi)的后續(xù)船舶的初始進(jìn)港次序;若此時(shí)無(wú)滿足靠泊約束的空閑泊位或該船不滿足進(jìn)港時(shí)間約束,則等到下一進(jìn)港時(shí)段為此艘船舶分配靠泊位置。記錄此時(shí)段分配泊位的最后一艘進(jìn)港船舶的序號(hào)i′與已分配船舶實(shí)際開始進(jìn)港時(shí)刻,令i=i′+1,并轉(zhuǎn)到步驟6。
步驟5安排此時(shí)段內(nèi)完成作業(yè)的船舶在滿足時(shí)間約束條件下出港,記錄船舶實(shí)際離港時(shí)刻,且其為此靠泊泊位的開始空閑時(shí)刻,并轉(zhuǎn)到步驟6。
步驟6若i≤船舶總數(shù),則令t=t+1,并轉(zhuǎn)到步驟3,否則輸出解。
如果直接對(duì)主問題中的變量進(jìn)行分支,那么需要在主問題中加入新的約束,從而生成新的對(duì)偶變量,這種分支策略會(huì)嚴(yán)重破壞子問題的結(jié)構(gòu),使得無(wú)論是主問題還是子問題,編程與計(jì)算都很繁瑣。因此,本文對(duì)原問題變量進(jìn)行分支,將約束條件加入子問題中。步驟如下所示:
步驟1針對(duì)子節(jié)點(diǎn)或者根節(jié)點(diǎn)計(jì)算得到的最優(yōu)解,判斷其是否為原問題的整數(shù)解,如果不是,則按照船舶編號(hào)從小到大的次序,找到第一艘含有非整數(shù)解的船舶i。
步驟2按照時(shí)刻t從小到大判斷xit,選擇第一個(gè)不是整數(shù)的xit。若不是整數(shù),則對(duì)變量分支,包括t′≤t和t′>t兩支。主問題與子問題變換規(guī)則如下:對(duì)于t′≤t這一分支,將t′≤t加到子問題中,即令t′>t的xit′都為0,且刪除已加入主問題中含有t′>t的的列。對(duì)于t′>t這一分支,將t′>t加入子問題中,即令t′≤t的xit′都為0,且刪除已加入主問題中含有t′≤t的的列。
步驟3若所有xit為整數(shù),則按照時(shí)刻t從小到大判斷yit,選取第一個(gè)不為整數(shù)的yit。若不為整數(shù),則分為t′≤t和t′>t兩支,且主問題與子問題變換參照步驟2。
步驟4若所有yit為整數(shù),則按照位置j從小到大判斷qij,選取第一個(gè)不為整數(shù)的qij。若=qij不為整數(shù),則分為j′≤j和j′>j兩支,且主問題與子問題變換參照步驟2。
常見的搜索策略包括深度優(yōu)先策略與廣度優(yōu)先策略,當(dāng)搜索樹的深度比較小時(shí),采用深度優(yōu)先搜索策略能較快找到問題的上界值。然而,本文的決策變量較多,將會(huì)產(chǎn)生比較多的分支,此時(shí)若采用深度優(yōu)先策略需耗費(fèi)很長(zhǎng)時(shí)間才能找到最優(yōu)解,因此本文采用廣度優(yōu)先策略,具體內(nèi)容如下。
步驟1初始化搜索樹,共有兩個(gè)搜索樹,分別為原搜索樹與新搜索樹。把根節(jié)點(diǎn)加入原搜索樹中,計(jì)算根節(jié)點(diǎn)。
步驟2若根節(jié)點(diǎn)的解為整數(shù)解,則轉(zhuǎn)到步驟7,否則轉(zhuǎn)到步驟3。
步驟3把根節(jié)點(diǎn)的解作為全局下界值,并進(jìn)行分支,在原搜索樹中刪除根節(jié)點(diǎn),并把分支得到的子節(jié)點(diǎn)加入原搜索樹。
步驟4若原搜索樹為空,轉(zhuǎn)到步驟7,否則,轉(zhuǎn)到步驟5。
步驟5利用列生成算法計(jì)算原搜索樹中的節(jié)點(diǎn),若某節(jié)點(diǎn)最優(yōu)值超過或者等于全局上界值,則剪枝,把此節(jié)點(diǎn)從原搜索樹中移除,并轉(zhuǎn)到步驟4,否則轉(zhuǎn)到步驟6。
步驟6若節(jié)點(diǎn)最優(yōu)值為整數(shù)解,則更新全局上界值,剪枝,并把此節(jié)點(diǎn)從原搜索樹中移除,且轉(zhuǎn)到步驟4,否則,進(jìn)行分支,并把得到的子節(jié)點(diǎn)加入到新搜索樹中,且轉(zhuǎn)到步驟4。
步驟7若新搜索樹為空,結(jié)束算法,否則,原搜索樹等于新搜索樹,并清空新搜索樹,且轉(zhuǎn)到步驟4。
在列生成過程中,當(dāng)存在檢驗(yàn)數(shù)小于0 的列時(shí),把它加入到限制性主問題中,無(wú)法保證對(duì)應(yīng)的決策變量的數(shù)值是1,即在最優(yōu)解中沒用到此列代表的船舶調(diào)度方案。因此,若每一次迭代只在限制性主問題中加入一條檢驗(yàn)數(shù)小于0且絕對(duì)值最大的列,可能在迭代更多次數(shù)之后才能求得最優(yōu)解,但這會(huì)降低每一次迭代問題的復(fù)雜度,減少求解時(shí)間。若把子問題中所有檢驗(yàn)數(shù)為負(fù)的列都加入限制性主問題,將會(huì)降低整個(gè)列生成過程所需的迭代次數(shù),但會(huì)增加限制性主問題的復(fù)雜度,使得限制性主問題的求解時(shí)間增加。因此,本文根據(jù)實(shí)驗(yàn)結(jié)果選擇適合本問題的列選取策略。
某集裝箱碼頭擁有連續(xù)岸線1 000 m,由于船舶長(zhǎng)度一般在50 的倍數(shù)附近,以50 m 為單位劃分為一個(gè)距離單元,則可劃分為20個(gè)單元,即岸線靠泊位置為1~20;計(jì)劃期為12 h,以30 min 為單位劃分為一個(gè)時(shí)間單元,則計(jì)劃期可以劃分為24 個(gè)單元,即進(jìn)出港時(shí)刻為1~24時(shí);根據(jù)港口實(shí)際作業(yè)情況,船舶安全航行距離為1 個(gè)時(shí)間單元,船舶從錨地航行到岸線的平均時(shí)間為1個(gè)時(shí)間單元,船舶進(jìn)出港時(shí)段長(zhǎng)度為4 個(gè)時(shí)間單元,且第一個(gè)時(shí)段為進(jìn)港時(shí)段;第一個(gè)潮汐時(shí)段開始時(shí)刻為第9時(shí)間單元,結(jié)束時(shí)刻為第22時(shí)間單元,且潮汐時(shí)段間隔為36個(gè)時(shí)間單元。各船舶預(yù)計(jì)到港時(shí)刻與預(yù)計(jì)離港時(shí)刻隨機(jī)生成,作業(yè)所需時(shí)間單元為[1,12]范圍內(nèi)的隨機(jī)整數(shù),有偏好泊位的船舶數(shù)量不超過船舶總數(shù)的2/3,且乘潮船舶數(shù)量不超過船舶總數(shù)的1/4。算法通過MATLAB R2014a和Gurobi求解器實(shí)現(xiàn),并在3.60 GHz Intel Core i7-7700CPU和8 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行程序。
根據(jù)上述數(shù)據(jù),生成不同船舶規(guī)模情況下的實(shí)驗(yàn),策略1 表示每次迭代在主問題中加入所有檢驗(yàn)數(shù)為負(fù)的列,策略2表示每次迭代在主問題中加入一條檢驗(yàn)數(shù)為負(fù)且絕對(duì)值最大的列,如表3所示。在所有實(shí)驗(yàn)中策略1 所需的計(jì)算時(shí)間小于策略2,且隨著船舶規(guī)模的增加,二者計(jì)算時(shí)間之間的差距越來(lái)越大,因此本文采用策略1所代表的列選取策略,即在每次迭代時(shí)在主問題中加入所有檢驗(yàn)數(shù)為負(fù)的列。
表3 列選取策略對(duì)比Table 3 Comparison of column selection strategy
若計(jì)劃期內(nèi)各艘船舶基本信息如表4 所示,其中3號(hào)船舶需要乘潮進(jìn)出港口。結(jié)果如表5 與圖2 所示,運(yùn)行時(shí)間為162 s,目標(biāo)成本為8 600元。在港口實(shí)際作業(yè)中,船舶按先到先服務(wù)(FCFS)策略進(jìn)行調(diào)度,且保證滯期成本與泊位偏離成本之和最小,得到的調(diào)度方案如圖3所示。
圖2 最優(yōu)集成調(diào)度方案Fig.2 Optimal integrated scheduling scheme
圖3 FCFS調(diào)度方案Fig.3 Scheduling scheme of FCFS
表4 船舶基本信息Table 4 Basic information of ships
表5 船舶調(diào)度方案Tab.5 Ship scheduling scheme
在FCFS方案中,3號(hào)船舶先于4號(hào)船舶進(jìn)港,此時(shí)4號(hào)船舶作業(yè)完成時(shí)刻為16,無(wú)法在此時(shí)段內(nèi)完成出港過程,因此只能在下一出港時(shí)段出港,導(dǎo)致4號(hào)船舶滯期,并導(dǎo)致5 號(hào)船舶偏離偏好泊位。本文得到的協(xié)同優(yōu)化方案改變了船舶進(jìn)港次序,從而避免上述情況的發(fā)生。從結(jié)果來(lái)看,F(xiàn)CFS方案總成本為11 980元,集成調(diào)度方案總成本為8 600 元,則相比于FCFS 方案,集成調(diào)度方案降低了28.2%成本。
在不同船舶數(shù)量的情況下生成下列實(shí)驗(yàn),針對(duì)同一種實(shí)驗(yàn),在相同運(yùn)行環(huán)境下,使用本文設(shè)計(jì)的分支定價(jià)算法、Gurobi 和傳統(tǒng)遺傳算法分別進(jìn)行求解,比較三者的目標(biāo)值與計(jì)算時(shí)間,并設(shè)定計(jì)算時(shí)間上限為3 600 s。若超過3 600 s,則算法終止,輸出此時(shí)程序中的局部最優(yōu)解,且用“—”表示無(wú)符合條件的解,GAP1表示分支定價(jià)算法與Gurobi目標(biāo)值的差值,GAP2表示遺傳算法與分支定價(jià)算法目標(biāo)值的差值,如表6 所示。從中可知,分支定價(jià)算法與Gurobi 的目標(biāo)值一樣,驗(yàn)證了本文算法的準(zhǔn)確性。同時(shí),隨著到港船舶數(shù)量的變大,Gurobi 求解所需時(shí)間呈現(xiàn)指數(shù)遞增的趨勢(shì),當(dāng)船舶規(guī)模不小于9 艘時(shí),其在一個(gè)小時(shí)內(nèi)已無(wú)法求出較優(yōu)整數(shù)解,而分支定價(jià)算法對(duì)于不同船舶規(guī)模,都可在規(guī)定時(shí)間內(nèi)求出最優(yōu)解,且一般在25 min 以內(nèi)。除此之外,GAP2 隨著船舶數(shù)量的增加而變大,表明遺傳算法求解質(zhì)量越來(lái)越差,而本文設(shè)計(jì)的分支定價(jià)算法在所有算例中求得最優(yōu)解。盡管遺傳算法所需要的求解時(shí)間比較少,但分支定價(jià)算法所需時(shí)間也在可以接受的范圍內(nèi),表明本文提出的分支定價(jià)算法求解效率較高。
表6 算法結(jié)果比較Table 6 Comparison of algorithm results
船舶進(jìn)出港時(shí)刻由各進(jìn)出港時(shí)段開始與結(jié)束時(shí)刻以及作業(yè)所需時(shí)間決定,它會(huì)直接影響本文模型的計(jì)算結(jié)果。由于每艘船作業(yè)所需時(shí)間是一定的,因此本文分析進(jìn)出港時(shí)段長(zhǎng)度對(duì)總成本的影響,如表7 所示。表7中的數(shù)據(jù)是改變船舶規(guī)模與進(jìn)出港時(shí)段生成的,且為了保證實(shí)驗(yàn)的一致性,船舶數(shù)量多的實(shí)驗(yàn)的基本數(shù)據(jù)包括船舶數(shù)量小的實(shí)驗(yàn)的基本數(shù)據(jù),例如船舶數(shù)量為8這一實(shí)驗(yàn)包括船舶數(shù)量為6 這一實(shí)驗(yàn)的6 艘船,并另外生成兩艘船。在港口實(shí)際作業(yè)中,每艘船完成進(jìn)出港過程所需時(shí)間最大約為40 min,為保證同一進(jìn)出港時(shí)段中至少有1艘船舶能夠安全通過航道,設(shè)定進(jìn)出港時(shí)段長(zhǎng)度分別為60、90、120、150、180,單位為min。
表7 進(jìn)出港時(shí)段設(shè)置分析Tab.7 Inbound and outbound port period setting analysis
從表7 可知,隨著船舶數(shù)量的增加,總成本逐漸增加,但對(duì)于同種船舶規(guī)模,總成本隨著進(jìn)出港時(shí)段長(zhǎng)度的增加先變小再逐漸變大。當(dāng)進(jìn)出港時(shí)段長(zhǎng)度增加,由于船舶需要在進(jìn)港時(shí)段才能執(zhí)行進(jìn)港過程,在出港時(shí)段才能執(zhí)行出港過程,導(dǎo)致部分船舶開始進(jìn)出港時(shí)刻變大,從而造成滯期時(shí)間增加,進(jìn)而引起總成本增加;當(dāng)進(jìn)出港時(shí)段長(zhǎng)度增加到一定程度時(shí),由于原本部分船舶到達(dá)港口的時(shí)刻在出港時(shí)段內(nèi)或作業(yè)完成時(shí)刻在進(jìn)港時(shí)段內(nèi),此時(shí)這些船舶可以在到達(dá)港口或作業(yè)完成時(shí)直接進(jìn)出港口,導(dǎo)致船舶開始進(jìn)出港時(shí)刻變小,從而降低滯期時(shí)間,進(jìn)而引起總成本減??;當(dāng)進(jìn)出港時(shí)段長(zhǎng)度繼續(xù)增加時(shí),船舶開始進(jìn)出港時(shí)刻已經(jīng)沒有了減小的空間,此時(shí)船舶需要等待越來(lái)越長(zhǎng)的時(shí)間才能開始進(jìn)出港口,從而導(dǎo)致滯期時(shí)間的增加,進(jìn)而引起總成本的增加。因此,港口需合理設(shè)置進(jìn)出港時(shí)段,從而提高作業(yè)效率,降低成本。
作為集裝箱港口的重要資源,泊位有效分配與航道合理利用是港口管理水平和服務(wù)能力的重要體現(xiàn)。本文對(duì)連續(xù)泊位下的泊位分配與船舶調(diào)度集成優(yōu)化問題進(jìn)行了研究,在考慮了船舶動(dòng)態(tài)到達(dá)、進(jìn)出港時(shí)段交替、大船需乘潮進(jìn)出港口與偏好泊位的基礎(chǔ)上,以總成本最小為目標(biāo)函數(shù),通過建立模型與設(shè)計(jì)算法,給出了一個(gè)計(jì)劃期內(nèi)到港船舶泊位分配方案與進(jìn)出港時(shí)刻,不僅可以降低總成本,還能減少船舶在港時(shí)間。
針對(duì)問題的特點(diǎn)設(shè)計(jì)了精確型分支定價(jià)算法,提出了有效的分支策略、搜索策略與列選取策略,可為解決類似問題提供了一種算法設(shè)計(jì)思路。
研究結(jié)果表明:在港口實(shí)際作業(yè)中,泊位分配與船舶調(diào)度之間的協(xié)同、乘潮船舶和進(jìn)出港時(shí)段的長(zhǎng)度是影響海側(cè)運(yùn)營(yíng)效率的關(guān)鍵要素。其中,首先應(yīng)重點(diǎn)關(guān)注泊位分配與船舶調(diào)度之間的交互影響;其次,在安排船舶進(jìn)出港時(shí)需優(yōu)先考慮乘潮船舶;最后,可依據(jù)每天船舶總量合理設(shè)置進(jìn)出港時(shí)段。
在未來(lái)的研究中,可研究船舶調(diào)度、泊位分配與岸橋調(diào)度集成優(yōu)化問題,并改進(jìn)子問題的求解方法,降低計(jì)算時(shí)間。