基于模擬退火遺傳算法的內(nèi)河港口船舶進(jìn)出港調(diào)度方法

李於彬

(中鐵長(zhǎng)江交通設(shè)計(jì)集團(tuán)有限公司,重慶 400121)

0 引 言

經(jīng)濟(jì)全球化的發(fā)展,使得水路運(yùn)輸?shù)倪\(yùn)量不斷上升,船舶也逐漸向高速化、大型化的方向發(fā)展。進(jìn)出港船舶數(shù)量的大幅增加,造成港口資源中的航道、泊位等配置緊張,船舶進(jìn)出港耗費(fèi)大量的時(shí)間,港口服務(wù)的滿意度逐漸下降[1]。在不大幅改變港口硬件設(shè)施的條件下,對(duì)船舶進(jìn)出港的調(diào)度方案進(jìn)行優(yōu)化處理,提高進(jìn)出港的效率,可以有效避免或減少港口船舶壓港、滯港等現(xiàn)象[2]。

增加港口規(guī)模,能夠有效改變港口擁擠的狀態(tài),但是港口的擴(kuò)建需要消耗大量的經(jīng)費(fèi),建設(shè)周期過(guò)長(zhǎng)[3]。對(duì)于內(nèi)河港口來(lái)說(shuō),利用優(yōu)化算法調(diào)整船舶進(jìn)出港口的調(diào)度方案,優(yōu)化船舶的進(jìn)出港時(shí)間,能夠最大效率的發(fā)揮港口的作用,改善港口的通航效率。在相關(guān)方面的研究中,鄭紅星等[4]綜合考慮了船舶進(jìn)出港受到的約束條件以及泊位的工作約束情況等,通過(guò)建立進(jìn)出港調(diào)度規(guī)劃模型,利用算法分析確定各類船舶的進(jìn)出港最優(yōu)時(shí)間段,大幅提高了港口的運(yùn)行效率。Kim K H[5]等在船舶進(jìn)出港模型中,考慮了船舶停靠的具體位置和具體時(shí)間,并利用成本最優(yōu)的優(yōu)化調(diào)度方式,采用模擬退火算法獲得模型的最優(yōu)解,取得了不錯(cuò)的效果。

本文針對(duì)內(nèi)河航道中船舶進(jìn)出港的調(diào)度問(wèn)題,研究了基于模擬退火算法和遺傳算法的調(diào)度模型,綜合考慮船舶進(jìn)出港過(guò)程中的速度、距離、泊位以及裝卸時(shí)間等因素,發(fā)揮兩種算法的優(yōu)勢(shì),實(shí)現(xiàn)資源調(diào)度的最優(yōu)化。通過(guò)試驗(yàn)結(jié)果證明,求解后的調(diào)度模型可以有效提高港口的船舶進(jìn)出港效率,降低資源消耗并提高港口的經(jīng)濟(jì)效益,為類似內(nèi)河港口的調(diào)度方法研究提供了參考。

1 內(nèi)河港口調(diào)度

1.1 傳統(tǒng)調(diào)度方法

傳統(tǒng)的船舶調(diào)度,以“先到先走”的服務(wù)模型為基礎(chǔ)。進(jìn)入港口的船舶,通過(guò)調(diào)度安排進(jìn)入航道,到達(dá)指定泊位后進(jìn)行停泊裝卸作業(yè)[6]。而其他未通過(guò)進(jìn)港審核的船舶,則需要在錨地等待,待泊位內(nèi)的船只完成作業(yè)后,安排其進(jìn)港,調(diào)度效率較低。

船舶符合出港的條件時(shí),同樣向調(diào)度中心發(fā)出申請(qǐng),由中心對(duì)其出港進(jìn)行調(diào)度放行。由于調(diào)度或其他原因,出現(xiàn)進(jìn)出港船舶沖突的情況時(shí),安排船舶原地等待,待問(wèn)題解決后,依次排隊(duì)出港[7]。

由于這種人工操作的船舶調(diào)度方式,運(yùn)行效率主要依靠工作人員的個(gè)人經(jīng)驗(yàn),使得船舶通行效率受到嚴(yán)重影響。大量的物資滯留,也會(huì)造成巨大的經(jīng)濟(jì)損失,迫切需要具有多目標(biāo)協(xié)調(diào)的能力的調(diào)度方法來(lái)實(shí)現(xiàn)船舶調(diào)度高效率運(yùn)行[8]。

1.2 內(nèi)河港口調(diào)度約束條件

對(duì)于內(nèi)河港口的船舶調(diào)度來(lái)說(shuō),除了需要考慮船舶的進(jìn)出港時(shí)間,還需要考慮內(nèi)河航道上是否存在其他船舶,航道內(nèi)這些非調(diào)度的船舶運(yùn)行狀態(tài),同樣會(huì)對(duì)港口的調(diào)度效率產(chǎn)生嚴(yán)重影響,需要綜合考慮[9]。

對(duì)于港口的船舶進(jìn)出港調(diào)度模型來(lái)說(shuō),如何在確保船舶安全的前提下,實(shí)現(xiàn)船舶的進(jìn)出港操作,最大限度的保證港口的運(yùn)轉(zhuǎn)效率,是調(diào)度模型需要處理的核心問(wèn)題和關(guān)鍵所在[10]。

一般情況下,船舶在錨地等待的時(shí)間越短,港口的運(yùn)轉(zhuǎn)效率越高。從而可以在船舶調(diào)度模型的建立中,在全面考慮調(diào)度公平性的前提下,以船舶在港口的等待時(shí)間作為港口調(diào)度模型效果的衡量指標(biāo),進(jìn)行進(jìn)出港調(diào)度[11]。

在綜合考慮船舶安全性的前提下,調(diào)度模型的約束條件主要包括三個(gè)方面:航道尤其是潮汐航道內(nèi)的船舶進(jìn)出港時(shí)間、泊位問(wèn)題、安全距離等。

對(duì)于被調(diào)度進(jìn)出港的船舶,需要保證其在此行進(jìn)過(guò)程中與其他同向船舶之間安全距離。因此需要在調(diào)度中,要求后方船舶的航行速度不能超過(guò)前方船舶,避免意外碰撞的發(fā)生[12]。安全調(diào)度距離涉及到的參數(shù)包括船舶的航速和兩者間的距離等。一般情況下,為了保證船舶間的安全性,要求兩者的安全距離大于船體平均長(zhǎng)度的六倍。在船舶同向行駛的過(guò)程中,需要前后兩船之間具有足夠的速度差或距離差,從而在前船到達(dá)目的地時(shí),與后船的距離保持在安全距離以外。

兩艘同向行駛船舶的安全時(shí)間間隔,可以用公式表示為

θij≥Xij×

(1)

式中:Vi和Vj分別為i,j兩船航行的速度;Ti和Tj分別為i,j兩船從出發(fā)到目的地之間行駛的時(shí)間;Li為船舶i的自身長(zhǎng)度;Xij為兩船的關(guān)系系數(shù),當(dāng)兩者是前后船的關(guān)系時(shí),取值為1,否則取0。

泊位的調(diào)度過(guò)程中,需要保證剩余泊位長(zhǎng)度大于船體長(zhǎng)度。對(duì)于長(zhǎng)度較大的船體,當(dāng)其進(jìn)港時(shí),需要保證在其到達(dá)泊位的時(shí)間內(nèi),離開(kāi)的船體長(zhǎng)度可以為其提供足夠長(zhǎng)的泊位位置。

2 模擬退火遺傳算法

2.1 模擬退火算法

模擬退火算法主要是模擬工業(yè)技術(shù)中的退火工藝,其工藝原理為,利用高溫提高材料內(nèi)部的原子動(dòng)能,提高其熱運(yùn)動(dòng)能力,進(jìn)而回到自身最優(yōu)化的位置[13]。

模擬退火算法中的主要參數(shù)包括初始溫度、升溫速率、恒溫溫度等。通過(guò)調(diào)整計(jì)算過(guò)程中的溫度參數(shù),通過(guò)組合迭代的關(guān)系,找到問(wèn)題的最佳答案。

2.2 遺傳算法

遺傳算法的工作原理來(lái)自于達(dá)爾文的進(jìn)化論理論,該算法主要通過(guò)染色體的變化,結(jié)合實(shí)際應(yīng)用,利用不同種群之間的交叉、變異和選擇的步驟的操作,找到求解問(wèn)題的最優(yōu)解。

遺傳算法的主要計(jì)算流程為:獲取初始種群,利用適應(yīng)度函數(shù)對(duì)種群加以評(píng)價(jià),選擇所有初始個(gè)體中的最佳個(gè)體作為父代,與其他染色體進(jìn)行交叉、變異操作,形成新的子代。繼續(xù)利用適應(yīng)度函數(shù)對(duì)其進(jìn)行評(píng)價(jià),直到找到最優(yōu)解。

2.3 模擬退火與遺傳算法的結(jié)合

模擬退火算法與遺傳算法在最優(yōu)解的尋找方面都具有各自的優(yōu)勢(shì),將其有機(jī)結(jié)合形成融合算法,既能夠增強(qiáng)算法的全局搜索能力,又可以有效避免出現(xiàn)算法早熟的現(xiàn)象。

利用融合后的算法求解船舶進(jìn)出港的調(diào)度序列問(wèn)題,可以首先利用遺傳算法的染色體規(guī)則來(lái)描述模型的船舶,并根據(jù)算法中的決策變量xij來(lái)設(shè)計(jì)染色體。

船舶在進(jìn)出港的過(guò)程中,時(shí)間具有隨機(jī)性,因此需要對(duì)決策變量xij進(jìn)行拆分,將所有參與到調(diào)度進(jìn)港的船舶分成進(jìn)港和出港兩個(gè)決策變量。設(shè)染色體A表示進(jìn)出港船舶的順序,對(duì)其進(jìn)行實(shí)數(shù)編碼,同一個(gè)泊位的先后兩艘出港船舶代表泊位使用的先后順序[14]。

對(duì)于調(diào)度隊(duì)列同樣利用自然數(shù)進(jìn)行編號(hào),其序號(hào)為隊(duì)列順序編碼,與船舶到達(dá)時(shí)間一致。利用染色體對(duì)于出港船舶進(jìn)行編碼,編碼的順序由實(shí)際規(guī)則參數(shù)決定,對(duì)于同一泊位中的船舶,其編碼反映了其進(jìn)出港的先后順序。

2.4 融合后算法的優(yōu)化

遺傳算法中,交叉算子對(duì)于進(jìn)化起到?jīng)Q定作用。交叉規(guī)則能夠有效提高種群內(nèi)染色體的搜索范圍,并能夠?qū)?yōu)秀的染色體加以保存,避免由于交叉破壞原有的計(jì)算結(jié)果。采用的混合交叉操作如下。

根據(jù)染色體的長(zhǎng)度,以隨機(jī)的方式產(chǎn)生多段染色體交叉序列。根據(jù)合適的位置選擇,來(lái)交換對(duì)應(yīng)的染色體基因片段。對(duì)于基因結(jié)合后出現(xiàn)沖突的染色體進(jìn)行檢測(cè),并根據(jù)情況進(jìn)行修復(fù)。

變異算子的作用在提高算法的搜索能力,利用基因突變的原理,避免過(guò)早出現(xiàn)算法收斂。

計(jì)算過(guò)程中,遺傳算法的變異概率Pm和交叉概率Pc一般是通過(guò)試驗(yàn)測(cè)試來(lái)獲得的。這些參數(shù)的一成不變使得當(dāng)系統(tǒng)工作條件發(fā)生變化時(shí),算法的計(jì)算結(jié)果與實(shí)際情況嚴(yán)重不符,造成算法失效,影響整個(gè)港口的調(diào)度運(yùn)行。

為了提高整個(gè)模型的搜索范圍,需要提高模型的交叉概率,從而保證新染色體的出現(xiàn),避免出現(xiàn)計(jì)算過(guò)早收斂、不能找到最優(yōu)解的情況。但是過(guò)高的交叉概率又會(huì)造成計(jì)算前期的搜索結(jié)果不具備代表性。因此對(duì)于染色體交叉概率的設(shè)置,需要符合一定的規(guī)則,既不能一成不變,又不能超出范圍,需要隨著種群的變化而改變。

在算法的設(shè)計(jì)中,對(duì)于需要提升種群進(jìn)化速率的情況就要提高交叉概率,對(duì)于需要保護(hù)染色體的情況,則需要降低交叉概率。

模型的交叉概率可以用函數(shù)形式來(lái)表示,計(jì)算公式表示為

(2)

式中:Pc1代表染色體交叉概率的上限;Pc2代表染色體交叉概率的下限;γ為系統(tǒng)優(yōu)異程度的比值,代表當(dāng)前優(yōu)秀個(gè)體與群體內(nèi)最優(yōu)個(gè)體之間的差距程度。在差距較大時(shí)γ較小,需提高整個(gè)模型的交叉概率,刺激染色體變化。

同樣,對(duì)于模型的變異概率,如果變異概率太小,則容易使算法陷入局部最優(yōu),而無(wú)法獲得全局最優(yōu)解。如果變異概率過(guò)大,則會(huì)使優(yōu)秀個(gè)體發(fā)生變異,同樣出現(xiàn)找不到最優(yōu)解的情況。

為此,同樣需要變異概率利用公式。其表示式為

(3)

式中:Pm1代表染色體變異概率的上限;Pm2代表染色體變異概率的下限;γ為系統(tǒng)優(yōu)異程度的比值。

通過(guò)交叉概率和變異概率的變化,能夠動(dòng)態(tài)調(diào)整系統(tǒng)模型參數(shù),對(duì)于整個(gè)模型求解效率的提高具有重要意義。概率的調(diào)整隨著種群而變化,使其符合種群規(guī)律,且每一次的變化均符合自適應(yīng)變化規(guī)律。這種動(dòng)態(tài)調(diào)整參數(shù)的方法,能夠有效提高遺傳算法的效率,避免出現(xiàn)找不到最優(yōu)解的情況。

3 實(shí)驗(yàn)結(jié)果與算法驗(yàn)證

3.1 實(shí)驗(yàn)條件設(shè)置

為了驗(yàn)證該模型的有效性,利用Matlab 2017b軟件對(duì)于算法進(jìn)行驗(yàn)證。在計(jì)算機(jī)上進(jìn)行算法計(jì)算,電腦配置為:CPU i5-65003.2 GHz,內(nèi)存8 Gb。

實(shí)驗(yàn)數(shù)據(jù)以重慶港數(shù)據(jù)為例,進(jìn)行算法的驗(yàn)證。港區(qū)航道水深6.2 m,均為雙向航道,港內(nèi)共有十個(gè)泊位,依次為泊位1,泊位2,……,泊位10。候泊區(qū)水深約為5.3 m,作業(yè)區(qū)的寬度為2n mile,長(zhǎng)度為2.7n mile,為長(zhǎng)方形區(qū)域。設(shè)定各船舶的平均速度相同,均為7節(jié),以提高系統(tǒng)計(jì)算效率。泊位信息如表1所示。

表1 泊位信息

設(shè)定混合算法中模擬退火算法的初始溫度為100 ℃,終止溫度設(shè)定為1 ℃。

溫度下降策略為指數(shù)下降,表示式為

Tk+1=0.9Tk

(4)

式中:Tk為k時(shí)刻的溫度。

設(shè)定初始種群內(nèi)個(gè)體的數(shù)量為500,交叉概率初始值為0.7,變異概率初始值為0.2。

3.2 實(shí)驗(yàn)結(jié)果對(duì)比

(1)調(diào)度結(jié)果

以該港口在12月中旬某天的數(shù)據(jù)為參考,船舶停靠數(shù)據(jù)規(guī)范后如表2所示。

表2 規(guī)范后的船舶?？繑?shù)據(jù)

利用上述算法,對(duì)整個(gè)船舶的調(diào)度進(jìn)行排序和安排,綜合考慮各船舶的出發(fā)時(shí)間以及船體長(zhǎng)度的限制,出發(fā)時(shí)間早且符合進(jìn)出港調(diào)度長(zhǎng)度的船舶先安排,出港時(shí)間晚的后安排,綜合考慮船舶停靠時(shí)間的要求。優(yōu)化后排序結(jié)果為8、4、2、13、12、14、5、3、7、15、1、11、6、9、10。

使用上述算法對(duì)該港口進(jìn)行船舶調(diào)度,最終對(duì)所有船舶調(diào)度形成一個(gè)調(diào)度序列,總體調(diào)度的結(jié)果為使得船舶總等待時(shí)間為1 075 min,平均等待時(shí)間為72 min。具有較好的公平性,并能有效保證船舶通航的效率?？傮w結(jié)果,符合模型的預(yù)期。

(2)算法對(duì)比

對(duì)其船舶數(shù)據(jù)進(jìn)行擴(kuò)充,利用相同的潮汐數(shù)據(jù)和泊位情況進(jìn)行對(duì)比。分別設(shè)定總調(diào)度的船舶數(shù)量分別為20艘、30艘和40艘,進(jìn)出港的船舶數(shù)量各占一半。

在相同的條件下,利用常用的船舶調(diào)度算法與上述算法進(jìn)行對(duì)比,船舶總等待時(shí)間的對(duì)比結(jié)果如表3所示。

表3 不同算法船舶總等待時(shí)間對(duì)比情況

從表3中可以看到,對(duì)于所有算法的總調(diào)度時(shí)間均會(huì)隨著船舶的數(shù)據(jù)增多而呈現(xiàn)增加的情況,且船舶數(shù)量越多,等待時(shí)間也就越長(zhǎng)。但從計(jì)算結(jié)果上看,改進(jìn)后算法還是要優(yōu)于其他兩種算法的。

當(dāng)船舶為20艘時(shí),改進(jìn)后算法的平均等待時(shí)間約為1 185 min,而FCFS算法和Random算法的平均等待時(shí)間分別約為1 625 min和4 231 min。當(dāng)船舶為30艘時(shí),改進(jìn)后算法的平均等待時(shí)間約為1 525 min,而FCFS算法和Random算法的平均等待時(shí)間分別約為2 621 min和8 064 min。當(dāng)船舶為40艘時(shí),其他兩種算法的差距更大,說(shuō)明改進(jìn)后算法的效率更高。

分析原因可知,FCFS 算法約束條件隨著船舶的數(shù)量增多,而出現(xiàn)過(guò)多約束觸發(fā),因此等待時(shí)間越來(lái)越長(zhǎng)。而Random 算法的隨機(jī)性過(guò)大,存在大量的約束條件,這些約束條件的出現(xiàn),使得船舶進(jìn)出港的調(diào)度,需要大量的等待時(shí)間,甚至在船舶過(guò)多時(shí)出現(xiàn)了調(diào)度沖突的情況。

(3)算法的收斂性

為了證明改進(jìn)后算法的收斂能力,以20艘船舶調(diào)度迭代曲線為例,使用混合調(diào)度算法的收斂結(jié)果如圖1所示。

圖1 改進(jìn)后算法的收斂曲線

可以看到,改進(jìn)后算法在收斂過(guò)程中,先是在一個(gè)大的范圍內(nèi)進(jìn)行搜索,發(fā)揮種群多樣性的優(yōu)勢(shì),最終使得種群均值與最優(yōu)解重合,算法在第205代左右發(fā)生收斂,完成船舶調(diào)度的尋優(yōu)過(guò)程。

(4)同類算法對(duì)比情況

為了證明模擬退火遺傳算法的優(yōu)勢(shì),比較其與其他遺傳算法的性能對(duì)比情況。在相同的運(yùn)行環(huán)境中,將算法與CWSGA遺傳算法進(jìn)行對(duì)比。同樣考慮船舶數(shù)量為20、30、40艘的情況,對(duì)比結(jié)果如表4所示。

表4 不同算法船舶總等待時(shí)間對(duì)比情況

從實(shí)驗(yàn)結(jié)果的總體來(lái)看,相比CWSGA算法,改進(jìn)后算法的調(diào)度結(jié)果更優(yōu)。在20、30、40艘的情況下,改進(jìn)后方法船舶的等待時(shí)間均小于CWSGA算法,證明改進(jìn)后算法的調(diào)度能力更強(qiáng),調(diào)度效果更好,更適合用于內(nèi)河港口的進(jìn)出港調(diào)度問(wèn)題。

4 結(jié) 論

針對(duì)內(nèi)河港口船舶進(jìn)出港的調(diào)度問(wèn)題,研究了基于模擬退火遺傳算法的調(diào)度策略研究。通過(guò)分析船舶調(diào)度的約束條件,充分發(fā)揮模擬退火算法和遺傳算法的優(yōu)勢(shì),對(duì)遺傳算法中的交叉因子和變異因子進(jìn)行優(yōu)化,使其更符合船舶調(diào)度的應(yīng)用要求。通過(guò)實(shí)驗(yàn)結(jié)果驗(yàn)證,改進(jìn)后的算法,對(duì)于內(nèi)河港口的船舶調(diào)度能夠有效給出最優(yōu)方案。將改進(jìn)后算法與其它算法進(jìn)行對(duì)比,改進(jìn)后算法的計(jì)算效率更高,船舶的等待時(shí)間更短。在不改變港口規(guī)模的情況下,利用改進(jìn)后的調(diào)度方法,能夠有效提高港口的效率,為水路運(yùn)輸事業(yè)的發(fā)展提供思路。