《数学模型》课程学习报告
浅谈基于数学模型的最短路径以及实际应用
一、引言
庆铃汽车
时代在前进，人们的学习理念在不断更新，数学建模应用能够为学生提供自己提取信息、提出问题和解决问题的机会。这次数学建模学习帮助自己在问题解决的过程中得到学数学、用数学的实际体验，从而加深对数学的理解，促进自己数学素质的全面提高。本人在学习数学模型课程之后，在研究中将定性研究与定量研究相结合，深入了解建模意识与建模应用的设计意图，并且通过自己所学习的建模方法解决实际问题。
二、数学模型学习心得
（一）最短路径方法分析
最短路径问题是交通网络分析中的一个重要问题，是资源分配、路线设计及分析等优化问题的基础。最短路径问题可分为单源最短路径问题及全源最短路径问题两种。其中单源最短路径问题更具有普遍意义，且可为全源最短路径问题提供良好的借鉴方案。单源最短路径问题的算法有很多种，从早期的基于限制条件的深度优先搜索算法、基于有向无环图的动态规划法、基于邻接矩阵的Dijkstra 算法、到最大相
关边法、最大相关点法、基于邻接表的Dijkstra算法、A*算法等。针对不同的网络特征、应用需求及具体的软硬件环境，各种算法在空间复杂度、时间复杂度、易实现性等方面各具特。其中，Dijkstra算法以极强的抗差性而得到广泛的普及和应用。
（二）最短路径Dijkstra算法分析
Dijkstra算法的基本思想是，从vs（源点）出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为P标号）、或者是从vs到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具体T标号的改变为具体P标号的点，从而使G中具体P标号的顶点数多一个，这样至多经过
n-1（n为图的顶点数）步，就可以求出从vs到各点的最短路。
（三）算法流程分析
图2.1带权有向图
对于图2.1这样的带权有向图，计算源点1到其他顶点间的最短路径长度的过程如表2-1所示。
表2-1 最短路径长度的过程
选迭Nod（）W D[2] D[3] D[4] D[5]
初始{1} —10 ∞30 100
1 {1,2}
2 10 60 30 100
2 {1,2,4}  4 10 50 30 90
3 {1,2,4,3}    3 10 50 30 60
4 {1,2,4,3,5}
5 10 50 30 60
算法流程如图2.1所示。表2-1中，初始时node（）={1}，d（1，2）=10，d（1，3）=∞，d（1，4）=30，d（1，5）=100。执行第一次迭代时，因为d（1，2）最小，所以取W=2，同时赋值d（1，3）=min（∞，10+50）=60，d（1，4）和d（1，5）的值不变。然后再进行下一次迭代。相应的路径，可以设一个顶点组成的数组s（），用以记录从源点到顶点y的最短路径[20]。
初始时，对所有的y≠1，设node（）=1。在Dijkstra算法中更新最短路径长度时，只要d（i，y）+d（y，j）<d（i，j）（i表示源点，j表示目标点），就将node（y）设为w；否则不修改node（y）的值。当Dijkstra算法结束时，就可以根据数组s（）到从源点i到目标j的最短路径线路，从d（）中到从源点i 到目标j的最短路径长度。
图2.2最短路径Dijkstra算法流程图
在图2.1中的有向图，经过Dijkstra算法计算后，如果要源点1到目标点5之间的最短路径d（1，5）的话，可以根据图2.2的流程执行。
其步骤如下：
（1）第1次迭代。从源点1到目标点5的最短路径长度d（1，4）=100，路径s（1，5）=15；
（2）第2次迭代。加入候选结点W=4时，因为d（1，4）+…+d（4，5）<d（1，5），所以d（1，5）=90，s（1，5）=145；
（3）第3次迭代。加入候选结点W=3时，因为d（1，4）+d（4，3）+d（3，5）<d（1，4）+d（4，5），所以d（1，5）=60，s（1，5）=1435；
（4）第4次迭代。d（1，5）和s（1，5）保持不变，源点1到目标点5的最短路径长度应该是60，路线为1→4→3→5。
三、建立模型分析与应用
（一）实际应用案例分析
主要计算西安永辉连锁超市配送中心去往各个门店的配送成本。配送中心标记为S，各门店标注为N，即唐延路店为N1，十里铺店为N2，中登店为N3，西长安街店为N4，大明宫万达店为N5，阳光天地店为N6。将各种车型进行标记，江铃汽车标记为A1、A2、A3、A4，庆铃汽车标记为B1、B2、B3、B4，东
风霸王标记为C1、C2、C3、C4，东风天锦标记为D1、D2。
由于主要研究配送路线的优化方式，而各个门店之间的路线距离不同，也不同车型的载重和燃油费率存在差异，因此配送成本会忽略车辆的损耗、人力费用等，主要是经过配送路线后，计算燃油费用，如下式：根据配送路线的设计，将每辆车的配送成本相加，从而得到总的配送成本。
配送成本=（配送里程×燃油费率×车辆载重）
约束条件主要是两个方面，一是配送路线约束条件，即点M不能直接到达N，可以标注其距离是∞。二是车载限制，即日均配送量不能超过车辆载重上限。因此，根据实际情况，点M到达点N时，要将点N的日均配送量增加到当前车型，如果当前车型日均配送量超过上限，则认为点M到点N的距离是∞。（二）建立车型组合
由于共有6家门店，根据配送量的需要，计算出车型组合，以车型组合为核心，进行配送路线的迭代。在车型组合中，当某车型的日均配送量超过车载上限时，车型组合的下一辆汽车自动从配送中心出发，去往余下的门店。同时，剔除出不合理的车型组合。原则是在同等配送量的情况下，使用车载量大的车型。车型组合如表3-1所示。
表3-1 车型组合
（三）配送路线迭代
根据配送过程中，配送中心与各个门店之间的距离，以配送车型组合方式3为例，从配送中心出发，进行配送路线的迭代。
由于汽车D1在经过N1、N2后，日均配送量超过上限，汽车D1无法继续配送，必须返回配送中心，由车型组合方式3中的汽车D2继续进行配送服务。
同理，汽车D2在经过N3、N4之后，日均配送量超过车载上限，使得汽车D1无法继续配送了，必须返回配送中心，由车型组合方式3中的汽车C1继续进行配送服务。由于C1、C2的车载量是4T，均只能配送一家门店，因此C1配送N5，C2配送N6。至此，完成了车型组合方式3的配送路线。
（3）确定局部最优
通过车型组合方式3，确定了配送路线，可以得出本次配送路线的配送成本。D1的配送成本为18×8.58×（2.9+2.8）=880.308元，D2的配送成本为18×8.19×（2.8+2.6）=796.068元，C1的配送成本为13×3.3×3.1=132.99元，C2的配送成本为13×5.2×3.3=223.08元，总成本为2032.446元。
在相同的车型组合方式下，重复进行步骤（2），计算不同配送路线的配送成本，进行相互比较，从而
确定局部最优。
（4）确定全局最优
得到局部最优后，变更车型组合方式，重新进行步骤（2）和步骤（3），从而得到每个车型组合方式的局部最优解，进行相互比较，最终得到全局最优解。整个算法的流程图3.1如下。