12 3 / 3 页下一页

查看: 102966|回复: 26

跪求关于最短路径的历年建模题~~附答案更佳

[复制链接]

字体大小: 正常放大

aopao

2 主题	3 听众	16 积分

升级 11.58%

该用户从未签到

自我介绍: 该生品学兼优，乐于助人，同时乐于向他人求助，是个合格的学生

电梯直达

1^#

发表于 2010-5-13 15:53 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

小女子因为在做一个带装载量**的车辆最短路径VRP，求历年的相关建模试题，能否参考一下。
各位高人，强人，过路的帮帮忙啊！~~

zan

转播0 淘帖0 分享0 收藏0 支持1 反对0 微信

使用道具举报

liujianye2006

0 主题	2 听众	10 积分

升级 5.26%

该用户从未签到

2^#

发表于 2010-5-13 16:05 |只看该作者 |招呼Ta 关注Ta

回复 1# aopao

顶一下！

我也说一句

发表

使用道具举报

苏大侠431

0 主题	3 听众	12 积分

升级 7.37%

该用户从未签到

自我介绍: 我是一名普通的本科生，加入该网站只要是为了扩大自己的视野，接受更多的知识。谢谢指导！！

3^#

发表于 2010-5-13 23:26 |只看该作者 |招呼Ta 关注Ta

不好意思！！！鄙人貌似帮不上忙了= =！！

我也说一句

发表

使用道具举报

kelenanhai

0 主题	3 听众	67 积分

升级 65.26%

该用户从未签到

自我介绍: 真诚与大家一道共同探讨,共同进步.

4^#

发表于 2010-5-14 09:23 |只看该作者 |招呼Ta 关注Ta

我也想要啊。。。。。。。。。。。。。。。。。。。。。。

我也说一句

发表

使用道具举报

kelenanhai

0 主题	3 听众	67 积分

升级 65.26%

该用户从未签到

自我介绍: 真诚与大家一道共同探讨,共同进步.

5^#

发表于 2010-5-14 09:24 |只看该作者 |招呼Ta 关注Ta

谁有能否分享一下。。。。。。。。。。。

我也说一句

发表

使用道具举报

qklk111

0 主题	3 听众	7 积分

升级 2.11%

该用户从未签到

自我介绍: 喜欢篮球

6^#

发表于 2010-5-15 01:46 |只看该作者 |招呼Ta 关注Ta

给大家都看看。好像都在准备好好学习学习

我也说一句

发表

使用道具举报

zhangweijianmo

0 主题	3 听众	16 积分

升级 11.58%

该用户从未签到

自我介绍: 我爱吃鱼

7^#

发表于 2010-5-16 19:55 |只看该作者 |招呼Ta 关注Ta

我也想要啊！可是好像都找不到。。。。。。。。。。。。。

我也说一句

发表

使用道具举报

zhonghang

11 主题	3 听众	463 积分

TA的每日心情

	无聊 2011-11-13 15:21

签到天数: 42 天

[LV.5]常住居民I

自我介绍: 我是一个男孩啊！欢饮啊

群组: 湖南大学数学建模

群组: Matlab讨论组

群组: 西南大学建模组

群组: 数学建摸协会

群组: 数学建模保研联盟

8^#

发表于 2010-5-20 23:25 |只看该作者 |招呼Ta 关注Ta

全国第四届研究生数学建模竞赛
题目    邮政运输网络中的邮路规划和邮车调度
摘    要
本文研究的是合理简化后的某地区邮政网络中的邮路规划和邮车调度问题，本文通过深入分析，针对提出的问题建立了相应的组合优化模型，并利用图论的相关知识结合多种现代优化算法进行求解，每个问题都得到了比较满意的结果。
问题一首先需要对车辆数进行规划，是一个广义多旅行商模型，其目标为邮车数量最少而不是行程最短，而且约束条件比较复杂。不可能直接求解，通过建立合理的准则对节点进行分组并经过分析将问题最终转化为求解节点数较少的且较易求解的以路程最短为目标的单旅行商问题，然后采用遗传算法对分组进行调整并寻优，提高了算法的效率和效能，计算结果表明，该县最少需要3辆邮车即可满足运输要求。进一步在给定邮车数量的基础上，以空载带来的损失最小为目标建立新的多旅行商模型，采用启发式方法与遗传算法相结合的方法进行求解，得到一个满足所有约束的损失较小的邮路规划，最小损失费用为62.9元。
问题二可以归结为一个多目标且具有复杂约束的多旅行商问题，基于贪婪算法的思想，将问题转化为单目标规划问题，并根据实际情况分阶段进行邮路和邮车数量的规划，使得该区的邮路数为12条，总运行成本为6585元。
问题三是在问题二的基础上改变了部分约束条件，通过制定合理的支局划分标准，重新对县局所辖区域进行划分，然后采用问题二的方法对邮政网络进行规划并寻优，使得总运行成本减少到6633元。
问题四是基于不固定根节点的最小生成树的多旅行商问题，通过制定合理的准则给出可能新县局地址的集合，从中选定新县局地址，采用问题二的方法进行规划并寻优，找到11条邮路的比较优的解，总成本减少到6237元，减少全区的邮路数和总运行成本，对构建快速、经济的运输网络起到了一定的作用。并给出了合理的建议。
关键词：旅行商问题  邮路  调度  最小树  贪婪算法

参赛队号  9005906                   参赛学校    第二炮兵工程学院
参赛队员姓名李明雨  张大巧  陈摩西

1、问题的提出
某地区邮政机构分地市中心局、县级中心局和支局**，邮政运输网络由区级邮政运输网和县级邮政运输网构成（邮政局、所分布如图1所示），有既定的邮政运输流程和时限规定，为了在缩短邮件运输时限和降低成本的同时，节约能耗和人力资源，提高邮政行业的服务质量和信誉，切实提高我国邮政的运行效益，保持邮政行业的竞争能力和取得良好的社会效益。需要解决以下问题：

图1
问题一，以县局X1及其所辖的16个支局为研究对象，邮政运输流程和时间**要求区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，已知该县每个支局要收发的邮件数量，问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，考虑空载开来的收入减少进行邮路规划和邮车运行的安排以提高邮政运输效益。
问题二，考虑每条邮路只需要一辆邮车即能满足运载能力要求并且邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定的条件下，采用尽可能少、尽可能短的邮路来降低全区邮政运输网的总运行成本。问应如何构建该地区的邮政运输网络，并给出邮路规划和邮车调度方案。
问题三，考虑到部分县与县交界地带的支局，其邮件由邻县县局负责运送可能会降低全区的运行成本，带来可观的经济效益。若允许在一定程度上打破行政区域的**，能否给出更好的邮路规划和邮车调度方案？（在此同样不必考虑邮车的运载能力的**，每条邮路的运行成本为3元/公里）
问题四，县局选址的合理与否对构建经济、快速的邮政运输网络起到决定性的作用。假设图2中县局X1，……，X5均允许迁址到本县内任一支局处，同时原来的县局弱化为普通支局。设想你是该地区网运部门负责人，请你重新为各个县局选址，陈述你的迁址理由并以书面材料形式提交省局网运处。
2、模型的假设与符号说明
2.1 模型假设
1、假设不考虑邮件中快件、普件之分。
2、假设区县局都能保证所需车辆。
3、假设不考虑同一个邮路中重复经过点的卸装邮件耗时。
4、区局不再另行安排车辆专门负责区局所辖支局邮件的收发。
5、问题一中，假设当天需收发的邮件数量为一定值，不考虑当天邮件数量随时间的变化；
6、问题二、三、四中假设邮车有足够的运力，不考虑邮件数量的约束。
7、邮车运行速度不受外界环境影响。
8、每条邮路只安排一辆邮车。
2.2 符号说明
——所有区、县局和支局所在点构成的赋权图；
——所有区、县局和支局所在点构成的完备赋权图；
——图中邮局间的公路里程；
——图的矩阵表示；
为需用邮车数
2.3 定义
定义1：邮路：邮政运输网络中邮车由某区级或县级邮局出发再回到该邮局的线路称为邮路。
定义2：推销员邮路：经过图中每个点至少一次的邮路。
定义3：交接点：在整个邮件运输过程中，进行邮件装卸的运输站点。
3、问题一的分析、建模与求解
3.1 问题的分析
本问题首先要求邮车数量进行规划，目标是邮车数量最少，受到的约束有：
一是地区的邮政运输有一定的流程和时限规定，根据这些规定县局邮车最早在09:00出发，且必须在15:00之前返回，这就要求县局每个邮路邮车从出发到返回所用的时间应该小于6个小时，且邮车行驶时间不仅要考虑行驶路程耗时，还要考虑邮路上在支局装卸邮件的耗时；
二是有各支局需收发邮包数量的**和县级邮车有运量的**，使得最小邮路数量（即从县级邮局出发到支局并回到县局的班次）最少为三次，（考虑到一辆县级邮车在一个工作日内有可能能够在实现内连续跑完一条以上的邮路，所以3不一定是所需邮车数量的下限）。各支局需要收发的邮包数量不同还会影响到邮车与邮路上支局发生交接的先后顺序；
三是要求根据邮车数量规划出的全部邮路能覆盖该县局所辖的16个支局。这是一个规划目标为旅行商数目的多旅行商的问题。
其次要求根据最小车辆数进一步对邮路进行规划，目标是使空载带来的收入减少量最少，约束条件同上，考虑到邮路对各支局的遍历性，这也是一个多旅行商问题。
3.2 模型的建立与求解
3.2.1 有关最少车辆数的模型建立与求解
通过以上分析，可以首先建立如下模型：
目标：（为需用邮车数）
   ；
   ；
县局出发的邮路遍历本县辖区内所有支局。
其中，为各邮车在邮路上的总耗时，  （为第j辆县级邮车在一个工作日内所行使的里程），为县局卸装邮件耗时，为县局卸装邮件耗时，为第辆邮车出发点、终点外途中经过县局的次数（考虑到一辆邮车有可能能够在一个工作日内连续跑完两条以上的邮路），为第条邮路上经过支局的交接频次。为邮车上的邮包数量；
这个模型是一个以旅行商数量最少为目标的具有复杂约束的多旅行商模型，需要借助图论的有关知识进行求解，首先建立网络图，其中，县局X1和各支局Z1, Z2, ……, Z16为图2的17个点，邮局间的直达公路为图的边。我们考虑弧上的权和节点权，把两个局之间的公路里程看作对应边的权，把在各邮局装卸邮件的时间作为该支局所在点的节点权。此图为一个赋权图。将没有公路连接的两个邮局之间的公路里程设为一个常数（），这样可以构造出完备图。建立一个17维的矩阵来描述图，矩阵中的参数为图各边上的权值。所给邮政网络就转化为图论中的加权网络图，问题就转化为一个图论问题，即在给定的加权网络图中寻求最少的邮路，各邮路要求满足时限约束、运量约束和邮件数量约束，并且各邮路总和要行遍所有顶点至少一次。本模型难以直接求解，考虑到邮车数量由邮路的数量及邮路的耗时所决定（一辆邮车有可能能够在时限内跑完两条以上的邮路），又根据邮车运量和需要运送的邮包数量的**，至少需要3条邮路才能完成当日邮包的运送，我们先固定邮路的数量为3进行讨论，从而将问题转化为求解以行程最短为目标的具有复杂约束条件的多旅行商问题，这是一个NP问题，在节点数较多的情况下无法直接寻求最优解，针对这种情况，考虑首先根据合理的准则对支局进行分组，进而将问题转化为求节点数不超过6的单旅行商问题，从而很容易寻求局部的最优解，然后用遗传算法调整分组情况并进行寻优，具体步骤如下：
Step1、对图可以分别用克鲁斯卡算法和狄克斯特拉算法求出以X1为根节点的最小生成树和各点到根点的最短路，结果如图2所示。

图2 以X1为根节点的最小生成树与各点到根点的最短路示意图
Step2、基于算出的最小生成树和最短路，依据一定的原则对图中X1以外的点进行分组；
根据实际工作的经验及以上分析，我们遵循如下原则对顶点进行分组：
准则一：尽量使同一干枝上及其分枝上的点分在同一组;
准则二：应将相邻的干枝上的点分在同一组;
准则三：尽量将长的干枝与短的千枝分在同一组；
准则四：每一组点对应的邮包数量的总合应满足邮车运量的**.
Step3、基于以上分组将图划分成相应的子图；
基于上述分组准则和最小生成树，我们将图划分为三个区域，可能的分组方式中顶点数量最大为6个，最小为3个，
Step4、在划分好的每一组顶点中加入X1构成相应的子图，并在此基础上寻求遍历子图中所有点并且满足邮政运输流程和时限以及邮件数量和邮车运量等约束条件的最短回路（从而将问题转化为节点数量较少的以行程最短为目标的单旅行商问题）；
分别在三个分组内找出满足各支局邮件数量和邮车运量**且时间最短的回路，称为各分区的最佳邮路。
车1 路线S1：X1—Z4—Z3—Z2—Z1—Z13—X1，寄达支局的邮件数量为51，支局收寄的邮件数量为51；每段路上的邮件袋数为：X1—Z4：51，Z4—Z3：52，Z3—Z2：51，Z2—Z1：51，Z1—Z13：52，Z13—X1：50。满足运量要求。
车2 路线S2：X1—Z4—Z5—Z10—Z9—Z8—Z7—Z6—Z4—X1，寄达支局的邮件数量为61，支局收寄的邮件数量为54；每段路上的邮件袋数为：X1—Z5：61，Z5—Z10：57，Z10—Z9：52，Z9—Z8：54，Z8—Z7：59，Z7—Z6：61，Z6—Z4：65，Z4—X1：65。满足运量要求。
车3 路线S3：X1—Z14—Z15—Z16—Z15—Z11—Z12—X1，寄达支局的邮件数量为64，支局收寄的邮件数量为65；每段路上的邮件袋数为：X1—Z14：64，Z14—Z15：58，Z15—Z16：55，Z16—Z15：57，Z15—Z11：57，Z11—Z12：50，Z12—X1：55。满足运量要求。
路线S1需时间TS1=5.4小时<6小时，符合要求；
路线S3需时间TS2=5.6小时<6小时，符合要求；
路线S3需时间TS3=5小时<6小时，符合要求；
邮路规划图如图3所示：

图3 初始邮路示意图
以上结果表明最少需要三条邮路可以在工作日内完成邮件的运送，而且不可能合并其中的两条由一辆邮车跑完，因此该县至少需要3辆邮车就可以完成邮件的运送。
3.2．2考虑空车率的模型建立与求解
下面对派出3辆邮车的条件下空车率带来的收入减少量进行规划，建立如下模型：
目标：
：；
   ；
县局出发的邮路遍历本县辖区内所有支局。
其中，为空载率带来的总损失；
为第辆邮车在其邮路上经过的支局数；；
为第辆邮车从其邮路上的第个邮局出发时的装载量；
为第辆邮车从其邮路上的第个邮局出发时到个邮局行驶的路程；特别地时，。
这是一个NP问题，需要借助启发式算法进行求解，考虑到，我们采用遗传算法，进行邮路内部路线的优化以期降低收入损失：
(1) 初始解
把上述找到的三条邮路作为本问题的初始解，根据初始路线计算各条路线的损失收入量的值为：
S1路线损失收入为52.2154元；
S2路线损失收入为17.5692元；
S3路线损失收入为40.7692元；
共计损失收入为：110.5538元。
(2)编码与适应度函数
本文以n个交接点的遍历次序为遗传算法的编码，如：交接点序列，d1，d2，…,d9，其编码为：1 2 3 …9；约束条件为：每交接点经过且只经过一次；初始群体为随机产生，适应度函数为以交接点为图顶点的哈密尔顿圈的长度的倒数。
即：
(3)选择机制
在初始群体的基础上，执行遗传算法。随着算法的执行，保留m个较优的个体作为样本，以供选择。在每一代运算过程中，个体被选中的概率与群体中的相对适应度成正比。
(4)交叉策略
本问题如果采取简单的一点交叉或多点交叉策略，必然导致未能完全遍历的非法结果。如：两父线路
1 2 3 4 5 | 7 8 9
8 7 6 5 3 | 2 1 9
若采取两点交叉，且交叉点随机选为5，则产生的两后代为：
1 2 3 4 5 2 8 9
8 7 6 5 3 7 1 9
则其过程显然错误。
为处理这一问题，可采取构造惩罚函数的方法，但试验效果不佳。实际上是使本来复杂的问题更加复杂化。为解决这一问题，目前有常用的几种方法：PMX( Partly matched crossover，部分匹配交叉法)，OX(Order crossover，顺序交叉法)，CX(Cycle crossover，循环交叉法)。
(5)交叉方法
由于PMX法趋向于所期望的交接点的绝对位置，比较符合邮政运输的实际情况，所以本文采用PMX法：
a.先根据均匀随机分布产生两个位串交叉点，定义这两点之间的区域为一匹配区域。如：
E=9 8 4 | 5 6 7 | 3 2 1
F=1 2 3 | 4 5 6 | 7 8 9
b.使用位置交换两个父串的匹配区域。交换E和F的两个匹配区域，得到：
E’=9 8 4 | 4 5 6 | 3 2 1
F’=1 2 3 | 5 6 7 | 7 8 9
c.对于两子串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系，逐一进行交换。对于E’有4到5，5到6，6到7的位置符号映射，对E’的匹配区外的4，5，6分别以5，6，7替换，如再出现重复，循环替换，如E中的4，替换过程为4—5—6—7。对于F’同理，得到：
E’’=9 8 7 | 4 5 6 | 3 2 1
F’’=1 2 3 | 5 6 7 | 4 8 9
由于单条线路的交接点个数一般不会超过500，而且变异的概率比较小，所以不必考虑变异。
(6)程序设计流程图
根据上述计算方法，作者用matlab软件进行了邮路优化程序设计，其流程如图4所示：

图4、遗传算法流程图
(7)结果
车1 路线为S1：X1—Z4—Z5—Z2—Z3—Z1—Z13—X1，损失收入为19.3231元；
车2 路线为S2：X1—Z4—Z6—Z7—Z8—Z9—Z10—X1，损失收入为28.8923元；
车3 路线为S3：X1—Z12—Z11—Z15—Z16—Z15—Z14—X1，损失收入为14.7077元；
总损失收入量为62.9231元。

图6 收入减小量最小的邮路示意图
4、问题二的分析、建模与求解
4.1 问题的分析
本问题要在遵循该地区的邮政运输流程和时限规定且要遍历所有邮局的条件下，使全区邮政运输网的运行成本最低。
由于本问题假设运输成本只与邮车数量和里程有关，因此降低运行成本的途径是用尽可能少、尽可能短的邮路完成邮件运输。这里要考虑两层的运输网络的规划，包括区级邮局到县级邮局邮路的规划和县级邮局到本县各支局的邮路规划。区级邮局到县级邮局的邮路要求必须遍历该地市辖区内的16个支局以及5个县局。县局到该县各支局的邮路选择要求遍历该县除区级邮车经过的各支局外的其它所有支局。根据运输流程和时限规定，区级邮车经过一条邮路的总耗时应该小于5个小时，总耗时包括路上行驶时间和到达县局及各支局的卸装邮件耗时；由于第一班区级邮车必须在早6:00后出发，第二班必须在18:00前返回，只考虑这个因素，供县局邮车使用的时间有12 个小时，而区级邮车到县局后经过1小时的处理时间县局邮车才能出发，县局邮车能用时间还剩（12－1－区级邮车到县局耗时），再有县局邮车返回再经过一小时处理时间后区级邮车才能返回，县局邮车能用时间要继续减去1小时和区级邮车从县局返回区级邮局的时间，定义为区级邮车走完其到县的这一邮路的总耗时，包括来、回时间，以及在县局卸装的10分钟耗时。因此县级邮车经过一条邮路的总耗时应该小于。需要分两级对邮路进行讨论，先讨论区级邮局遍历各县邮局和地市辖区内各支局的邮路问题，确定出邮路以后才能确定各县级邮局的时间约束量和县级邮局不用到达的本辖区内支局，在这个约束条件下再讨论县级邮局出发到达各支局的邮路。
4.2 模型的建立与求解
根据以上分析，可以建立如下模型：
目标：；
   ；
   ；
   所有区级出发的邮路遍历15个地市辖区内支局和5个县局；
各县局出发的邮路遍历本县辖区内没有被区级邮车经过的所有支局。
其中，
为所需邮车总数；
为所需区级邮车数；
为县所第需县级邮车数；
为区级邮车所走邮路的总里程数；
为县第j条邮路的里程数；
为区级邮车走完经过第个县局的邮路需用的时间；
为第个县的县级邮车走完本县内第条邮路需用的时间。
此问题是一个多目标具有复杂约束的多旅行商问题，首先需要转化为单目标规划问题来进行求解。考虑到在对邮政运输成本的影响因素中邮车数量的影响在一定程度上要大于里程数的影响（受邮政运输流程和时限的约束每条邮路的里程数不会太大），因此我们采用贪婪算法的思想，首先满足车辆数最少再寻求里程数最短，从而将多目标规划转化为单目标规划。同时，由于需要同时考虑区级和县级邮政网络，根据既有邮政运输流程，县局邮车所需遍历的支局数决定于区级邮车的邮路，因此需要分区级和县级两层先后进行规划。
4.2.1 区到县邮路规划问题的建模与求解
本问题中县级邮局邮路上的时间约束和要遍历支局个数约束受到区级邮局邮路变化的影响，因此，在求解该问题时要先对区级到县级邮路进行规划，再对县级邮局到支局的邮路进行规划，对应的模型为：
目标：；
   ；
   所有区级出发的邮路遍历15个地市辖区内支局和5个县局。
其中，
为所需区级邮车数；
为区级邮车所走邮路的总里程数；
为区级邮车走完经过第个县局的邮路需用的时间。
本模型不是一个纯粹的多旅行商问题，主要是要遍历的顶点不确定，为了尽量县局邮车的工作量，应该尽量使区局邮车尽量多地经过其邮路附近的县级支局，因此需要对模型进行改进，进行求解。
我们的方法是：
Step1、用问题一中使用的算法和编写的程序求出图以D为根节点的最小生成树和D点到X1，X2，X3，X4，X5的最短路，结果如图7：

图7
Step2、依据得到的最小生成树和最短路，依据一定的原则，对图中地市辖区范围内的支局和5个县局这21个顶点进行初始分组。
根据对问题的分析和对此类问题的研究，确定分组的原则为：
准则一：尽量使同一干枝上及其分枝上的点分在同一组；
准则二：应将相邻的干枝上的点分在同一组；
准则三：尽量将长的干枝与短的干枝分在同一组；
Step3、按上面的分组情况，每一组顶点中加入D构成相应的子图，在子图中找出满足约束的邮路。
这里容易考虑到沿最短路以及最短路连接的最小树上的干枝找出满足约束的初始邮路。找到初始邮路后为了达到最终目标，这里考虑邮路要尽可能多的经过支局，以减少派车需要多走的路程。因此要在满足时间约束的条件下尽可能多的把县辖区内的支局加入邮路。
Step4、用贪婪算法实现这一过程。找到一个子图里的最优解。
Step5、综合考虑这些邮路，用禁忌搜索的算法进行子图间的调整，把子图附近的点或者有最小生成树干枝连接的点作为候选集，把搜完被选集作为终止条件，编写程序进行计算可以得到最佳的区级邮车到各县的邮路规划。
4.2.2 县局到所辖支局邮路规划问题的建模与求解
下面再对各县局到其辖区支局的邮路进行规划，去掉区级邮车经过的支局，每个县的各个支局与县局构成一个图，要求从县局出发经过个支局至少一次，问题就变为一个有约束条件的多旅行商问题。
其模型为：
目标：；
   ；
   ；
   各县局出发的邮路遍历本县辖区内没有被区级邮车经过的所有支局。
其中，
为县所第需县级邮车数；
为县第j条邮路的里程数；
为区级邮车走完经过第个县局的邮路需用的时间；
为第个县的县级邮车走完本县内第条邮路需用的时间。
根据区级邮局到该县的邮路耗时可以确定县局有成走完一条回路的时间要求，问题分析中已给出计算公式。
针对每个县构成的新图进行讨论和求解，步骤如下：
Step1、采用用克鲁斯卡算法和狄克斯特拉算法生成每个新图的以县局为根节点的最小生成树和各图中各支局到县局的最短路。
Step2、基于得到的最小生成树和最短路，依据一定的原则对图中除县局外的顶点进行分组；分组后构成多个子图。
准则一：尽量使同一干枝上及其分枝上的点分在同一组；
准则二：应将相邻的干枝上的点分在同一组；
准则三：尽量将长的干枝与短的干枝分在同一组；
准则四：在符合约束的条件下尽可能少的分组；
Step4、对每个子图求最佳推销员回路。
Step5、调整子图周边的一些点，使一个县区域内邮路最优。
这样可以得到一组各县的邮路规划路线。
4.2.3 全区邮路组合选优问题的求解
把前面讨论得到的结果作为全区邮路规划的初始解，对前面所编禁忌搜索的程序进行调整，依据一定的原则选取一些点作为候选集，进行搜索，可以得到一组优化解:
一、13条邮路线的求解
1、邮路规划如图8：

图8 全局最优邮路安排图
全区分为13个邮路，区到县有5条邮路，县X1内有2条邮路，县X2内有2条邮路，县X3内没有邮路，县X4内有1条邮路，县X5内有3条邮路，分别如下：
区到县的邮路为：

路线耗时（分钟）里程（km）备注
D S1：D—Z62—Z16—Z15—Z14—X1—Z12—Z17—Z12—Z11—Z62—D 287.7692 263
S2: D—Z66—Z63—Z18—X2—Z27—Z28—Z31—Z29—Z64—Z65—Z67—D 298.1538 258
S3: D—Z69—Z30—Z33—X3—Z33—Z32—Z34—Z35—Z71—D 298.4615 280 经过Z35但不卸装邮件
S4: D—Z72—Z73—Z42—Z41—X4—Z36—Z35—Z70—Z68—D 252.1538 219
S5: D—Z61—Z58—Z52—X5—Z53—Z52—Z59—Z60—D 288.3077 269
县X1 S6:
X1—Z13—Z1—Z2—Z3—Z4—X1 259.0 117
S7: X1—Z5—Z6—Z7—Z8—Z9—Z10—X1 248.0 109
县X2 S8：X2—Z19—Z20—Z26—Z25
—Z21—X2 256.0 118 经过Z21但不卸装邮件
S9：X2—Z21—Z22—Z23—Z24
—Z25—Z21—X2 274.0 127 经过Z25但不卸装邮件
县X4 S10：X4—Z37—Z38—Z39—Z40
—Z43—X4 305.0 140
县X5 S11：X5—Z54—Z55—Z56—Z57
—Z54—X5 284.0 132
S12：X5—Z50—Z49—Z48—Z47
—Z45—Z47—Z51—X5 291.0 133 经过Z51但不卸装邮件
S13：X5—Z51—Z46—Z44—Z46
—Z51—X5 303.0 144
总计 2309

由上述S1，S2，S3，S4，S5邮路的耗时可得到各县局邮路的时间约束为：X1：322.2308分钟，X2：311.8462分钟，X3：311.5385分钟，X4：357.8462分钟，X5：321.6923分钟。S6，S7，S8，S9，S10，S11，S12，S13每条邮路的耗时都小于其时间约束。
2、邮车调度安排如下：
根据区级邮车在每个邮路上的到达县局和从县局返回需用的时间对邮车进行调度：
往返时间如下：
S1：去时间：109.5385分钟  回时间：168.2308分钟
S2：去时间：97.1538分钟回时间：191分钟
S3：去时间：144.2308分钟  回时间：139.2308分钟
S4：去时间：98.4615分钟回时间：143.6923分钟
S5：去时间：129.4615分钟  回时间：148.846分钟
区级到各县局的第一班次邮车出发时间为6:00，第二班车到县X1的出发时间为12:22，到县X2的出发时间为12:11，到县X3的出发时间为12:11，到县X4的出发时间为12:57，到县X5的出发时间为12:21，这样可以保证邮车不在县局做多余等待；县X1的邮车出发时间为8:50，县X2的邮车的出发时间为8:38，县X4的邮车出发时间为8:39，县X5的邮车出发时间为9:10。
3、邮路费用计算结果为：需要的运行成本为：6927元。
二、12条邮路安排：
12条邮路的计算结果如下表所示：
表1
路线耗时（分钟）里程（km）备注
D S1：D—Z62—Z16—Z15—Z14—X1—Z12—Z11—Z62—Z59—Z61—D 276.1539 245
S2: D—Z66—Z63—Z18—X2—Z27—Z28—Z31—Z29—Z64—Z65—Z67—D 298.1538 258
S3: D—Z69—Z30—Z33—X3—Z33—Z32—Z34—Z35—Z71—D 298.4615 280 经过Z35但不卸装邮件
S4: D—Z72—Z73—Z42—Z41—X4—Z36—Z35—Z70—Z68—D 252.1538 219
S5: D—Z61—Z58—Z52—X5—Z51—Z46—Z44—Z60—D 299.0 286 Z51、Z61不卸装邮件
县X1 S6:
X1—Z13—Z1—Z2—Z3—Z4—X1 259.0 117
S7: X1—Z5—Z6—Z7—Z8—Z9—Z10—X1 248.0 109
县X2 S8：X2—Z17—Z19—Z20—Z26—Z20—X2 302.0 141
S9：X2—Z21—Z22—Z23—Z24
—Z25—Z21—X2 274.0 127
县X4 S10：X4—Z37—Z38—Z39—Z40
—Z43—X4 305.0 140
县X5 S11：X5—Z54—Z55—Z56—Z57
—Z53—X5 305.0 140
S12：X5—Z50—Z49—Z48—Z47
—Z45—Z47—Z51—X5 296.0 133
总计 2195
可得到总费用为：2159×3=6585元
由上述S1，S2，S3，S4，S5邮路的耗时可得到各县局邮路的时间约束如下表2：
表2各县邮路的时间约束表
县局县X1 县X2 县X3 县X4 县X5
时间约束（分钟） 333.8462 311.8462 311.5385 357.8462 311.0
S6，S7，S8，S9，S10，S11，S12，S13每条邮路的耗时都小于其时间约束。
2、邮车调度安排如下：
根据区级邮车在每个邮路上到达县局和从县局返回需用的时间对邮车进行调度，这里考虑区级第二班次调度时间时，基于使区级邮车不在县局做多余等待的原则。
往返时间和邮车调度安排如表3、4：
表3区级邮车到各县往返时间表
S1 S2 S3 S4 S5
D到X行驶时间（分钟） 109.5385 97.1538 144.2308 98.4615 124.4615
X到D行驶时间（分钟） 156.6154 191 139.2308 143.6923 164.5385
表4邮车调度安排表
邮车出发时间邮车出发时间
S1邮路上第一班邮车 6:00 S1邮路上第二班邮车 12:33
S2邮路上第一班邮车 6:00 S2邮路上第二班邮车 12:11
S3邮路上第一班邮车 6:00 S3邮路上第二班邮车 12:11
S4邮路上第一班邮车 6:00 S4邮路上第二班邮车 12:57
S5邮路上第一班邮车 6:00 S5邮路上第二班邮车 12:11
S6 S7邮路上邮车 8:50 S8 S9邮路上邮车 8:38
S10邮路上邮车 8:39 S11 S12邮路上邮车 9:05

最优规划邮路如下图9所示

图9 最小费用的最优邮路示意图
5、问题三的分析、建模与求解
5.1 问题的分析
本问题在问题二的基础上引入新的影响因素，即考虑在一定程度上可以打破行政区域的**，这就意味着各县局出发的邮路不仅不必遍历本县辖区内没有被区级邮车经过的所有支局，还可以经过邻县的支局并与之发生交接。因此模型中有关县局邮车的遍历性的约束条件变为所有的县局邮车合起来必须遍历各县辖区内没有被区级邮车经过的所有支局，据此建立问题三的模型如下。
5.2 模型的建立与求解
根据以上分析建立问题三的模型如下：
目标：；
   ；
   ；
   所有区级出发的邮路遍历15个地市辖区内支局和5个县局；
各县局出发的邮路遍历所有县辖区内没有被区级邮车经过的所有支局。
其中，
为所需邮车总数；
为所需区级邮车数；
为县所第需县级邮车数；
为区级邮车所走邮路的总里程数；
为县第j条邮路的里程数；
为区级邮车走完经过第个县局的邮路需用的时间；
为第个县的县级邮车走完本县内第条邮路需用的时间。
和问题二类似，本问题中县级邮局邮路上的时间约束和要遍历支局个数约束受到区级邮局邮路的选择变化的影响，因此，在求解该问题时要先对区级到县级邮路进行规划，再对县级邮局到支局的邮路进行规划。
5.2.1 区到县邮路规划问题的建模与求解
本问题的求解采用问题二中的求解方法。
5.2.2 县局到支局邮路规划问题的建模与求解
本问题的求解采用问题二中的求解方法。
由于规定县与县之间的界限可以在一定程上被打破，因此符合以下条件的支局可以考虑划归邻县管理：
(1)支局距离本县较远而据邻近县局较近，如支局44；
(2)该支局不再本县的最小树的支上，而在邻近的最小树枝上，如支局27。
5.2.3 全区邮路组合选优问题的求解
把前面讨论得到的结果作为全区邮路规划的初始解，对前面所编禁忌搜索的程序进行调整，依据一定的原则选取一些点作为候选集，进行搜索，可以得到一组优化解。
(1)采用13条邮路
根据节5.2.1的规定，考虑将点44归入县X4范围中；考虑支局27划归县X2范围。计算结果见下表5。

表5
路线耗时（分钟）里程（km）备注
D S1：D—Z62—Z9—Z10—X1—Z12—Z17—Z12—Z11—Z62—D 278.1538 258
S2：D—Z67—Z65—Z64—X2—Z19—Z18—Z63—Z66—D 272.0769 246
S3：D—Z68—Z29—Z31—Z28—X3—Z33—Z32—Z34—Z30—Z70—Z69—D 274.3077 243 经过Z69但不卸装邮件
S4：D—Z72—Z73—Z41—X4—Z36—Z35—Z70—Z71—Z69—D 243.4615 215 经过Z41但不卸装邮件
S5：D—Z61—Z59—Z58—Z52—X5—Z51—Z46—Z60—D 297.5385 279 经过Z51但不卸装邮件
县X1 S6：X1—Z13—Z1—Z2—Z3—Z4—X1 234 117
S7：X1—Z4—Z5—Z6—Z7—Z8—Z16—Z15—Z14—X1 283 127
县X2 S8：
X2—Z27—Z22—Z23—Z21—X2 222 100
S9：X2—Z21—Z25—Z24—Z26
—Z20—X2 298 139
县X4 S10：
X4—Z43—Z44—Z42—Z41—X4 250 115
S11：
X4—Z40—Z39—Z38—Z37—X4 218 99
县X5 S12：X5—Z54—Z55—Z56—Z57
—Z53—X5 305 140
S13：X5—Z50—Z49—Z48—Z47
—Z45—Z47—Z51—X5 291 133
总计 2211

如上表所示，当把县局X3的支局27划归到县局X2后，全区运行成本为6633元，全区总里程减少98公里，成本减少294元，减少了4.24%。
由上述S1，S2，S3，S4，S5邮路的耗时可得到各县局邮路的时间约束为：X1：331.8462分钟，X2：337.9231分钟，X3：335.6923分钟，X4：366.5385分钟，X5：331分钟。S6，S7，S8，S9，S10，S11，S12，S13每条邮路的耗时都小于其时间约束。
邮车调度安排如下：
根据区级邮车在每个邮路上的到达县局和从县局返回需用的时间对邮车进行调度，往返时间如下：
S1：去时间：119.3077分钟  回时间：148.8461分钟
S2：去时间：116.5385分钟回时间：145.5384分钟
S3：去时间：113.2308分钟  回时间：151.0769分钟
S4：去时间：81.0769分钟回时间：152.3846分钟
S5：去时间：137.2308分钟  回时间：150.3077分钟
区级到各县局的第一班次邮车出发时间为6:00，第二班车到县X1的出发时间为11:43，到县X2的出发时间为11:58，到县X4的出发时间为11:10，到县X5的出发时间为12:05，这样可以保证邮车不在县局做多余等待；
县X1的邮车出发时间为8:59，县X2的邮车的出发时间为8:57，县X4的邮车出发时间为8:21，县X5的邮车出发时间为9:17。调整后的运输路线图见图10所示。

图10
(2)12条邮路
根据节5.2.1的规定，考虑将点44归入县X4范围中。计算结果见下表7。
表7
路线耗时（分钟）里程（km）备注
D S1：D—Z62—Z9—Z10—X1—Z12—Z11—Z62—D—Z68—D 292.9231 274 中途经过D不卸装邮件
S2：D—Z66—Z63—Z18—X2—Z27—X28—Z31—Z29—Z64—Z65—Z67—D 298.1538 258
S3：D—Z69—Z30—Z33—X3—Z33—Z32—Z34—Z35—Z71—D 298.4615 280 经过Z35但不卸装邮件
S4：D—Z72—Z73—Z41—X4—Z39—Z38—Z37—Z36—Z35—Z70—Z69—D 280.2308 244 经过Z69但不卸装邮件
S5：D—Z61—Z59—Z58—Z52—X5—Z51—Z46—Z60—D 292.5385 279 经过Z51但不卸装邮件
县X1 S6：X1—Z13—Z1—Z2—Z3—Z4—X1 259.0 117
S7：X1—Z5—Z6—Z7—Z8—Z16—Z15—Z14—X1 289.0 127
县X2 S8：X2—Z17—Z19—Z20—Z26
—Z20—X2 302.0 141
S9：X2—Z21—Z22—Z23—Z24—Z25—Z21—X2 279.0 127
县X4 S10：X4—Z41—Z42—Z44—Z43—Z40—X4 284.0 132
县X5 S11：X5—Z54—Z55—Z56—Z57
—Z53—X5 305.0 140
S12：X5—Z50—Z49—Z48—Z47
—Z45—Z47—Z51—X5 296.0 133
总计 2252
可得到总费用为：2252×3=6756元
由上述S1，S2，S3，S4，S5邮路的耗时可得到各县局邮路的时间约束如下表8：
表8 各县邮路的时间约束表
县局县X1 县X2 县X3 县X4 县X5
时间约束（分钟） 317.0769 311.8462 311.5385 329.7692 317.4615
S6，S7，S8，S9，S10，S11，S12每条邮路的耗时都小于其时间约束。
2、邮车调度安排如下：
根据区级邮车在每个邮路上到达县局和从县局返回需用的时间对邮车进行调度，这里考虑区级第二班次调度时间时，基于使区级邮车不在县局做多余等待的原则。
往返时间和邮车调度安排如下表9、10：
表9区级邮车到各县往返时间表
S1 S2 S3 S4 S5
D到X行驶时间（分钟） 99.9231 97.1538 144.2308 86.0769 137.2308
X到D行驶时间（分钟） 183.0 191.0 139.2308 184.1538 150.3077
表10邮车调度安排表
邮车出发时间邮车出发时间
S1邮路上第一班邮车 6:00 S1邮路上第二班邮车 12:17
S2邮路上第一班邮车 6:00 S2邮路上第二班邮车 12:11
S3邮路上第一班邮车 6:00 S3邮路上第二班邮车 12:11
S4邮路上第一班邮车 6:00 S4邮路上第二班邮车 12:29
S5邮路上第一班邮车 6:00 S5邮路上第二班邮车 12:17
S6 S7邮路上邮车 8:40 S8 S9邮路上邮车 8:38
S10邮路上邮车 8:27 S11 S12邮路上邮车 9:18

问题2中的邮路方案中，采用12条邮路的总里程为2195公里。
5.2.4 结果的检验与分析
以上结果在一定程度上反映了打破现有行政区局的**，可能降低全区的运行成本能够带来可观的经济效益。
6问题四的分析与求解
6.1 问题四的分析
本问题是一个基于可变根节点最小生成树的多旅行商问题，本题要求对县邮局进行合理的选址，达到降低整个邮政运输网络的运行成本。新的县邮局地址可以选在本县辖区内的任意一个支局所在地，确定某个支局改为县邮局后，原县邮局变为一个支局。重新选址应兼顾区级邮车到县级邮局的邮路优化和县级邮局到各支局邮路的优化，同时也要遵循该地区的邮政运输流程和时限规定，同时不能打破现有县的划分，在此条件下，对各个县的地址进行重新选址讨论。
如果重新选址，就会带来一系列的问题，比如成本的变化，遍历时间的变化等，其中成本就包括了购车费用、邮路运行成本、迁址费用、迁地址带来的损失等，因此我们在县局地址改变的时候就要相应的考虑这些因素，以获得最大的经济利益。针对题目所给数据特点，在邮政运输流程和时限规定基础上，我们主要考虑两个因素：投入车辆数及邮路的总长度。
6.2模型的建立与求解
6.2.1 模型的陈述
1、模型的假设
根据以上分析，可以对模型进行如下假设：
①、每条邮路只需要一辆车邮车即能满足运载能力要求；
②、邮车的调度应满足地区的邮政运输流程和时限规定；
③、营业成本只包括车辆的数量及运行的总里程数。
2、模型建立
其基本数学表达式与问题二相当，只是在约束条件中增加一条：县局可以是本县内任何一个邮局，这里不再写出数学表达式。
6.2.2 模型的求解
   由于问题二的求解是基于县局地址不变进行邮路规划与邮车调度优化的，而在本问中，当邮车的数目及新县局地址确定以后，此问题的求解就可以转化为问题二的求解，其具体求解步骤如下：
Step1、初始邮车数、初始新县局地址集合的确定。其中初始邮车数（区局）可以取问题二的邮车数，县局初始邮车数的获取采用分区获得；初始新县局地址集合可以通过合理的准则获得，具体准则如下：
1：经济性：新县局地址应当能够获得更大的经济效益，也就是说新邮路路程短或邮车要变少；
2：便利性：新县局地址应当有便利的交通，能够与临近的区级、支局方便往来；
3：均衡性：新县局地址应当有较好的距离关系，不至于存在多数较偏远的支局；
4：互利性：对于支局较分散的县局，要充分利用区级班车的优势；
5：时效性：县局应当有一向较快速到达区局的路线，以保证类似像特快邮件的发送。
其中判断数据可以通过题中给定的距离矩阵进行转化，通过计算机求解计算可得初始新县局地址集合。
Step2、从新县局地址集合里选择一个地址作为县局,利用问题二提出的方法对全区的邮车数量和邮路进行规划；
Step3、通过重复1-2步，再进行选优，而后得到邮路的较优解。
以下为按照以上方法寻优，得到问题四的较优解，其中更改后的新县局地址如图11及表11，优化后的邮路为11条，总路程为2079，其结果具体见图12及表12。

图11 改变后的县址

表11 县局地址改变方案
县名改变方案备注
县x1 县局地址改选在Z14
县x2 县局地址改选在Z20
县x3 县局地址改选在Z29
县x4 无
县x5 县局地址改选在Z53

图12 题四邮路优化结果
表 12 改变县址后的邮路表
路线类型新邮路路程（km）备注
D—县x1 79 61 62 16 15 14 12 17 12 11 62 79 247
D—县x2 79 66 63 18 19 20 75 27 65 67 79 265
D—县x3 79 66 64 29 30 34 35 70 68 69 71 72 79 247 66不卸货
D—县x4 79 73 42 41 43 77 40 39 38 37 36 71 79 265 71不卸货
D—县x5 79 61 59 58 52 53 51 46 44 60 79       273    61,51不卸货
县x1
14 74 13 1 2 3 4 14 139
14 5 6 7 8 9 10 14 104
县x2 20 26 25 24 23 22 21 20 133
县x3 29 31 28 76 33 32 30 29 134 30不卸货
县x5 53 78 54 55 56 57 53 140
53 50 49 48 47 45 47 51 53 132
总路程 2079 （km）
邮路数 11 条
6.2.3 结果的检验与分析
   通过电脑编程反算以及编程计算考察各项约束条件，可知各邮路均能满足题中的各项约束条件。从表13容易看出，不能改变县局地址的问题二的优化结果与可改变县局地址的问题四的优化结果相差还是比较大，一方面反映了优化算法的有效性，但同时也可以从图12可以看出，个别邮路仍存在一定距离的辐射型线路或较长路程的S形路，从而导致总路程的增加。

表13 问题二与问题四求解结果对比表
问题二问题四
总路程 2195 (km) 2079 (km)
总邮车数 12 11

7模型评价
该问题是一个NP问题，通过划分区域，将该问题进行分解，降低了复杂度。并将遗传算法、禁忌搜索和贪婪算法融入该问题中去，使得能够很快找到比较有的解。但是该算法也有不尽人意之处，为了能够找到更优的解，需要进行人工干预。
参考文献
[1].傅家良,运筹学方法与模型[M].上海,复旦大学出版社.2006年.
[2].邢文训,现代优化计算方法[M].北京,清华大学出版社.1998年.
[3] .CHEN H ,dewald CG. A Generalized Chain Labeling Algorithm for Solving Multi-commodity Flow Problem [J]. Computers &operations Research, 1974 ,1 :437～465.
[4].WOLLMER R D. Multi-commodity Networks with Resource Constrains: The Generalized Multi-commodity Flow Problem [J]. Networks , 1972 ,1 :245～263.
[5].BALACHANDRAN V. Generalized Transportation Networks with Stochastic Demands: An Operator Theoretic Approach [J]. Networks , 1979 ,9 :169～184.
[6].SHAN Y. A dynamic multi-commodity network flow model for real time optimal rail freight car management [M] .Ph. D. Dissertation. Princcton University, 1985.
[7].邮电部邮政科学研究划院.邮政通信网专题研究报告汇编.1994
[8].吴象南, 杨海荣.邮政通信网组织管理[M]. 北京:人民邮电出版社, 1996
附录
对本市所辖各县县局地址进行调整的建议
省邮政局网运处：
我市下辖五个县城，每个县有一个县局，且每个县下辖不同数目、不同分布的一些支局，其分布图如下：

图13 当前全市邮局分布图
经长期对我市邮政运输网络运行效益的考察，以及对各县县局位置进行充分分析论证，发现各县局现在的位置对我市整个邮政网络的运行效益有很大的制约。为了发挥自身优势，在缩短邮件运输时限和降低成本的同时，节约能耗和人力资源，提高我市邮政网络的整体效益，保证我市邮政业的市场竞争力和良好的社会效益，故想调整现有县局的位置。
邮局迁址需要一定的经费支持，我考虑可以把新的县局地址选在已有的一个支局所在地，把该支局进行扩建，作为新的县局，而把旧县局作为一个支局继续使用，这样可以减小调整需要的经费；另外，调整后带来的是一个长期的经济效益提升，因此当前的投入是值得的。
经过反复的规划、计算及对调整后的运输效益评估，建议把X1县的县局调整到Z14 支局处，把X2县的县局调整到Z20支局处，把X3县的县局调整到Z29处，X4县的县局不调整，X5县的县局调整到Z53处，调整后新的分布图如下：

图14 调整后全市邮局分布图
经过这样调整，邮路可以从原来的十二条减少到十一条，总路程可以由原来的2195km减少到2079km，这将可以大大减小整个网络的运行成本，提高我市邮政运输的效率，提升邮件运输的时效。特提出申请。

                                       ××市邮政局网运处

                                          2007年10月22日