# mathpractice1 **Repository Path**: karllzy/mathpractice1 ## Basic Information - **Project Name**: mathpractice1 - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-07-26 - **Last Updated**: 2021-07-27 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 数模竞赛练习1 ## 问题一的分析 ### 时间阶段分析 我们可以把这个暴露时间大致归类成这样子，就大概规划成这个样子就差不多了。 ```mermaid gantt title 两轮齐射计划安排 section 第一轮 前往装载地D1-D6 :a1, 30d 前往发射点F1-F60 :b1, after a1, 20d section 第二轮 前往装载点D1-D6 :after b1 , 12d 前往不同的发射点 : 24d ``` 我们将这些点重新编号记为： $$ \mathbf{p} = [D1, D2, \cdots, F_{63}] $$ 现在构成了距离邻接矩阵： $$ \mathbf{D}=d_{i,j} = \begin{bmatrix} d_{1,1} & d_{1,2} & \cdots & d_{1,130} \\ d_{2,1} & d_{2,2} & \cdots & d_{2,130} \\ \vdots & \vdots & \ddots & \vdots \\ d_{130,1} & d_{130,2} & \cdots & d_{130,130} \\ \end{bmatrix} $$ 矩阵中的$d_{i,j}$表示从点$p_i$到$p_j$,的距离。 此外还有一个道路类型矩阵，$\mathbf{K}, k_{i,j}\in{0, 1}$, $0$表示单车道，$1$表示双车道 然后就可以得到3个道路行驶速度矩阵, $$ T_A,T_B, T_C=\frac{d_{i, j}}{s_{\alpha d} \cdot k_{i,j} + s_{\alpha n}\cdot(1-k_{i,j})}, \alpha \in [A,B,C] $$ 车辆也进行编号$C=[A1, A2, A3,\cdots,C12]$总共是24辆车。 ### 方案矩阵的构建 通过对各类车速相除，就可以得到三类车辆的行驶时间矩阵 而一个==方案==包含了5个部分，分别是 在出发点的等待时间$T = [t_1, t2, \cdots, t_24]$ 第一波的装载点$Z_1=[z_{1,1}, z_{1,2}, \cdots, z_{1,24}]$ 第一波的发射点$F_1=[f_{1,1}, f_{1,2}, \cdots, f_{1,24}]$ 第二波装装载点$Z_2=[z_{2,1}, z_{2,2}, \cdots, z_{2,24}]$ 第二波的发射点$F_2=[f_{2,1}, f_{2,2}, \cdots, f_{2,24}]$ 构成==方案矩阵== $$ \mathbf{S}=s_{i,j} = \begin{bmatrix} T_1 \\ Z_1 \\ F_1 \\ Z_2 \\ F_2 \\ \end{bmatrix}, \qquad s_{i,j} \in \mathbf{p} $$ 假如有一辆车A1则，他的方案对应的就是$S_{:,1}=[T_1, z_{1,1}, f_{1,1}, z_{2, 1}, f_{2,1}]$ 优化目标，总的暴露时间最短 各个车的暴露时间求和，对于每辆车他的暴露时间就可以得出为 $$ t_{expose}= t_{z1}+t_{f1}+t{z2}+t_{f2} $$ 先不考虑是否存在撞车的问题，那么每当确定一个装载点$Z_{1,1}$的时候，就会确定出相应的最短路径向量$\mathbf{r}_1$,则相应的时间 $$ t_{z1}=\sum_i^{len(\mathbf{r}_1)} t_{A,r_1[i], r_1[i+1]} $$ 然后求到达发射点的时间，则又有一个最短路径向量$\mathbf{r}_{f1}$ $$ t_{f1}=\sum_i^{len(\mathbf{r}_{f1})} t_{A,r_{f1}[i], r_{f1}[i+1]} $$ 后续两个的方法类似，求和后就可以得到$t_{expose}$ 优化目标就是 $$ \min \quad t_{expose} $$ ### 时域非线性约束构建 限制条件如下， 1. 取点的限制条件，各部分是在各个整数范围内： 2. 发射点不可以被重复使用也就是$\forall f_{1,i} \not \in F_2$ 3. 道路当中不能出现会车 前面两条都属于简单的约束，比较好实现，在这里不做讨论，重点讨论第三个，单向车道不能在道路中出现会车。 所以我们给出一些进一步的定义，来便于统计车辆的数量， 首先，车子所经过的节点是固定的，那个路径肯定也都是固定的了。我们把全部的路径固定为一个路径矩阵，以及对应的时间矩阵。 $$ \mathbf{R}= \begin{bmatrix} D1 &D2 &\cdots &D2 \\ J2 &J23 &\cdots &J23 \\ \vdots &\vdots & &\vdots\\ F_{6} & J_{40} & & J_{20}\\ \vdots &\vdots & &\vdots\\ 999 & F_{42} & & 999\\ \end{bmatrix}, \qquad $$ 与之对应的就有时间矩阵, 第一行表示的是在出点的等待时间，但是第二个点表示的就是从$R_{i}$到$R_{i+1}$： $$ \mathbf{T}= \begin{bmatrix} 30 & 20 &\cdots &0 \\ 3 & 4 &\cdots &5 \\ \vdots &\vdots & &\vdots\\ 8 & 9 & & 20\\ \vdots &\vdots & &\vdots\\ 0 & 10 & & 0\\ \end{bmatrix}, \qquad $$ 那么会车只有两种情况会发生 - 两辆存在车路径中出发点和到达节点刚好相互相等，且对应的累计时间存在重合 - 两辆车存在路径中出发结合和到达节点完全相等，且累计出发时间出满足过大佬给的公式 定义一个道路承载情况矩阵，表示同时承载的车辆数量。 $$ \mathbf{L}=l_{i,j} = \begin{bmatrix} l_{1,1} & l_{1,2} & \cdots & l_{1,130} \\ l_{2,1} & l_{2,2} & \cdots & l_{2,130} \\ \vdots & \vdots & \ddots & \vdots \\ l_{130,1} & l_{130,2} & \cdots & l_{130,130} \\  \end{bmatrix} $$ 初始状态下全部为0， 针对第一种情况先检查$R_{:,1}$和$R_{:,2}$ 当存在刚好完全相反的节点对时，检查时间。 例如$r_{1,3}=r_{2,5}=D3且r_{1,4}=r_{2,4}=D2$表示两辆车分别想从D3到D2和D2到D3，此时检查累计时间 一号车辆的出发时间为$\sum_{i=0}^{3} t_{1,i}$， 到达时间为$\sum_{i=0}^{4} t_{1,i}$ 二号车辆的出发时间为$\sum_{i=0}^{4} t_{2,i}$， 到达时间为$\sum_{i=0}^{5} t_{2,i}$ 若$t_{1e}-t_{2s} \ge 0$或者$t_{2e}-t_{1s} \ge 0$则道路承载情况增加1，同理检查$c1$和$c3$以此类推，最终计算出道路最大承载情况矩阵。 针对另一种情况则是两车同时出发时，时间满足一定条件。 例如$r_{1,3}=r_{2,4}=p_3且r_{1,4}=r_{2,5}=p_2$表示两辆车都想从p3到p2，此时检查时间 一号车辆的出发时间为$\sum_{i=0}^{3} t_{1,i}$， 到达时间为$\sum_{i=0}^{4} t_{1,i}$ 二号车辆的出发时间为$\sum_{i=0}^{4} t_{2,i}$， 到达时间为$\sum_{i=0}^{5} t_{2,i}$ 若时间满足条件如下:$(t_{1s}-t_{2s}) \cdot (t_{1e}-t_{2e})<0$，道路承载情况增加1，同理检查$c1$和$c3$以此类推，最终计算出道路最大承载情况矩阵。 则，可以计算出非线性约束 $$ \mathbf{L} \le \mathbf{K} $$ 当不满足约束时，会人为进行解法修改，修改方式如下： 针对这种情况，首先确定等待时间， 当$t_{1s}t_{2s} 时\min(t_{1s}-t_{2s},t_{2e}-t_{1s})$则，第一个较小，$c_2$等待，否则$c_1$等待 获得道路承载情况矩阵. 针对这一情况，需要修改相应的车辆行驶时间矩阵，让后出发的车辆在出发节点内进行等待， 等待的时长$t_{wait}=\max(t_{1e}-t_{2s}, t_{2e}-t_{1s})$ 若多次修改仍然无法满足K的需求,则认为该方案无效 ## 使用遗传算法进行求解 ```mermaid graph TB st(开始)-->op[初始化种群,120个点x种群数量] op-->op2[评估这些方案S] op2-->EVA{s是否评估结束}--NO-->fa fa(获取120个所要去的目标S)-->R[运用DJ算法获得R] R-->T[通过路径获知时间T] T-->L[负载检查] L-->co{比较L<=K} co--No-->W[添加W部分]-->T co--Yes-->t(计算R的总时间)-->op2 EVA--yes-->select[选取合适的方案个体] select-->diedai{迭代是否结束} diedai--yes-->over(over) diedai--no-->zajiao[杂交]-->op2 ```