2024年五一数学建模B题思路及实现(省一)

题目

  随着城市化的持续发展，交通规划在新兴城市建设中显得尤为关键。在未来新城规划中，自动驾驶技术预期将成为交通出行的主导模式，彻底改变出行方式和城市规划的基础理念。自动驾驶车辆，得益于先进的传感器、智能算法和通信技术，能够自动遵循预设路线，无需人为操作。将自动驾驶技术整合到一个特定未来新城的交通需求规划中，以期实现更高效、更可持续的城市交通网络。
  交通需求指从特定起点出发，到达指定终点的交通量(车辆数)。以图1中的交通网络1为例，假设(起点,终点)对(1,4)的交通需求为100辆，其中40辆分配到路径1-2-4，60辆车分配到路径1-3-4，该过程称为交通需求分配。在道路完全通畅的情况下，从起点1到达终点4的交通量比例(以下称为“可达率”)为(40+60)/100=100%。而一旦产生突发状况，例如路段1-2发生了交通事故导致该路段无法通行，那么原本选择通过1-2-4路径的交通需求将无法满足。此时，只有通过路径1-3-4的交通需求才能够被实现，交通需求可达率为60/100=60%。

图1 交通网络1

  假设每个(起点,终点)对之间使用的路径数不超过5(各路段长度均为单位1，优先选择距离短的路径)。假设交通网络中所有车辆均为无人驾驶车辆，并且所有车辆都服从系统预先规划的路径进行出行。注意：本题的图2和图3中的路段为双向路段，即路段2-3和路段3-2是两条不同的路段。在本题中，不要求交通流量值取整数，即交通流量值可以为任意的非负实数。请依据附件1~3，建立数学模型，完成以下问题：
问题1： 图2为一个小型交通网络。各(起点,终点)对之间的交通需求见附件1。请建立数学模型，给出各(起点,终点)对之间交通需求分配到对应路径上的交通量，使得网络中任意1条路段出现突发状况时(每个路段出现突发状况概率相同)，网络中所有交通需求的期望可达率最大。在表1中填入指定(起点,终点)对规划的路径，以及对应分配的交通量(若规划路径数不足5条无需填满表格)。

图2 交通网络图2 表1 问题1结果

问题2： 在图3所示的交通网络中，各(起点,终点)对之间的交通需求见附件2。请建立数学模型，给出各(起点,终点)对之间交通需求分配到对应路径上的交通量，使得网络中任意5条路段出现突发状况时(每个路段出现突发状况概率相同)，网络中所有交通需求的期望可达率最大。在表2中填入指定(起点,终点)对规划的路径，以及对应分配的交通量(若规划路径数不足5条无需填满表格)。

图3 交通网络3 表2 问题2结果

问题3： 在交通网络3中，各(起点,终点)对之间的交通需求见附件2，各路段的容量上限见附件3。请建立数学模型，给出各(起点,终点)对之间交通需求分配到对应路径上的交通量，使得网络中任意5条路段出现突发状况时(每个路段出现突发状况概率相同)，网络中所有交通需求的期望可达率最大，且交通需求分配到对应的路径后，各路段上的交通量不能超过路段容量(路段交通量计算方法：路段交通量=经过该路段的路径交通量之和。例如，路径1-0-6与路径1-0-3均经过路段1-0，则路段1-0交通量=路径1-0-6交通量+路径1-0-3交通量)。在表3中填入指定(起点,终点)对规划的路径，以及对应分配的交通量(若规划路径数不足5条无需填满表格)。

表3 问题3结果

问题4： 现计划在交通网络3中新修建6条路段(单向直线路段且长度为单位1，例如节点31至节点32)，新建路段起点和终点必须是交通网络中的任意两个节点，并且假设新建路段的容量足够大。新建路段不能跨越其他路段(例如，不能在节点21与节点39之间修建路段)，只能在网络内部修建(例如，不能在节点4与节点34之间修建路段)。请建立数学模型，给出新修建路段方案，使得在新网络中任意5条路段出现突发事故时(包括新建路段，每个路段出现突发状况概率相同)，网络中所有交通需求的期望可达率尽可能最大，且交通需求分配到对应的路径后，各路段上的交通量不能超过路段容量(新建路段容量足够大，不用考虑这个因素)。在表4中填入期望可达率最大的5种方案及其可达率。

表4 问题4结果

---

关键词 ：蒙特卡洛法   目标规划模型  Yen算法  CVRP目标规划模型

摘 要：

  本文针对交通路径规划问题进行研究，运用了蒙特卡洛法、Dijkstra算法、Yen算法、联合学习策略等方法进行分析，建立了目标规划模型、CVRP规划模型，旨在得出得出面对特殊情况都具有较高通达率的规划路径。
  针对问题一，本文基于Dijkstra算法求解出两站点间的最短路径，引入变量p评判各规划路径的正常与否，结合附件得出约束条件，建立目标规划模型：$$maxW=\frac{p_1{q}_a+p_2{q}_b+p_3{q}_c+p_4{q}_d+p_5{q}_e+p_6{q}_f}{180}$$  式中，$q_i$表示第$i$条规划路径的分配交通量。求解时采用蒙特卡洛法随机生成各规划路径上的分配交通量，通过多次重复实验得出最后结果（见表5-3）。
  针对问题二，本文采用$Yen$算法对最短路径的求解进行改进，同时得出多条规划路径。在确立所有规划路径后仍然采用蒙特卡洛法，重复进行10000次实验，得出各规划路径上的理论分配交通量（见表5-6）。
  针对问题三，本文采用联合学习策略，将每条路段容量上限、流量动平衡、规划路径和行驶全长作为变量，将最终通达率为目标函数，建立$CVRP$目标规划模型：$$min\sum _{i,j\in A}{c}_{ij}{x}_{ij}$$  通过Matlab求解得出每条规划路径上的分配交通量（见表5-7）。
  针对问题四，本文综合遍历搜索法、蒙特卡洛法和Yen算法，分别用于突发事故发生前后路径对比、随机生成6条新建路段、查找新建路段后任意两点间的多条规划路径。以全局可达率为目标函数，以路径容量、路径长度、新路选址为约束条件，建立全局可达率目标规划模型：$$w=\frac{1}{n}\sum \frac{1}{n}\sum _{n=1}^n\frac{2l(i,j)-l^{{}^{\prime }}(i,j)}{l(i,j)},i,j\in A,n\in N^{\ast }$$  通过Matlab得出5种可达率最高的建设方案（见表5-9）。

一、问题背景与重述

1.1问题背景

  随着人工智能和机器学习等技术的不断发展，自动驾驶技术也在不断进步和完善，方便了人们的出行，预计未来将在汽车行业以及交通运输领域发挥越来越重要的作用。自动驾驶技术是指利用各种感知器、计算机以及控制系统，使汽车自主地在道路上行驶而无需人工干预的技术。这项技术的发展可以大大提高交通安全性、减少交通事故、缓解交通拥堵、节约能源和减少排放等。自动驾驶技术作为近年的社会热点，引发了许多学者的研究讨论，如高镇海等人建立健全自动驾驶社会性行为的评价体系¹。
  基于上述情况，本文针对未来新城背景下，自动驾驶技术的交通需求规划和可达率进行研究。目前的自动驾驶技术没有那么完善，汽车的可达率受车流量、事故等的影响，不稳定因素导致车辆无法到达的问题亟待解决。以往的学者也研究过自动驾驶线路优化问题：丁志杰等人提出了一种矿山场景下的自动驾驶矿车节能路径规划方法²。在前人研究的基础上，本文建立模型，基于特定交通网络对不同道路的交通需求进行分析，旨在获取交通需求中的最大期望可达率。

1.2问题重述

  本文通过建立数学模型，解决以下问题：
1.建立数学模型，根据附件1的数据，求得所有交通需求的最大期望可达率，并完成表1规划的路径和对应的交通量；
2.建立数学模型，根据附件2的数据，求得所有交通需求的最大期望可达率，并完成表1规划的路径和对应的交通量；
3.在问题二的基础上，要求各路段上的交通量不能超过路段容量，将规划的路径，以及对应分配的交通量填入表3；
4.建立数学模型，给出新修建6条路段方案，在表4中填入期望可达率最大的5种方案及其可达率。

二、问题分析

2.1对于问题一的分析

  问题一要求结合各个路段的交通需求量，给出每个路径上最适合的交通量。本文结合附件所给出的交通需求量，首先求出起点和终点之间的一条最短路径作为基准路径。在得出一条最短路径的基础上，寻找其他最短路径，结合小路径可能发生突发状况的情况，通过多次重复实验得出最优分配交通量。

2.2对于问题二的分析

  问题二要求得出在任意5条路段出现突发状况时，期望可达率最大情况下各规划路径的分配交通量。对于这种较为复杂的KSP问题，本文基于Dijkstra算法对其进行优化，同时求出多条最短路径。随后将任意5条路段发生突发状况的事件考虑进去，通过多次实验得出最优分配交通量。

2.3对于问题三的分析

  问题三在问题二的基础条件上，加入了路段容量，要求在此基础上得出最优规划路径和分配交通量。对于该种有容量约束的车辆路径规划问题，采用传统的方法处理起来较为复杂，本文参考相关文献，结合图神经网络算法对该问进行求解，同时得出最短路径和分配交通量。

2.4对于问题四的分析

  问题四要求在原有交通网络的基础上新建6条路段，以确保新网格在任意5条路段发生突发情况下，任意两点间都存在着较高的可达率。本文考虑将可达率作为目标函数，将6条路段的选址、路段容量、5条突发情况的路段作为约束条件，通过不断生成随机数，通过大量训练寻找合适的修建路段。

三、模型假设

  结合本题的实际，为确保模型求解的准确性和合理性，本文排除一些因素的干扰，提出以下几点假设：
1.假设各个小路径之间相互独立；
2.假设交通网络不受恶劣天气等其他突发事件的影响；
3.假设每条小路径的都能够得到利用，不会出现不使用小路径的情况。

四、符号说明

  为便于问题的求解，本文给出以下符号说明：

五、模型的建立与求解

  经过以上的分析和准备，本文将逐步建立以下数学模型，进一步阐述模型的实际建立过程。

5.1问题一的建立与求解

5.1.1基于Dijkstra算法的最短路径规划

  对于求解的规划路径，其中包含了一系列的小路径，因此在求解时需要去综合考虑各个小路径的理论分配交通量，求解时较为繁琐。本文在求解时结合假设1 （各个小路径之间相互独立），对大于等于两条小路径构成的路径进行拆解，将从$i$点到$j$点的大路径上的总交通量$L_{(i,j)}$ 视为由n个小路径上的交通量$l_{(a,b)}$所组成，其中$l_{(a,b)}$表示从a点到b点的小路径交通量，满足：$$L_{(i,j)}=\sum ^n{l}_{(a,b)}$$  但在拆解过程中首先需要确保的是，所拆解的大路径是从$i$点到$j$点的最短路径。这就意味着在拆解前，本文首先对两点间的最短路径进行求解。假设从$i$点到$j$点的大路径为$L_{(i,j)}$ ，将所有顶点的最短路径估计值设置为无穷大，起始点设为0。随后结合$Dijkstra$算法³进行求解，具体流程图如下：

图5-1 Dijkstra算法流程图

  重新创建优先队列，并将起始点1代入优先队列。当优先队列非空时，取出队列中具有最小交通量的顶点$u$。随后对与顶点$u$相邻的每个节点$v$，计算u和v之间的交通量，若该交通量小于目前$v$的最短路径估计值，则更新$v$的最小交通量，并将$v$加入优先队列。随后不断重复寻找与下一个节点间的最小交通量，直到确立大路径的最短路径，其模型可表示为：$$min{L}_{(i,j)}=\sum _{n=1}^{n}min{l}_{(i,j)}$$  上式是在各个路径均不存在突发情况下所得出的理论交通量，在实际生活中不可避免地存在着突发状况，进而导致交通出现瘫痪，即满足$l_{(a,b)}=0$。此时随之而来的问题是，若出现突发状况的路段恰好在规划路径上，则该条路径就无法投入使用。因此，本文引入变量$p$用来评判路径的正常与否。$$p=\{\begin{array}{l}1,有事故\\ 0,无事故\end{array}$$

5.1.2约束条件

  问题1要求给出从1到9和从3到7的所有规划路径及其分配交通量。在此本文以起点为1，终点为9的情况为例，对其约束条件进行判断。根据$Dijkstra$算法，从站点1到站点9的最短路径可以表示为：$$min{L}_{(1,9)}=\sum _{n=1}^{n}min{l}_{(a,b)}$$  由$Matlab$计算得出，该种情况下的最短路径长度为4，其所有可能的规划路径共有5种，具体分布情况如下图所示：

图5-2 最短规划路径图   本文对这六条规划路径分别命名为a,b,c,d,e,f以方便进一步分析处理。 表5-1 （1,9）对最短路径计算结果

  要确保规划路径可以全线运输不受阻碍，则需要确保各规划路径在路径上任意两点间的交通需求都能够满足且不能超出。由此，本文通过查找附件1中相关数据，得出各规划路径的最大承载量如上表所示。将规划路径的最大承载量命名为$q_i$，则：$$s.t.\{\begin{array}{l}0<a\le 110\\ 0<b\le 100\\ 0<c\le 100\\ 0<d\le 120\\ 0<e\le 100\\ 0<f\le 100\\ a+b+c+d+e+f=180\end{array}$$  同时，将规划路径是否能够正常投入使用考虑进去，则满足约束条件:$$s.t.\{\begin{array}{l}{p}_1+p_2+p_3+p_4+p_5+p_6=Z,Z\in 0,1,2,3,4,5,6\\ p_i=1or0,i=1,2,3,4,5,6\end{array}$$$$  同理可得从3到7的所有规划路径及其分配交通量。根据计算结果，从3到7的规划路径共有六条，命名为f,g,h,i,j,其对应的最小交通需求如下表所示：

表5-2 （3,7）对最短路径计算

  针对上表，同样可以得出各规划路径的约束条件，即最大承载量。考虑到篇幅问题，本文在此不赘述，具体约束条件见附录。

5.1.3建立目标规划模型求解

  问题一要求出满足最大期望可达率最大情况下的各规划路径上的分配交通量，本文结合上述约束条件和最短规划路径，建立目标规划模型：$$maxW=\frac{p_1{q}_a+p_2{q}_b+p_3{q}_c+p_4{q}_d+p_5{q}_e+p_6{q}_f}{180}$$
$$s.t.\{\begin{array}{l}0<a\le 110\\ 0<b\le 100\\ 0<c\le 100\\ 0<d\le 120\\ 0<e\le 100\\ 0<f\le 100\\ a+b+c+d+e+f=180\\ p_1+p_2+p_3+p_4+p_5+p_6=Z,Z\in (0,1,2,3,4,5,6)\\ p_i=1or0,i=1,2,3,4,5,6\end{array}$$  式中，$q_i$表示第$i$条规划路径的分配交通量。在对上述模型计算时，其中包含了10个变量，采用常规的求解方式较为繁琐费时。因此，本文结合蒙特卡洛法⁴对模型进行求解，结合约束条件，随机生成10000组数据进行仿真，进而得出可达率最高情况下各规划路径的分配交通量。
同理可以建立目标规划模型，结合约束条件通过$Matlab$得出（3,7）对各规划路径的分配交通量。对于（1,9）对和（3,7）的计算过程，其输出图像为：

图5-3 目标函数求解结果图

  由上图可得，（1,9）对之间的规划路径的分配交通量通过不断迭代，理论可达率达到86.67%，（3,7）之间的理论可达率达到了80.71%。其中，有两种情况下的概率接近，故图像无法完整显示。根据Matlab运算结果，本文得出结果如下：

5.2问题二的建立与求解

5.2.1基于Yen算法求解最短路径

  问题1在求解两点间最短路径时，采用$Dijkstra$算法得出的路径仅有一条，需要重复多次计算得出其余长度相等的最短路径。对于简单的交通网络来说可以适用，但对于较为复杂的交通网络使用时较为繁琐。对此，本文采用$Yen$算法⁵。进行多条最短路径规划求解。该算法在求解时，会尽量计算出足够数量的相异路径。若将问题2的交通网络图中所有点看作为一个集合A，求解出的第一个最短路径中所有点的集合为B，该方法会选取与B中相似性较大的路径：$$l_q=min[\sum _{i\in B}\frac{l_a(P_j,P_i)}{l(P_i)}],j\in A$$  式中，$P_i$表示原路径，$l_a(P_j,P_i)$表示路径$P_j$与原路径的共同路段长度，$l_q$表示新路径。结合本题交通线路图，其计算步骤为：
①确定求解路径的源节点$s$、目的节点$d$、和需要计算的路径数量$M$。
②使用$Dijkstra$算法求解计算最短路径。
③计算节点完全偏离路径。将已用路径上的顶点全部删除，然后使用$Dijkstra$算法求解最短路径。若求解路径成功，路径存入路径集合$B$，本轮计算结束，等待下一轮计算；若求解路径失败，对原始图交通线路图进行处理，将原路径中包含的边删除，然后尝试计算链路完全偏离路径。如果计算成功，则将得到的路径存入路径集合$A$。
④计算偏离路径。此步骤和传统$Yen$算法步骤大概相似，不同之处在于，本文会在遍历偏离点列表时，先删除不可用的偏离点，提高计算效率。另外，从集合$A$中选取路径时，会考虑选取的路径和集合$A$中已有路径的相近性。

5.2.2约束条件

  基于$Yen$算法对交通网络图3中的（27,6）对进行最短路径求解，得出共有5条长度为6的规划路径，如下图所示：

图5-4 基于Yen算法（27,6）对间的最短路径   将这5条规划路径分别命名为$a,b,c,d,e$,结合查找附件2数据，得出： 表5-4 （27,6）对最短路径结果

  同理可得（19,25）对间的4条路径及其最小交通需求：

表5-5 （19,25）对最短路径结果

  根据上表总结得出以下约束条件：
$$s.t.\{\begin{array}{l}0<a\le 121\\ 0<b\le 121\\ 0<c\le 121\\ 0<d\le 121\\ 0<e\le 121\\ a+b+c+d+e=121\\ p_1+p_2+p_3+p_4+p_5=Z,Z\in (0,1,2,3,4,5)\\ p_i=1or0,i=1,2,3,4,5,6\end{array}$$

5.2.3建立目标规划模型

  问题二要求在网格中任意5条路段出现突发状况的前提下，得出确保网格中所有交通需求的期望可达率最大的约束条件各规划路径分配交通量。本文结合上述约束条件，建立目标规划模型如下：$$maxW=\frac{p_1{q}_a+p_2{q}_b+p_3{q}_c+p_4{q}_d+p_5{q}_e}{180}$$  同理可得(19,25)对间的目标规划模型，接着结合蒙特卡洛法对模型进行求解，结合约束条件，随机生成100000组数据进行仿真，进而得出可达率最高情况下各规划路径的分配交通量，其输出图像为：

图5-5 （27,6）对和（19,25）对间的规划路径

  本文从两张结果图得出，随着迭代次数的增多，图像会逐渐收敛且交通可达率在不断增加直到趋于一个固定值，说明该方法得出的结果精度较高，具有科学性。（27,6）对间的可达率达到了85.12%，（19,25）对之间的可达率为 。因此，问题2中（27,6）对和（19，25）对的结果为：

5.3问题三的建立与求解

5.3.1技术路线

  对于第三问，可以将该题看做为$CVRP$问题进行求解⁶。对此，本文建立CVRP规划模型进行求解，具体过程如下：

图5-6 联合学习策略PBNR的技术路线图

5.3.2约束条件

（1）变量约束
  假设$x_{ij}$是二元变量，$x_{ij}=1$代表节点（i，j）之间存在规划的车辆路径，反之该变量为0则表示不存在这条路径。$$x_{ij}\in (0,1),i,j\in A$$（2）流量平衡约束
  $CVRP$目标规划模型中要求每个客户只能被访问一次，因此所有流入节点$i$的路径只能存在一条，同理从$j$流出的路由也只能有一条。$$\sum _{j\in V,j\ne i}{x}_{ij}=1,i\in N$$ $$\sum _{i\in V,j\ne i}{x}_{ij}=1,j\in N$$（3）完整性约束
  $CVRP$定义了车辆的每一条有效路径都必须是从出发点出发，最后返回出发点。但对于本题，本文将终点与起始点的赋值统一，将终点视为起点。$x_{i,0}$表示从起点到终点的路径，总数量为所有可能的规划路径，记为K。$$\sum _{i\in N}{x}_{i,0}=K$$（4）容量约束
  $CVRP$区别于其他道路规划求解方法最明显的特征是具有容量上限，本文记为$C$。车辆已交付货物量的更新公式如下：$$u_j=u_i+q_j,x_{ij}=1,i,j\in A,i,j\ne 0$$  每条规划路径不能承载超过容量的交通量，即车辆当前剩余货物不能低于下一个节点的需求量，同时也不能超过他的最大容量$C$。$$q_i\le u_i\le C,\forall i\in V$$

5.3.3建立CVRP目标规划模型

  CVRP以完成所有节点需求的前提下，规划一条行驶距离最短的车辆路径，建立CVRP目标规划函数可表示为：$$min\sum _{i,j\in A}{c}_{ij}{x}_{ij}$$$$s.t.\{\begin{array}{l}\sum _{i\in N}{x}_{i,0}=K\\ \sum _{j\in V,j\ne i}{x}_{ij}=1,i\in N\\ \sum _{i\in V,j\ne i}{x}_{ij}=1,j\in N\\ x_{ij}\in (0,1),i,j\in A\\ q_i\le u_i\le C,\forall i\in V\\ u_j=u_i+q_j,x_{ij}=1,i,j\in A,i,j\ne 0\end{array}$$  求解得出（32,29）对之间和（17,8）对之间的规划路径及其交通量为：

表5-7 问题3结果

5.4问题四的建立与求解

5.4.1确立目标函数

  问题四要求满足在新建6条路段后，5条路出现突发事故的前提下，仍然能够保证任意两个节点间具有较高的可达率。本文以任意两点间的可达率为目标函数，假设修路后没有发生突发状况下，从$i$点到$j$点间的最短路径为$r(i,j)$，发生突发状况后从$i$点到$j$点间的最短路径为 。为了评判整体任意两点间的可达率，本文结合遍历搜索法的思想，将所有组合进行综合考虑，建立目标函数为：$$w=\frac{1}{n}\sum \frac{r^{\prime }(i,j)}{r(i,j)}$$  式中，n代表累加的次数，本文通过求平均可达率的方法来评判整体可达率。

5.4.2约束条件

（1）容量约束
  结合附件3给出的容量上限，任意两点间的交通量应该不超过其路段承载量。基于此项，本文对每条路段上的车辆数进行约束：$$\sum q(i,j)\le c(i,j)$$（2）变量约束
  对于每一对进行最短路径求解的点对，首先需要满足求解的点都在更新后的交通网络图内，$i$和$j$需要服从区间分布。同时，规定$l(i,j)$表示两点间的最短路径长度，$l^{\prime }(i,j)$表示发生突发状况下的最短路径长度，则满足：$$\frac{r^{\prime }(i,j)}{r(i,j)}=\frac{1}{n}\sum _{n=1}^n\frac{2l(i,j)-l^{\prime }(i,j)}{l(i,j)},i,j\in A,n\in N^{\ast }$$  式中，$n$为两点间所有最短路径的数量。在计算最短路径时，仍然采用$Yen$算法，同时求解出多条最短路径，选择一条作为主要运输路径，其余路径作为备选路径。分配交通量时，采用平均分配的方法去分配交通量。
（3）路径约束
  原交通网络中共有65条路段，可以将待建路段的备选区域分为两种，一种是由4个站点围成的四边形模式，另一种是由5个站点围成的五边形模式。经过统计，共有15个四边形模式，3个五边形模型，具体修建计划如下：

表5-8 新建路段选址模式

  假设在第i个修建选址上修建的路段为${\alpha }_i$，是否在第$i$个修建选址上修建为 ，则修建的6条路应满足以下条件：$$s.t.\{\begin{array}{l}\sum _{n=1}^{18}{\beta }_i=6\\ {\beta }_i=\{\begin{array}{l}1,修建\\ 0,不修\end{array}\\ B^{\prime }=B+\sum {\alpha }_i{\beta }_i\end{array}$$

5.4.3建立目标规划模型

  结合以上目标函数和约束条件，本文建立目标规划模型为：$$w=\frac{1}{n}\sum _{n=1}^n\frac{2l(i,j)-l^{\prime }(i,j)}{l(i,j)},i,j\in A,n\in N^{\ast }$$$$s.t.\{\begin{array}{l}\sum _{n=1}^{18}{\beta }_i=6\\ {\beta }_i=\{\begin{array}{l}1,修建\\ 0,不修\end{array}\\ B^{\prime }=B+\sum {\alpha }_i{\beta }_i\\ \sum q(i,j)\le c(i,j)\end{array}$$

  通过Matlab计算得出可达率最高的五种方新建路段选址方案为：

表5-9 问题4结果

六、模型的检验

6.1.灵敏度检验

  根据问题一中建立的目标规划模型，计算公式为：$$maxW=\frac{p_1{q}_a+p_2{q}_b+p_3{q}_c+p_4{q}_d+p_5{q}_e+p_6{q}_f}{180}$$  其中180为附件中给出的1-9路径的交通需求量，经过分析比对，选取该方程交通需求量作为研究对象，通过将交通需求量值上下变化3%，观察6种情况最终交通最大通达率的变化来检验模型的精度和准确性，并根据该改Matlab 中对应的值整合得出下表：

表 6-1 灵敏度检验表

  为了更直观的体现，绘制出箱线图：

图6-1 灵敏度检验图   根据表中和图中可知，在交通需求量的值上下变动3%时，最大通达率值改变的百分比绝对值基本都小于0.5%，说明交通需求量的改变对问题一的最大通达率计算模型的影响不大，体现了模型的可行性和准确性。

七、模型的评价及改进

7.1模型的评价

7.1.1模型的优点

1.问题一采用Dijkstra算法求解最短路径，计算方便快捷。
2.问题二采用Yen算法，同时求解多条最短路径，有效提高了计算效率。
3.问题三采用联合学习策略进行有容量的路径规划，求解的结果更为准确。
4.问题四采用蒙特卡洛法随机生成6段新路，重复实验了10000次，计算结果具有较高的准确性，可信度较高。

7.1.2模型的缺点

1.问题二在确定突发状况时，假设路段之间相互独立，实际中可能存在着联系。
2.问题四在求解时，没有考虑新建6条路段的最大容量，处理时假设为容量无上限，与实际情况存在着差异。

7.2模型的改进

针对缺点一，可以考虑进一步建立动态规划模型，对相邻路段进行分析，通过赋值让两者具有关联性，但在解决上缺乏大量数据支撑。
针对缺点二，可以采用蒙特卡洛法随机生成6条路段的容量上限，即连续采用两次蒙特卡洛法。但这样可能会导致随机性较大，不具有较强的收敛性，结果不准。

---

1. 高镇海，于桐，孙天骏.考虑社会性行为的自动驾驶运动规划研究综述[J/OL].机械工程学报,1-17[2024-05-02]. ↩︎

2. 丁志杰，王亚飞，章翼辰,等.基于复合动态采样的自动驾驶矿车节能路径规划方法[J].汽车工程,2024,46(04):588-595+642. ↩︎

3. 冯琳洁，杜树新，裘一，等.基于Dijkstra算法的工业园区应急疏散路径规划[J].工业控制计算机,2024,37(03):44-46. ↩︎

4. 别朝红，王锡凡.蒙特卡洛法在评估电力系统可靠性中的应用[J].电力系统自动化,1997,(06):68-75. ↩︎

5. 王为亮，谭绍锋，肖雁鹏.一种基于光网络的搜索K最短路径的Yen改进算法[J].光通信技术,2022,46(04):101-106. ↩︎

6. 李冰洁.基于图神经网络和强化学习的路径规划方法[D].中南大学,2023. ↩︎