汽車輪渡智能裝載優(yōu)化方案研究

陳 樸, 方景芳, 劉 軍, 陳家偉

(蘭州理工大學(xué) 機(jī)電工程學(xué)院, 甘肅 蘭州 730050)

汽車輪渡作為城市立體交通系統(tǒng)的一部分，有著不可或缺的作用.傳統(tǒng)汽車渡船的裝載過程，由渡口安全員和渡船駕駛員共同完成.船只的載重與平衡等實(shí)況，通過儀器顯示，由駕駛員控制.安全員通過無線電傳呼機(jī)通報(bào)待渡船只的剩余容量、裝載進(jìn)展等信息，人工安排車輛的上船次序.這種半人工的汽渡裝載過程，往往持續(xù)時(shí)間較長(zhǎng)，無法充分利用船只的運(yùn)載能力且效率低下，智能化程度亟待提高.如何實(shí)現(xiàn)汽渡船裝載過程的智能化尚未見相關(guān)研究，但國(guó)內(nèi)外已有諸多一般船舶裝載研究，可作借鑒.

Le Carrer等[1]為優(yōu)化潮汐港口和淺海的船舶裝載設(shè)計(jì)了一個(gè)計(jì)算貨物裝載和調(diào)度決策的航運(yùn)決策模型，采用粒子群優(yōu)化和蒙特卡羅模擬求解航運(yùn)凈收益約束優(yōu)化問題.Azevedo等[2]以最優(yōu)化船舶穩(wěn)性和最小化倒箱操作為目標(biāo)，以加權(quán)形式，結(jié)合基于規(guī)則的方式，采用智能搜索算法對(duì)三維集裝箱配載問題進(jìn)行求解，并給出具體算例驗(yàn)證了算法的有效性.Daniela等[3]針對(duì)掛靠多港口集裝箱船的智能化配載問題，提出了一種MIP(混合整數(shù)規(guī)劃)模型.Parreo等[4]提出一種貪婪隨機(jī)自適應(yīng)搜索算法，比經(jīng)典整數(shù)規(guī)劃算法更具多樣性，能產(chǎn)生較多優(yōu)異解.Zhang等[5]以倒箱量和船舶穩(wěn)性為目標(biāo)，利用啟發(fā)式算法和多目標(biāo)遺傳算法，并采用貪婪搜索策略從理論上解決了船舶的配載問題.Jo等[6]針對(duì)三維集裝箱配載優(yōu)化問題，以穩(wěn)性和倒箱量為目標(biāo)，提出一種Pareto聚類搜索算法，能產(chǎn)生較好的非劣解集.Wu等[7]以集裝箱船裝載過程為背景，分析了影響裝載的因素，為集裝箱裝載系統(tǒng)的建設(shè)提供了可靠思路.Khoirun等[8]研究了水泥公司卸船負(fù)荷，使用混合整數(shù)線性規(guī)劃求解方法以最小化總運(yùn)輸成本.Wen等[9]為制定最小化所需船舶貨艙數(shù)量的預(yù)制產(chǎn)品裝載計(jì)劃，建立整數(shù)規(guī)劃模型，設(shè)計(jì)啟發(fā)式算法來獲得高質(zhì)量的解決方案.

李虎等[10]以船舶艙容限制、允許重量和貨物堆裝規(guī)則為約束條件,構(gòu)造了一種混合遺傳算法來解決散貨船配載問題,以提高倉(cāng)容利用率和裝載效率.朱瑩等[11]建立了集裝箱船裝載的數(shù)學(xué)模型，提出了一種新型混合遺傳智能算法，算法中設(shè)計(jì)了包含貨物裝填順序和放置狀態(tài)的兩段編碼方式.朱瑩等[12]還以船艙空間利用率最大為目標(biāo)，建立雜貨船裝載問題的數(shù)學(xué)模型，提出了一種結(jié)合啟發(fā)式算法和遺傳算法的混合遺傳算法，并驗(yàn)證了算法的正確性.汪達(dá)欽等[13]在船舶配載0/1規(guī)劃模型中，將港機(jī)在各船艙的作業(yè)分配作為決策變量,以最短裝船時(shí)間為目標(biāo),聯(lián)合優(yōu)化船舶配載和港機(jī)分配問題,從而實(shí)現(xiàn)了出廠物流的整體優(yōu)化.田浩[14]考慮了集裝箱船舶各個(gè)液艙中裝載量及自由液面對(duì)集裝箱船配載的影響，使用遺傳算法對(duì)集裝箱船舶配載問題進(jìn)行求解.方晟等[15]根據(jù)散貨船使用多裝船機(jī)的裝載作業(yè)情況,建立了散貨船智能裝載數(shù)學(xué)模型,使用多目標(biāo)遺傳算法求解,得到優(yōu)化后的Pareto解集.

縱觀國(guó)內(nèi)外研究現(xiàn)狀，船舶裝載問題的研究對(duì)象多為集裝箱船和散貨船，關(guān)于汽渡船裝載的研究幾乎沒有.汽車不同于貨物，汽渡裝載方式也不同于集裝箱船和散貨船.本文建立了汽渡裝載模型，利用汽渡裝載算法求解，并設(shè)計(jì)了汽渡智能裝載系統(tǒng)以智能化裝載模式替代傳統(tǒng)的人工裝載模式，結(jié)合G公司實(shí)際案例，提高了汽渡公司的經(jīng)濟(jì)效益，具有一定的現(xiàn)實(shí)意義.

1 汽渡渡運(yùn)流程分析

一般在汽渡渡運(yùn)過程中，到達(dá)車輛首先經(jīng)過過磅區(qū)稱重，然后進(jìn)入渡口收費(fèi)站，收費(fèi)站根據(jù)車輛的重量和類型收取渡江費(fèi)用，當(dāng)待渡車輛總重量接近渡船安全載重，即暫停收費(fèi)，待渡車輛進(jìn)入等待區(qū).在渡口安全員的指揮下，待渡車輛依序上船準(zhǔn)備渡江，當(dāng)待渡車輛由于甲板面積限制無法駛?cè)爰装鍟r(shí)結(jié)束裝載，渡船執(zhí)行渡江任務(wù)，未能裝載的車輛停留在待渡區(qū)等待下一艘渡船裝載.并以此循環(huán)，其渡運(yùn)流程如圖1所示.

圖1 渡運(yùn)流程圖Fig.1 Ferry flow chart

通過分析，可知渡運(yùn)流程主要有以下幾個(gè)特點(diǎn)：

(1) 渡船裝載時(shí)，待渡車輛與甲板邊緣以及待渡車輛間均需留出一定的空間.

(2) 渡船裝載時(shí)，車輛不能夠堆疊擺放，只能平面二維裝載；車輛停放的方向應(yīng)順應(yīng)上下船方向.

(3) 渡船的卸載，采用FIFO原則，即先進(jìn)先出原則.

(4) 由于渡船的渡運(yùn)成本主要與船舶自身的噸位和航行距離有關(guān)，渡船的裝載量對(duì)成本影響較小，故裝載量越高收益越高.

通過分析原渡運(yùn)流程和裝載特點(diǎn)，本文的主要工作如下：

(1) 車輛過磅得到車輛的重量和類型信息，使進(jìn)入等待區(qū)的車輛重量盡量接近且小于當(dāng)次渡運(yùn)船舶的最大載重.

(2) 在等待區(qū)設(shè)圖像識(shí)別參照桿,并在正上方安裝攝像頭對(duì)所有等待區(qū)車輛拍照，進(jìn)行圖像識(shí)別得到每輛車的長(zhǎng)、寬信息，最后通過汽渡裝載系統(tǒng)內(nèi)設(shè)計(jì)的汽渡智能裝載算法得到智能裝載方案，同時(shí)使企業(yè)的渡運(yùn)收益最高，如圖2所示.

圖2 汽渡智能裝載示意圖Fig.2 Schematic diagram of intelligent loading of automobile ferry

2 汽車輪渡裝載模型

2.1 模型假設(shè)

為便于模型的建立，假設(shè)：汽渡的渡運(yùn)成本與車輛裝載的多少無關(guān)；在保證安全的前提下，渡船一次裝載車輛的總票價(jià)越高，渡口的效益越高；汽渡船裝載不允許車輛堆疊放置，其裝載情況不同于散貨船或集裝箱貨船的裝載，在本模型中車輛不可旋轉(zhuǎn)且裝載順序設(shè)定為自右向左，自上而下；所有車輛在等待過程中均不會(huì)中途離隊(duì)；裝載時(shí)，不同于集裝箱船裝載時(shí)各集裝箱之間可以緊靠，汽渡裝載時(shí)車輛與車輛之間必須保證的空隙為安全車距2d0，車輛與渡船首、尾和兩側(cè)之間的空隙均為d0，且待渡車輛不會(huì)發(fā)生碰撞等特殊情況.為防止出現(xiàn)二次等待，規(guī)定如上次到達(dá)車輛未進(jìn)入等待區(qū)則下一次必須進(jìn)入.

本文建模設(shè)計(jì)參數(shù)包括：到達(dá)車輛集合D，包含m輛車；dj=(wj,pj)，j=1,2,…,n，wj為第j輛車的重量,pj為第j輛車的票價(jià)；等待區(qū)車輛集合為C，且D?C，包含n輛車且n≤m;ci=(li,fi,wi,pi)，i=1,2,…,n，li為車輛i的長(zhǎng)度,fi為車輛i的寬度,wi為車輛i的重量，pi為車輛i的票價(jià)；W為渡船的定額噸位；L為渡船的甲板長(zhǎng)度；F為渡船甲板寬度；d0為裝載時(shí)保留的空隙長(zhǎng)度，2d0為安全車距；ai為車ci最右側(cè)與甲板右邊緣之間的距離;bi為車ci最上側(cè)與甲板上邊緣之間的距離；xi為決策變量，表示車輛ci是否裝上甲板；yj為決策變量，表示車輛dj是否進(jìn)入等待區(qū)；xi和yj的具體含義如下：

2.2 模型構(gòu)建

本模型考慮如下因素：結(jié)合渡船的自重和吃水情況與單個(gè)待渡車輛的重量，重量約束將有效限制渡船裝載待渡車輛的總數(shù)量；汽渡船配備有相應(yīng)的平衡重裝置，故渡船的平衡性對(duì)車輛裝載的影響很??；渡船在江面航行，風(fēng)力的影響較小；汽渡船只有在江面能見度達(dá)標(biāo)時(shí)才可航行等.因此，本汽渡裝載模型類似于二維裝箱問題，是典型的組合優(yōu)化問題，其中目標(biāo)函數(shù)設(shè)定為單次渡運(yùn)收益最高，約束條件為重量約束和面積約束.

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

(3)

約束條件：

其中：式(3)為模型目標(biāo)函數(shù)，即使渡船裝載車輛的總收益最高；式(4，5)表示重量約束，即等待區(qū)和裝載車輛的總重量均不超過渡船的定額噸位；式(6,7)表示尺寸約束中每輛車的長(zhǎng)、寬加上前后、左右的安全車距和不可超過甲板的長(zhǎng)和寬；式(8)表示裝載時(shí)車輛不可與其他車輛及甲板邊緣重合；式(9)表示面積約束，即裝載車輛總面積不超過甲板面積；式(10)表示變量li、fi為正數(shù)，且ai、bi必須不小于裝載時(shí)保留的空隙長(zhǎng)度d0.

3 算法設(shè)計(jì)

汽渡船的智能裝載問題可分解為兩部分，首先是篩選進(jìn)入等待區(qū)的車輛，使其在不超重的前提下總收入最高，該部分的求解與背包問題類似；其次，由于渡船裝載不允許車輛堆疊放置，也不可旋轉(zhuǎn)，故等待區(qū)車輛裝載問題可簡(jiǎn)化為二維裝箱問題，用BL算法求解.等待區(qū)裝載上渡船甲板的車輛越多，裝載率越高.故結(jié)合背包問題算法和BL算法，設(shè)計(jì)啟發(fā)式算法求解在重量和面積約束下，某航次渡船的最佳車輛裝載方案，進(jìn)而求得最高收益和對(duì)應(yīng)的裝載率.算法求解步驟如下：

步驟1：將上次到達(dá)但未進(jìn)入等待區(qū)車輛設(shè)為最優(yōu)先進(jìn)入等待區(qū).輸入過磅處測(cè)得的本次到達(dá)車輛票價(jià)和重量，判斷進(jìn)入等待區(qū)的車輛總重量是否小于渡船安全載重，若是則全部進(jìn)入等待區(qū)，執(zhí)行步驟4，否則執(zhí)行步驟2.

步驟2：將本次到達(dá)車輛的單位重量收益存儲(chǔ)到pvalue，并按照單位重量收益降序排列于上次到達(dá)但未進(jìn)入等待區(qū)車輛之后.

步驟3：將車輛按照步驟2中順序依次進(jìn)入等待區(qū)，計(jì)算已進(jìn)入等待區(qū)車輛總重量，當(dāng)總重量超過渡船安全載重時(shí)停止車輛進(jìn)入，執(zhí)行步驟4.

步驟4：將等待區(qū)車輛根據(jù)進(jìn)入順序排序并編號(hào)，同時(shí)圖像識(shí)別后得到每輛車的長(zhǎng)寬信息.

步驟5：隨機(jī)放置ci至緊靠甲板右上角,將ci盡可能向下移動(dòng),再將ci盡可能向左移動(dòng),直到ci不能再向下向左移動(dòng)為止.判斷過程中是否與其他車輛或甲板邊緣有重合，若是則不將ci裝船，令xi=0,i=i+1,i=1,2,…,n，否則將ci裝船執(zhí)行步驟6.

步驟6：令xi=1，記錄所有能裝下(xi=1)的車輛編號(hào)，輸出裝載結(jié)果.

4 算例分析

以G汽渡公司為例，G公司主要承擔(dān)G市和P市的汽車渡運(yùn)任務(wù)，現(xiàn)有三條航線，主力渡運(yùn)船10只，船型均為對(duì)稱的，雙頭、單體、單甲板、舯橋樓式，但其甲板長(zhǎng)寬和定額噸位各不相同.以航線1為例，服務(wù)于該航線的為渡船1、2、3.渡船1的定額噸位W1為150 t,甲板長(zhǎng)度和寬度為40 m和13 m;渡船2的W2為220 t，甲板長(zhǎng)度和寬度為50 m和15 m;渡船3的W3為190 t，甲板長(zhǎng)度和寬度為45 m和13 m.

本文首先選取G公司某年某日航線1航次5的待渡車輛情況.該航次渡船1、3從北岸出發(fā)，渡船2從南岸出發(fā)；兩岸到達(dá)車輛共96輛，其中客車67輛，貨車29輛，票價(jià)根據(jù)G汽渡有限公司渡運(yùn)收費(fèi)標(biāo)準(zhǔn)計(jì)算，由車輛類型等決定；重量數(shù)據(jù)在過磅時(shí)測(cè)得，原裝載方案的裝載率等數(shù)據(jù)為G公司歷史數(shù)據(jù).本文設(shè)計(jì)汽渡智能裝載算法并計(jì)算，結(jié)合渡船1數(shù)據(jù)得到第一批進(jìn)入南岸等待區(qū)車輛，對(duì)比原方案和智能裝載方案等待區(qū)車輛的數(shù)據(jù)，如表1所列.

表1 等待區(qū)車輛數(shù)據(jù)對(duì)比Tab.1 Comparison of vehicle data in waiting area

通過圖像識(shí)別得到等待區(qū)車輛長(zhǎng)寬信息，設(shè)計(jì)汽渡裝載算法并計(jì)算，得到等待區(qū)裝上渡船1甲板的車輛及其停放方案，安全車距d0設(shè)定為0.4 m，迭代100次，算法尋優(yōu)的收益最大值為958元，裝載車輛數(shù)為21輛，如圖3所示.而原裝載方案的單次渡運(yùn)收益為763元，裝載車輛數(shù)為17輛.船舶裝載率(船舶載重量利用率)的公式如下：

(11)

求得最佳裝載方案的裝載率為70.42%，而原裝載方案的裝載率為61.34%.

在汽渡裝載算法的基礎(chǔ)上設(shè)計(jì)汽渡船智能裝載系統(tǒng)，運(yùn)行界面如圖4所示.當(dāng)1號(hào)渡船靠岸后，將等待區(qū)車輛信息輸入即可得到最佳裝載車輛停放圖、應(yīng)載車輛數(shù)和裝載率.

圖4 系統(tǒng)運(yùn)行界面Fig.4 System operation interface

對(duì)該航線其他汽渡船使用智能裝載方案優(yōu)化后對(duì)比，如表2所列.使用IBM SPSS 19對(duì)結(jié)果進(jìn)行配對(duì)樣本t檢驗(yàn)(見表3～5).

表2 裝載方案對(duì)比Tab.2 Comparison of loading schemes

表3 成對(duì)樣本統(tǒng)計(jì)量Tab.3 Paired sample statistics

表4 成對(duì)樣本檢驗(yàn)Tab.4 Paired sample test

表5 成對(duì)樣本相關(guān)系數(shù)Tab.5 Paired sample correlation coefficient

由表2可知，在該航線上本文設(shè)計(jì)的智能裝載方案比原裝載方案裝載率平均提高了7.64%，收益也平均提高了16.64%，表4中的sig=0.00<0.05，表明收益和裝載率前后都有顯著變化.最后，對(duì)比G公司某年所有航線歷史數(shù)據(jù)和大規(guī)模使用智能裝載方案優(yōu)化后結(jié)果(表6)，優(yōu)化后比優(yōu)化前提高了7.46%的裝載率，提高了15.7%的收益.

表6 大規(guī)模優(yōu)化結(jié)果Tab.6 Large scale optimization results

5 結(jié)論

本文深入研究汽車渡船裝載現(xiàn)狀，結(jié)合G汽渡公司的原渡運(yùn)流程進(jìn)行分析，設(shè)計(jì)了一套基于啟發(fā)式算法的智能裝載流程優(yōu)化方案.實(shí)際運(yùn)用結(jié)果表明,本文提出的智能裝載方案和算法能比原方案獲得更好效益.應(yīng)用此方案裝載率提高了7.46%，G公司日平均收益提高了30 279.64元.優(yōu)化后的方案不僅可以減少甲板面積的浪費(fèi)，增加汽渡公司總收益，還能提高裝載率，減少待渡車輛等待時(shí)間.設(shè)計(jì)的渡船裝載系統(tǒng)可應(yīng)用于汽渡船舶裝載，能夠有效降低安全員的工作強(qiáng)度，避免反復(fù)的人工確認(rèn)，使汽渡裝載的智能化程度大大提高.