張　敏王　燕　薛　景　李　重

（南京工業(yè)大學(xué)交通運(yùn)輸工程學(xué)院　南京　210009）1（南京郵電大學(xué)計(jì)算機(jī)學(xué)院　南京　210023）2

?

航運(yùn)調(diào)度中的自動(dòng)化研究

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

（南京工業(yè)大學(xué)交通運(yùn)輸工程學(xué)院南京210009）1（南京郵電大學(xué)計(jì)算機(jī)學(xué)院南京210023）2

摘要首先，考慮時(shí)間窗、載貨率、分批多次運(yùn)輸?shù)纫蛩兀覀兘⒋罢{(diào)度模型，最小化碳排放量。然后，我們用貪心算法先得出多個(gè)較優(yōu)解。之后，我們將貪心得出的解和其他隨機(jī)解作為初始解，用遺傳算法進(jìn)行求解，研究結(jié)果表明：本方法可以有效的減少二氧化碳的排放，在較短時(shí)間內(nèi)制定船舶日程表。這為編寫船舶自動(dòng)調(diào)度軟件奠定基礎(chǔ)，有助于提高船舶調(diào)度領(lǐng)域中的自動(dòng)化程度。

關(guān)鍵詞船舶調(diào)度時(shí)間窗低碳環(huán)保貪心遺傳算法

一、引言

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

二、算法設(shè)計(jì)

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

1、貪心遺傳算法步驟

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

本文設(shè)計(jì)的貪心遺傳算法基本步驟如下：

①選擇編碼方式；

②使用貪心算法得到的可行解，及產(chǎn)生隨機(jī)解作為初始種群；

③計(jì)算初始種群的適應(yīng)值；

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

⑤不滿足終止條件｛

交叉｛

If（新解適應(yīng)值大于舊解）

選擇新解

Else

選擇舊解

｝

變異｛

If（新解適應(yīng)值大于舊解）

選擇新解

Else

選擇舊解

｝

計(jì)算適應(yīng)值；

｝回到④。

2、初始種群的建立

（1）編碼方式的選擇

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

（2）產(chǎn)生初始種群

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

交叉變異生成新的種群后，比較新生成的子代和相同位置父代的適應(yīng)度，若父代更好，就用父代取代子代。當(dāng)適應(yīng)度差別較大時(shí)，比較所有個(gè)體的適應(yīng)度，復(fù)制最好的5個(gè)個(gè)體，同時(shí)刪去最差的5個(gè)個(gè)體。

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

每個(gè)解由一串?dāng)?shù)字組成，0作為分界線可將這串?dāng)?shù)字拆分為多段。例如12034056可由0分為12，34，56。將前后補(bǔ)足起始點(diǎn)和終點(diǎn)，變?yōu)?120，0340，0560。由于有V艘船，可將這些數(shù)字串按順序分給船，作為船的運(yùn)行路線。如12034056這個(gè)解代表船一走0120，船二走0340，船三走0560。

（4）分配卸貨量

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

（5）適應(yīng)值的計(jì)算

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

適應(yīng)度值越小越好。

（6）終止條件

一個(gè)解滿足所有的時(shí)間窗要求和客戶需求，且碳排放比已知解更少則終止?；虬l(fā)生早熟，交叉無法產(chǎn)生新的可行解，變異產(chǎn)生新解的速度也過慢，就停止。

（7）交叉

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

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

（8）變異

隨機(jī)選擇一條染色體，觀察其適應(yīng)度高低，若不是優(yōu)秀的個(gè)體，則發(fā)生變異。隨機(jī)選擇一個(gè)非0基因，將其插入該染色體中的某一隨機(jī)位置。

參考文獻(xiàn)

［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］玄關(guān)男，陳潤(rùn)偉.遺傳算法與工程優(yōu)化［M］.北京：清華大學(xué)出版社，2012.

張敏（1984～），女，南京工業(yè)大學(xué)交通運(yùn)輸工程學(xué)院，講師。

王燕，女，南京郵電大學(xué)計(jì)算機(jī)學(xué)院，本科生。

薛景（1980～），男，南京郵電大學(xué)計(jì)算機(jī)學(xué)院，講師。

李重，男，南京郵電大學(xué)計(jì)算機(jī)學(xué)院，本科生。

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

中圖分類號(hào)O221.4

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)160323-7235

作者簡(jiǎn)介