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

王建鵬

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

關(guān)鍵詞：海上投送;船舶選擇;回溯算法

1大規(guī)模作戰(zhàn)部隊海上投送船舶選擇問題描述

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

2大規(guī)模作戰(zhàn)部隊海上投送船舶選擇模型

2.1船舶運力約束處理

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

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

2.2目標(biāo)函數(shù)處理

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

目標(biāo)函數(shù)一：船舶的運力總和y最小，數(shù)學(xué)表達式為

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

目標(biāo)函數(shù)二：所有被選船舶完成任務(wù)的總時間z最短，數(shù)學(xué)表達式為

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

由于上述2個優(yōu)化目標(biāo)的單位不統(tǒng)一，不能直接轉(zhuǎn)化為單一的目標(biāo)函數(shù)，因此，本文采取功效系數(shù)方法解決多目標(biāo)規(guī)劃問題。將2個目標(biāo)函數(shù)通過線性加權(quán)法進行歸一化處理，得到新的目標(biāo)函數(shù)YZ，其結(jié)果為

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

2.3模型的建立

根據(jù)以上分析，本文對大規(guī)模作戰(zhàn)部隊海上投送船舶選擇問題建立如下模型：

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

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

3.1算法思想

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

3.2求解步驟

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

①將模型中的的總運力需求設(shè)為target;

②進行遞歸計算;

③當(dāng)target小于或等于0時停止計算;

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

⑤計算全部結(jié)果集中各組合的目標(biāo)函數(shù)值;

⑥目標(biāo)函數(shù)值最大組合的即為最優(yōu)方案組合。

4算例分析

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

參考文獻

[1] 苑德春，潘藩，葛同民，羅雷.大規(guī)模作戰(zhàn)部隊海上投送船舶選擇優(yōu)化研究[J].軍事交通學(xué)院學(xué)報，2013，15（1）.

[2] 姚恩瑜，何勇，陳仕平.數(shù)學(xué)規(guī)劃與組合優(yōu)化[M].杭州：浙江大學(xué)出版社，2001：22-25.