復(fù)雜水網(wǎng)中船舶航行路徑多目標(biāo)規(guī)劃模型

周春輝，陳銘章，何義才，徐周華，文元橋

(1.武漢理工大學(xué) 航運(yùn)學(xué)院，武漢 430063；2.湖北省內(nèi)河航運(yùn)技術(shù)重點(diǎn)實(shí)驗(yàn)室，武漢 430079；3.武漢大學(xué) 測(cè)繪學(xué)院，武漢 430070)

復(fù)雜水網(wǎng)中船舶航行路徑多目標(biāo)規(guī)劃模型

周春輝1,2，陳銘章1,2，何義才1,3，徐周華1，文元橋1

(1.武漢理工大學(xué) 航運(yùn)學(xué)院，武漢 430063；2.湖北省內(nèi)河航運(yùn)技術(shù)重點(diǎn)實(shí)驗(yàn)室，武漢 430079；3.武漢大學(xué) 測(cè)繪學(xué)院，武漢 430070)

在深入研究船舶交通流理論的基礎(chǔ)上，結(jié)合內(nèi)河復(fù)雜水網(wǎng)獨(dú)有的特性，構(gòu)建復(fù)雜水網(wǎng)條件下的船舶航行路徑多目標(biāo)規(guī)劃模型；運(yùn)用層次分析法獲取多目標(biāo)規(guī)劃模型各子目標(biāo)的權(quán)重；利用線性加權(quán)法和Floyd算法求解得到綜合最優(yōu)航行路徑。該模型不僅綜合考慮了影響航行路徑選擇的各種因素，而且對(duì)其進(jìn)行了合理的量化，并通過算例證明了模型的合理性和有效性。

復(fù)雜水網(wǎng)；船舶交通流；最優(yōu)航行路徑；多目標(biāo)規(guī)劃；線性加權(quán)法；Floyd算法

近年來，隨著水上通航需求不斷上升，國(guó)內(nèi)部分通航條件受限的河段(尤其是江蘇、浙江一帶的水網(wǎng)區(qū)域)擁擠堵塞狀況日益嚴(yán)重。無論是從船舶自主航行路徑選擇的角度還是從內(nèi)河航運(yùn)管理部門調(diào)度需要的角度考慮，都迫切需要整個(gè)水網(wǎng)層面的航行路徑規(guī)劃方案。目前國(guó)內(nèi)外相關(guān)學(xué)者已在這方面進(jìn)行一些初步研究。

李文歡[1]對(duì)集裝箱班輪運(yùn)輸?shù)暮骄€網(wǎng)絡(luò)優(yōu)化問題進(jìn)行深入研究，提出利用圖論中的旅行商問題模型及整數(shù)規(guī)劃等方法求解集裝箱船最優(yōu)航行路徑，并依據(jù)長(zhǎng)江中下游集裝箱班輪運(yùn)輸航線網(wǎng)絡(luò)的統(tǒng)計(jì)信息設(shè)計(jì)優(yōu)化算法，對(duì)模型進(jìn)行驗(yàn)證。劉建秋[2]從系統(tǒng)總收益最大化的角度出發(fā)，綜合考慮模糊變量和隨機(jī)變量，建立不確定環(huán)境下的支線集裝箱班輪優(yōu)化網(wǎng)絡(luò)模型，并以長(zhǎng)三角某運(yùn)輸公司為例，采用蟻群算法求取網(wǎng)絡(luò)運(yùn)輸路徑。PFLIEGL[3]針對(duì)內(nèi)河水網(wǎng)中河道及船閘通航條件的動(dòng)態(tài)變化使調(diào)度變得困難，提出在澳大利亞Danube河上建立內(nèi)河信息服務(wù)系統(tǒng)，以促進(jìn)水網(wǎng)中船舶的調(diào)度與管理。

總的來說，目前水網(wǎng)層面上的船舶航行路徑選擇和船舶聯(lián)合調(diào)度尚處在研究探索階段，主要以信息共享為前提，一定程度上運(yùn)用預(yù)調(diào)度協(xié)調(diào)機(jī)制來提高航道的利用率，尚沒有實(shí)用的調(diào)度和路徑規(guī)劃模型，且相關(guān)研究主要集中在涉及船閘的船舶調(diào)度方面，很少涉及復(fù)雜水網(wǎng)條件下的船舶調(diào)度和航行路徑規(guī)劃。因此，研究復(fù)雜水網(wǎng)中船舶航行路徑多目標(biāo)規(guī)劃模型不僅對(duì)船舶自主航行路徑選擇的研究具有一定的指導(dǎo)意義，而且對(duì)內(nèi)河船舶管理調(diào)度部門管理調(diào)度船舶具有一定的參考價(jià)值。

1 航行路徑選擇的多目標(biāo)規(guī)劃模型

1.1問題分析

影響船舶航行路徑選擇的因素可分為主因素觀和客觀因素2類，其中：主觀因素主要包括駕駛員的駕駛經(jīng)驗(yàn)、駕駛路徑選擇偏好及航行目的等；客觀因素主要包括航行總路程、總時(shí)間、擁擠程度及通行費(fèi)用等。因此，最優(yōu)航行路徑選擇是一個(gè)各種因素交互作用的多目標(biāo)規(guī)劃問題。[4]

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

根據(jù)對(duì)最優(yōu)航行路徑選擇影響因素的分析，選擇總路程最小化、航道綜合時(shí)間阻抗最小化、擁擠程度最小化和通行費(fèi)用最小化作為模型子目標(biāo)。

1.2.1總路程最小化

(1)

1.2.2航道綜合時(shí)間阻抗最小化

與道路交通中的交通阻抗不同，內(nèi)河航道的交通時(shí)間阻抗由航道基本段和船閘時(shí)間阻抗2部分組成。根據(jù)水網(wǎng)交通分配路徑的選擇理論，水網(wǎng)時(shí)間阻抗函數(shù)模型[5]為

(2)

文獻(xiàn)[5]基于船舶交通流理論，結(jié)合交通流特性中的流量、速度和密度等3個(gè)參數(shù)提出3個(gè)參數(shù)間的關(guān)系模型，其中速度-流量的關(guān)系為

(3)

式(3)中：q為船舶流流量，艘/h；v為船舶流航行速度，km/h；vf為自由流速度，km/h；k為船舶流密度，艘/km；kf為自由流狀態(tài)下航道中的最大船舶密度，艘/km；kj為阻塞密度，艘/km；ρ為波速系數(shù)，0≤ρ≤1。

基于船舶交通流理論，假設(shè)航道段a上船舶的平均航行時(shí)間Ra(q)與航道長(zhǎng)度la及船舶航行的平均速度va(q)有關(guān)，即

(4)

根據(jù)交通流理論，假設(shè)航道上船舶的到達(dá)分布符合泊松分布[6]，λb為船閘b處船舶的到達(dá)率，E(T)為過閘服務(wù)時(shí)間，Var[T]為服務(wù)時(shí)間的方差，得到服務(wù)強(qiáng)度ρb=λb°E(T)。由Pollaczck-Khintchine公式可得M/G/1模型系統(tǒng)內(nèi)船閘b的平均排隊(duì)等待船舶數(shù)Nb為

(5)

(6)

綜上所述，假設(shè)船舶傾向于選擇航行總阻抗最小的路徑，最優(yōu)航行路徑選擇的目標(biāo)函數(shù)為T2，則聯(lián)立式(2)～式(6)可得

(7)

1.2.3擁擠程度最小化

擁擠程度S[7]可用航道中交通流的飽和度來衡量。假設(shè)航道段a上的設(shè)計(jì)通行能力為ca，實(shí)際交通流量為fa，則飽和度sa=fa/ca。假設(shè)船舶傾向于選擇從起點(diǎn)到終點(diǎn)擁擠程度最小的航行路徑，則最優(yōu)航行路徑選擇的目標(biāo)函數(shù)T3為

(8)

1.2.4通行費(fèi)用最小化

船舶的通行費(fèi)用主要包括燃料費(fèi)和過閘費(fèi)2部分。由于船舶在內(nèi)河中航行時(shí)周圍環(huán)境穩(wěn)定，風(fēng)浪影響幾乎可以忽略不計(jì)，因此在船舶載重不變的情況下可假設(shè)航行所消耗的燃料費(fèi)與航程成正比。由此，在通行費(fèi)用最小化的目標(biāo)下，最優(yōu)航行路徑選擇的目標(biāo)函數(shù)T4為

(9)

1.3航行路徑選擇的多目標(biāo)規(guī)劃模型

聯(lián)立式(1)、式(7)～式(9)得最優(yōu)航行路徑選擇的多目標(biāo)規(guī)劃模型為

(10)

1.4模型求解

對(duì)于多目標(biāo)規(guī)劃問題，可用線性加權(quán)法、約束法、效用系數(shù)法和評(píng)價(jià)函數(shù)法等方法進(jìn)行求解。根據(jù)所建立的多目標(biāo)規(guī)劃模型和各分目標(biāo)的特點(diǎn)，采取線性加權(quán)法進(jìn)行求解?？紤]到上述多目標(biāo)規(guī)劃模型的4個(gè)子目標(biāo)的量綱不同，采用極差化法對(duì)變量進(jìn)行無量綱化處理。[8]

(11)

(12)

利用線性加權(quán)法對(duì)多目標(biāo)規(guī)劃模型進(jìn)行求解，得

(13)

式(13)中：λ1，λ2，λ3，λ4分別為4個(gè)子目標(biāo)的權(quán)重系數(shù)，既可采用層次分析法求取，也可根據(jù)船舶對(duì)各個(gè)子目標(biāo)的偏好程度或船舶調(diào)度者的調(diào)度意愿來主觀確定。

2 算例分析

2.1層次分析法確定權(quán)重

由于建立的多目標(biāo)規(guī)劃模型有4個(gè)子目標(biāo)，而每個(gè)子目標(biāo)的重要性無論是對(duì)調(diào)度者還是對(duì)船舶駕駛員而言都是不同的，因此根據(jù)層次分析法[9]確定4個(gè)子目標(biāo)的權(quán)重系數(shù)λ1，λ2，λ3和λ4的值。

2.1.1建立評(píng)價(jià)體系

根據(jù)層析分析法評(píng)價(jià)體系構(gòu)建規(guī)則，構(gòu)建最優(yōu)航行路徑評(píng)價(jià)體系(見圖1)。

圖1 航行路徑選擇評(píng)價(jià)體系

2.1.2確定準(zhǔn)則層判斷矩陣

利用表1所示的1～9標(biāo)度法對(duì)準(zhǔn)則層中的4個(gè)因素(總航程B1，綜合時(shí)間阻抗B2，擁擠程度B3，通行費(fèi)用B4)進(jìn)行成對(duì)比較。

表1 1～9標(biāo)度法的意義

2.1.3最大特征根與一致性檢驗(yàn)

求解可得最大特征根λmax=4.12，特征向量(權(quán)重系數(shù))λi=(0.05，0.57，0.26，0.12)。一致性指標(biāo)計(jì)算式為

(14)

查找Saaty給出的平均隨機(jī)一致性指標(biāo)RI[9]，計(jì)算一致性比例可得

(15)

由于0.043<0.1，因此判斷矩陣的一致性是可以接受的，權(quán)重系數(shù)λi=(0.05，0.57，0.26，0.12)。

2.2確定鄰近點(diǎn)之間的“距離”

由式(13)可得4個(gè)子目標(biāo)的取值對(duì)于船舶或船舶調(diào)度者來說均是越小越好，因此式(13)的取值可認(rèn)為是“距離”。根據(jù)Floyd算法[10]的求解條件，需先確定鄰近點(diǎn)之間的距離。在能獲得數(shù)據(jù)和確定λ1～λ4的情況下，鄰近點(diǎn)之間的“距離”容易求取。假設(shè)模型4個(gè)子目標(biāo)的值計(jì)入4個(gè)數(shù)組(t1,t2,t3,t4)中，則多目標(biāo)規(guī)劃模型的值(即鄰近點(diǎn)之間的“距離”)計(jì)入數(shù)組t中，t=λ1t1+λ2t2+λ3t3+λ4t4。

2.3計(jì)算結(jié)果與分析

假設(shè)兩點(diǎn)之間沒有直接連接或沒有連接，則兩點(diǎn)之間的距離定義為無窮大，通過確定t1,t2,t3,t4的值，并取λi=(0.05，0.57，0.26，0.12)，得鄰近點(diǎn)之間的“距離”t(即賦權(quán)圖的權(quán)矩陣，見圖2)。

圖2 水網(wǎng)示意及鄰近點(diǎn)之間的“距離”

利用Floyd算法進(jìn)行求解，上述t即為賦權(quán)圖的權(quán)矩陣，得到水網(wǎng)中任意兩點(diǎn)最短路徑的長(zhǎng)度d(i,j)和第i個(gè)點(diǎn)到第j個(gè)點(diǎn)最短路徑中第i個(gè)點(diǎn)后繼點(diǎn)的編號(hào)path(i,j)，見表2。

表2 i點(diǎn)到j(luò)點(diǎn)的最短路徑中i點(diǎn)后繼點(diǎn)編號(hào)

至此，即求出圖1網(wǎng)絡(luò)中任意兩點(diǎn)之間的最短路徑及其最短“距離”。例如，從表2中可查到點(diǎn)1到點(diǎn)8的最短路徑path(1,8)為1—4—7—8。但是，該結(jié)果不是唯一的，會(huì)隨著各種因素的變化而變化。例如:船舶的偏好或船舶調(diào)度者的意愿不同而使得λ1，λ2，λ3及λ4的取值不同；航道改道會(huì)導(dǎo)致總航程發(fā)生變化；航行時(shí)間及緊張程度不同會(huì)導(dǎo)致理解阻抗不同；隨著時(shí)間的推移，船舶密度發(fā)生變化會(huì)導(dǎo)致?lián)頂D程度不同；油價(jià)或過閘費(fèi)用的變化導(dǎo)致通行費(fèi)用上升。

3 結(jié)束語

針對(duì)最優(yōu)航行路徑選擇問題的多樣性特點(diǎn)，將該問題轉(zhuǎn)化成一個(gè)具有4個(gè)子目標(biāo)的多目標(biāo)規(guī)劃模型，并利用線性加權(quán)法和Floyd算法進(jìn)行求解。通過分析，在獲取航道資料、過閘費(fèi)用、油價(jià)、水網(wǎng)中船舶的實(shí)時(shí)分布、船舶本身航行時(shí)間的緊迫度及航行目的等信息的條件下，可根據(jù)建立的多目標(biāo)規(guī)劃模型及其求解算法求得船舶的最優(yōu)航行路徑，實(shí)現(xiàn)復(fù)雜水網(wǎng)條件下船舶的自主航行路徑選擇和調(diào)度部門對(duì)船舶的宏觀調(diào)度。

但是，運(yùn)用建立的復(fù)雜水網(wǎng)條件下船舶聯(lián)合調(diào)度多目標(biāo)規(guī)劃模型的前提是獲得內(nèi)河航運(yùn)調(diào)度部門提供的航道信息和船舶交通流量信息，除了考慮航行路徑路程、航行路徑阻抗、航行路徑擁擠程度及航行費(fèi)用等4項(xiàng)評(píng)價(jià)指標(biāo)之外，還可考慮服務(wù)水平、上水與下水等因素。此外，建立一個(gè)更加適合復(fù)雜、動(dòng)態(tài)變化的水網(wǎng)交通調(diào)度模型是進(jìn)一步研究的方向。

[1] 李文歡.集裝箱班輪運(yùn)輸?shù)暮骄€網(wǎng)絡(luò)優(yōu)化研究[D].上海:上海海事大學(xué),2007.

[2] 劉建秋.不確定環(huán)境下支線集裝箱班輪網(wǎng)絡(luò)優(yōu)化研究 [D].大連:大連海事大學(xué),2010.

[3] PFLIEGL R.Innovative Application for Dynamic Navigational Support and Transport Management on Inland Waterways:Experience from a Research Project on the Danube River[J].Journal of Transportation Research Board,2001,1763:85-89.

[4] 宗傳苓,李相勇,王英濤.出行前路徑選擇的多目標(biāo)規(guī)劃模型[J].交通運(yùn)輸系統(tǒng)工程與信息,2005,5(6):58-61.

[5] 朱俊.基于船舶流的交通時(shí)間阻抗模型[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2010,34(3):591-594.

[6] 孫榮恒,李建平.排隊(duì)論基礎(chǔ)[M].北京:科學(xué)出版社,2002.

[7] 達(dá)慶東,張國(guó)伍.交通擁擠定量分析方法[J].交通運(yùn)輸系統(tǒng)工程信息,2002,2(4):45-48.

[8] 呂寶軍.機(jī)動(dòng)車出行路線選擇及軟件實(shí)現(xiàn)[D].天津:天津大學(xué),2012：45-48.

[9] 司守奎,孫璽菁.數(shù)學(xué)建模算法與應(yīng)用[M].北京:國(guó)防工業(yè)出版社,2011：167-171.

[10] 張秀蘭,林峰.數(shù)學(xué)建模與實(shí)驗(yàn)[M].北京:化學(xué)工業(yè)出版社,2013：101-108.

Multi-ObjectiveProgrammingModelofShipSailingPathforComplexWaterNetwork

ZHOUChunhui1,2，CHENMingzhang1,2，HEYicai1,3，XUZhouhua1，WENYuanqiao1

(1.School of Navigation,Wuhan University of Technology,Wuhan 430063,China;2.Hubei Inland Shipping Technology Key Laboratory,Wuhan 430070,China;3.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China)

On the basis of the vessel traffic flow theory,taking the unique characteristics of the inland water net,the multi-objective programming model of ship sailing path is established under the condition of complex water network,and the AHP is used to get the weights of each sub-goal of the multi-objective programming model.By means of the linear weighting method and Floyd algorithm the overall optimal sailing path is decided.This model,taking the factors that affect the sailing path selection into account quantitatively,is verified by a numerical example.

complex water network; ship traffic flow; optimal sailing path; multi-objective programming; linear weighting; Floyd algorithm

U697.1

A

2017-01-11

國(guó)家自然科學(xué)基金(51209166；51679180);湖北省交通廳科技計(jì)劃項(xiàng)目(2014-721-4-2);武漢理工大學(xué)自主創(chuàng)新研究基金(2017-HY-B1-07)

周春輝(1978—)，男，湖北松滋人，博士，副教授，從事交通安全仿真方面研究。E-mail:chunhui@whut.edu.cn

陳銘章(1996—)，男，湖北黃岡人，學(xué)士,從事水路交通運(yùn)輸研究。E-mail:984393738@qq.com

1000-4653(2016)04-0078-05