基于回溯算法的海上兵力投送船舶選擇優化研究

王建鵬

摘 要：隨著我國經濟水平的提高以及國家軍事戰略體系的逐漸構成，部隊海上投送船舶選擇優化問題已經成為新時期我國軍事準備所面臨的一項重大現實問題。本文建立了部隊海上投送船舶選擇模型，并利用回溯算法對模型進行求解、驗證，在保證所用船舶完成任務的總時間最小的同時，力求使用船舶運力最少。

關鍵詞：海上投送;船舶選擇;回溯算法

1大規模作戰部隊海上投送船舶選擇問題描述

大規模作戰部隊海上投送船舶選擇問題可以描述為：作戰需將大量的人員和裝備進行海上投送，現有可用船舶（如海軍登陸艦、登陸艇、陸空軍船艇登陸艇、民用雜貨船、散貨船、滾裝船、多用途船、集裝箱船）等各類型船各若干艘，從這些可用船中進行選擇，合理搭配一組船舶組合，目標函數是使投送時間都盡可能短，同時使占用船舶運力（船舶運輸裝備的能力和運輸人員的能力）盡可能小，所選船舶組合需要同時滿足待運部隊所需總配載面積、裝備配載面積、人員乘載面積等要求。

2大規模作戰部隊海上投送船舶選擇模型

2.1船舶運力約束處理

船舶運力包括船舶運輸物資裝備的能力和運輸人員的能力，本文將船舶運輸裝備的能力和運輸人員的能力統一用面積y表示，即

式中：Kz為該型船的客位數;為單人所需的配載面積;有效為該型船的有效配載面積，船舶有效面積既可配載裝備，也可配載人員。

2.2目標函數處理

選船問題實際考慮的優化目標主要有2個：一個是船舶的運力最小;另一個是所有船舶完成任務的時間之和最小。這2個目標間是存在矛盾的，很難找到共同的最優解，需要采用多目標規劃的方法求解折中非劣解。

目標函數一：船舶的運力總和y最小，數學表達式為

式中：為船型i的運力;為問題的決策變量，表示船型i被選擇的船的數量。

目標函數二：所有被選船舶完成任務的總時間z最短，數學表達式為

式中：為該船型的平均裝卸載時間，指在理想碼頭條件下和工人平均操作熟練程度下，裝載部隊各型裝備所需的平均時間。

由于上述2個優化目標的單位不統一，不能直接轉化為單一的目標函數，因此，本文采取功效系數方法解決多目標規劃問題。將2個目標函數通過線性加權法進行歸一化處理，得到新的目標函數YZ，其結果為

式中：a為目標函數Y的權重系數;b為目標函數Z的權重系數，且a+b=1。可以針對不同類型的任務通過咨詢專家賦予a，b不同的比值，從而達到根據任務的輕重緩急合理搭配船型比例，統籌安排運力資源的目的。

2.3模型的建立

根據以上分析，本文對大規模作戰部隊海上投送船舶選擇問題建立如下模型：

式中：X=（X1，X2，...，Xn）為決策向量集合;為船舶運力集合;為船舶載質量集合;為可選船舶可裝載質量裝備面積的集合;為決策向量，≥0，∈Z，i=0，1，…，n，為非負整數，例如： =3為i型船舶有3艘被選中;n為船型的型號數量;m為裝備的型號數量;z為重裝備的型號數量;為j型裝備數量;為j型重裝備數量;為j型裝備的限制面積;為j型裝備的配載系數。

3 基于回溯算法的模型求解

3.1算法思想

有一類叫做“組合總和”的問題可以用回溯算法就行求解，問題描述為：給定一個無重復元素的數組“candidates”和一個目標數 “target”，找出“candidates” 中所有可以使數字和為 “target” 的組合。“candidates”中的數字可以無限制重復被選取。此處以candidates = [2，3，6，7]，target = 7為例進行說明。候選數組里有 2，如果找到了 7 - 2 = 5 的所有組合，再在之前加上 2，就是 7 的所有組合;同理考慮 3，如果找到了 7 - 3 = 4 的所有組合，再在之前加上 3，就是 7 的所有組合，依次這樣找下去。以 target = 7 為根結點，每一個分支做減法，減到 0 或者負數的時候，就到了葉子結點;在結果為 0 的子葉節點進行“結算”，即從結果為0的子葉節點到根節點的路徑作為一個組合添加到結果集，此結果集就是題目所求組合。對結果進行觀察不難發現，其中有[2，2，3]，[3，2，2]，[2，32]之類的結果，可以求解完畢以后用去重復的方法予以剔除，或在計算過程中以“減枝”的方法去除，節約計算時間。

3.2求解步驟

結合前文所建立的模型，對3.1中的算法做進行修改，修改后計算步驟如下：

①將模型中的的總運力需求設為target;

②進行遞歸計算;

③當target小于或等于0時停止計算;

④將子葉節點到根節點的路徑作為一個組合添加到結果集;

⑤計算全部結果集中各組合的目標函數值;

⑥目標函數值最大組合的即為最優方案組合。

4算例分析

某演習中，第1梯隊在艦隊和作戰機群強大火力掩護下，向敵海岸防御前沿發起了猛烈的攻擊。根據作戰計劃，擔負任務的某部作為第2梯隊，必須在第1梯隊占領敵陣地，奪取敵沿岸港口后，實施后續登陸，現該部隊已整裝待命。現命令某軍區聯合作戰指揮部迅速、合理選調船舶，在最短時間內完成該集團軍的裝載任務。模型中走道系數（0≤≤1）取0.2，統一取0.875 ，當運輸任務為“緊急”時，令模型中目標函數控制參數a=0.1，b=0.9，將實驗結果代人模型中可驗證該結果滿足模型約束，說明實驗結果的正確性。

參考文獻

[1] 苑德春，潘藩，葛同民，羅雷.大規模作戰部隊海上投送船舶選擇優化研究[J].軍事交通學院學報，2013，15（1）.

[2] 姚恩瑜，何勇，陳仕平.數學規劃與組合優化[M].杭州：浙江大學出版社，2001：22-25.