摘 要
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，即高质量高速度的完成送货任务，针对本案例，我们采用了大量的科学分析方法，并进行了反复验证，得出如下结果：
问题1：根据所给问题与数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路. 在此基础上，我们通过观察分析计算对上述结果进行修正，然后我们再采用穷举法对问题结果进行验证，结果相吻合。最终得到如下路线：
北京→香港 → 湖南→海南→ 广西 →重庆 → 河南 →云南 →西藏 →新疆 → 青海 → 甘肃 →宁夏 →江苏→ 福建 →上海 →台湾 →上海 →黑龙江 →内蒙古 →黑龙江→吉林 →北京。（最短时间为61小时）
问题2：由于题中有货物重量与体积限制，货机一次最多只能载50件产品，考虑19个城市的总需求为114，这就估算出至少需要返回2次，采用逆向求解的方法，相当于3架货机同时送货，要设计线路使总共花费的时间最短，尽量使送货任务均衡，最大限度不超过50件货物，最后得出结果为：北京 → 吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 → 北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。（总的时间为71.77777）（其中红色表示只路过不送货）
问题3：要求问题1，2的花费最少，只需对前两个模型做进一步优化即可，经过优化计算我们得到如下结果：
问题1的最少花费为584250（元），路线如下：北京→香港 → 湖南→海南→ 广西 →重庆 → 河南 →云南 →西藏 →新疆 → 青海 → 甘肃 →宁夏 →江苏→ 福建 →上海 →台湾 →上海 →黑龙江 →内蒙古 →黑龙江→吉林 →北京
问题2的最少花费为711750（元），线路如下：北京 → 吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 → 北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。
关键词：关键字：最短路径 送货线路优化 赋权连通简单无向图 Excel 最小生成树
§1 问题的重述
一、问题背景
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司专业生产某专用设备产品，专用设备产品每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900公里/小时，将货物送至全国各个省辖市（图1所示红色圆点，除北京之外共19个省辖市），假定货机只能沿这些连通线路飞行，而不能走其它任何路线；但由于受重量和体积限制，货机可中途返回取货。经过的各个省市都要一定的停靠费用和停靠时间（停靠时间为常量2小时），假设经过某个省市的停靠费用为：
停靠费用=5000元×该省市的消费指数. 二、相关数据
1、各个城市间的通路和权数
1、上图1描述了中国各个省市之间的航班以及权重以图中标注为准；
2、有些省市之间是没有航班，需要中转。
2、城市消费指数和需求量数据表
三、要解决的问题
1、问题一：若图示中19个省辖市每个省辖市只要一件产品请设计送货方案，使所用时间最少，标出送货线路。
2、 问题二：若图示中19个省辖市需求量见表1，请设计送货方案，使所用时间最少。
3、问题三：若该实业公司为了花费最少，针对问题1和问题2分别求出花费、标出送货线路。
§2 问题的分析
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，在有限的单次最大载重的前提下，考虑在时间允许的范围内如何将货物最快、最省钱的送到客户手中。我们要研究制定既省时又省钱的最佳送货计划。 一、对问题的具体分析
1、对问题一的分析：
我们对第一问要求时间最短，我们最短时间转化最短距离，围绕货物所要运到的地址数据及这些地址之间的距离，采用Floyd 算法进行求解得到任意两地之间的最短距离，再根据最小生成树的求法可以求出该图G 的最小生成树，由于该问题研究的是闭合回路，所以又需要对问题进行整体优化，最后得出了最佳飞行线路。
2、对问题二的分析：
根据重量、体积和各个城市的需求量的限制，货机一次最多只能载50件产品，考虑19个城市的总需求为114，这就估算出至少需要返回2次，采用逆向求解的方法，相
当于3架货机同时送货，要设计线路使总共花费的时间最短，尽量使送货任务均衡，最大限度不超过50件货物，最后得出结果。
3、对问题三的分析：
第三问中仍将所有约束转化为路径约束，求出最优解。
3 模型的假设
1、飞机在送货期间能保持正常工作状态，不受燃料以及天气变化等影响；
2、假设飞机自身无任何故障，不考虑飞机的起飞和降落时间，认为飞机在工作时速度始终保持在平均速度为900公里/小时； 3、飞机的外形及重量的变化不影响飞机的速度； 4、假设货物在存放中，货物与货物之间无空隙；
5、飞机在送完一地货物时所剩货物不满足下一地需求时则返回； 6、假定货机只能沿着图中的连通路线飞行，而不走其他的路线； 7、假设飞机送完货后必须返回北京。
§4符号说明
一、符号说明
1、将地图上城市用点表示，并进行编号详细见下
2、AiAj ：点Ai 到点Aj 的线段
3、权（1）：表示题目中给出的两城市之间的权，如北京—新疆（A1A5）的权（1）为23；.
4、权（2）：表示通过两城市之间路程所花费的时间，如北京—新疆（A1A5）的权（2）为23*100/900+2=4.5555556（小时）
5、权（3）：表示通过两城市之间路程的花费，如北京—新疆（A1A5）的权（3）为23*2500+1.55*5000=65250（小时），1.15为两城市指数的平均值.
6、V ：A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合.
7、E ：A1A5，A1A6，A1A10，A1A13， A1A15，A1A17， A1A19，A2A5，A2A11，A3A11，A3A18，A4A5，A4A12，A4A15，A5A12，A5A14，A5A15，A6A7，A6A15，A6A17，A7A16，A8A18，A8A19，A9A10，A9A14，A9A18，A9A19，A13A15，A13A16， A19A20的集合.
8、W ：V 中点之间的权（2）的集合，则G=（V ，E ，W ）表示赋权连通简单无向图 9、M ：V 中点之间的权（3）的集合，则F=（V ，E ，M ）表示赋权连通简单无向图 10、G （V ，E ）：赋权连通图； 11、G i ：G （V ，E ）的第i 个子图； 12、L i ：为子图G i 中的最佳回路； 13、w (e ) ：为边e 的权； 14、w (v ) ：为点v 的点权； 15、l i ：L i 的各边的大小；
§5 模型的建立与求解
依据问题的要求及相关假设，建立相应的模型并进行求解： 一、问题一的模型建立与求解
1、模型Ⅰ
最小生成树模型
根据题目意思，两城市之间的时间=权（1）*100/速度+2（单位：小时） 例如北京到新疆A1A5权（1）是4.5555556，其他见下
表3
定义V 为A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合，定义E 为 A1A5，A1A6，A1A10，A1A13， A1A15，A1A17， A1A19，A2A5，A2A11，A2A13，A3A11，A3A18，A4A5，A4A12，A4A15，A5A12，A5A14，A5A15，A6A7，A6A17，A7A16，A8A18，A8A19，A9A10，A9A14，A9A18，A9A19，A13A15，A13A16， A19A20的集合，定义W 为V 中点之间的权（2）的集合，则G=（V ，E ，W ）表示图.
2、模型I 求解
根据最小生成树的求法可以求出改图G 的最小生成树如图2
沿着最小生成树的路线相对较短，为：A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A5—A4—A5—A2—A13—A16—A7—A6—A17—A15—A1—A10—A9—A14—A9—A10—A1
经过观察上面下划线的部分并A5—A12—A5—A4—A5—A2—A13—A16不是最短的，经计算这个路线A5—A12—A4—A15—A13—A16比上一段的要短，故用它替换上一段，这里经过了A15，那从A17可直接到A1，不用再经过A15，故A7—A6—A17—A15—A1这段可用A7—A6—A17—A1来替换，A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A4—A15—A13—A16—A7—A6—A17—A1—A10—A9—A14—A9—A10—A1，由于这条路径最后一段，A20，和A9都重走了，故可对路径进行重组，依据线路最短和经过两次的城市最少的原则，经过综合分析，得出最优的路径为
A1—A17—A6—A7—A16—A13—A15—A4—A12—A5—A2—A11—A3—A18—A8—A19—A20—A19—A9—A14—A9—A10—A1。
可以将相邻两点的权（2）相加，和为总时间，经过计算上述线路所花时间是61小时，为最短时间.
二、问题二的模型建立与求解 1、建立模型
把各个城市间的航线示意图抽象为一赋权连通图G (V , E ) ，在权图G 中，v i ∈v (G ) 对应的示意图中各个货物需求地，v 0表示北京，e j ∈E (G ) 对应图中的航线，边权w (e j ) 对应示意图中的航线长。
建立的数学模型如下：
∀e ∈E (G ) ，∃w (e ) ∈N ，∃v ∈v (G ) ，∃w (v ) ∈|V *T , |v 0∈V (G ) ，
求G 中回路L 1, L 2,......, L k (k >) ，使得满足：
（1）
v
k
∈V (L i ), i =1, 2,......, k
；
（2） V (L i ) =V (G ) ；
i =1
n
（3）∑∑
w (e ) =min（目标为总距离最短）；或m ax |
∑
e ∈E (L )
w (e ) +
∑
t ∈V (t )
w (v ) |=
min （目标为飞行所用时间最少）。 2、模型求解
i =1e ∈E (L )
由分析得此货机至少要回去取货二次，相当于把图G 分成三个子图G i (i =1, 2, 3) ，
在每个子图G i 中寻找最佳回路L i (i =1, 2, 3) 。
因为最小生成树包括图G 中的所有顶点，而且最小树的边权是相邻两点之间是的距离，它描述顶点之间的相近程度，故可利用最小生成树进行初步分块。根据最小生成树求解Kruskal 算法，找到图的最小生成树如下图3：
现要对已经得到的最小生成树进行分解，以获得三个子图G ，使得分解的每一组的各个城市需求和不超过50件货物，并且尽量使每一组的线路最短。从而根据最小生成树的分解方法把图G （V ，E ）划分为三个子图G i , i =1, 2, 3，分别在G i 中寻找最佳航线。
依据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找最优的分块结果，在G i , i =1, 2, 3，中分别寻找一条从北京出发，遍历V 并回到北京的最短路线。在G （V ，E ）中求三条从北京O 出发并回到北京O 的路L 1, L 2, L 3，依据的步骤如下，做出G 和O 之间的最短路；以O 与G 连通的路径及原图G 的最优树在G i 中保留的边为基础，进行增环扩环调整，使最后尽可能形成一个环路。
三条环路如下图4所示：
线路如下：北京 →吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 (时间为88/9+8*2=25.777778)
北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 →北京(时间58/9+6*2=18.444444)北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。(时间68/9+10*2=27.555556)
总的时间为25.777778+18.444444+27.555556=71.77777 三、问题三的模型建立与求解
根据题目和假设，假设两城市之间运输的价格=权（1）*2500+平均指数*5000（单位：价格）
北京到新疆A1A5权（1）是23，北京的指数为1.9，上海为1.2，则先求出平均指数（1.9+1.2）/2=1.55，根据公式可得
北京到新疆A1A5关于时间的运输价格的权为23*2500+1.55*5000= 65250（小时），其他各城市间的权（3）见下
表4
针对问题一
根据最小生成树的求法根据权（3）求出改图G 的最小生成树如图5所示： 沿着最小生成树的路线相对较短，为：A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A5—A4—A5—A2—A13—A16—A7—A6—A17—A15—A1—A10—A9—A14—A9—A10—A1
经过观察上面下划线的部分并A5—A12—A5—A4—A5—A2—A13—A16不是最短的，经计算这个路线A5—A12—A4—A15—A13—A16比上一段的要短，故用它替换上一段，这里经过了A15，那从A17可直接到A1，不用再经过A15，故A7—A6—A17—A15—A1这段可用A7—A6—A17—A1来替换，A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A4—A15—A13—A16—A7—A6—A17—A1—A10—A9—A14—A9—A10—A1，由于这条路径最后一段，A20，和A9都重走了，故可对路径进行重组，依据线路最短和经过两次的城市最少的原则，经过综合分析，得出最优的路径为
A1—A17—A6—A7—A16—A13—A15—A4—A12—A5—A2—A11—A3—A18—A8—A19—A20—A19—A9—A14—A9—A10—A1。
可以将相邻两点的权（3）相加，和为总花费，最少为584250元。 针对问题二
把各个城市间的航线示意图抽象为一赋权连通图G (V , E ) ，在权图G 中，v i ∈v (G ) 对应的示意图中各个货物需求地，v 0表示北京，e j ∈E (G ) 对应图中的航线，边权w (e j ) 对应示意图中的航线长，将航线长及在各个城市停留的时间都转化相应的花费Z (即权（3）。
建立的数学模型如下：
e )
i
∀e ∈E (G ) ，∃w (e ) ∈N ，∃v ∈v (G ) ，∃w (v ) ∈|V *T , |v 0∈V (G ) ，
求G 中回路L 1, L 2,......, L k (k >) ，使得满足：
（1）
v
k
∈V (L i ), i =1, 2,......, k
；
（2） V (L i ) =V (G ) ；
i =1
n
（3）∑∑
min （目标为飞行总的花费最少）。 2、模型求解
i =1e ∈E (L )
Z (e i ) =min（目标为总花费最少）；或m ax |
∑
e ∈E (L )
Z (e i ) +
∑
t ∈V (t )
Z (v ) |=
由分析得此货机至少要回去取货二次，相当于把图G 分成三个子图G i (i =1, 2, 3) ，在每个子图G i 中寻找最佳回路L i (i =1, 2, 3) 。
现要对已经得到的最小生成树进行分解，以获得三个子图G ，使得分解的每一组的各个城市需求和不超过50件货物，并且尽量使每一组的线路最短。从而根据最小生成树的分解方法把图G （V ，E ）划分为三个子图G i , i =1, 2, 3，分别在G i 中寻找最佳航线。
依据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找最优的分块结果，在G i , i =1, 2, 3，中分别寻找一条从北京出发，遍历V 并回到北京的最短路线。在G （V ，E ）中求三条从北京O 出发并回到北京O 的路L 1, L 2, L 3，依据的步骤如下，做出G 和O 之间的最短路；以O 与G 连通的路径及原图G 的最优树在G i 中保留的边为基础，进行增环扩环调整，使最后尽可能形成一个环路。
线路如下：北京 →吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 →北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。
总的费用为711750（元）
§7 模型的评价与推广
一、模型的优缺点
1、优点：
〔1〕. 本文的三个问题，给出了在各种约束条件下的最短时间以及最少花费的计算方法，具有较强的实用性和通用性，可用于日常生活中；
〔2〕. 在忽略其他条件限制的最短时间问题中，我们采用最小生成树方法进行求解，并用了枚举法进行验证，经过大量的计算使结果更准确，更符合实际情况，从而达到解决实际问题的目的；
〔3〕. 采用枚举法对问题结果进行验证，使计算结果更加准确，更符合实际；
〔4〕. 对于加入了省辖市需求量的问题当中，我们在第一问的基础上，计算出北京到
各个城市间的最短距离，并再次利用最小生成树的方法，进行计算验证得出结果，解决实际问题。
〔5〕. 在本题目的最后一问当中，给出了计算在货物体积和重量等多个限制条件下的最优化解法，采用最小生成树算法解决了这个与实际问题非常接近的问题，具有很好的实际意义。
2、缺点：
〔1〕. 本题中为使问题便于研究，我们做了许多假设，这或许对模型的实际意义产生影响；
〔2〕. 本问题并非线性优化问题，加之节点过多，需要到量的精密计算，多次重复因此很难做到求出的结果就是最优解，只是相对较优的结果；
〔3〕. 本为题所建立的模型，本省舍弃了某些因素的影响的结果，但会使所求结果与实际生活产生偏差。
七．模型的推广
本文依据所研究的问题建立了三个模型，这三种模型对于许多数学问题的解决方法和途径都有一定的帮助。
第一问中利用最小生成树的方法来解决的，此种优化方法可用来指导现实生活中所遇到的许多问题，如：旅游最短线路问题、货物运送问题、邮递问题以及管道输水等等一些实际问题。求解这些问题可以参考最小生成树方法，再利用枚举法经过大量的计算可得出非常接近最优解。
第二问中是加入了限制条件的运货最优问题，利用赋权连通图，并根据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找到最优的分块，再利用最小生成树方法求解在有需求量约束的前提下最短线路的模型，然后综合比较得出符合要求的较优的线路。在日常生活中，可以利用该模型来求解与最优树和最大流量有关的实际问题。
在第一问和第二问的基础上所延伸出来的第三个问题也可以采用该算法解决实际问题。这类问题在实际生活中随处可看见，且都可以应用这些模型进行解决。在将实际问题抽象为具体数学问题的时候，根据数学建模的思想以及步骤，会做出一定的假设，因此会导致一定的误差，因此不同的实际问题，要根据具体情况认真考虑，得出最优的设计方案，对于解决实际问题具有很重要的意义
参考文献
[1] 李庆扬，关治，白峰衫 . 数值计算原理 . 北京：清华大学出版社 , 2000；
[2] 刘来福，曾文艺. 数学模型与数学建模（第二版） . 北京：北京师范大学出版社， 2002；
[3] 蔡锁章 . 数学建模原理与方法 . 北京：海洋出版社， 2000； [4]王勇，池洁，物流配送路线及配送时间的优化分析 2010-6-4；
[5]吴群妹，实际配送中多个配送点闭回路最短路径的选取， 2010-6-4； [6]郭亚军 , 综合评价理论与方法 [M]. 北京：科学出版社 ,2002；
[7]池洁，李莉，物流中配送区域与配送路线的网络优化法， 2010-6-4 ；
源程序
M=1000; a=zeros(20);
a(5,12)=8;a(5,2)=6;a(5,4)=11;a(4,12)=12;a(2,11)=4;a(3,11)=2;a(1,5)=23; a(5,14)=20;a(5,15)=22;a(2,13)=8;a(13,16)=7;a(7,16)=2;a(6,7)=3;a(6,17)=2; a(4,15)=15;a(1,6)=21;a(1,17)=24;a(8,18)=4;a(8,19)=3;a(1,10)=8; a(13,15)=12;a(3,18)=10;a(1,15)=12;a(1,13)=20;a(1,19)=9; a(14,9)=11;a(10,9)=2;a(18,9)=15;a(19,9)=17; a(20,19)=4;
a=a+a';a(find(a==0))=M; for i=1:20 a(i,i)=0; end
result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp);
[jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1));
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result
摘 要
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，即高质量高速度的完成送货任务，针对本案例，我们采用了大量的科学分析方法，并进行了反复验证，得出如下结果：
问题1：根据所给问题与数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路. 在此基础上，我们通过观察分析计算对上述结果进行修正，然后我们再采用穷举法对问题结果进行验证，结果相吻合。最终得到如下路线：
北京→香港 → 湖南→海南→ 广西 →重庆 → 河南 →云南 →西藏 →新疆 → 青海 → 甘肃 →宁夏 →江苏→ 福建 →上海 →台湾 →上海 →黑龙江 →内蒙古 →黑龙江→吉林 →北京。（最短时间为61小时）
问题2：由于题中有货物重量与体积限制，货机一次最多只能载50件产品，考虑19个城市的总需求为114，这就估算出至少需要返回2次，采用逆向求解的方法，相当于3架货机同时送货，要设计线路使总共花费的时间最短，尽量使送货任务均衡，最大限度不超过50件货物，最后得出结果为：北京 → 吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 → 北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。（总的时间为71.77777）（其中红色表示只路过不送货）
问题3：要求问题1，2的花费最少，只需对前两个模型做进一步优化即可，经过优化计算我们得到如下结果：
问题1的最少花费为584250（元），路线如下：北京→香港 → 湖南→海南→ 广西 →重庆 → 河南 →云南 →西藏 →新疆 → 青海 → 甘肃 →宁夏 →江苏→ 福建 →上海 →台湾 →上海 →黑龙江 →内蒙古 →黑龙江→吉林 →北京
问题2的最少花费为711750（元），线路如下：北京 → 吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 → 北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。
关键词：关键字：最短路径 送货线路优化 赋权连通简单无向图 Excel 最小生成树
§1 问题的重述
一、问题背景
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司专业生产某专用设备产品，专用设备产品每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900公里/小时，将货物送至全国各个省辖市（图1所示红色圆点，除北京之外共19个省辖市），假定货机只能沿这些连通线路飞行，而不能走其它任何路线；但由于受重量和体积限制，货机可中途返回取货。经过的各个省市都要一定的停靠费用和停靠时间（停靠时间为常量2小时），假设经过某个省市的停靠费用为：
停靠费用=5000元×该省市的消费指数. 二、相关数据
1、各个城市间的通路和权数
1、上图1描述了中国各个省市之间的航班以及权重以图中标注为准；
2、有些省市之间是没有航班，需要中转。
2、城市消费指数和需求量数据表
三、要解决的问题
1、问题一：若图示中19个省辖市每个省辖市只要一件产品请设计送货方案，使所用时间最少，标出送货线路。
2、 问题二：若图示中19个省辖市需求量见表1，请设计送货方案，使所用时间最少。
3、问题三：若该实业公司为了花费最少，针对问题1和问题2分别求出花费、标出送货线路。
§2 问题的分析
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，在有限的单次最大载重的前提下，考虑在时间允许的范围内如何将货物最快、最省钱的送到客户手中。我们要研究制定既省时又省钱的最佳送货计划。 一、对问题的具体分析
1、对问题一的分析：
我们对第一问要求时间最短，我们最短时间转化最短距离，围绕货物所要运到的地址数据及这些地址之间的距离，采用Floyd 算法进行求解得到任意两地之间的最短距离，再根据最小生成树的求法可以求出该图G 的最小生成树，由于该问题研究的是闭合回路，所以又需要对问题进行整体优化，最后得出了最佳飞行线路。
2、对问题二的分析：
根据重量、体积和各个城市的需求量的限制，货机一次最多只能载50件产品，考虑19个城市的总需求为114，这就估算出至少需要返回2次，采用逆向求解的方法，相
当于3架货机同时送货，要设计线路使总共花费的时间最短，尽量使送货任务均衡，最大限度不超过50件货物，最后得出结果。
3、对问题三的分析：
第三问中仍将所有约束转化为路径约束，求出最优解。
3 模型的假设
1、飞机在送货期间能保持正常工作状态，不受燃料以及天气变化等影响；
2、假设飞机自身无任何故障，不考虑飞机的起飞和降落时间，认为飞机在工作时速度始终保持在平均速度为900公里/小时； 3、飞机的外形及重量的变化不影响飞机的速度； 4、假设货物在存放中，货物与货物之间无空隙；
5、飞机在送完一地货物时所剩货物不满足下一地需求时则返回； 6、假定货机只能沿着图中的连通路线飞行，而不走其他的路线； 7、假设飞机送完货后必须返回北京。
§4符号说明
一、符号说明
1、将地图上城市用点表示，并进行编号详细见下
2、AiAj ：点Ai 到点Aj 的线段
3、权（1）：表示题目中给出的两城市之间的权，如北京—新疆（A1A5）的权（1）为23；.
4、权（2）：表示通过两城市之间路程所花费的时间，如北京—新疆（A1A5）的权（2）为23*100/900+2=4.5555556（小时）
5、权（3）：表示通过两城市之间路程的花费，如北京—新疆（A1A5）的权（3）为23*2500+1.55*5000=65250（小时），1.15为两城市指数的平均值.
6、V ：A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合.
7、E ：A1A5，A1A6，A1A10，A1A13， A1A15，A1A17， A1A19，A2A5，A2A11，A3A11，A3A18，A4A5，A4A12，A4A15，A5A12，A5A14，A5A15，A6A7，A6A15，A6A17，A7A16，A8A18，A8A19，A9A10，A9A14，A9A18，A9A19，A13A15，A13A16， A19A20的集合.
8、W ：V 中点之间的权（2）的集合，则G=（V ，E ，W ）表示赋权连通简单无向图 9、M ：V 中点之间的权（3）的集合，则F=（V ，E ，M ）表示赋权连通简单无向图 10、G （V ，E ）：赋权连通图； 11、G i ：G （V ，E ）的第i 个子图； 12、L i ：为子图G i 中的最佳回路； 13、w (e ) ：为边e 的权； 14、w (v ) ：为点v 的点权； 15、l i ：L i 的各边的大小；
§5 模型的建立与求解
依据问题的要求及相关假设，建立相应的模型并进行求解： 一、问题一的模型建立与求解
1、模型Ⅰ
最小生成树模型
根据题目意思，两城市之间的时间=权（1）*100/速度+2（单位：小时） 例如北京到新疆A1A5权（1）是4.5555556，其他见下
表3
定义V 为A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合，定义E 为 A1A5，A1A6，A1A10，A1A13， A1A15，A1A17， A1A19，A2A5，A2A11，A2A13，A3A11，A3A18，A4A5，A4A12，A4A15，A5A12，A5A14，A5A15，A6A7，A6A17，A7A16，A8A18，A8A19，A9A10，A9A14，A9A18，A9A19，A13A15，A13A16， A19A20的集合，定义W 为V 中点之间的权（2）的集合，则G=（V ，E ，W ）表示图.
2、模型I 求解
根据最小生成树的求法可以求出改图G 的最小生成树如图2
沿着最小生成树的路线相对较短，为：A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A5—A4—A5—A2—A13—A16—A7—A6—A17—A15—A1—A10—A9—A14—A9—A10—A1
经过观察上面下划线的部分并A5—A12—A5—A4—A5—A2—A13—A16不是最短的，经计算这个路线A5—A12—A4—A15—A13—A16比上一段的要短，故用它替换上一段，这里经过了A15，那从A17可直接到A1，不用再经过A15，故A7—A6—A17—A15—A1这段可用A7—A6—A17—A1来替换，A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A4—A15—A13—A16—A7—A6—A17—A1—A10—A9—A14—A9—A10—A1，由于这条路径最后一段，A20，和A9都重走了，故可对路径进行重组，依据线路最短和经过两次的城市最少的原则，经过综合分析，得出最优的路径为
A1—A17—A6—A7—A16—A13—A15—A4—A12—A5—A2—A11—A3—A18—A8—A19—A20—A19—A9—A14—A9—A10—A1。
可以将相邻两点的权（2）相加，和为总时间，经过计算上述线路所花时间是61小时，为最短时间.
二、问题二的模型建立与求解 1、建立模型
把各个城市间的航线示意图抽象为一赋权连通图G (V , E ) ，在权图G 中，v i ∈v (G ) 对应的示意图中各个货物需求地，v 0表示北京，e j ∈E (G ) 对应图中的航线，边权w (e j ) 对应示意图中的航线长。
建立的数学模型如下：
∀e ∈E (G ) ，∃w (e ) ∈N ，∃v ∈v (G ) ，∃w (v ) ∈|V *T , |v 0∈V (G ) ，
求G 中回路L 1, L 2,......, L k (k >) ，使得满足：
（1）
v
k
∈V (L i ), i =1, 2,......, k
；
（2） V (L i ) =V (G ) ；
i =1
n
（3）∑∑
w (e ) =min（目标为总距离最短）；或m ax |
∑
e ∈E (L )
w (e ) +
∑
t ∈V (t )
w (v ) |=
min （目标为飞行所用时间最少）。 2、模型求解
i =1e ∈E (L )
由分析得此货机至少要回去取货二次，相当于把图G 分成三个子图G i (i =1, 2, 3) ，
在每个子图G i 中寻找最佳回路L i (i =1, 2, 3) 。
因为最小生成树包括图G 中的所有顶点，而且最小树的边权是相邻两点之间是的距离，它描述顶点之间的相近程度，故可利用最小生成树进行初步分块。根据最小生成树求解Kruskal 算法，找到图的最小生成树如下图3：
现要对已经得到的最小生成树进行分解，以获得三个子图G ，使得分解的每一组的各个城市需求和不超过50件货物，并且尽量使每一组的线路最短。从而根据最小生成树的分解方法把图G （V ，E ）划分为三个子图G i , i =1, 2, 3，分别在G i 中寻找最佳航线。
依据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找最优的分块结果，在G i , i =1, 2, 3，中分别寻找一条从北京出发，遍历V 并回到北京的最短路线。在G （V ，E ）中求三条从北京O 出发并回到北京O 的路L 1, L 2, L 3，依据的步骤如下，做出G 和O 之间的最短路；以O 与G 连通的路径及原图G 的最优树在G i 中保留的边为基础，进行增环扩环调整，使最后尽可能形成一个环路。
三条环路如下图4所示：
线路如下：北京 →吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 (时间为88/9+8*2=25.777778)
北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 →北京(时间58/9+6*2=18.444444)北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。(时间68/9+10*2=27.555556)
总的时间为25.777778+18.444444+27.555556=71.77777 三、问题三的模型建立与求解
根据题目和假设，假设两城市之间运输的价格=权（1）*2500+平均指数*5000（单位：价格）
北京到新疆A1A5权（1）是23，北京的指数为1.9，上海为1.2，则先求出平均指数（1.9+1.2）/2=1.55，根据公式可得
北京到新疆A1A5关于时间的运输价格的权为23*2500+1.55*5000= 65250（小时），其他各城市间的权（3）见下
表4
针对问题一
根据最小生成树的求法根据权（3）求出改图G 的最小生成树如图5所示： 沿着最小生成树的路线相对较短，为：A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A5—A4—A5—A2—A13—A16—A7—A6—A17—A15—A1—A10—A9—A14—A9—A10—A1
经过观察上面下划线的部分并A5—A12—A5—A4—A5—A2—A13—A16不是最短的，经计算这个路线A5—A12—A4—A15—A13—A16比上一段的要短，故用它替换上一段，这里经过了A15，那从A17可直接到A1，不用再经过A15，故A7—A6—A17—A15—A1这段可用A7—A6—A17—A1来替换，A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A4—A15—A13—A16—A7—A6—A17—A1—A10—A9—A14—A9—A10—A1，由于这条路径最后一段，A20，和A9都重走了，故可对路径进行重组，依据线路最短和经过两次的城市最少的原则，经过综合分析，得出最优的路径为
A1—A17—A6—A7—A16—A13—A15—A4—A12—A5—A2—A11—A3—A18—A8—A19—A20—A19—A9—A14—A9—A10—A1。
可以将相邻两点的权（3）相加，和为总花费，最少为584250元。 针对问题二
把各个城市间的航线示意图抽象为一赋权连通图G (V , E ) ，在权图G 中，v i ∈v (G ) 对应的示意图中各个货物需求地，v 0表示北京，e j ∈E (G ) 对应图中的航线，边权w (e j ) 对应示意图中的航线长，将航线长及在各个城市停留的时间都转化相应的花费Z (即权（3）。
建立的数学模型如下：
e )
i
∀e ∈E (G ) ，∃w (e ) ∈N ，∃v ∈v (G ) ，∃w (v ) ∈|V *T , |v 0∈V (G ) ，
求G 中回路L 1, L 2,......, L k (k >) ，使得满足：
（1）
v
k
∈V (L i ), i =1, 2,......, k
；
（2） V (L i ) =V (G ) ；
i =1
n
（3）∑∑
min （目标为飞行总的花费最少）。 2、模型求解
i =1e ∈E (L )
Z (e i ) =min（目标为总花费最少）；或m ax |
∑
e ∈E (L )
Z (e i ) +
∑
t ∈V (t )
Z (v ) |=
由分析得此货机至少要回去取货二次，相当于把图G 分成三个子图G i (i =1, 2, 3) ，在每个子图G i 中寻找最佳回路L i (i =1, 2, 3) 。
现要对已经得到的最小生成树进行分解，以获得三个子图G ，使得分解的每一组的各个城市需求和不超过50件货物，并且尽量使每一组的线路最短。从而根据最小生成树的分解方法把图G （V ，E ）划分为三个子图G i , i =1, 2, 3，分别在G i 中寻找最佳航线。
依据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找最优的分块结果，在G i , i =1, 2, 3，中分别寻找一条从北京出发，遍历V 并回到北京的最短路线。在G （V ，E ）中求三条从北京O 出发并回到北京O 的路L 1, L 2, L 3，依据的步骤如下，做出G 和O 之间的最短路；以O 与G 连通的路径及原图G 的最优树在G i 中保留的边为基础，进行增环扩环调整，使最后尽可能形成一个环路。
线路如下：北京 →吉林 → 黑龙江 → 内蒙古 → 新疆 → 西藏 → 云南 → 河南 → 北京 → 重庆 → 广西 → 海南 → 湖南 → 香港 →北京 → 重庆 → 青海 → 甘肃 → 宁夏 → 江苏 → 福建 → 上海 → 台湾 → 上海 → 北京。
总的费用为711750（元）
§7 模型的评价与推广
一、模型的优缺点
1、优点：
〔1〕. 本文的三个问题，给出了在各种约束条件下的最短时间以及最少花费的计算方法，具有较强的实用性和通用性，可用于日常生活中；
〔2〕. 在忽略其他条件限制的最短时间问题中，我们采用最小生成树方法进行求解，并用了枚举法进行验证，经过大量的计算使结果更准确，更符合实际情况，从而达到解决实际问题的目的；
〔3〕. 采用枚举法对问题结果进行验证，使计算结果更加准确，更符合实际；
〔4〕. 对于加入了省辖市需求量的问题当中，我们在第一问的基础上，计算出北京到
各个城市间的最短距离，并再次利用最小生成树的方法，进行计算验证得出结果，解决实际问题。
〔5〕. 在本题目的最后一问当中，给出了计算在货物体积和重量等多个限制条件下的最优化解法，采用最小生成树算法解决了这个与实际问题非常接近的问题，具有很好的实际意义。
2、缺点：
〔1〕. 本题中为使问题便于研究，我们做了许多假设，这或许对模型的实际意义产生影响；
〔2〕. 本问题并非线性优化问题，加之节点过多，需要到量的精密计算，多次重复因此很难做到求出的结果就是最优解，只是相对较优的结果；
〔3〕. 本为题所建立的模型，本省舍弃了某些因素的影响的结果，但会使所求结果与实际生活产生偏差。
七．模型的推广
本文依据所研究的问题建立了三个模型，这三种模型对于许多数学问题的解决方法和途径都有一定的帮助。
第一问中利用最小生成树的方法来解决的，此种优化方法可用来指导现实生活中所遇到的许多问题，如：旅游最短线路问题、货物运送问题、邮递问题以及管道输水等等一些实际问题。求解这些问题可以参考最小生成树方法，再利用枚举法经过大量的计算可得出非常接近最优解。
第二问中是加入了限制条件的运货最优问题，利用赋权连通图，并根据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找到最优的分块，再利用最小生成树方法求解在有需求量约束的前提下最短线路的模型，然后综合比较得出符合要求的较优的线路。在日常生活中，可以利用该模型来求解与最优树和最大流量有关的实际问题。
在第一问和第二问的基础上所延伸出来的第三个问题也可以采用该算法解决实际问题。这类问题在实际生活中随处可看见，且都可以应用这些模型进行解决。在将实际问题抽象为具体数学问题的时候，根据数学建模的思想以及步骤，会做出一定的假设，因此会导致一定的误差，因此不同的实际问题，要根据具体情况认真考虑，得出最优的设计方案，对于解决实际问题具有很重要的意义
参考文献
[1] 李庆扬，关治，白峰衫 . 数值计算原理 . 北京：清华大学出版社 , 2000；
[2] 刘来福，曾文艺. 数学模型与数学建模（第二版） . 北京：北京师范大学出版社， 2002；
[3] 蔡锁章 . 数学建模原理与方法 . 北京：海洋出版社， 2000； [4]王勇，池洁，物流配送路线及配送时间的优化分析 2010-6-4；
[5]吴群妹，实际配送中多个配送点闭回路最短路径的选取， 2010-6-4； [6]郭亚军 , 综合评价理论与方法 [M]. 北京：科学出版社 ,2002；
[7]池洁，李莉，物流中配送区域与配送路线的网络优化法， 2010-6-4 ；
源程序
M=1000; a=zeros(20);
a(5,12)=8;a(5,2)=6;a(5,4)=11;a(4,12)=12;a(2,11)=4;a(3,11)=2;a(1,5)=23; a(5,14)=20;a(5,15)=22;a(2,13)=8;a(13,16)=7;a(7,16)=2;a(6,7)=3;a(6,17)=2; a(4,15)=15;a(1,6)=21;a(1,17)=24;a(8,18)=4;a(8,19)=3;a(1,10)=8; a(13,15)=12;a(3,18)=10;a(1,15)=12;a(1,13)=20;a(1,19)=9; a(14,9)=11;a(10,9)=2;a(18,9)=15;a(19,9)=17; a(20,19)=4;
a=a+a';a(find(a==0))=M; for i=1:20 a(i,i)=0; end
result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp);
[jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1));
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result