一種基於森林模型與改進遺傳算法的船舶引航排班方法

2023-07-13 14:57:26 2

一種基於森林模型與改進遺傳算法的船舶引航排班方法
【專利摘要】本發明公開了一種基於森林模型與改進遺傳算法的船舶引航排班方法。該方法根據引航任務銜接條件構建引航任務森林模型，採用改進廣度優先搜索算法遍歷引航任務森林獲取初始引航任務組；根據初始引航任務組，採樣改進遺傳算法獲取最優引航排班計劃。本發明考慮了引航排班中各種成文的排班規則及不成文排班習慣，同時將引航排班問題所涉及的約束條件轉化為費用模型，從可行性、公平性、效益三個角度出發，求解船舶引航排班方法。
【專利說明】一種基於森林模型與改進遺傳算法的船舶引航排班方法

【技術領域】
[0001] 本發明屬於引航調度中的引航任務排班方法，具體涉及一種森林模型的引航排班 問題模型及其基於改進遺傳算法的求解方法。

【背景技術】
[0002] 我國是一個港口大國。然而，在港口迅猛發展的同時，我國港口在引航調度效率上 相對落後，這嚴重製約了港口的核心競爭力，也造成了一定的資源浪費。各引航公司迫切需 要建立一個高效可行的引航調度體系實現引航資源優化配置，提高港口競爭力。引航調度 的管理重點就在引航排班上，因此，探討引航調度中引航排班的建模優化和有效的解決方 法，成為亟待解決的關鍵理論問題。
[0003] 引航排班問題屬於NP-hard組合優化問題。由於此類問題規模龐大並且限制因素 複雜，所以智能算法在解決該類問題中得到廣泛運用。目前應用於組合優化的算法主要有 局部搜索法，模擬退火算法，遺傳算法，神經網絡等。引航排班方法主要有基於集覆蓋方法， 基於遺傳算法的方法，基於模擬退火算法的方法。排班問題的解決思路大同小異，分為兩 步：1、產生初始引航任務組；2、運用智能優化算法對初始引航任務組進行搜索，生成可行 的任務組組合。
[0004] 目前有的引航排班方法存在以下問題：
[0005] 1.第一步構建的初始引航任務組直接影響第二步智能優化算法的工作量。已有方 法在構建初始引航任務組時採用的引航排班模型使得智能優化算法不可避免增加排除不 可行解工作，增加了求解難度；
[0006] 2.現有方法只考慮了在引航規則範圍內找到可行排班結果，未綜合考慮到引航任 務之間等待時間，引航任務組時間均衡，引航任務組始末地點轉移帶來的成本問題。
[0007] 3.基本智能優化算法搜索能力有限，特別是當引航任務數目較多，考慮因素增多 時，搜索最優解將顯得無能為力。


【發明內容】

[0008] 為解決上述技術問題，本發明目的是提供一種一種基於森林模型與改進遺傳算法 的船舶引航排班方法，避免了後期智能優化算法在求解時增加排除不可行解的步驟，減小 求解難度，相比一般算法具有更優的尋優能力。
[0009] 為實現上述目的，本發明的技術方案如下：
[0010] 一種基於森林模型與改進遺傳算法的船舶引航排班方法，該方法包括以下步驟：
[0011] 步驟（1):建立本地資料庫，進行合同收池；
[0012] 步驟（2):從池中選出待引航排班船舶，根據引航任務銜接條件構建引航任務森 林模型；
[0013] 步驟（3):採用改進廣度優先搜索算法遍歷引航任務森林獲取初始引航任務組；
[0014] 步驟（4):根據初始引航任務組，採用改進遺傳算法求解最優引航排班計劃；
[0015] 步驟（5):根據確定的最優引航排班計劃進行引航排班。
[0016] 其中，步驟（2)建立引航排班問題森林模型考慮的引航任務銜接條件為將時間上 可以順承，地點相同的引航任務銜接，引航任務銜接條件的數學模型如下：
[0017]

【權利要求】
1. 一種基於森林模型與改進遺傳算法的船舶引航排班方法，包括建立本地資料庫，進 行合同收池，其特徵在於，該方法依次包括以下步驟： 步驟（Ia):建立本地資料庫，進行合同收池； 步驟（Ib):從池中選出待引航排班船舶，根據引航任務銜接條件構建引航任務森林模 型； 步驟（Ic):採用改進廣度優先搜索算法遍歷引航任務森林獲取初始引航任務組； 步驟（Id):根據初始引航任務組，採用改進遺傳算法求解最優引航排班計劃； 步驟（Ie):根據確定的最優引航排班計劃進行引航排班。
2. 根據權利要求1所述一種基於森林模型與改進遺傳算法的船舶引航排班方法，其特 徵在於，對於所述步驟（Ib)，引航任務銜接條件的數學模型如下：
taskj_stime表示第j個引航任務的起始時間，task^etime表示第i個引航任務的結 束時間，taski_epos表示第i個引航任務的結束地點，taskj_spos表示第j個引航任務的 起始地點。
3. 根據權利要求1所述一種基於森林模型與改進遺傳算法的船舶引航排班方法，其特 徵在於，對於所述步驟（Ib)，構建引航任務森林模型的具體步驟如下： 步驟（3a):構建引航任務集合R; 步驟（3b):以引航任務為根節點，遍歷引航任務集合R，根據引航任務銜接條件，為每 個引航任務找出所有孩子節點，構造森林F; 步驟（3c):遍歷森林F，若根據引航任務銜接條件，樹中葉子節點存在孩子節點或孩子 樹，則通過將所有孩子節點與孩子樹作為葉子節點的孩子更新當前樹及森林F; 步驟（3d):若森林F中樹的葉子節點存在孩子節點或孩子樹，轉步驟（3c); 步驟（3e):輸出引航任務的森林模型。
4. 根據權利要求1所述一種基於森林模型與改進遺傳算法的船舶引航排班方法，其特 徵在於，對於所述步驟（Ic)，採用改進廣度優先搜索算法遍歷引航任務森林獲取初始引航 任務組的具體步驟如下： 步驟（4a):採用Vi/命名森林中第t棵樹的第i層第j個節點且所有節點標記為未訪 問； 步驟（4b):參數初始化；設置t= 1，i= 1，j=l，m=l，n= 1，初始引航任務組存放 二維矩陣G為全零矩陣； 步驟（4c):若V1/標記為已訪問，則t加1,轉步驟（4d); 若節點Vi/為未訪問非葉子節點且存在未訪問孩子節點，則將節點Vi/存入G[m] [n]，n加I，i加I，轉步驟（4c); 若節點Vi/為未訪問非葉子節點且不存在未訪問孩子節點，將節點Vi/標記為已訪問 並置矩陣G第m維元素全為0,轉步驟（4c); 若節點Vi/為已訪問節點且存在未訪問兄弟節點，則j加1，轉步驟（4c); 若節點Vi/為未訪問葉子節點，則將節點Vi/存入G[m] [n]並標記為已訪問，m加1，置 n=l，i=l，j= 1，轉步驟（4c); 步驟（4d):如果t小於森林中樹的總數，則t加1，轉步驟（4c);反之，進入步驟（4e); 步驟（4e):從初始引航任務組存放矩陣G輸出初始引航任務組及初始引航任務組數 Ngroup〇
5. 根據權利要求1所述一種基於森林模型與改進遺傳算法的船舶引航排班方法，其特 徵在於，對於所述步驟（Id)，改進遺傳算法求解最優引航排班計劃具體步驟如下： 步驟（5a):初始化參數；設置種群大小popsize，總運行代數gen，運行次數g= 1 ;交 叉概率P。，變異概率Pm，最優子群比入； 步驟（5b):初始化種群；隨機產生popsize個個體； 步驟（5c):計算適應度；根據適應度函數計算每個個體的適應度值； 步驟（5d):選擇；將所有個體進行排序，以比率A選擇具有較優適應度值的個體構建 最優個體子群； 步驟（5e):交叉；從最優個體子群中隨機選擇一個個體，當前個體以概率p。與隨機選 擇的該個體交叉，得到子個體； 步驟（5f):變異；隨機產生一（0, 1)間實數rm，若rm〈變異概率pm，則對當前個體執行 變異操作； 步驟（5g):計算當前個體適應度值，如果該當前個體適應度值小於交叉變異前適應度 值，更新當前個體；否則，個體不更新； 步驟（5h):如果當前運行次數總運行代數gen，則運行次數g加1，轉步驟（5c);反 之，進入步驟（5i); 步驟（5i):輸出最優解。
6. 根據權利要求5所述基於森林模型與改進遺傳算法的船舶引航排班方法，其特徵在 於，對於步驟（5c)，適應度值函數f?的計算公式如下： f=Ci^obji+c^ 氺obj2+c3 氺obj3+c4 氺obj4+c5^obj5+c6 氺obj6+c7 氺obj7 (2) 其中，Obj1為目標函數第1部分，表示一個引航任務組組合中引航任務組的數目大小產 生的費用，Obj1數學表達式如下：
其中，M為染色體長度，g(i)表示染色體第i個基因，g(i)取值如下式所示：
Obj2為目標函數第2部分，表示一個引航任務組組合中各引航任務組的等待時間產生 的費用，Obj2數學表達式如下：
其中，Ngroup為引航任務組數，waitcos&為第i個引航任務組的時間等待費用，其計 算方式如下：
wait_time為兩銜接引航任務等待時間間隔，VT為等待時間閾值，《a、《b為等待時間 費用權值； Obj3為目標函數第3部分，表示一個引航任務組組合中各引航任務組始末地點不同產 生的地點轉移費用，Obj3表達式如下：
其中，Ngroup為引航任務組數，poscos&為第i個引航任務組的地點轉移費用，其計算 方式如下：
gtasl^spospgtasl^eposi分別為第i個引航任務組的起始地點與結束地點，Cogp為地 點轉移費用權值。 Obj4為目標函數第4部分，表示一個引航任務組組合中各引航任務組工作時間差異產 生的費用，〇bj4表達式如下：
其中，taskno為引航任務數，Nsmup為引航任務組數，gtask_timei為第i個引航任務組 的工作時間；avetime為一個任務組組合平均工作時間，其計算公式如下：
Obj5為目標函數第5部分，表示一個引航任務組組合中存在未覆蓋引航任務產生的費 用，〇bj5表達式如下：
其中，NtaskS引航任務數，wu為引航任務未覆蓋費用權值，uncover(i)為第i個引 航任務的未覆蓋函數，其計算公式如下：
〇bj6為目標函數第6部分，表示一個引航任務組組合中存在重複覆蓋引航任務產生的 費用，Qbj6表達式如下：
其中，NtaskS引航任務數，w。為引航任務重複覆蓋費用權值，overcover(i)為第i個引航任務的重複覆蓋函數，其計算公式如下：
Ngroup為引航任務組數，r^_為第i個引航任務在第j個引航任務組的覆蓋函數，其計算 公式如下：
Obj7為目標函數第7部分，表示一個引航任務組組合中存在工作時間超時限的引航任 務組產生的費用，Obj7表達式如下：
其中，Nsmup為引航任務組數，。為引航任務組時間超限費用權值，gr〇up_t〇(i)為第i個引航任務組的時間超限函數，其計算公式如下：
Cpc2、c3、c4、C5、C6、C7分別為各目標函數的權值。
7. 根據權利要求5所述基於森林模型與改進遺傳算法的船舶引航排班方法，其特徵在 於，對於所述步驟（5c)，適應度計算具體步驟如下： 步驟（7a):置基因位i= 1，引航任務組集合group為空集合； 步驟（7b):如果基因位i的值gi為1，將第i個初始引航任務組加入引航任務組集合group,i加1 ;如果i的值為0,g加1 ; 步驟（7c):如果i的大小小於染色體長度，則i加1，轉步驟（7b);反之，進入步驟 (7d)； 步驟（7d):按上述公式（2)計算引航任務組集合group引航排班的總費用，即為個體 的適應度值。
8. 根據權利要求5所述基於森林模型與改進遺傳算法的船舶引航排班方法，其特徵在 於，對於所述步驟（5d)，最優個體子群的構建方法具體步驟如下： 步驟（8a):將所有個體的適應度值由小到大進行排序； 步驟（8b):根據比率X和種群大小popsize依次選擇適應度值較小的 [入*popsize+0. 5]個個體組成最優個體子群，其中[A*p〇psize+0. 5]代表對 入 *popsize+0. 5 取整。
【文檔編號】G06Q10/04GK104268639SQ201410465020
【公開日】2015年1月7日 申請日期:2014年9月12日 優先權日:2014年9月12日
【發明者】薛雲燦, 張海霞, 李彬, 楊啟文 申請人:河海大學常州校區