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

張曉東 童 劍 郭 敏 黃祥釗

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

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

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

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

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

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

1 引言

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

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

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

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

2.1 物體外形的表示方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 物資轉(zhuǎn)運時間計算

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

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

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

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

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

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

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

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

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

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

主要分為以下兩種情況：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

轉(zhuǎn)運車配班設計的基本思路是：

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

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

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

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

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

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

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

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

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

下面針對具體情況進行舉例分析說明：

假設：

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

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

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

3）轉(zhuǎn)運車共有A、B、C、D 4臺，A、B車負責上層甲板的物資轉(zhuǎn)運，C、D車負責下層甲板倉庫的物資轉(zhuǎn)運，兩層甲板間車輛不跨層使用；

4）轉(zhuǎn)運車從上層甲板上任意位置Fn（n＝1，2，3，4）到前升降平臺的時間設為QTn（n＝1，2，3，4），到后升降平臺的時間為HTn（n＝1，2，3，4），從前升降平臺到后升降平臺的時間為QH；轉(zhuǎn)運車輛從下層甲板倉庫中任意位置Jn（n＝1，2，3，4）到前升降平臺的時間為qtn（n＝1，2，3，4），到后升降平臺的時間為htn（n＝1，2，3，4），從前升降平臺到后升降平臺的時間為qh；

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

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

則上述轉(zhuǎn)運車配班設計思路的具體實現(xiàn)如下：

1）上層甲板為物資1配置轉(zhuǎn)運車A，下層甲板倉庫為物資1配置轉(zhuǎn)運車C；

2）由于2M0＜1M1、2M2＜1M3，說明物資2在上層甲板此時無法配置轉(zhuǎn)運車A，下層甲板倉庫此時也無法配置轉(zhuǎn)運車C；

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

4）接著以物資3作為基準，對物資4的轉(zhuǎn)運車配班進行分析。由于4M0＜3M1、4M2＜3M3，說明物資4在上層甲板。此時無法配置轉(zhuǎn)運車A，下層甲板倉庫此時也無法配置轉(zhuǎn)運車C；

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

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

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

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

6 結(jié)論

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

通過對艦船物資轉(zhuǎn)運方案的計算機輔助決策算法思路的研究，基本理清了針對該問題的算法研究思路，但還存在以下幾點問題需要進一步開展研究：

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

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

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

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

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

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

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

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

［7］吳海彬，林宜.基于改進Voronoi圖的移動機器人在線路徑規(guī)劃［J］.中國工程機械學報，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］張洪寧，張鵬程，劉春明，等.基于動力學模型的輪式移動機器人運動控制［J］.兵工自動化，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－），男，碩士，工程師。研究方向：智能機械及自動化。E-mail：childsword＠163.com

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

10.3969/j.issn.1673-3185.2011.04.023