航運調度中的自動化研究

張　敏王　燕　薛　景　李　重

（南京工業大學交通運輸工程學院　南京　210009）1（南京郵電大學計算機學院　南京　210023）2

?

航運調度中的自動化研究

張敏1王燕2薛景2李重2

（南京工業大學交通運輸工程學院南京210009）1（南京郵電大學計算機學院南京210023）2

摘要首先，考慮時間窗、載貨率、分批多次運輸等因素，我們建立船舶調度模型，最小化碳排放量。然后，我們用貪心算法先得出多個較優解。之后，我們將貪心得出的解和其他隨機解作為初始解，用遺傳算法進行求解，研究結果表明：本方法可以有效的減少二氧化碳的排放，在較短時間內制定船舶日程表。這為編寫船舶自動調度軟件奠定基礎，有助于提高船舶調度領域中的自動化程度。

關鍵詞船舶調度時間窗低碳環保貪心遺傳算法

一、引言

綠色航運系統是指航運公司從裝貨點到達卸貨點，在滿足卸貨點需求量和時間窗要求，不超載，不超速等要求的情況下，滿足經濟航速、低碳戰略的要求。模擬退火方法具有收斂速度快，全局搜索的特點，Osman［1］對車輛路徑規劃問題（VRP）的模擬退火算法進行了研究，他提出的模擬退火方法主要適合于解決路線分組。遺傳算法具有求解組合優化問題的良好特性，Holland［2］首先采用遺傳算法（GA）編碼解決VRPTW問題。本文根據Min Zhang［3］等人的研究，考慮了大量現實情況，將遺傳算法［4］、貪心算法和實際約束聯系起來。設計一種能夠解決復雜的約束條件的算法，是我們能夠制定更有效的航運計劃，符合綠色航運系統的要求。

二、算法設計

現有一配送中心使用若干船舶向若干客戶送貨，配送中心的裝貨時間窗，每個客戶的需求量、需求緊急程度、收貨時間窗已知，任一客戶可被多次訪問，任一船舶可多次出航，直至滿足所有需求。

1、貪心遺傳算法步驟

船按到達配送中心時間決定出發順序，以客戶重要程度和時間窗的約束（一般時間窗緊迫的客戶重要性會比較高）決定船走的路線：船到達第一重要客戶i需裝的貨小于船的最小載貨量就前往次重要的客戶j，直至船的載貨量大于最小載貨量小于最大載貨量。然后安排下一艘船，直至得到可行的較優解。

本文設計的貪心遺傳算法基本步驟如下：

①選擇編碼方式；

②使用貪心算法得到的可行解，及產生隨機解作為初始種群；

③計算初始種群的適應值；

④滿足終止條件，則終止；

⑤不滿足終止條件｛

交叉｛

If（新解適應值大于舊解）

選擇新解

Else

選擇舊解

｝

變異｛

If（新解適應值大于舊解）

選擇新解

Else

選擇舊解

｝

計算適應值；

｝回到④。

2、初始種群的建立

（1）編碼方式的選擇

解采用自然數數組的表示方式，用0表示配送中心，用1，2，3…n表示客戶。

（2）產生初始種群

由貪心法可以得到可行解，放入初始種群中。一般而言，將貪心得到的解分解為所有船從配送中心出發的次數接近最優解。所以初始種群的長度大體固定，即從配送中心出發的次數比貪心解增減2。每次從配送中心出發后途經隨機不超過總客戶數的點后，返回配送中心，且客戶不重復。按以上方法產生一定量的隨機解。

交叉變異生成新的種群后，比較新生成的子代和相同位置父代的適應度，若父代更好，就用父代取代子代。當適應度差別較大時，比較所有個體的適應度，復制最好的5個個體，同時刪去最差的5個個體。

（3）染色體拆分為可行解

每個解由一串數字組成，0作為分界線可將這串數字拆分為多段。例如12034056可由0分為12，34，56。將前后補足起始點和終點，變為0120，0340，0560。由于有V艘船，可將這些數字串按順序分給船，作為船的運行路線。如12034056這個解代表船一走0120，船二走0340，船三走0560。

（4）分配卸貨量

按照順序遍歷V艘船的路徑。解拆分后，每艘船可能得到多段路徑，每一段代表著船出行一次。按順序遍歷每艘船的k段路徑。一段路徑由0和m個不重復的非0數字組成，這m個數字代表船要途經的m個客戶。這條船的載貨量為在這m個客戶的卸貨量之和。先計算這m個客戶的總需求量，若大于船的最大載貨量，則按事先設定好的每個客戶的重要性（根據截止時間遠近，客戶重要等級等因素決定）順序卸下該客戶的需求量，即優先滿足重要客戶，船的載貨量為船的最大載貨量；若小于船的最大載貨量，則按這段路徑的順序卸下該客戶的需求量，船的載貨量為途經客戶的卸貨量和。同時在船途經的每個客戶i對應的位置記錄這艘船這次出行在該點的卸貨量。

（5）適應值的計算

一個較優解應該盡可能滿足時間窗的要求和客戶的需求。一個解是一串數字，這串數字除了0之外有num個數字，這些數字代表著船要途經的客戶，因此，每個客戶至少出現一次，否則必然得不到可行解。如果有客戶沒有出現，就給予無限大的懲罰pmax，不需要進行之后的計算。將解拆分后，按照順序遍歷V艘船的路徑，每次船出行的載貨量若小于最小載貨量，則不能出行，因此給予一個較大的懲罰p1。遍歷船每次出行途經的客戶，若船途經一個已經沒有需求的客戶i，屬于排放過多二氧化碳，因此給予較小懲罰p2；若船途經客戶i時，已經超過i的卸貨時間，給予懲罰p3，使p2＜p3＜p1。當遍歷完船的路徑，若仍有客戶需求沒有被滿足，則實際中客戶滿意度將大大降低，所以給予最大的懲罰p4。則適應度為：

適應度值越小越好。

（6）終止條件

一個解滿足所有的時間窗要求和客戶需求，且碳排放比已知解更少則終止。或發生早熟，交叉無法產生新的可行解，變異產生新解的速度也過慢，就停止。

（7）交叉

①基于次序的雜交：從父代中選擇數量相同位置的集合，產生二進制的掩碼串。將父代A中掩碼為0的位置復制到子代a中相同的位置上，其余位置用父代B相同位置的基因填充。將父代B中掩碼為0的位置復制到子代b中相同的位置上，其余位置用父代A相同位置的基因填充。從而產生兩個新的子代。例如01032505404670780808和01023605054707808，選取第2到10位進行雜交，結果為010226054547670780808和010335050044707808。通過刪除多余基因和添加缺乏基因使子代合法化。

②部分調度交換雜交：將染色體切換成一段段的路徑，將第n段的父代a和父代b交換，產生新的子代a，b。通過刪除多余基因和添加缺乏基因使子代合法化。

（8）變異

隨機選擇一條染色體，觀察其適應度高低，若不是優秀的個體，則發生變異。隨機選擇一個非0基因，將其插入該染色體中的某一隨機位置。

參考文獻

［1］Osman I H. Meta-strategy simulated annealing an Tabu search algorithms for the vehicle routing problem［J］. Annu Oper Res，1993，41：77～86.

［2］John Holland. Hidden order：How adaptation builds complexity［M］. Basic Books，1996.

［3］Min Zhang，Yoshiaki Ishihara，Ahusaku Hiraki. Ship Scheduling by Pure Car Carries with Time Windows and Split Loads in Changeable Speeds［J］. Japan Industrial Management Association，2013.7，356-365.

［4］玄關男，陳潤偉.遺傳算法與工程優化［M］.北京：清華大學出版社，2012.

張敏（1984～），女，南京工業大學交通運輸工程學院，講師。

王燕，女，南京郵電大學計算機學院，本科生。

薛景（1980～），男，南京郵電大學計算機學院，講師。

李重，男，南京郵電大學計算機學院，本科生。

Research on the Shipping Scheduling Automation

Zhang Min1Wang Yan2Xue Jing2Li Zhong2
（College of Transportation Science & Engineering，Nanjing Tech University Nanjing 210009）1（School of Computer Science & Technology，Nanjing University of Posts and Telecommunications Nanjing 210023）2

AbstractFirst，considering time windows，load factors，batch shipment，we set up ship scheduling model to minimize carbon emissions. Then，we use the greedy algorithm to obtain several optimum solutions. After that，we take the above solutions and other random solutions as initial solutions，and use genetic algorithm to solve the problem. Results show that：This method can effectively reduce the carbon emissions，create schedules for ships in a relative short period of time.

KeywordsShip scheduling Time windows Low-carbon environmental-friendly Greedy genetic algorithm

中圖分類號O221.4

文獻標識碼A

文章編號160323-7235

作者簡介