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

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

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

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

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

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

1 汽渡渡運流程分析

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

圖1 渡運流程圖Fig.1 Ferry flow chart

通過分析，可知渡運流程主要有以下幾個特點：

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

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

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

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

通過分析原渡運流程和裝載特點，本文的主要工作如下：

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

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

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

2 汽車輪渡裝載模型

2.1 模型假設(shè)

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

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

2.2 模型構(gòu)建

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

目標函數(shù)：

(3)

約束條件：

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

3 算法設(shè)計

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

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

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

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

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

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

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

4 算例分析

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

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

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

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

(11)

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

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

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

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

表2 裝載方案對比Tab.2 Comparison of loading schemes

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

表4 成對樣本檢驗Tab.4 Paired sample test

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

由表2可知，在該航線上本文設(shè)計的智能裝載方案比原裝載方案裝載率平均提高了7.64%，收益也平均提高了16.64%，表4中的sig=0.00<0.05，表明收益和裝載率前后都有顯著變化.最后，對比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汽渡公司的原渡運流程進行分析，設(shè)計了一套基于啟發(fā)式算法的智能裝載流程優(yōu)化方案.實際運用結(jié)果表明,本文提出的智能裝載方案和算法能比原方案獲得更好效益.應(yīng)用此方案裝載率提高了7.46%，G公司日平均收益提高了30 279.64元.優(yōu)化后的方案不僅可以減少甲板面積的浪費，增加汽渡公司總收益，還能提高裝載率，減少待渡車輛等待時間.設(shè)計的渡船裝載系統(tǒng)可應(yīng)用于汽渡船舶裝載，能夠有效降低安全員的工作強度，避免反復的人工確認，使汽渡裝載的智能化程度大大提高.