最小偏差法船舶調(diào)度

林 輝， 陳順懷

(武漢理工大學(xué) a.交通學(xué)院, b.高性能船舶技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室， 湖北 武漢 430063)

0 引 言

在世界海洋運(yùn)輸業(yè)迅速發(fā)展的今天，船舶調(diào)度作為港口調(diào)度的關(guān)鍵內(nèi)容之一，從20世紀(jì)50年代開始就引起了許多學(xué)者的關(guān)注。船舶調(diào)度是一種能降低船務(wù)公司營(yíng)運(yùn)成本的手段。船舶調(diào)度方案的優(yōu)劣直接關(guān)系到船舶航運(yùn)過程中的船舶運(yùn)輸效率、油耗情況以及港口成本等諸多經(jīng)濟(jì)效益的好壞，從而對(duì)航運(yùn)公司的盈利能力產(chǎn)生實(shí)質(zhì)性的影響，因此對(duì)配船方案的優(yōu)化就顯得尤為重要。配船方案的優(yōu)化過程涉及諸多問題，比如船舶運(yùn)輸成本的構(gòu)成、客流量的滿足、船舶速度和航行時(shí)間的匹配等。因此，船舶調(diào)度優(yōu)化是一個(gè)多目標(biāo)優(yōu)化問題。

每條航線的配船方案和調(diào)度是由船務(wù)公司的專門調(diào)度人員負(fù)責(zé)安排的。一般來說，在船舶調(diào)度中所考慮的問題有許多是隨機(jī)可變的，比如本文所討論的客船調(diào)度，除淡季和旺季的客流量差異以外，其每日的客流量也是隨機(jī)變化的，還有水域、天氣條件也會(huì)有所差異。這些都成為影響船舶調(diào)度方案優(yōu)劣的約束條件。

現(xiàn)今，絕大多數(shù)船舶(包括集裝箱船、散貨船、客船)的配船主要還是依靠專門調(diào)度人員的經(jīng)驗(yàn)，以至于現(xiàn)有的船舶運(yùn)輸資源未得到充分的利用，從而導(dǎo)致運(yùn)輸成本相對(duì)較高，并且不能較好地滿足客戶的需求。因此，采用合適的方法對(duì)該問題進(jìn)行優(yōu)化處理非常重要。目前，已有許多學(xué)者采用蟻群算法等相關(guān)算法進(jìn)行求解優(yōu)化，本文在其后也對(duì)其進(jìn)行了一些比較。

1 遺傳算法及最小偏差法簡(jiǎn)介

1.1 遺傳算法及其基本理論

遺傳算法(Genetic Algorithm，GA)是一種自適應(yīng)全局優(yōu)化搜索算法。它主要借鑒生物在繁殖生存過程中的遺傳和進(jìn)化規(guī)律。早在20世紀(jì)60年代, HOLLAND就提出GA算法的理論;20世紀(jì)70年代， JONG首次根據(jù)GA理論開展計(jì)算機(jī)數(shù)值試驗(yàn)；20世紀(jì)80年代， GOLDBERG對(duì)之前學(xué)者所做的理論和試驗(yàn)研究進(jìn)行總結(jié)歸納得到現(xiàn)今的經(jīng)典遺傳算法。

GA是一種傳統(tǒng)的智能算法，它有良好的隨機(jī)性和全局性，是一種高效的、并行的、全局性的成熟優(yōu)化方法。經(jīng)典遺傳算法的優(yōu)化變量是采用二進(jìn)制碼來描述的，多個(gè)優(yōu)化變量的二進(jìn)制碼串接在一起形成一組染色體，這種編碼方式既適用于變異操作，又可對(duì)其進(jìn)行交叉操作。在創(chuàng)建初始種群時(shí)，代表個(gè)體的二進(jìn)制串是在一定字長(zhǎng)的限制下隨機(jī)產(chǎn)生的。GA算法中的交叉算子其主要功能是交叉2條染色體，交叉位置是隨機(jī)產(chǎn)生的，染色體的交叉位置也是隨機(jī)選取的，從而保證后代的隨機(jī)性，2個(gè)染色體在進(jìn)行隨機(jī)交叉后，其對(duì)應(yīng)位置的二進(jìn)制碼將進(jìn)行交換并生成新的2個(gè)染色體。變異算子作用在單一染色體上，通過1個(gè)隨機(jī)概率對(duì)單個(gè)染色體上的二進(jìn)制碼進(jìn)行變異，即將“0”變異成“1”，或者將“1”變異成“0”，從而得到新的染色體。最后將這些不斷交叉變異的個(gè)體代入適應(yīng)度函數(shù)進(jìn)行計(jì)算，比較適應(yīng)度值之間的差異是否滿足精度要求，滿足精度要求即可獲得全局最優(yōu)解。

1.2 最小偏差法

在實(shí)際的多目標(biāo)尋優(yōu)過程中，由于約束條件和優(yōu)化目標(biāo)較多，往往很難求得最優(yōu)解，故在工程應(yīng)用中主要以尋找多目標(biāo)優(yōu)化中的滿意解為最終優(yōu)化目標(biāo)。本文采用的最小偏差法就是一種可用于多目標(biāo)問題優(yōu)化的決策方法。

常見的多目標(biāo)優(yōu)化模型可以表示為

x∈Rn(1)

式中：f1(x),f2(x),…，fl(x)為l個(gè)極小化目標(biāo)函數(shù)；fl+1(x),fl+2(x),…，fm(x) 為m-l個(gè)極大化目標(biāo)函數(shù)；gj為線性、非線性不等式函數(shù)式；hk為線性、非線性等式函數(shù)式；j為不等式約束編號(hào)，其值為1，2,3，…；k為等式約束編號(hào)，其值為1,2,3，…；x為決策變量，x=(xl,x2,…，xn)T。

多目標(biāo)優(yōu)化問題的核心思想是將多個(gè)適應(yīng)度函數(shù)同時(shí)求取最優(yōu)解，但是由于不同適應(yīng)度函數(shù)的最優(yōu)解必然是不同的值，故而在多目標(biāo)優(yōu)化問題中引入較優(yōu)解的概念,即多個(gè)適應(yīng)度函數(shù)在較優(yōu)解的情況下，可同時(shí)獲得相對(duì)較優(yōu)的適應(yīng)度值。1951年，TKOOPMANS提出一種與較優(yōu)解概念相同的有效解概念，被稱之為Pareto最優(yōu)解。Pareto最優(yōu)解是通過對(duì)多個(gè)適應(yīng)度函數(shù)構(gòu)成的向量函數(shù)的適應(yīng)度值進(jìn)行大小比較獲得的。

假設(shè)X?Rn是多目標(biāo)優(yōu)化問題的約束集，若x*∈X，且不存在x∈X使得?i∈(1,2,…,l),fi(x)≤fi(x*)，而對(duì)于?i∈(l+1,l+2,…,m),fi(x)≥fi(x*)，則稱x*為其有效解[4-5]。

對(duì)于多目標(biāo)優(yōu)化問題，主要工作就是尋找合適的方法來獲得目標(biāo)的Pareto最優(yōu)解，因此，尋找一種合適的決策函數(shù)來處理多個(gè)適應(yīng)度函數(shù)，使其能進(jìn)行相互比較就成了關(guān)鍵性問題。如式(2)所示，可以通過一定的權(quán)重策略將m個(gè)函數(shù)式構(gòu)成1個(gè)以x為自變量的復(fù)合函數(shù)式：

F′(x)=F′(f1(x),f2(x),…，fm(x))(2)

對(duì)式(2)中多個(gè)適應(yīng)度函數(shù)共同優(yōu)化問題的解是一個(gè)解集，即不只存在一個(gè)解，不同的決策方法和求解算法獲得的解不盡相同，其具有的意義也存在差異，本文采用最小偏差法[5-6]作為統(tǒng)一適應(yīng)度函數(shù)的決策方法：

2 船隊(duì)調(diào)度優(yōu)化模型的構(gòu)建

本文主要以迅隆公司的船舶調(diào)度案例為基礎(chǔ)，結(jié)合其公司船舶數(shù)量、航線情況和航班要求等基礎(chǔ)條件建立數(shù)學(xué)模型。

迅隆公司擁有6艘客船構(gòu)成的船隊(duì)，將這6艘客船分別命名為迅隆1～6號(hào)。船型的不同導(dǎo)致每條船的載客人數(shù)和每公里耗油都有差異，此外所需船員人數(shù)也不同。船隊(duì)航行的航線主要有4條，分別是蛇口-中環(huán)、蛇口-澳門、蛇口-機(jī)場(chǎng)和福永-澳門。耗油量的不同可能由航線里程和水域狀況的不同導(dǎo)致，不同船型的噸位不同導(dǎo)致其在港口的停泊、服務(wù)等綜合費(fèi)用也存在較大的差異[8]。

2.1 航運(yùn)成本組成部分

耗油量：不同船舶的主機(jī)在不同單位時(shí)間和單位里程的油耗存在較大差異。本文按如下的公式計(jì)算主機(jī)在船舶往返航班中的油耗成本：

往返航班油耗成本=往返航班里程×

油耗×單位油價(jià) (4)

人員工資：出航的工作人員除了有基本的工資、伙食補(bǔ)貼之外，還有按出勤天數(shù)計(jì)算的獎(jiǎng)金。本文通過相關(guān)薪資數(shù)據(jù)，按如下公式計(jì)算船員的航行補(bǔ)貼：

航行補(bǔ)貼=航班數(shù)×基本航線補(bǔ)貼×航線系數(shù) (5)

港口費(fèi)用：由于不同噸位的船舶在不同的港口收費(fèi)標(biāo)準(zhǔn)存在差異，故必須根據(jù)碼頭的實(shí)際情況獲取港口費(fèi)用。

2.2 目標(biāo)函數(shù)

2.2.1 總成本最小化

該優(yōu)化模型以船舶日總成本費(fèi)用最小化為目標(biāo)構(gòu)建優(yōu)化模型，其中包括成本、碼頭綜合管理費(fèi)用和船員津貼成本(船員工資為固定成本，此處不作考慮)。

(1) 船舶油耗成本。不同船型的船舶在不同航線上由于主機(jī)油耗和航程的不同，成本也不盡相同，此處令不同船舶在不同航班上的油耗成本為oij，則

oij=xij×cij(6)

式中：xij為船舶i開往往返航班j的次數(shù)，xij∈(0,1)。它是模型的0-1變量，決定了本研究所建立的數(shù)學(xué)模型將是0-1整數(shù)規(guī)劃。具體含義如下：

(8)

式中：cij為船舶i開往往返航班j的耗油量；Pf為單位油價(jià)；i為船舶編號(hào)，i=1,2,3,…,M，M為船舶數(shù)量;j為往返航班編號(hào)，j=1,2,3,…,N，N為航班數(shù)量。

(2) 船舶碼頭管理綜合費(fèi)用。由船舶i在往返航班j中的碼頭使用費(fèi)用Wij得到1天中所有航班所需要的碼頭總費(fèi)用為

“張勇說得已經(jīng)非常直白，花如此巨資直接收購(gòu)而不是戰(zhàn)略投資餓了么，說明餓了么對(duì)于阿里未來發(fā)展之重要性，就是成為新零售戰(zhàn)略的重要力量?！焙诬娤颉吨袊?guó)儲(chǔ)運(yùn)》雜志記者闡述了自己的觀點(diǎn)。

(9)

式中：Po為1天中所有航班所需碼頭費(fèi)用；Wij為船舶i在往返班j中的碼頭使用費(fèi)。

(3) 船員工資。針對(duì)人員薪資基本維持不變的特性將其不予考慮，只在數(shù)學(xué)模型中包含航線補(bǔ)貼的計(jì)算，而略去基本工資總額。船舶i開往往返航班j支付給船員的總補(bǔ)貼為ρj·Cri，因此1天中往返航班總補(bǔ)貼P為

ρj·Cri(10)

式中：ρj為船舶往返航次數(shù)j的相關(guān)補(bǔ)貼系數(shù)；Cri為船舶i所有船員的基本航線補(bǔ)貼。

綜上所述，船隊(duì)1天的成本最小化目標(biāo)函數(shù)為

2.2.2 空載率最小化

班輪在營(yíng)運(yùn)過程中，在滿足當(dāng)天游客數(shù)量的前提下，使船舶空載率最小化，充分利用船舶的運(yùn)營(yíng)空間，其中的客流量Fpk使用現(xiàn)有的載客能力估計(jì)。于是有

,k∈SK(12)

式中：SJKk為航線k往返航班的集合；si為船舶i的座位數(shù)；Fpk為航線k的日平均客流量，人；SK為航線集合。

2.2.3 船舶調(diào)度次數(shù)差異最小化

為使船舶調(diào)度便利，M艘船舶在N個(gè)往返航班被調(diào)度的期望次數(shù)為N/M，故其第3個(gè)目標(biāo)函數(shù)為

,i=1,2,…,M(13)

2.3 基于最小偏差法統(tǒng)一目標(biāo)函數(shù)

綜合上面的目標(biāo)函數(shù)，得到班輪調(diào)度的多目標(biāo)優(yōu)化模型為

(14)

根據(jù)上述多目標(biāo)優(yōu)化模型和最小偏差法[7]，得到統(tǒng)一的目標(biāo)函數(shù)為

式中：C1max，C2max，C3max和C1min，C2min，C3min分別為各目標(biāo)函數(shù)在約束條件作為單目標(biāo)函數(shù)進(jìn)行尋優(yōu)求解的最大值和最小值。

2.4 約束條件

該船隊(duì)調(diào)度優(yōu)化模型共有3組約束條件。

(1) 對(duì)于任一航班都須并且只須1艘船。

,i=1,2,3,…,M；j=1,2,3,…,N(16)

(2) 避免船舶在往返過程中的時(shí)間沖突。比如往返航班1和7的時(shí)間段有交集，不可能使用同一艘船舶。

xij1+xij2≤1

?i=1,2,…,M,j1,j2=1,2,3,…,N

且j1≠j2,Ωj1∩Ωj2≠?(17)

(3) 每艘船舶至少被調(diào)動(dòng)1次，以充分利用船隊(duì)資源。

≥1,i=1,2,3,…,M(18)

3 算法運(yùn)行和結(jié)果分析

3.1 基于最小偏差法遺傳算法尋優(yōu)步驟

本文借助MATLAB中的GA Toolbox進(jìn)行求解[9]。由于班輪調(diào)度屬于0-1整數(shù)規(guī)劃問題，這里采用工具箱中的整數(shù)規(guī)劃遺傳算法工具箱進(jìn)行求解。

(1) 由于最小偏差法中須得到同等約束條件下多目標(biāo)中各目標(biāo)函數(shù)的最大值和最小值，傳統(tǒng)優(yōu)化算法對(duì)初始解的選取較為敏感，為確保尋優(yōu)結(jié)果，先采用MATLAB中遺傳算法工具箱進(jìn)行單目標(biāo)問題的模型構(gòu)建和求解，得到其最大值和最小值。

(2) 利用式(1)中計(jì)算出的最大、最小值代入最小偏差法構(gòu)建的多目標(biāo)優(yōu)化模型中，通過MATLAB工具箱進(jìn)行求解。

3.2 優(yōu)化結(jié)果及分析

在完成MATLAB平臺(tái)上優(yōu)化模型的目標(biāo)函數(shù)和約束條件的編寫后，運(yùn)行該優(yōu)化算法，在遺傳算法中，可以對(duì)其遺傳策略進(jìn)行設(shè)置，不同的遺傳策略得到的優(yōu)化方案不同。本文通過改變EliteCount這一遺傳參數(shù)來得到較優(yōu)方案，然后將較優(yōu)方案與原方案進(jìn)行對(duì)比。班輪公司現(xiàn)采用的方案如表1所示。

表1 原調(diào)度方案

通過遺傳算法進(jìn)行優(yōu)化后的結(jié)果如表2所示，其過程如圖1所示，優(yōu)化調(diào)度方案如表3所示。

表2 優(yōu)化結(jié)果

圖1 遺傳算法優(yōu)化過程

航線編號(hào)航班編號(hào)船舶編號(hào)航線編號(hào)航班編號(hào)船舶編號(hào)1152123125313213431441443154153316316131762713185281319429242052106421121114224

方案對(duì)比結(jié)果如表4所示。

表4 3種方案的對(duì)比結(jié)果

由表4的數(shù)據(jù)分析可得：通過遺傳算法進(jìn)行整數(shù)規(guī)劃得到的方案較原方案有明顯的優(yōu)勢(shì)，除此之外，也比傳統(tǒng)蟻群算法優(yōu)化得到的方案[10]較優(yōu)。

4 結(jié) 論

本文利用實(shí)際船舶公司的數(shù)據(jù)對(duì)船舶調(diào)度問題進(jìn)行分析研究，以MATLAB為計(jì)算平臺(tái)，構(gòu)建遺傳算法優(yōu)化模型，采用最小偏差法處理船舶調(diào)度中的多目標(biāo)優(yōu)化，得出以下結(jié)論：

(1) 文中針對(duì)的班輪調(diào)度優(yōu)化結(jié)果與原方案進(jìn)行對(duì)比可得：類似船舶調(diào)度類的問題可通過采用類似整數(shù)規(guī)劃的方式進(jìn)行優(yōu)化，這不僅可以將船舶運(yùn)輸效率最大化，同時(shí)營(yíng)運(yùn)成本最小化。

(2) 本文采用的遺傳算法優(yōu)化后結(jié)果與原方案相比較好，驗(yàn)證了遺傳算法在多目標(biāo)混合整數(shù)0-1規(guī)劃問題中的應(yīng)用優(yōu)勢(shì)性和合理性。

(3) 本文主要以MATLAB進(jìn)行計(jì)算，可見MATLAB在工程計(jì)算中應(yīng)用的便利性、合理性。

(4) 在船舶實(shí)際調(diào)度過程中還有很多因素參與影響，本文僅從成本、空載率和差異化這3個(gè)目標(biāo)進(jìn)行優(yōu)化，故還須在日后的研究中考慮更多因素，完善調(diào)度方案，以使方案更貼近實(shí)際調(diào)度情況。

[ 1 ] 呂如福. 多目標(biāo)船舶調(diào)度優(yōu)化問題蟻群算法研究[D]. 杭州：浙江大學(xué),2010.

[ 2 ] 王中華. 基于遺傳算法的港口船舶調(diào)度優(yōu)化問題研究[D]. 上海：上海海事大學(xué),2007.

[ 3 ] 王沖, 茅云生, 辛鍾桂. 基于遺傳算法的船舶分段運(yùn)輸調(diào)度方法[J]. 上海交通大學(xué)學(xué)報(bào), 2017, 51(3):338-343.

[ 4 ] 錢燕, 周良. 基于遺傳算法的不定期船舶調(diào)度優(yōu)化模型研究[J]. 計(jì)算機(jī)與數(shù)字工程, 2014, 42(4):601-605.

[ 5 ] 周美英, 李典慶. 多目標(biāo)優(yōu)化設(shè)計(jì)的最小偏差法[J]. 機(jī)械設(shè)計(jì), 2002, 19(12):50-52.

[ 6 ] LI W L, TAN J H. Optimization of Container Ship Principal Parameters based on Minimum-Deviation Method[J]. Shipbuilding of China, 2002, 43(4):1-5.

[ 7 ] WEI F T, SONG L, YAN L. Application of Minimum-Deviation Method to Mechanical Multi-Objective Optimal Design[J].Journal of Engineering Graphics, 2011, 32(3):100-104.

[ 8 ] 王文全, 黃勝, 侯遠(yuǎn)航,等. 基于改進(jìn)人工蜂群算法的大型艦船主尺度優(yōu)化[J]. 武漢理工大學(xué)學(xué)報(bào), 2012, 34(6):58-62.

[ 9 ] 周俊杰.Matlab/Simulink實(shí)例講解[M]. 北京：中國(guó)水利水電出版社,2014.

[10] 張新宇, 林俊, 郭子堅(jiān),等. 基于模擬退火多種群遺傳算法的港口船舶調(diào)度優(yōu)化[J]. 中國(guó)航海, 2016, 39(1):26-30.