多波次导弹发射中的规划问题(二) 问题一解答

爱被打了一巴掌 2023-08-17 16:12 109阅读 0赞

## 前言 ##

在 [多波次导弹发射中的规划问题(一) 网络图绘制及数据整理][Link 1] 中，我们初步整理出了作战区域网络图，以及各种车型在网络中行车的耗时矩阵。接下来我们来研究问题一的解题步骤，这是其他几问的基础，一旦确定了问题一的解题思路和模型，其他几问可以在此基础上进行修改调整即可轻松搞定。

## 问题分析 ##

### 明确作战任务的网络图 ###

本次多波次导弹发射的作战任务建立在网络图上，网络图相当于地图，是一切作战任务安排的基本依据。在 [多波次导弹发射中的规划问题(一) 网络图绘制及数据整理][Link 1] 中，初步整理工作已经完成。在这里还是要明确网络图的一些信息：

[![作战区域道路点位编号网络图][005Iu54rgy1g6mml3rxm6j34la2dle3x.jpg]][005Iu54rgy1g6mml3rxm6j34la2dle3x.jpg]

网络图中一共有130个点，其中

*  待机区域为 D1 ~D2 （序号为 1 ~ 2 ）
 *  转载区域为 Z01 ~ Z06 （序号为 3 ~ 8 ）
 *  发射区域为 F01 ~ F60 （序号为 9 ~ 68 ）
 *  道路节点为 J01 ~ J62 （序号为 69 ~ 130 ）
    
     *  J01 ~ J11 为主干道 1 （序号为 69 ~ 79 ）
     *  J12 ~ J20 为主干道 2 （序号为 80 ~ 88 ）
     *  J21 ~ J62 为其他道路 （序号为 89 ~ 130 ）

### 明确作战任务的发射车属性 ###

在本题目的多波次导弹发射任务中，执行任务的一共有三种车型，记为 `A型车` `B型车` `C型车` 。这些车按照车型和行车道路，其行车速度会有不同：

发射车基本信息

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数量</th> 
   <th>主干道车速(km/h)</th> 
   <th>其他道路车速(km/h)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>A型车</td> 
   <td>6</td> 
   <td>70</td> 
   <td>45</td> 
  </tr> 
  <tr> 
   <td>B型车</td> 
   <td>6</td> 
   <td>60</td> 
   <td>35</td> 
  </tr> 
  <tr> 
   <td>C型车</td> 
   <td>12</td> 
   <td>50</td> 
   <td>30</td> 
  </tr> 
 </tbody> 
</table>

### 明确作战任务的机动策略 ###

根据题目相关内容描述，可以整理出多波次导弹发射作战任务的机动策略：

**待机区域隐蔽待机** → 带弹行车至某一个发射点位 (点位不可以重复使用) → 等待最后一辆车就位 → **第一波齐射** → 行车至转载区域 → **安排装载导弹** (点位不够，会出现等待) → 行车至某一发射点位(点位不可以重复使用) → 等待最后一辆车就位 → **第二波齐射**

以上机动策略可以简单的 记作 “ **D-F-Z-F** ” ，也就是在待机区域、发射区域、转载区域之间的行走。

### 明确作战任务的暴露时长计算 ###

题目中的暴露时长指的是，所有车辆从待机区域出发到完成第二波齐射任务为止所耗费的时间的总和。其中

*  在待机区域，因为是隐蔽待机，所以不存在暴露时长。
 *  在发射区域，因为要等待所有车就位才能齐射，所以在该区域内的等待时间也要算入暴露时长。
 *  在转载区域，因为转载区域是单台装弹作业方式，并且区域只可以容纳两台发射车，因此当出现3台及以上时，会出现暴露在区域外的情况，此时需要计算暴露时长。
 *  在所有道路，行走耗费时间均要算入暴露时长。

### 明确行车冲突的产生 ###

由于在网络地图上行车时，可能会出现行车冲突的情况，也就是撞车。那么这里我们首先得定义 什么叫做行车冲突？行车冲突可以理解为，在某个时间，某个道路上，行驶的车辆在时间和空间上的冲突。

行车冲突按照主干道和非主干道来区分：

*  对于主干道来说，题目规定其行车方式为双通道通行，这意味着**可以在主干道同时行驶两台发射车，无论行车方向是否一致，都不存在撞车的可能。**
 *  对于非主干道来说，题目规定其行车方式为单通道通行，可以在节点处会车，即可以在节点处反向行驶，交错通过节点；但是在节点与节点之间时
    
     *  可能会出现同向行驶，速度快的车从后面与前面速度慢的车撞车（**即追尾**）
     *  可能会出现反向行驶，两台车直接头碰头撞车（**即对撞**）

因此，在确定行车路线后，应该及时验证是否存在上述撞车情况，若出现撞车则需要另行考虑。

## D - F 阶段作战任务的分析与解答 ##

### 作战任务分析 ###

首先，24 台发射车在均匀分布在待机区域携带导弹隐蔽待机。即在 D1 和 D2 区域，分别安排 A型车 各 3 台，B型车 各 3 台，C型车 各 6 台。接到作战任务后，两个区域的发射车开始行动，陆续离开待机区域，去寻找最近的发射点，到达发射点后 ，就位待命。当指挥部(这是我假想的)收到最后一台发射车已经到达发射点的消息时，发出命令，执行第一波齐射任务，所有发射车立即发射导弹。这就是第一波齐射。

### 暴露时间计算 ###

分析前面的暴露时长计算可以知道，必然存在一种可能，就是行车速度快的发射车在到达指定发射点后，会原地待命，等待其他的慢车到达发射点，这期间存在暴露时长。

[![image][]][image]

发射车在不同机动策略下的暴露时长对比

如上左图所示，要想缩短暴露时间，那么最后齐射时间必须要短，也就是最后一台发射车到达的时间要短。但是，如果所有车同时出发，虽然不可能出现撞车(跑的快的在前面，跑得慢的在后面)，而快车先到要等待慢车，存在发射区域的暴露时长。此时的总暴露时长等于最后一台发射车到达的时间乘以 24 。

如上右图所示，转变下思维，仍然是同样的车，最后一辆车到达的时间也短。在此基础上，让快车先在待机区域等待，然后陆续派出，这样暴露时间就被归在了待机区域，但是不计入暴露时长。此时的总暴露时长等于所有车的行车耗时之和。这种情况下的暴露时长必然最短。于是问题转变成求所有车到达发射点所耗费时长之和最短的问题。

### 行车冲突检验 ###

对于计算得到的结果，必须验证其是否存在行车冲突问题。根据分析中的行车冲突定义，我们可以这样来判断是否存在冲突撞车的情况：

首先，找到任意两条行车路线，选取两条线路中各自任意相邻的两个点位，以及对应的时间。即出发点，到达点，出发时间，到达时间，这四个判断依据进行比较。

*  如果点位在主干道上，则不存在撞车
 *  如果点位不在主干道上
    
     *  若点位存在同向关系（出发点相同并且到达点也相同），并且存在先出发（出发时间小）后到达（达到时间大）或者后出发（出发时间大）先到达（到达时间小）的情况，则定义为追尾撞车。
     *  点位存在反向关系（出发点与到达点刚好相反），并且存在时间重叠交叉的情况（其中一个的出发时间小于另一个的到达时间，或者其中一个的到达时间大于另一个的出发时间），则定义为对撞撞车。
     *  其他情况，一律不存在撞车

### 适用模型分析 ###

根据上述分析，D - F 阶段的作战任务可以归为 `任务指派问题` 。即把 60 个发射点当作被指派的人，把 24 台发射车当作被指派的任务，某台发射车从待机区域行走到发射区域的最短行车耗时当作某人完成某项任务所需要的时长。目标函数就是使得24台发射车到达发射点所需的时间之和最短(即完成任务所需时间最短)。其中

*  24台发射车需要按照待机区域和车型来计算到达60个发射点所需的时长（见下图）。
 *  发射车从待机区域到发射点的行车耗时需要计算，这个已经在 [多波次导弹发射中的规划问题(一) 网络图绘制及数据整理][Link 1] 中得到了。
 *  最短行车耗时属于图论中的最短路径问题，一般可以采取 `Floyd方法` 或者 `dijkstra方法` 进行求解。

[![image][image 1]][image 1]

发射车-发射点矩阵

### 模型建立 ###

一般来说，求解任务指派问题，常用 0 - 1 整数规划模型来求解。在本题目中可以按照如下方法求解：

*  **Step1**: 输入各种车型的行车耗时矩阵数据，给定起点为 D1 和 D2 ,终点为 60 个发射点 F1 ~ F60，利用图论最短路径模型(Floyd 或者 Dijkstra)分别求出这两个点到 60 个点(按顺序计算)的耗时数组。将产生 6 个 长度为 60 的耗时数组。
 *  **Step2**：将上述耗时数组，按照车型数量和出发点重组为 0 - 1 整数规划用的耗时表，如上图所示，将会得到一个 24\*60 的耗时表。
 *  **step3**：建立 0 - 1 整数规划模型。
 *  **Step4**：计算结果整理。
 *  **Step5**：行车冲突检验。

其中 0 - 1 整数规划模型如下：  
记 $ c\_\{ij\} $ 表示第 \$i\$ 台车行走到第 \$j\$ 个发射点所耗费的时长。引进 0 - 1 变量：  
\\\[ x\_\{ij\}=\\begin\{cases\} 1& \\text\{第\}i\\text\{台车行走到第\}j\\text\{个发射点进行发射\}\\\\ 0& \\text\{第\}i\\text\{台车行不行走到第\}j\\text\{个发射点进行发射\}\\\\ \\end\{cases\} \\\]

建立如下 0 - 1 整数规划模型：

\\\[ \\min \\sum\_\{i=1\}^\{24\}\{\\sum\_\{j=1\}^\{60\}\{c\_\{ij\}x\_\{ij\}\}\} \\\]

\\\[ s.t.\\begin\{cases\} \\sum\_\{i=1\}^\{24\}\{x\_\{ij\}\\le 1\}& j=1,2,\\cdots ,60\\\\ \\sum\_\{j=1\}^\{60\}\{x\_\{ij\}=1\}& i=1,2,\\cdots ,24\\\\ x\_\{ij\}=0\\text\{或\}1& i=1,2,\\cdots ,24;j=1,2,\\cdots ,60\\\\ \\end\{cases\} \\\]

### 模型代码 ###

*  主程序代码

%% 准备存储空间
    clc, clear, close all
    
    %% 导入整理的数据
    time_cost_A = xlsread('data','A型车耗时矩阵'); % 导入耗时矩阵
    time_cost_B = xlsread('data','B型车耗时矩阵');
    time_cost_C = xlsread('data','C型车耗时矩阵');
    
    %% 点位序号编组
    D = (1:2); % 待机区域点位
    Z = (1:6) + 2; % 转载区域点位
    F = (1:60) + 2 + 6; % 发射区域点位
    J1 = (1:11) + 2 + 6 +60; % 主干道1点位
    J2 = (12:20) + 2 + 6 +60; % 主干道2点位
    J3 = (21:62) + 2 + 6 + 60; % 普通道路点位
    
    %% 车型编号
    A1 = (1:3);     A2 = (4:6);   % A型车
    B1 = (7:9);     B2 = (10:12); % B型车
    C1 = (13:18);   C2 = (19:24); % C型车
    
    %% 所有车 从 D 开往 F 的所有情况
    A_D_F = calRoute(time_cost_A,D,F,{'A'});
    B_D_F = calRoute(time_cost_B,D,F,{'B'});
    C_D_F = calRoute(time_cost_C,D,F,{'C'});
    
    %% 整合出24辆车分别到60个发射点的耗时矩阵
    DF(A1,:) = repmat(([A_D_F{1,1}.cost]),length(A1),1);
    DF(A2,:) = repmat(([A_D_F{2,1}.cost]),length(A2),1);
    DF(B1,:) = repmat(([B_D_F{1,1}.cost]),length(B1),1);
    DF(B2,:) = repmat(([B_D_F{2,1}.cost]),length(B2),1);
    DF(C1,:) = repmat(([C_D_F{1,1}.cost]),length(C1),1);
    DF(C2,:) = repmat(([C_D_F{2,1}.cost]),length(C2),1);
    
    %% 0 - 1 整数规划模型
    [DF_go,DF_time]= myintlinprog(DF);
    
    %% 整理计算结果
    DF_result = struct('car',{},'start',{},'end',{},'cost',{},'path',{},'time',{});
    for i = A1
        DF_result(i) = A_D_F{1,1}(DF_go(i,:)~=0);
        DF_result(i).car = sprintf('A0%d',i);
    end
    for i = A2
        DF_result(i) = A_D_F{2,1}(DF_go(i,:)~=0);
        DF_result(i).car = sprintf('A0%d',i);
    end
    for i = B1
        DF_result(i) = B_D_F{1,1}(DF_go(i,:)~=0);
        DF_result(i).car = sprintf('B0%d',i-6);
    end
    for i = B2
        DF_result(i) = B_D_F{2,1}(DF_go(i,:)~=0);
        DF_result(i).car = sprintf('B0%d',i-6);
    end
    for i = C1
        DF_result(i) = C_D_F{1,1}(DF_go(i,:)~=0);
        if i-12<10
        DF_result(i).car = sprintf('C0%d',i-12);
        else
        DF_result(i).car = sprintf('C%d',i-12);
        end
    end
    for i = C2
        DF_result(i) = C_D_F{2,1}(DF_go(i,:)~=0);
        if i-12<10
        DF_result(i).car = sprintf('C0%d',i-12);
        else
        DF_result(i).car = sprintf('C%d',i-12);
        end
    end
    %% 计算第一波发射时间
    launch1_time = max([DF_result.cost]);
    %% 重新调整发车时间
    delta_time = launch1_time - [DF_result.cost];
    for i = 1:24
        DF_result(i).time = DF_result(i).time + delta_time(i);
    end
    fprintf('第一波齐射时间为第%.2f小时,总暴露时间为%.2f小时\n',launch1_time,DF_time);
    
    %% 检测是否冲突
    isCrack(DF_result)
    %% 冲突线路调整
    move_time = DF_result(2).time(1) - DF_result(17).time(1);
    DF_result(2).time =  DF_result(2).time - move_time;
    fprintf('第一波齐射时间为第%.2f小时,总暴露时间为%.2f小时\n',launch1_time,DF_time + move_time);
    %% 再次检查是否冲突
    isCrack(DF_result)
    %% 结果输出保存
    [DF_result.leave] = deal(launch1_time);
    [DF_result.exposed] = deal(DF_result.cost);
    DF_result(2).exposed = DF_result(2).exposed + move_time;

*  计算某一车型的最短路径和耗时的子程序

function RA = calRoute(time_cost,Start,End,car)
    % 给定起点和终点，计算最优路径和耗时
    % time_cost     input 网络耗时矩阵（根据车型计算得出）
    % Stat          input 起点
    % End           input 终点
    % car           input 当前车型
    % RA            output 保存计算结果：车型、起止点、耗时、路径、节点时间的结构体
    m = length(Start); % 起点个数
    n = length(End); % 终点个数
    % 记录一对起点到终点的最优路径情况
    R_A = struct('car',{},'start',{},'end',{},'cost',{},'path',{},'time',{});
    % 记录总的最优路径
    RA = cell(m,1);
    for i = 1:m
        for j = 1:n
            R_A(j).car = car; % 记录当前车型
            R_A(j).start = Start(i); % 记录车辆出发点
            R_A(j).end = End(j); % 记录车辆终到点
            % 从出发点到终到点之间最短路径的计算
            [R_A(j).cost ,R_A(j).path] = mydijkstra(time_cost,Start(i),End(j)); 
            % 求到达各个节点的时间
            time = 0;
            R_A(j).time(1) = time;
            path = [R_A(j).path];
            for k = 1:length(path)-1
                time_temp = time_cost(R_A(j).path(k),R_A(j).path(k+1));
                time = time + time_temp;
                R_A(j).time(k+1) = time ;
            end
        end
        % 将一对起止点最短路径存到元胞中
        RA{i,1} = R_A;
        % 清除临时存储的结构体
        clear R_A
    end
    end

*  最短路径选择子程序

function [mydistance,mypath]=mydijkstra(a,sb,db)
    %寻找i,j两点最短路径
    % 输入：a—邻接矩阵，a（i，j)是指i到j之间的距离，可以是有向的
    % sb—起点的标号, db—终点的标号
    % 输出：mydistance—最短路的距离, mypath—最短路的路径
    n=size(a,1); visited(1:n) = 0;
    distance(1:n) = inf; distance(sb) = 0; %起点到各顶点距离的初始化
    visited(sb)=1; u=sb;  %u为最新的P标号顶点
    parent(1:n) = 0; %前驱顶点的初始化
    for i = 1: n-1
        id=find(visited==0); %查找未标号的顶点
        for v = id
            if  a(u, v) + distance(u) < distance(v)
                distance(v) = distance(u) + a(u, v);  %修改标号值
                parent(v) = u;
            end
        end
        temp=distance;
        temp(visited==1)=inf;  %已标号点的距离换成无穷
        [t, u] = min(temp);  %找标号值最小的顶点
        visited(u) = 1;       %标记已经标号的顶点
    end
    mypath = [];
    if parent(db) ~= 0   %如果存在路!
        t = db; mypath = [db];
        while t ~= sb
            p = parent(t);
            mypath = [p mypath];
            t = p;
        end
    end
    mydistance = distance(db);
    end

*  0 - 1 整数规划模型子程序

function [DF_go,DF_time] = myintlinprog(DF)
    c = DF;
    [m,n] = size(c);% m个任务，n个委派人员
    c = c(:);
    a = zeros(n,n*m);
    
    for j = 1:n
        a(j,((j-1)*m+1:j*m)) = 1;
    end
    
    b = ones(n,1);
    Aeq = zeros(m,m*n);
    
    for i = 1:m
        Aeq(i,(i:m:m*n)) = 1;
    end
    
    Beq = ones(m,1);
    intcon = 1:m*n;
    lb = zeros(m*n,1); ub = ones(m*n,1);
    [x,y] = intlinprog(c,intcon,a,b,Aeq,Beq,lb,ub);
    DF_go = reshape(x,[m,n]);
    DF_time = y;
    end

*  检测是否冲突的子程序

function isCrack(DF_result)
     flag = 0;
    J1 = (1:11) + 2 + 6 +60; % 主干道1点位
    J2 = (12:20) + 2 + 6 +60; % 主干道2点位
    n1 = 1:length(DF_result);
    for i = n1
        for j = n1(n1~=i)
            path1 = [DF_result(i).path]; time1 = [DF_result(i).time];
            path2 = [DF_result(j).path]; time2 = [DF_result(j).time];
            n1 = 1:length(path1)-1;
            n2 = 1:length(path2)-1;
            for k = n1
                for r =  n2
                    s1 = path1(k); e1 = path1(k+1);
                    st1 = time1(k); et1 = time1(k+1);
                    s2 = path2(r); e2 = path2(r+1);
                    st2 = time2(r); et2 = time2(r+1);
                    % 主干道不存在撞车
                    if (ismember(s1,J1) || ismember(s1,J2)) && (ismember(e1,J1) || ismember(e1,J2)) && ...
                            (ismember(s2,J1) || ismember(s2,J2)) && (ismember(e2,J1) || ismember(e2,J2))
                        flag = 0;
                    % 非主干道同向追尾撞车
                    elseif s1 == s2 && e1 == e2 && ((st1 < st2 && et1 > et2) ||(st1 > st2 && et1 < et2))
                        flag = 1; fprintf('%s与%s在%d-%d与%d-%d存在同向撞车，请做出调整！\n',DF_result(i).car,DF_result(j).car,s1,e1,s2,e2);
                    % 非主干道反向对撞撞车
                    elseif s1 == e2 && s2 == e1 && ((st1 < et2)||(st2 < et1))
                        flag = 1; fprintf('%s与%s在%d-%d与%d-%d存在反向撞车，请做出调整！\n',DF_result(i).car,DF_result(j).car,s1,e1,s2,e2);
                    else
                        flag = 0;
                    end
                end
            end
        end
    end
    end

### 模型结果 ###

[![image][image 2]][image 2]

其中经历了一次调整，为了避免撞车，将撞车的 A02 往前调整，即提前发车，但带来了暴露时间，因此又要重新计算最终结果为：  
第一波齐射时间为第3.33小时,总暴露时间为51.76小时。  
  
  
车辆指派安排表：

[![image][image 3]][image 3]

转载于:https://www.cnblogs.com/gshang/p/11458447.html

[Link 1]: https://www.cnblogs.com/gshang/p/11455691.html
[005Iu54rgy1g6mml3rxm6j34la2dle3x.jpg]: https://ws4.sinaimg.cn/large/005Iu54rgy1g6mml3rxm6j34la2dle3x.jpg
[image]: https://ws1.sinaimg.cn/large/005Iu54rgy1g6ncfp1uzdj31670dtwfv.jpg
[image 1]: /images/20230810/195f1f260b9145f582cbbec1fb9c7674.png
[image 2]: https://ws2.sinaimg.cn/large/005Iu54rgy1g6ote0r082j30z606w74o.jpg
[image 3]: /images/20230810/a8f01b330a844061baaf801c260d8a4f.png