張曉東 童 劍 郭 敏 黃祥釗

1海軍裝備部 艦船辦公室，北京100071 2中國(guó)艦船研究設(shè)計(jì)中心，湖北武漢430064 3華中科技大學(xué) 系統(tǒng)工程研究所，湖北 武漢430074

艦船物資轉(zhuǎn)運(yùn)方案計(jì)算機(jī)輔助決策算法研究

張曉東1童 劍2郭 敏3黃祥釗2

1海軍裝備部 艦船辦公室，北京100071 2中國(guó)艦船研究設(shè)計(jì)中心，湖北武漢430064 3華中科技大學(xué) 系統(tǒng)工程研究所，湖北 武漢430074

瞬息萬(wàn)變的現(xiàn)代戰(zhàn)場(chǎng)對(duì)大中型水面戰(zhàn)斗艦船甲板物資轉(zhuǎn)運(yùn)的效率提出越來(lái)越高的要求。引入計(jì)算機(jī)輔助決策技術(shù)，在考慮多種牽制因素的情況下，快速獲得最優(yōu)的物資轉(zhuǎn)運(yùn)方案。詳細(xì)分析和闡述艦船物資轉(zhuǎn)運(yùn)線路規(guī)劃、時(shí)間計(jì)算、作業(yè)排序以及資源配班等4個(gè)主要問(wèn)題的計(jì)算機(jī)解決方法，為利用計(jì)算機(jī)輔助制定最優(yōu)物資轉(zhuǎn)運(yùn)方案提供可行途徑。

線路規(guī)劃；轉(zhuǎn)運(yùn)作業(yè)時(shí)序；資源配班；轉(zhuǎn)運(yùn)方案；決策支持

1 引言

現(xiàn)代大中型水面戰(zhàn)斗艦船由于作戰(zhàn)使命任務(wù)的需要，攜帶有大量戰(zhàn)斗和生活物資，并且在遠(yuǎn)海作戰(zhàn)時(shí)還需要中途大量補(bǔ)給物資。各類(lèi)置于甲板上的戰(zhàn)斗物資包括彈藥以及加滿燃油的飛機(jī)等都具有較高危險(xiǎn)性，如果這些物資長(zhǎng)時(shí)間暴露于甲板或不能快速調(diào)整艦載武器的布置狀態(tài)備戰(zhàn)，艦船隨時(shí)會(huì)成為敵方攻擊的目標(biāo)。因此，甲板面的各類(lèi)戰(zhàn)斗物資不僅需要安全轉(zhuǎn)運(yùn)，更需要高效轉(zhuǎn)運(yùn)［1－3］。

關(guān)于艦船物資轉(zhuǎn)運(yùn)，國(guó)內(nèi)相關(guān)的研究成果雖然較多，但對(duì)物體運(yùn)動(dòng)的轉(zhuǎn)角限制以及物體并行運(yùn)動(dòng)的最優(yōu)時(shí)序等影響實(shí)際作業(yè)執(zhí)行效率的重要問(wèn)題卻考慮較少，因此研究成果在實(shí)際應(yīng)用中的可操作性略顯欠缺。本文通過(guò)對(duì)艦面物資轉(zhuǎn)運(yùn)作業(yè)路徑規(guī)劃、時(shí)間計(jì)算、作業(yè)排序以及多作業(yè)并發(fā)下的轉(zhuǎn)運(yùn)資源的配班設(shè)計(jì)等研究，探索利用計(jì)算機(jī)技術(shù)為大中型艦船艦面物資安全、高效的調(diào)配和轉(zhuǎn)運(yùn)作業(yè)制定規(guī)劃方案的可行解決途徑，從而為相關(guān)指揮人員提供便捷的輔助決策手段。目前基于本文所提方法而開(kāi)發(fā)的軟件已得到了實(shí)際應(yīng)用，效果良好。

2 物資轉(zhuǎn)運(yùn)線路規(guī)劃

物資轉(zhuǎn)運(yùn)的首要問(wèn)題是轉(zhuǎn)運(yùn)線路的規(guī)劃。相對(duì)于大型物資如批量運(yùn)送的彈藥以及飛機(jī)等而言，艦船甲板面積較小，因此在物資轉(zhuǎn)運(yùn)的路徑規(guī)劃方面不能單純將此類(lèi)物資視為質(zhì)點(diǎn)考慮其運(yùn)送路線，而應(yīng)該結(jié)合考慮各類(lèi)物資的不規(guī)則外部輪廓，從而在路徑規(guī)劃上避免物資與物資之間、物資與船體結(jié)構(gòu)之間發(fā)生碰撞，并在此基礎(chǔ)上充分考慮運(yùn)送車(chē)輛的輪轉(zhuǎn)角漸變特性，建立數(shù)學(xué)模型，研究適合于艦船物資轉(zhuǎn)運(yùn)的路徑搜索算法和策略。

2.1 物體外形的表示方法

艦船上的物資通常由專用轉(zhuǎn)運(yùn)車(chē)轉(zhuǎn)運(yùn)。物資或碼放在車(chē)上（如彈藥等），或由轉(zhuǎn)運(yùn)車(chē)牽引（如飛機(jī)等）。如果由轉(zhuǎn)運(yùn)車(chē)托運(yùn)，則說(shuō)明物資的體積較車(chē)小，可將車(chē)的外形作為轉(zhuǎn)運(yùn)物資的外部輪廓，而如果由轉(zhuǎn)運(yùn)車(chē)牽引，則說(shuō)明物資的體積較車(chē)大，此時(shí)可直接考慮被牽引物資的外形輪廓。鑒于大型艦船甲板面用于人員和物資轉(zhuǎn)運(yùn)活動(dòng)的區(qū)域一般較為平整，甲板上的凸出物不會(huì)對(duì)車(chē)輛和物資轉(zhuǎn)運(yùn)作業(yè)的安全構(gòu)成威脅，因此可以僅從俯視角度下的二維平面分析物體之間的相對(duì)位置。

二維平面中物資外形的表示方法，是將物體的俯視投影面上的外沿輪廓線轉(zhuǎn)換成一系列節(jié)點(diǎn)坐標(biāo)。節(jié)點(diǎn)的數(shù)量根據(jù)物體外形的不規(guī)則程度確定，一般輪廓曲線較少的物體其輪廓節(jié)點(diǎn)也少，而輪廓曲線復(fù)雜的物體完整表達(dá)的其輪廓節(jié)點(diǎn)數(shù)量將非常龐大。較小的數(shù)據(jù)量有利于提高下文提及的線路規(guī)劃運(yùn)算效率。為盡可能在減少表征物體外沿輪廓數(shù)據(jù)量的同時(shí)，能夠近似完整地表達(dá)物體外部輪廓，可將物體復(fù)雜的外沿輪廓曲線近似劃分為多條直線段的組合，從而使該物體表征為若干多邊形的組合。

2.2 物體姿態(tài)的表示方法

艦上物資在轉(zhuǎn)運(yùn)過(guò)程中，很少有呈圓形的俯視投影面，因此物體在運(yùn)動(dòng)過(guò)程中將呈現(xiàn)出不同的姿態(tài)；而不同的姿態(tài)下物體所占用的甲板空間以及與周?chē)矬w的距離都不同，轉(zhuǎn)運(yùn)線路的設(shè)計(jì)將必然不同，因此需要將物體在二維平面上的姿態(tài)和指向轉(zhuǎn)換成數(shù)字描述方式。物體在甲板上的姿態(tài)主要體現(xiàn)在與艦船縱軸線的夾角變化，而要將這一特性轉(zhuǎn)換為數(shù)學(xué)語(yǔ)言，必需進(jìn)行角度數(shù)值的離散化，即在360°連續(xù)的角度數(shù)值中選擇若干個(gè)角度，則轉(zhuǎn)運(yùn)物資的任意姿態(tài)均能按照相應(yīng)的門(mén)限進(jìn)行歸并處理，從而使姿態(tài)角度的變化具備利用計(jì)算機(jī)進(jìn)行計(jì)算處理的條件。圖1為按照45°的精度將360°劃分為8個(gè)區(qū)間的示例，在該精度條件下，計(jì)算機(jī)所能識(shí)別的物資姿態(tài)角度為8種。

圖1 物體姿態(tài)角的定義Fig.1 Definition of posture angle for an object

2.3 艦船甲板轉(zhuǎn)運(yùn)空間的表示方法

由于物資的轉(zhuǎn)運(yùn)作業(yè)以大中型艦船的甲板面為背景，因此需要將艦船甲板面也表示成一系列數(shù)值。下面以甲板輪廓是矩形為例，以艦縱向?yàn)閤軸，艦橫向?yàn)閥軸構(gòu)建直角坐標(biāo)系，將甲板平面劃分成m×n個(gè)正方形柵格 （m行，n列），從而利用（m＋1）×（n＋1）個(gè)點(diǎn)坐標(biāo)表示出甲板面。在柵格圖中，每個(gè)柵格分為兩種情況：一是自由柵格點(diǎn)，柵格屬于自由空間，即轉(zhuǎn)運(yùn)物資輪廓曲線可以進(jìn)入的空間；二是障礙物柵格點(diǎn)，屬于障礙物空間，這些柵格點(diǎn)上不允許轉(zhuǎn)運(yùn)物資輪廓曲線進(jìn)入。圖2為m=70、n=32時(shí)，矩形輪廓甲板面的柵格點(diǎn)示意圖。

圖2 空間網(wǎng)格的定義Fig.2 Schematic of space grid

2.4 轉(zhuǎn)運(yùn)線路規(guī)劃算法的基本原理

根據(jù)物體轉(zhuǎn)運(yùn)車(chē)輛的運(yùn)動(dòng)約束條件，在全部轉(zhuǎn)運(yùn)作業(yè)空間柵格中生成物體的一步轉(zhuǎn)移網(wǎng)格［4－5］，如圖3。根據(jù)機(jī)器人運(yùn)動(dòng)規(guī)劃原理［6－7］，從某個(gè)網(wǎng)格節(jié)點(diǎn)A出發(fā)，按照一定步長(zhǎng)，一步可以達(dá)到下列節(jié)點(diǎn)：

圖3 物資一步轉(zhuǎn)移網(wǎng)格圖Fig.3 Material transfer meshes

其中F2為物體的幾何中心點(diǎn)所在位置沿著姿態(tài)角方向前進(jìn)所能到達(dá)的目標(biāo)柵格點(diǎn)，B2為沿著姿態(tài)角方向后退所能到達(dá)的目標(biāo)柵格點(diǎn)，F(xiàn)1為沿著左圓方向弧線前進(jìn)所能到達(dá)的目標(biāo)柵格點(diǎn)，B1為沿著左圓方向弧線后退所能到達(dá)的目標(biāo)柵格點(diǎn)，F(xiàn)3為沿著右圓方向弧線前進(jìn)所能到達(dá)的目標(biāo)柵格點(diǎn)，B3為沿著右圓方向弧線后退所能到達(dá)的目標(biāo)柵格點(diǎn)。物體每走微小的一步（稱為一個(gè)步長(zhǎng)）都選擇其中的一條路徑，那么從起始點(diǎn)（起始點(diǎn)坐標(biāo)和姿態(tài)角）到終止點(diǎn) （終止點(diǎn)坐標(biāo)和姿態(tài)角）的任意一條可行路徑都可以表示為一系列圓弧和直線的組合。

目前有很多求解最短路的算法［8－10］。比如Dijkstra、Flod以及A*、D*算法［11］等等，但是這些算法由于遍歷計(jì)算的節(jié)點(diǎn)很多，當(dāng)柵格空間節(jié)點(diǎn)非常多的情況下，計(jì)算時(shí)間往往不能滿足調(diào)運(yùn)的實(shí)時(shí)性要求。因此針對(duì)本問(wèn)題，我們主要結(jié)合遺傳算法來(lái)進(jìn)行線路規(guī)劃。遺傳算法是由Holand在60年代提出的一種以自然遺傳機(jī)制和自然選擇等生物進(jìn)化理論為基礎(chǔ)的隨機(jī)化搜索算法，其優(yōu)越性表現(xiàn)在：1）在搜索過(guò)程中不易陷入局部最優(yōu)，即使在適應(yīng)度函數(shù)不連續(xù)、不規(guī)則、有噪聲的情況下也能以較大的概率找到全局最優(yōu)解；2）采用自然進(jìn)化機(jī)制來(lái)表現(xiàn)復(fù)雜的現(xiàn)象，能快速解決較困難的問(wèn)題，易于介入已有的模型，擴(kuò)展性強(qiáng)。

利用遺傳算法求解該路徑問(wèn)題的基本思路是：在轉(zhuǎn)運(yùn)全局地圖的基礎(chǔ)上，產(chǎn)生一組從起始點(diǎn)至目標(biāo)點(diǎn)的由若干中途點(diǎn)組成的初始種群，再按適應(yīng)度的大小選擇個(gè)體，并進(jìn)行復(fù)制、交叉和變異等遺傳操作，從而產(chǎn)生出代表新的解集的群體，如此往復(fù)，逐代演化產(chǎn)生出越來(lái)越好的近似解。整個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣，后代種群比前代具有更短的線路長(zhǎng)度，因此末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼（從基因到性狀的映射），可以作為問(wèn)題近似最優(yōu)解。

3 物資轉(zhuǎn)運(yùn)時(shí)間計(jì)算

物資在轉(zhuǎn)運(yùn)線路上的移動(dòng)可以分為兩類(lèi)：一是物資通過(guò)升降平臺(tái)進(jìn)行轉(zhuǎn)運(yùn)，這類(lèi)操作的執(zhí)行時(shí)間相對(duì)固定，主要由升降平臺(tái)的運(yùn)行指標(biāo)決定；二是物資在甲板上的轉(zhuǎn)運(yùn)，這類(lèi)操作的執(zhí)行時(shí)間影響因素較為復(fù)雜，主要有轉(zhuǎn)運(yùn)線路的長(zhǎng)度（距離影響）、途中的轉(zhuǎn)彎弧度（速度影響）、線路周邊的空閑空間大?。ㄋ俣扔绊懀┮约稗D(zhuǎn)運(yùn)車(chē)駕駛員的熟練程度（速度影響）等。其中線路周邊的空閑空間影響轉(zhuǎn)運(yùn)速度是由于當(dāng)周?chē)D(zhuǎn)運(yùn)空間較小時(shí)，為了保證物資的運(yùn)輸安全，轉(zhuǎn)運(yùn)車(chē)將以較低的速度通過(guò)，而當(dāng)空間較為寬敞時(shí)，則可以較快的速度通過(guò)。

為了較為精確地?cái)M合計(jì)算出物體在轉(zhuǎn)運(yùn)線路上所花費(fèi)的時(shí)間，可以根據(jù)問(wèn)題的實(shí)際背景，將轉(zhuǎn)運(yùn)線路中第n個(gè)節(jié)點(diǎn)和第n＋1個(gè)節(jié)點(diǎn)之間的轉(zhuǎn)角分成L個(gè)等級(jí)表示。例如將360°角劃分為12份，即30°為一個(gè)等級(jí)（可以再細(xì)化，細(xì)化程度根據(jù)數(shù)據(jù)量大小和運(yùn)算速度決定），則以0°、30°、60°、90°……的順序逐級(jí)遞增，其轉(zhuǎn)角對(duì)應(yīng)著不同的加權(quán)系數(shù)Zi（i＝1，2，…，12），其中0≤Zi≤1（一般轉(zhuǎn)運(yùn)車(chē)不能橫向移動(dòng)，則當(dāng)轉(zhuǎn)角為90°時(shí)，Zi＝0；直線運(yùn)行時(shí)速度最大，則當(dāng)轉(zhuǎn)角為0°時(shí)，Zi＝1），同理將線路周?chē)臻e空間大小按照間隔距離也劃分出相應(yīng)等級(jí)，例如以50 mm為一檔將最短間隔距離劃分為300 mm、350 mm、400 mm、450 mm……m個(gè)等級(jí)，則同樣每個(gè)等級(jí)范圍內(nèi)的最短距離對(duì)應(yīng)著不同的加權(quán)系數(shù)Ji（i＝1，2，…，m），其中0≤Ji≤1（當(dāng)周?chē)臻g非常擁擠，對(duì)轉(zhuǎn)運(yùn)車(chē)駕駛員安全轉(zhuǎn)運(yùn)物資構(gòu)成極大心理壓力，如最近的物體間隔正處在安全轉(zhuǎn)運(yùn)的最小規(guī)定門(mén)限值時(shí)，如300 mm，則Ji＝0；當(dāng)周?chē)臻g較大，對(duì)轉(zhuǎn)運(yùn)車(chē)駕駛員安全轉(zhuǎn)運(yùn)物資不構(gòu)成任何心理壓力，如最近的物體間隔為5～10 m，則Ji＝1）。

如圖4所示的一段轉(zhuǎn)運(yùn)線路，按照不同的轉(zhuǎn)彎半徑分為3段，每段線路長(zhǎng)為li（i＝1，2，3），考慮到轉(zhuǎn)彎半徑和周?chē)臻g對(duì)轉(zhuǎn)運(yùn)車(chē)速度的影響，轉(zhuǎn)運(yùn)車(chē)在每段線路上運(yùn)行的速度分別為v×Zi×Ji（i＝1，2，3，0≤Zi≤1，0≤Ji≤1，V表示轉(zhuǎn)運(yùn)車(chē)額定負(fù)載狀態(tài)下的限定車(chē)速），則該段線路上總的轉(zhuǎn)運(yùn)時(shí)間可有如下表示：T＝l1／（V×Z1×J1）＋l2／（V× Z2×J2）＋l3／（V×Z3×J3）。

假設(shè)圖4中l(wèi)1＝10 m，l2＝5 m，l3＝20 m，轉(zhuǎn)運(yùn)車(chē)直行速度為1 m／s，根據(jù)圖4中l(wèi)1和l2的轉(zhuǎn)角變化率對(duì)比情況，設(shè)定轉(zhuǎn)角加權(quán)系數(shù)Z1＝0.5，Z2＝0.3，而Z3＝1，再設(shè)定本段線路周?chē)鷽](méi)有其他物體，則最短距離加權(quán)系數(shù)J1＝J2＝J3＝1，則按上述公式本段線路的轉(zhuǎn)運(yùn)時(shí)間應(yīng)為：T≈56.7 s。

由于轉(zhuǎn)運(yùn)線路的長(zhǎng)度、轉(zhuǎn)角以及與周?chē)矬w的間隔距離等特征參數(shù)均可由上節(jié)中的方法得出，因此艦船甲板面上任何物資的轉(zhuǎn)運(yùn)時(shí)間均可依本節(jié)所述方法近似得出。當(dāng)然，為了使計(jì)算出的運(yùn)行時(shí)間更趨近于真實(shí)情況，還應(yīng)結(jié)合大量實(shí)踐操作得出作業(yè)時(shí)間的統(tǒng)計(jì)數(shù)據(jù)，并在此基礎(chǔ)上對(duì)相關(guān)加權(quán)系數(shù)Zi和Ji的取值進(jìn)行調(diào)整。

圖4 轉(zhuǎn)運(yùn)線路的分段表示Fig.4 Schema of a transfer path

4 物資轉(zhuǎn)運(yùn)排序規(guī)則

多件物資的轉(zhuǎn)運(yùn)作業(yè)必須是有序進(jìn)行，而次序的排列需要按照一定的規(guī)則。如欲轉(zhuǎn)運(yùn)物資的原始位置正處在其他需轉(zhuǎn)運(yùn)物資的轉(zhuǎn)運(yùn)路線上，則應(yīng)先調(diào)移該物資；又如某物資的轉(zhuǎn)運(yùn)目的地處在其他需轉(zhuǎn)運(yùn)物資的轉(zhuǎn)運(yùn)路線上時(shí)該物資應(yīng)后調(diào)動(dòng)等等。為了提高作業(yè)效率，艦船上一次要執(zhí)行多種物資的轉(zhuǎn)運(yùn)工作，因此必須綜合考慮所有物資的轉(zhuǎn)運(yùn)線路才能得出正確的排序方案。

下面首先以兩件物資轉(zhuǎn)運(yùn)線路之間的關(guān)系對(duì)物資的轉(zhuǎn)運(yùn)次序進(jìn)行研究，然后以一種3件物資轉(zhuǎn)運(yùn)的情況為例進(jìn)行方法適用性分析。

4.1 兩條線路在描述上基本重合

主要分為以下兩種情況：

1）A物體的起始位置處在B物體的轉(zhuǎn)運(yùn)線路上，而B(niǎo)物體的目標(biāo)位置處在A物體的轉(zhuǎn)運(yùn)線路上，則B物體可以隨A物體一起移動(dòng)完成轉(zhuǎn)運(yùn)，如圖5a所示。

2）A物體的起始位置處在B物體的轉(zhuǎn)運(yùn)線路上，而其目標(biāo)位置也處在B物體的轉(zhuǎn)運(yùn)線路上。該情況下A物體必須先移動(dòng)，B物體才能移動(dòng)，但又不允許A物體先到達(dá)目的地，否則會(huì)堵塞B物體的轉(zhuǎn)運(yùn)線路。因此A物體需要采取避讓性的轉(zhuǎn)運(yùn)操作，即將其移動(dòng)到附近某個(gè)空閑位置暫留，待B物體通過(guò)A物體初始位置后再返回原位置進(jìn)行轉(zhuǎn)運(yùn)。如圖5b所示。

圖5 兩物體轉(zhuǎn)運(yùn)線路在描述上基本重合Fig.5 Two transfer paths in the same way

4.2 轉(zhuǎn)運(yùn)線路在描述上不完全重合

4.2.1 轉(zhuǎn)運(yùn)線路中段在描述上不重合

轉(zhuǎn)運(yùn)線路中段又分兩種情況：

1）A、B物體的轉(zhuǎn)運(yùn)線路中段代號(hào)分別為X、Y。由于A物體起始位置處在B物體的轉(zhuǎn)運(yùn)線路上，因此A物體應(yīng)先于B物體經(jīng)過(guò)n點(diǎn)移動(dòng)到X段或Y段，并且先于B物體經(jīng)過(guò)O點(diǎn)才能保證轉(zhuǎn)運(yùn)任務(wù)的完成。如圖6a所示。

圖5 兩物體轉(zhuǎn)運(yùn)線路中段不重合Fig.5 Two transfer paths different in central part

2）A物體的起始位置和目的地同處在B物體的轉(zhuǎn)運(yùn)線路上，與4.1節(jié)2）中的情況相似，但由于中段線路不同，A物體不必采取特殊的避讓性調(diào)運(yùn)操作，可先移動(dòng)通過(guò)n點(diǎn)到X段，B再移動(dòng)到Y(jié)段，而在O點(diǎn)處應(yīng)保證B物體先于A物體通過(guò)則能完成轉(zhuǎn)運(yùn)。如圖6b所示。

4.2.2 轉(zhuǎn)運(yùn)線路起始段在描述上不重合

A物體和B物體的起始位置均不處在另一方的轉(zhuǎn)運(yùn)線路上，但B物體的目標(biāo)位置處在A物體的轉(zhuǎn)運(yùn)線路上。A物體需先調(diào)運(yùn)經(jīng)過(guò)交點(diǎn)O到達(dá)目的地，B物體才能完成轉(zhuǎn)運(yùn)。如圖7所示。

圖7 兩條轉(zhuǎn)運(yùn)線路起始段在描述上不重合Fig.7 Two transfer paths different at the beginning part

4.2.3 轉(zhuǎn)運(yùn)線路目標(biāo)段在描述上不重合

A物體和B物體的目的地均不處在另一方的轉(zhuǎn)運(yùn)線路上，但A物體的起始位置處在B物體的轉(zhuǎn)運(yùn)線路上。A物體需先調(diào)運(yùn)通過(guò)交點(diǎn)O，B物體才能完成轉(zhuǎn)運(yùn)，如圖8所示。

圖8 兩條轉(zhuǎn)運(yùn)線路目標(biāo)段在描述上不重合Fig.8 Two transfer paths different at the ending part

4.3 轉(zhuǎn)運(yùn)線路在描述上不重合但相交

A物體和B物體的轉(zhuǎn)運(yùn)線路僅在某處會(huì)使用相同的資源。該情況下A、B兩物體可同時(shí)移動(dòng)，在交點(diǎn)O處協(xié)調(diào)通過(guò)，如圖9所示。

圖9 兩條轉(zhuǎn)運(yùn)線路目標(biāo)段在描述上不重合但相交Fig.9 Two transfer paths different but cross each other

4.4 轉(zhuǎn)運(yùn)線路在描述上不相交

A物體和B物體的轉(zhuǎn)運(yùn)線路具有互異性，在這種情況下兩物體的調(diào)運(yùn)次序是任意的，如圖10所示。

圖10 兩條轉(zhuǎn)運(yùn)線路目標(biāo)段在描述上不相交Fig.10 Two transfer paths totally different

4.5 3件物資轉(zhuǎn)運(yùn)示例

以上是兩件物資轉(zhuǎn)運(yùn)線路之間所有可能的關(guān)系，并對(duì)每種關(guān)系下轉(zhuǎn)運(yùn)作業(yè)的先后次序進(jìn)行了分析，這是多件物資轉(zhuǎn)運(yùn)作業(yè)次序研究的理論基礎(chǔ)。下面以3件物資的轉(zhuǎn)運(yùn)為例說(shuō)明如何使用上述研究結(jié)果得出相應(yīng)的轉(zhuǎn)運(yùn)次序。

如圖11所示，對(duì)A、B、C 3件物資的轉(zhuǎn)運(yùn)線路分別為：A線路n－m－X－o－A，B線路A－n－Y－o－A－B，C線路m－X－o－A－C。其中A物體與B物體的調(diào)運(yùn)線路關(guān)系屬于上面分析的4.2.1節(jié)中的第2種情況，依據(jù)上面得出的結(jié)論，A物體應(yīng)先移動(dòng)通過(guò)n點(diǎn)到X段，而在O點(diǎn)處應(yīng)保證B物體先于A物體通過(guò)；A物體與C物體的轉(zhuǎn)運(yùn)線路關(guān)系屬于4.2.1節(jié)分析的第2種情況，依據(jù)結(jié)論，C物體需先調(diào)運(yùn)經(jīng)過(guò)m點(diǎn)和O點(diǎn)到達(dá)目標(biāo)站位；B物體與C物體的轉(zhuǎn)運(yùn)線路關(guān)系屬于4.3節(jié)分析過(guò)情況，則依結(jié)論B、C兩物體可同時(shí)移動(dòng)，在A的目標(biāo)位置上協(xié)調(diào)通過(guò)。

圖11 3件物資的轉(zhuǎn)運(yùn)線路示例圖Fig.11 A demonstration for three transfer paths

按照上述分析，在A物體與B物體之間，A物體先移動(dòng)，在A物體與C物體之間，C物體先移動(dòng)，則3件物資的轉(zhuǎn)運(yùn)次序?yàn)镃、A、B。在對(duì)調(diào)運(yùn)作業(yè)的具體過(guò)程進(jìn)行分析時(shí)上述的3種線路關(guān)系所得出的結(jié)論都應(yīng)該是被滿足的，因此有：C物體先于A物體經(jīng)過(guò)m點(diǎn)，A物體先于B物體經(jīng)過(guò)n點(diǎn)，B、C兩物體可不分先后但均先于A物體通過(guò)O點(diǎn)完成調(diào)運(yùn)。由此可見(jiàn)，多件物體的轉(zhuǎn)運(yùn)順序可以通過(guò)這些物體經(jīng)過(guò)一些特殊交點(diǎn)的先后次序表達(dá)。因此，可以將上述兩件物資在各種情況下的轉(zhuǎn)運(yùn)順序建成基礎(chǔ)規(guī)則庫(kù)，進(jìn)而解決更多物資同時(shí)轉(zhuǎn)運(yùn)的計(jì)算機(jī)輔助排序問(wèn)題。

5 物資轉(zhuǎn)運(yùn)資源配班

根據(jù)上述轉(zhuǎn)運(yùn)線路規(guī)劃、轉(zhuǎn)運(yùn)時(shí)間計(jì)算以及轉(zhuǎn)運(yùn)排序規(guī)則所闡述的原理，利用計(jì)算機(jī)可以列舉出各種先后順序下的多件物資轉(zhuǎn)運(yùn)的作業(yè)時(shí)序，但所有的時(shí)序還只是考慮了物資轉(zhuǎn)運(yùn)空間上的干涉問(wèn)題，而要使作業(yè)時(shí)序具有實(shí)際可行性，還需結(jié)合轉(zhuǎn)運(yùn)資源如轉(zhuǎn)運(yùn)車(chē)輛以及人員班組的數(shù)量、狀態(tài)及位置等具體情況對(duì)作業(yè)時(shí)序進(jìn)行配班篩選，從而獲得轉(zhuǎn)運(yùn)總時(shí)間最短或者所需資源最省的轉(zhuǎn)運(yùn)方案。由于轉(zhuǎn)運(yùn)車(chē)輛和人員班組的配班屬于同類(lèi)問(wèn)題，因此本文主要闡述轉(zhuǎn)運(yùn)車(chē)輛的配班設(shè)計(jì)思路。

如上所述，物資轉(zhuǎn)運(yùn)線路、作業(yè)時(shí)段各有不同，因此需要針對(duì)這些特點(diǎn)考察轉(zhuǎn)運(yùn)車(chē)輛是否能按照線路規(guī)劃得出的作業(yè)時(shí)序在規(guī)定的時(shí)間到達(dá)指定物資附近，并選取能夠及時(shí)到達(dá)的車(chē)輛進(jìn)行配班和作業(yè)時(shí)長(zhǎng)的比較。

轉(zhuǎn)運(yùn)車(chē)配班設(shè)計(jì)的基本思路是：

1）針對(duì)作業(yè)時(shí)序S中最早轉(zhuǎn)運(yùn)的物資n，配置轉(zhuǎn)運(yùn)車(chē)P；

2）以物資n結(jié)束轉(zhuǎn)運(yùn)的時(shí)間為基準(zhǔn)，以轉(zhuǎn)運(yùn)車(chē)移動(dòng)時(shí)間為限制條件，在后續(xù)轉(zhuǎn)運(yùn)物資n＋i（i＝1，2，3，…）中尋找可以繼續(xù)使用轉(zhuǎn)運(yùn)車(chē)P的物資m；

3）如果存在若干件物資m，則選取這些物資中開(kāi)始轉(zhuǎn)運(yùn)時(shí)間距離物資1結(jié)束轉(zhuǎn)運(yùn)時(shí)間最近的物資X，為其配置轉(zhuǎn)運(yùn)車(chē)P；

4）以物資X結(jié)束轉(zhuǎn)運(yùn)的時(shí)間為基準(zhǔn)，循環(huán)執(zhí)行上述2）、3）項(xiàng)，直至遍歷不到物資m為止，得出可供配置轉(zhuǎn)運(yùn)車(chē)P的全部物資項(xiàng)；

5）為尚未配置轉(zhuǎn)運(yùn)車(chē)中最早轉(zhuǎn)運(yùn)的物資配置轉(zhuǎn)運(yùn)車(chē)P＋1；

6）循環(huán)執(zhí)行上述2）～5），直至全部轉(zhuǎn)運(yùn)車(chē)已分配完；

7）如果此時(shí)所有物資均分配到了轉(zhuǎn)運(yùn)車(chē)，則將作業(yè)時(shí)序S的配班結(jié)果保存為轉(zhuǎn)運(yùn)作業(yè)方案Z，否則由于轉(zhuǎn)運(yùn)資源不能滿足要求，作業(yè)時(shí)序S被舍棄；

8）針對(duì)作業(yè)時(shí)序S＋1，執(zhí)行1）～7）項(xiàng)，將獲得的配班結(jié)果保存為轉(zhuǎn)運(yùn)作業(yè)方案Z＋1，依此思路直至將線路規(guī)劃算法計(jì)算得出的全部作業(yè)時(shí)序組合遍歷完畢；

9）在最終得到的全部轉(zhuǎn)運(yùn)作業(yè)方案中，找出轉(zhuǎn)運(yùn)總時(shí)間最小的方案和轉(zhuǎn)運(yùn)車(chē)使用臺(tái)數(shù)最省的方案。

下面針對(duì)具體情況進(jìn)行舉例分析說(shuō)明：

假設(shè)：

1）艦船上有4件物資需要轉(zhuǎn)運(yùn)，初始位置和目的地見(jiàn)表1（表中Fi和Ji分別指上層甲板和下層甲板中的任意幾點(diǎn)位置）。

表1 物資轉(zhuǎn)運(yùn)情況示例表Tab.1 Example list for object transfer

2）艦船用于物資轉(zhuǎn)運(yùn)的升降平臺(tái)共有前后兩部，且初始時(shí)均處于上層甲板。升降平臺(tái)上升（或下降）所用時(shí)間設(shè)為QS；

3）轉(zhuǎn)運(yùn)車(chē)共有A、B、C、D 4臺(tái)，A、B車(chē)負(fù)責(zé)上層甲板的物資轉(zhuǎn)運(yùn)，C、D車(chē)負(fù)責(zé)下層甲板倉(cāng)庫(kù)的物資轉(zhuǎn)運(yùn)，兩層甲板間車(chē)輛不跨層使用；

4）轉(zhuǎn)運(yùn)車(chē)從上層甲板上任意位置Fn（n＝1，2，3，4）到前升降平臺(tái)的時(shí)間設(shè)為QTn（n＝1，2，3，4），到后升降平臺(tái)的時(shí)間為HTn（n＝1，2，3，4），從前升降平臺(tái)到后升降平臺(tái)的時(shí)間為QH；轉(zhuǎn)運(yùn)車(chē)輛從下層甲板倉(cāng)庫(kù)中任意位置Jn（n＝1，2，3，4）到前升降平臺(tái)的時(shí)間為qtn（n＝1，2，3，4），到后升降平臺(tái)的時(shí)間為htn（n＝1，2，3，4），從前升降平臺(tái)到后升降平臺(tái)的時(shí)間為qh；

5）在不考慮轉(zhuǎn)運(yùn)車(chē)輛的前提下由線路規(guī)劃算法得出的某種線路時(shí)序如圖12所示，其中iM0表示物資i（i＝1，2，3，4）開(kāi)始轉(zhuǎn)運(yùn)的時(shí)間，iM1表示物資在上層甲板上轉(zhuǎn)運(yùn)結(jié)束的時(shí)間，iM2表示物資完成升降平臺(tái)轉(zhuǎn)運(yùn)的時(shí)間，iM3表示物資完成倉(cāng)庫(kù)內(nèi)轉(zhuǎn)運(yùn)的時(shí)間。

圖12 物資轉(zhuǎn)運(yùn)作業(yè)時(shí)序圖Fig.12 Operation timing diagrams

則上述轉(zhuǎn)運(yùn)車(chē)配班設(shè)計(jì)思路的具體實(shí)現(xiàn)如下：

1）上層甲板為物資1配置轉(zhuǎn)運(yùn)車(chē)A，下層甲板倉(cāng)庫(kù)為物資1配置轉(zhuǎn)運(yùn)車(chē)C；

2）由于2M0＜1M1、2M2＜1M3，說(shuō)明物資2在上層甲板此時(shí)無(wú)法配置轉(zhuǎn)運(yùn)車(chē)A，下層甲板倉(cāng)庫(kù)此時(shí)也無(wú)法配置轉(zhuǎn)運(yùn)車(chē)C；

3）由于3M0－1M1≥QT3、3M2－1M3≥qt1，且物資3在上層甲板和下層甲板開(kāi)始轉(zhuǎn)運(yùn)的時(shí)間都距離物資1結(jié)束的時(shí)間最近，因此可為物資3在上層甲板配置轉(zhuǎn)運(yùn)車(chē)A，下層甲板倉(cāng)庫(kù)配置轉(zhuǎn)運(yùn)車(chē)C；

4）接著以物資3作為基準(zhǔn)，對(duì)物資4的轉(zhuǎn)運(yùn)車(chē)配班進(jìn)行分析。由于4M0＜3M1、4M2＜3M3，說(shuō)明物資4在上層甲板。此時(shí)無(wú)法配置轉(zhuǎn)運(yùn)車(chē)A，下層甲板倉(cāng)庫(kù)此時(shí)也無(wú)法配置轉(zhuǎn)運(yùn)車(chē)C；

5）在結(jié)束物資1～4的第一輪轉(zhuǎn)運(yùn)車(chē)配班篩選后，剩余物資2和4未完成配班，引入轉(zhuǎn)運(yùn)車(chē)B、D進(jìn)行配班：在上層甲板為物資2配置轉(zhuǎn)運(yùn)車(chē)B，下層甲板倉(cāng)庫(kù)為物資2配置轉(zhuǎn)運(yùn)車(chē)D；

6）由于4M0－2M1≥HT4、4M2－2M3≥ht2，可為物資4在上層甲板配置轉(zhuǎn)運(yùn)車(chē)B，下層甲板倉(cāng)庫(kù)配置轉(zhuǎn)運(yùn)車(chē)D；

7）完成在該時(shí)序下的轉(zhuǎn)運(yùn)作業(yè)方案。

通過(guò)此例，說(shuō)明了該配班算法思路可以作為通過(guò)艦船物資轉(zhuǎn)運(yùn)時(shí)序進(jìn)一步生成轉(zhuǎn)運(yùn)方案的可行方法。

6 結(jié)論

本文闡述將計(jì)算機(jī)輔助決策技術(shù)應(yīng)用在大中型艦船甲板物資轉(zhuǎn)運(yùn)領(lǐng)域并獲得最優(yōu)作業(yè)方案的基本思路，詳細(xì)分析了為不規(guī)則外形物體計(jì)算無(wú)碰撞干涉轉(zhuǎn)運(yùn)線路的算法思路，以及在此基礎(chǔ)上以加權(quán)系數(shù)的方式將轉(zhuǎn)運(yùn)線路的實(shí)現(xiàn)難易結(jié)合進(jìn)轉(zhuǎn)運(yùn)作業(yè)時(shí)間的計(jì)算中；再針對(duì)物資轉(zhuǎn)運(yùn)線路與其轉(zhuǎn)運(yùn)順序之間的關(guān)系進(jìn)行梳理分析，獲得轉(zhuǎn)運(yùn)作業(yè)時(shí)序排列的重要算法規(guī)則；最后將艦船上配置的轉(zhuǎn)運(yùn)資源與每種轉(zhuǎn)運(yùn)作業(yè)時(shí)序進(jìn)行匹配，從而得到滿足資源條件的情況下耗時(shí)最短的轉(zhuǎn)運(yùn)方案和轉(zhuǎn)運(yùn)資源使用最省的方案。

通過(guò)對(duì)艦船物資轉(zhuǎn)運(yùn)方案的計(jì)算機(jī)輔助決策算法思路的研究，基本理清了針對(duì)該問(wèn)題的算法研究思路，但還存在以下幾點(diǎn)問(wèn)題需要進(jìn)一步開(kāi)展研究：

1）通過(guò)物資轉(zhuǎn)運(yùn)線路規(guī)劃算法得出的線路結(jié)果一般用細(xì)密的柵格節(jié)點(diǎn)連成的曲線表示，而通常在艦船甲板上這些柵格節(jié)點(diǎn)并不存在，因此目前轉(zhuǎn)運(yùn)車(chē)駕駛員只能粗略按照規(guī)劃線路驅(qū)動(dòng)轉(zhuǎn)運(yùn)車(chē)，將影響后續(xù)得出的優(yōu)化轉(zhuǎn)運(yùn)方案的實(shí)際作業(yè)效果。如何使轉(zhuǎn)運(yùn)車(chē)能精確地按照指定的線路運(yùn)送物資，還需通過(guò)開(kāi)展相關(guān)轉(zhuǎn)運(yùn)線路指示技術(shù)的研究以保證轉(zhuǎn)運(yùn)方案的最優(yōu)實(shí)施效果得以充分發(fā)揮；

2）物資轉(zhuǎn)運(yùn)時(shí)間計(jì)算的算法原理雖較為簡(jiǎn)單，但相關(guān)時(shí)間參數(shù)特別是加權(quán)系數(shù)的設(shè)置對(duì)轉(zhuǎn)運(yùn)時(shí)間的準(zhǔn)確性有著至關(guān)重要的影響，而轉(zhuǎn)運(yùn)作業(yè)時(shí)間的準(zhǔn)確程度又直接關(guān)系到后續(xù)作業(yè)排序以及配班設(shè)計(jì)的結(jié)果。因?yàn)檗D(zhuǎn)運(yùn)車(chē)及班組的配班要滿足線路時(shí)序圖的要求，必須避免其在規(guī)定的時(shí)間內(nèi)無(wú)法到達(dá)指定目的地的情況；而如果這些計(jì)算得出的時(shí)間與真實(shí)操作所需花費(fèi)的時(shí)間存在較大差別，則配班算法得出的最優(yōu)方案甚至在實(shí)際作業(yè)中不具有可行性，這樣的結(jié)果將使決策算法得出的最優(yōu)方案完全尚失對(duì)現(xiàn)實(shí)操作的指導(dǎo)意義。因此，必須在嚴(yán)格依照設(shè)備相關(guān)運(yùn)行性能指標(biāo)進(jìn)行分析計(jì)算的前提下，通過(guò)開(kāi)展實(shí)操試驗(yàn)對(duì)相關(guān)參數(shù)進(jìn)行不斷的修正 （相關(guān)參數(shù)應(yīng)為可更改的輸入變量），以使得理論計(jì)算與實(shí)際運(yùn)行的時(shí)間盡可能趨于一致。

［1］劉亞杰，王航宇，謝君.調(diào)運(yùn)問(wèn)題中基于柵格模型的快速路徑規(guī)劃方法［J］.海軍工程大學(xué)學(xué)報(bào)，2009，21（1）：87－90.

［2］馬登武，郭小威，呂曉峰.基于網(wǎng)絡(luò)計(jì)劃技術(shù)的艦載機(jī)航空導(dǎo)彈轉(zhuǎn)運(yùn)流程［J］.兵工自動(dòng)化，2010，29（9）：48－51.

［3］楊炳恒，王海東，韓峰，等.艦載機(jī)調(diào)運(yùn)作業(yè)流程優(yōu)化研究［J］.科學(xué)技術(shù)與工程，2010，10（22）：5602－5605.

［4］王紅衛(wèi)，馬勇，謝勇，等.基于平滑A*算法的移動(dòng)機(jī)器人路徑規(guī)劃 ［J］.同濟(jì)大學(xué)學(xué)報(bào) （自然科學(xué)版），2010，38（11）：1647－1650，1655.

［5］劉亞杰，王航宇，謝君.狹窄環(huán)境中基于幾何法的全局路徑規(guī)劃新方法［J］.海軍工程大學(xué)學(xué)報(bào)，2010，22（4）：82－86.

［6］溫瑞，王航宇，謝君.一種移動(dòng)機(jī)器人路徑規(guī)劃方法［J］.兵工自動(dòng)化，2009，28（12）：60－63.

［7］吳海彬，林宜.基于改進(jìn)Voronoi圖的移動(dòng)機(jī)器人在線路徑規(guī)劃［J］.中國(guó)工程機(jī)械學(xué)報(bào)，2007，5（1）：117－121.

［8］ERINC G.Nonholonomic motion planning with genetic algorithms for car－like robots［D］.Bremen：International University of Bremen，2006.

［9］張洪寧，張鵬程，劉春明，等.基于動(dòng)力學(xué)模型的輪式移動(dòng)機(jī)器人運(yùn)動(dòng)控制［J］.兵工自動(dòng)化，2008，27（11）：79－82.

［10］PLAKU E，KAVRAKI L E，VARDI M Y.Discrete search leading continuous exploration for kinodynamic motion planning ［C］//Robotics：Science and Systems.Atlanta，Georgia，2007.

［11］NASH A，DANIEL K，KOENIG S，et al.Theta*：Any－angle path planning on grids［C］//Pproceedings of the National Conference on Artificial Intelligence（AAAI）.AAAI Press，2007：1177－1183.

Computer Aided Decision-Making Method for Material Transfer Planning on Ship Deck

Zhang Xiao－dong1Tong Jian2Guo Min3Huang Xiang－zhao2
1 Ship Division，Naval Armament Department of PLAN，Beijing 100071，China 2 China Ship Development and Design Center，Wuhan 430064，China 3 Huazhong University of Science and Technology，Wuhan 430074，China

Modern battlefield requests faster and faster deck material transfer on the large warship.We made use of computer-aided design technology to solve the problem of optimizing ship deck material transfer scheme，considering multi－factors that affect the result of a naval warfare.We discussed and analyzed the method about computer-aided ship deck material transfer planning，and explained the strategy in detail about how to plan transferred paths，calculate task time，sequence，resource partnership and so on.

paths planning；task sequence；resource partnership；transfer planning；decision-making support

TP242，O22

：A

：1673－3185（2011）04－104－07

2011-05-06

張曉東（1971－），男，碩士，工程師。研究方向：航空保障裝備研制。E-mail：haijun_zxd＠163.com

童 劍（1979－），男，碩士，工程師。研究方向：智能機(jī)械及自動(dòng)化。E-mail：childsword＠163.com

郭 敏（1969－），男，博士，副教授。研究方向：供應(yīng)鏈管理、證據(jù)推理理論、仿真、建模與優(yōu)化。E-mail：guomin＠m(xù)ail.hust.edu.cn

10.3969/j.issn.1673-3185.2011.04.023