数学与应用数学论文-中国邮递员问题的数学模型.doc

北方民族大学学士学位毕业论文目 录前 言1第一章 中国邮递员问题的整数规划模型21.1 图论中模型21.2 中国邮递员问题的整数规划模型561.2.1 传统中国邮递员问题的建模61.2.2 广义中国邮递员问题及其建模71.2.3 随机中国邮递员问题及其建模711第二章 中国邮递员问题的DNA计算142.1 DNA计算模型142.2 中国邮递员问题的图论模型变换152.3 中国邮递员问题的DNA算法11162.4 总结19第三章 中国邮路问题的数学模型203.1 问题的重述203.2 需解决的问题213.3 问题假设213.4 符号说明223.5 问题一的建模与求解23（一） 模型的分析与建立243.6 模型的求解27结 语30致 谢31参考文献3231第 页 共35页前 言图论是一个新的数学分支，也是一门很有实用价值的学科，它在自然科学，社会科学等各领域均有很多应用。近年来，计算机技术在图论中的应用使得图论得到飞速的发展，应用范围也不断拓广，已渗透到诸如语言学，逻辑学，物理学，化学，电讯工程，计算机科学以及数学的其它分支中。特别在计算机科学中，如形式语言，数据结构，分布式系统，操作系统等方面均扮演着重要的角色。最早的图论问题要追溯到1736年的哥尼斯堡七桥问题，而且在19世纪关于图论的许多重要结论都已相继提出。但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。其实现实生活中的许多问题都是可以通过图论中的相关知识得以解决的，这些例子俯拾即是。例如，住在城市里的人出行的街道, 抽象出来就是由顶点(结点)和边(线) 构成的图, 在这个图上, 清洁工人必须把这个城市的所有街道清扫一遍，也就是走完所有的边，于是, 清洁工人马上遇到一个十分重要的图论问题: 怎样扫才能一条不落地把所有街道扫上一遍，而且使得所走的总路程最短，这就是典型的欧拉回路问题。再如，有一个推销员，他要去n个城市推销他的商品，因此他要从他所居住的城市出发，走遍他所有想去推销商品的城市，再回到他居住的城市，于是, 推销员马上遇到另一个十分重要的图论问题: 怎样扫才能一个城市不落地把所有城市走一遍，而且使得所走的总路程最短，这就是典型的哈密顿回路问题。在现实生活中，由于大多数人不懂图论知识，或者虽然懂一点图论知识，但不知道如何将图论中的知识运用到我们的生活实践中去，导致我们的效率低下，有时甚至使得我们的工作难于完成。因此，研究图论知识及其应用有着非常重要的意义。本文将讨论中国邮递员问题，以帮助大家增加图论知识并解决现实生活中的一些实际问题。第一章 中国邮递员问题的整数规划模型关于邮递员最优投递路线问题最早是由管梅谷首先提出并进行研究的，国际上现在统称之为中国邮递员问题。早期关于中国邮递员问题的讨论总是基于无向图展开的，事实上，由于单行线或上下行路线的坡度等原因，这一问题有时必须借助于有向图来进行研究和解决。到目前为止，对中国邮递员问题的研究主要是从图论角度展开的，给出的多数都是各种启发式算法或递推算法。本章讨论了数学规划模型，数学规划建模具有借助软件包求解方便、易于修改和推广等多方面的优点，即使对于大型问题也易于建模分析和解决的优点。1.1 图论中模型任给定一个图G，对E(G)加权，即对每个，任意指定一个非负实数，求G的一个含有一切边回路W，使得W的总权1 如果G是Euler图，则所求的中国邮路W就是一条Euler回路。1921年，Fleury给出求Euler图G中一个Euler回路的算法。值得指出的是，即使已知G是Euler图，如果没有一定的路线遵循，也不是漫不经心就可以找出它的一个Euler回路的，例如图1-1是Euler图，设从开始，寻找一条Euler回路，如果开始三步是就失败了，因为回到之后发现左侧的上的边还没有用过，而的关联边已全用过，不能从再去通过左侧那些未用过的边了（注意每边只能用一次）。究其失败的原因，是因为用了边之后，在未用过的边们导出的子图上，是桥，提前过桥的后果是断了去左侧的后路。这里的教训是，非必要时，不要通过未用过的边的导出子图的桥，根据这一思路，Fleury设计了如下求Euler回路的有效算法，代号FE算法2：（1） 任取，令； 图 1-1（2） 设行迹已选定，则从中选一条边，使得与相关联，且非必要时不要选的桥；（3） 反复执行（2），直至每边皆入选为止。FE算法是有效算法，其时间复杂度是。用FE算法在上图中可选得Euler回路： FE算法的正确性证明如下： 令G是Euler图，是FE算法终止时得到的行迹，由算法知在中的次数为零，显然，于是是G的一条闭行迹，下证就是G的Euler回路，反证之，若不是G的Euler回路，设是中次数非零的顶组成的顶子集。容易看出，且。令，则；设m是，而的v的下标的最大值，见图2-2。由于的终点在中，于是是的桥，设e是中与关联的边。且，由算法知e为的桥，故e也是在中导出的子图的桥。设是在中导出的子图，则，于是每顶皆偶次，中无桥，与e是的桥矛盾。 图 1-2下面讨论加权图G中有奇次顶时中国邮路问题的解法。这种情形有的边不得已要通过至少两次，哪些边要通过不止一次才能使得完成投递的时间最短呢？让我们通过一个实例来探讨这一问题3。在图1-3中，边旁写的是权 图 1-3（1） 在图1-3中，奇次顶集为 （2） 在中，每对顶的距离为（Dijkstra算法去求） （3） 构造完全加权图，边权，见图1-4： 图 1-4（4） 求（3）中的最佳（总权最小）的完备匹配， （5） 在G中求得和间最短轨；与间最短轨（6） 在G中沿与把边变成同权“倍边”，见图54 图 1-5（7） 在Euler图15上用FE算法求得一条Euler回路 ，即为所求的中国邮路（不唯一） 上述解法具有代表性，一般的中国邮路解法步骤总结如下： 设G是连通加权图（1） 求G中奇次顶集合.（2） 对中的每个顶对，用Dijkstra算法求距离.（3） 够作加权完全图,，中边之权为.（4） 求加权图的总权最小的完备匹配M.（5） 在G中秋M中同一边之端点间的最短轨.（6） 把G中在（5）求得的每条最短轨之边变成同权倍边，得Euler图G.（7） 用FE算法求G的一条Euler回路W，W即为中国邮路. 1.2 中国邮递员问题的整数规划模型51.2.1 传统中国邮递员问题的建模传统的中国邮递员问题可以概述如下6：一个邮递员每次送信要从其所在的邮局出发，走遍所负责投递范围内的每条街道，完成送信任务后回到原来的邮局，应该选择怎样的路线行走，才能使得所走的总路程数最小。把该问题抽象成图论问题就是给定一个连通图G(V，E)，其中：是顶点的集合，表示街道交汇的地方；E是顶点间边的集合，表示街道，即，每个边上有非负，表示边即街道的长度。问题是要确定G的一个子图(是一个圈)，它过每条边至少1次，而且使得该圈的总权(即图上各边的和)最小。从图论知识知，若G不含有奇点(即相邻边的个数为奇数)，则G有圈，它过每边1次且仅仅1次，所以这个圈就是所要求的圈。若G含有奇点(即相邻边的个数为奇数)，则G的任一过每边至少上通过了k次，设，就在与之间添加k-1条新边，并令这些条新边的权都等于边的权，称这些新边为的添加边。显然，若边e上的添加边多余1条，那么去掉其中偶数条后，得到的图中任一过每边至少1次的圈的总权不会增大。因此可以假定每边上添加边的个数至多1条。这样，寻找邮递员最优投递路线的问题就可以归结为如下：给定连通图G(V，E)，每条边对应的顶点和之间添加1条边，得到边数双倍于G的另一个连通图G(V，E)，求 E， E使不含奇点且总权为最小。若 ，则记为或(i，j)，而相应的添加边为，与边相对应，设定0-1整数变量。若，即称边是从到的，或称为弧。这样，就可以把无向图理解为有向图。每个惟一对应一组的值，反之亦然。可以借助变量(i=1，2，n； j=1，2，n)来定义最优投递员问题的约束如下：（1）过每边至少1次且添加边至多1条，E1对应的所有的xi，j的值(称为E1的值系)满足：对（2）图不含奇点，即对于任意一个顶点Vi，有进向弧，必有与之等量的出向弧：这一问题的目标是使得的总权最小，即min，其中，为边上的权，。这样，就得到中国邮递员问题的显式整数规划模型(CPP)如下 (1)这一模型不仅可以用于求解中国邮递员问题，而且可以确定相应的最优投递路线：如=1，即表示邮递员应该从沿着边(即街道)到。1.2.2 广义中国邮递员问题及其建模上节所述的邮递员问题，假定了邮递员投递范围内的每条街道的上行和下行是无差别的，而在实际信件的投递过程中可能不是这样的，如遇到单行线街道、街道有一定的坡度、街道两边不能单行中同时投递等。这样的邮递员问题称之为广义的中国邮递员问题。这一广义的中国邮递员问题可以抽象为一个有向图问题。类似于前面所述的邮递员问题(称为传统的中国邮递员问题)，广义的邮递员问题可以叙述为：给定一个连通有向图G(V，E)，每个弧e上有非负权w(e)，需要寻找G的一个回路，它过每个弧至少1次，且使得总权为最小。对于广义的中国邮递员问题，添加弧的个数至多1条有时已经不再可行，即需要多条添加弧，才能使对应的连通有向图G的任一顶点的进向弧数与出向弧数相同，从而使G(V，E)存在回路(E回路)。在此，如e=(，)E，则称弧e是顶点的进向弧，同时也是顶点的出向弧。可以证明，如G(V，E)的顶点数为n，则每条弧上至多增加(n-1)条添加弧，即可实现各顶点的进向弧数与出向弧数相等。根据以上分析，对于G(V，E)的每条弧E定义一正整数变量，表示弧上增加了条添加弧，由此形成另一个有向图G(V，E)。类似于上节的分析，可以有如下广义中国邮递员问题的显式整数规划模型(GCPP)： (2)通过这一模型的求解，可以得到广义中国邮递员问题的最优投递路线。下面我们通过具体的数值示例来对上述两个模型进行应用求解：算例1：考虑图1-6所示的中国邮递员问题： 图1-6传统中国邮递员问题根据前面的模型讨论，这一数值例示邮递员问题对应的整数规划模型如下： + (3)应用整数规划求解工具QSB，求解得到这一问题的最优解，如：其他，最小权重为68。假定邮局在顶点，则有如下最优投递线路：注意，这一问题的最优投递路线不惟一。同理可以求得邮局从任何一顶点出发时的最优投递路线。算例2：考虑图1-7所示的广义中国邮递员问题。 图1-7 广义中国邮递员问题相应的广义中国邮递员问题的整数规划模型如下： (4)应用相同的整数规划求解软件，求解这一模型得到下列最优解：， ，最小权重为159。假定邮局在顶点，则有如下投递路线：这是一个回路。类似可以确定邮局在任一顶点时的最佳投递路线。这一最优投递路线是根据模型的最优解，采用类似接龙游戏的方法找出的。这里需要注意的是，如某的值大于1，意味着该弧要重复走。所有的和应等于所走的所有街道数(包括重复走的)。1.2.3 随机中国邮递员问题及其建模7上述讨论的传统的和广义的中国邮递员问题都假定与边或弧相联系的权重是确定型的常数。实际中经常遇到权重非固定的情况，如考虑的权重是该街道上所花费的投递时间，这一参数往往不是常数，每次投递所花费的时间会由于邮件量的多少而变动，但一般会遵循某种变化形式，即权重是具有某种分布的随机变量，这时可以称对应的问题为随机中国邮递员问题。处理传统中国邮递员问题的奇偶点图上作业法及其改进算法对这一随机问题都无能为力，但借助于本文建立的整数规划模型，应用随机规划理论，可以很方便地进行处理。随机问题的处理方法有多种，如期望值法、机会约束法、最优值分布法、相关机会约束法、多阶段(如两阶段)法。本文在此处仅讨论机会约束法，其核心是概率约束条件的确定型等价处理。其他方法可以按照随机规划理论类似处理，在此略去。注意到，CPP或GCPP的约束中都不含有权重参数，因此，处理权重随机的问题只需要将目标函数做相应的确定型等价处理即可。权重随机时，目标函数也是随机变量，根据随机规划理论，随机的CPP问题可以转化为如下2个确定型等价模型7： 1-CPP()minw (5)2-CPP(w)max (6)其中，1-CPP()指对固定的求解以及权重w,而2-CPP(w)指对固定的权重w求解和。此处，称为权重w的可行度，w为总权重的希望水平。如果诸权重均服从正态分布而且相互独立，服从，则1-CPP()和2-CPP(w)分别等价于下列2个数学规划8：1-NCPP()minw (7)2-NCPP(w)max (8) 其中：F(X)为标准正态累积分布函数；F-1(y)为其逆函数。进一步地，可分别等价于如下2个数学规划问题：1-NCPP() s.t.CPP的约束条件 (9)2-NCPP(w) (10) s.t.CPP的约束条件其中，注意到F-1()是的单调递增函数。对于其他类型的随机问题也可以类似地进行分析。注意上述规划是非线性的，因此需要借助非线性整数规划的求解工具和软件或两阶段法进行求解，大型问题也可以借助于现代智能优化算法进行求解。基于传统的中国邮递员问题，建立了这一问题的显式整数规划模型，并将之推广到基于赋权有向图的广义邮递员问题和权重不确定的随机邮递员问题。另外的推广是考虑权重是模糊型或灰色型、粗糙型、信度型的中国邮递员问题，根据相应的不确定性内涵，对于目标函数进行相应的确定型转化。本章讨论的是单目标问题，如果考虑多目标中国邮递员问题，数学规划灵活、机动、易于修正和变形的特点，可以用来非常方便地处理这一可能的拓展问题。第二章 中国邮递员问题的DNA计算目前，人们已对DNA计算技术展开了深入研究。应用DNA计算方法，开拓性地解决了一个给定有向图的Hamilton路径问题。给出了一种对于可满足性问题(SAT问题)的DNA计算模型。利用单链DNA分子的“发夹”结构，解决了一个3-SAT问题。给出了一种基于表面的SAT问题的算法，随后对其进行了改进。将DNA计算应用于0-1规划问题，解决了一类特殊0-1规划问题，即指派问题的推广。在其基础上完全解决了0-1规划问题，并将进而解决了两类特殊的整数规划问题。中国邮递员问题是运筹学中的一个重要问题，本章提出了“虚拟权值”和“虚拟节点”的概念，然后基于DNA计算在并行运算方面的良好特性，提出了中国邮递员问题的一种基于DNA计算的新求解算法。新算法首先利用多聚酶链式反应技术来排除非解，从而得到中国邮递员问题的所有可行解；然后，结合基于表面的DNA计算方法与荧光标记策略等技术，最终从所有可行解中析出最优解。算法分析表明，新算法具有易于解读，编码简单等特点。2.1 DNA计算模型DNA是一种高分子化合物，组成它的基本单位是脱氧核苷酸，每个脱氧核苷酸由一分子磷酸，一分子脱氧核糖和一分子含氮碱基组成。含氮碱基有四种，即腺嘌呤(A)，鸟嘌呤(G)，胞嘧啶(C)和胸腺嘧啶(T)。DNA不仅具有一定的化学组成，还具有规则的双螺旋结构。DNA计算的基本思想是利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下，生成各种数据池(Data Pool)，然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控生化反应过程，最后利用多聚酶链式反应PCR，凝胶提纯，诱变等分子生物技术检测所需要的运算结果。DNA计算的核心问题是将经过编码的DNA链作为输入，在试管内或其他载体上经过一定时间完成控制的生物化学反应，以此来完成运算，使得从反应后的产物中能得到全部的解空间。2.2 中国邮递员问题的图论模型变换中国邮递员问题的距离图模型无法直接应用于DNA计算，因此需要对其进行适当变换。在给出具体变换模型之前，先给出需要用到的相关概念的定义。定义19虚拟权值:给定的连通无向图，其中为图中的节点集合，为图中的无向弧集合，令为无向弧对应的距离，将按距离长度进行分组，假定可分为个组，其中表示属于组中的无向弧的距离长度。我们称组对应的组号为属于组中的无向弧的虚拟权值。对属于组中的任意无向弧，其虚拟权值记为。中国邮递员问题的虚拟权值图模型，对于给定的连通无向图，其中为图中的节点集合， 为图中的无向弧集合，令为无向弧对应的虚拟权值，则对图中给定的节点，需要从所有可能路径集中求得一条最优路径。其中满足：1) 从节点开始到节点结束；2) ；其中满足：，其中表示路径中所有无向弧对应的虚拟权值之和。定义2虚拟节点/路径节点:给定的连通无向图，其中为图中的节点集合，为图中的无向弧集合，令为无向弧对应的虚拟权值，假定无向弧的两个端节点分别为A，B，则在无向弧上可增加个中间节点，将平均分为段，令， 即有，其中表示节点之间的无向弧对应的虚拟权值。以上新增加的中间节点称为“虚拟节点”，而图中的节点集V中的节点成为“路径节点”。中国邮递员问题的虚拟节点图模型：对于给定的连通无向图，其中为图中的节点集合， 为图中的无向弧集合，则对图中给定的节点，需要从所有可能路径集Pj中求得一条最优路径j。其中满足：(1) 从节点vs开始到节点vs结束；(2) ；其中满足：，其中表示路径中所有无向弧对应的虚拟权值之和。2.3 中国邮递员问题的DNA算法11对给定街区的中国邮递员问题，依据2.2节中的描述，首先给出问题对应的虚拟权值图模型，其中为连通无向图，为图中的节点集合，为图中的无向弧(路径)集合。然后，再给出问题对应的虚拟节点图模型，其中为连通无向图， 为图中的节点集合， 为图中的无向弧(路径)集合。显然有：。针对中国邮递员问题对应的虚拟节点图模型，不妨假定节点为邮局，则对应的中国邮递员问题的DNA算法如下：步骤1随机生成大量长度为20-mer的DNA单链，对，选择n个不同的DNA单链分别与其对应。对任意节点，用表示其所对应的DNA单链。步骤2 ，得到对应的反转补链。并在试管T1中生成大量的拷贝。步骤3 ， ，其中为一条邮局节点 (用S表示邮局)， 之间的路径。则用如下方法生成DNA单链、来表示路径，并在试管T2中生成大量、的拷贝。（1）用依次链接上最后再链接上的前10-mer寡聚核苷酸，所构成的长度为20(t+1.5)-mer的DNA单链，来表示路径；（2）用依次链接上最后再链接上的前10-mer寡聚核苷酸，所构成的长度为20(t+1. 5)-me的DNA单链，来表示路径。步骤4， ，其中为一条之间的路径。则用如下方法生成DNA单链、来表示路径，并在试管T3中生成大量、的拷贝。1)用的后10-mer寡聚核苷酸，依次链接上、最后再链接上的前10-mer寡聚核苷酸所构成的长度为20(t+1)-mer的DNA单链，来表示路径； 2)用的后10-mer寡聚核苷酸，依次链接上、最后再链接上的前10-mer寡聚核苷酸所构成的长度为20(t+1)-mer的DNA单链，来表示路径。步骤5将试管T1、T2、T3倒入试管T4。在试管T4中将产生大量的连接酶反应。注：连接酶反应：存在一种称为连接酶的酶，该种酶能将两条不同的DNA单链串联成为一条DNA双链。步骤6利用作为引物，基于多聚酶链式反应(Polymerase Chain Reaction， PCR)放大技术，使得步骤5所得到的产物中，仅以起始，并以结束的DNA双链得到放大。分离放大的DNA链并保存到试管T5。加热解开试管T5中的DNA双链，生成DNA单链。步骤7 ，其中为一条之间的无向弧，为之间的虚拟节点，则分别利用吸附到磁珠上的、来孵化(Incubate)生成的单链DNA。由于只有包含或的DNA单链才能与或产生连接酶反应，因此可通过磁珠的磁性分离出试管T5中包含或的DNA单链。步骤8对步骤7所得到的产物，依次对中的所有其他无向弧分别重复步骤8。保留最终得到的DNA单链。步骤9对步骤8所得到的所有DNA单链，首先，使之带上负电，然后将其放置于矩阵凝胶体(GelMatrix)的负极。基于相斥原理，所有DNA单链将向反方向移动。由于长的DNA链的移动速度小于短的DNA链，因此，可以分离出移动速度最快的DNA单链。步骤10对步骤9所得到的任意DNA单链，按以下方法确定其对应的路径中包含的各条无向弧的访问顺序：1) 将得到的DNA单链固定在表面上；2) ，其中为一条之间的无向弧，为之间的虚拟节点，将、连接上不同的荧光素；3) 将、加到表面上；4) 重复上述步骤2)和3)，直到DNA单链构成DNA双链。5) 利用激光共聚焦显微镜观察表面上的DNA双链的荧光素颜色，即可确定其对应的路径中包含的各条无向弧的访问顺序。显然，针对具有n个节点的模型，步骤1的时间复杂度为O(n)；在步骤2中，由于DNA计算的并行性，针对不同的，在试管T1中生成大量的拷贝是同时进行的，因此其时间复杂度也为O(n)；在步骤3中，假定模型中的不同路径条数为m，则步骤3的时间复杂度为O(m)；类似步骤3，易知步骤4的时间复杂度也为O(m)；步骤5、6、7、8的时间复杂度显然均为O(1)；而对步骤10，由于模型中的不同路径条数为m，因此得到的DNA单链至多为m，因此，其时间复杂度为O(m)。一般而言，由于m n，故综上所述，算法的总的时间复杂度为O(m)。2.4 总结 本章描述了DNA的计算模型，模型的转换和算法，从DNA算法中可以看到其具有良好的并行性，因此在解决一类困难问题，特别是完全问题上具有硅计算机无法比拟的优势。利用多聚酶链式反应放大技术，提出了中国邮递员问题的一种基于DNA计算的求解算法。算法分析表明，新算法具有易于解读、编码简单等特点。第三章 中国邮路问题的数学模型3.1 问题的重述某地区的邮政局、所分布如图1所示，分为地市中心局（简称地市局）、县级中心局（简称县局）和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案并进行邮车的合理调度。图1 某地区邮政局、所分布图（图中代号1至73依次代表支局Z1, Z2, , Z73）为了满足邮政的时限要求，必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。题目给出了该地区的邮政运输流程及时限规定如Step1-Step4：假设区级两个班次邮车的行驶路线相同，要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z58, Z59, , Z73和5个县局X1，X5。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公路网分布见表1，并且县级邮车平均时速为30km/h，区级邮车的平均时速为65km/h，邮车在各支局卸装邮件耗时5分钟，在各县局卸装邮件耗时10分钟。3.2 需解决的问题问题：以县局X1及其所辖的16个支局Z1, Z2, , Z16为研究对象，假设区级第一班次邮车08:00到达县局，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，确定最少邮车数。同时，在考虑空车损失费用（空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量(袋)/邮车最大承运的邮件量(袋)，单车由于空车率而造成的空车损失费用为（空车率*2元/公里）的情况下，为提高邮政运输效益，设计合理的邮路规划及相应的邮车调度方案。 3.3 问题假设根据题意，可以进行如下假设：1 邮车在邮路上的速度是一定的，不会出现抛锚等现象2 在各个县局、支局的邮件处理时间一定，不会出现特殊情况而延误时间3 邮车到达各个支局时包裹的数量达到数据表中给出的数据，并且一次性取走该支局所有的包裹。4 邮路确定后，各邮车必须按所属邮路进行支局的遍历，不能遍历邮路外的其他支局。3.4 符号说明 论文中涉及到的符号说明如下：区局 ：县局 ：支局 ：邮政网络图（点边赋权图）其中： ：顶点集合E：两个节点的无向边集合 ：寄达支局的邮件量 ：支局收寄的邮件量 ：支局到支局的距离：县局包含的节点集合：包含的支局节点数：县局的邮路数：县局的最少邮路数=：县局的第j条邮路：运行邮路所需的时间：邮路所经过的支局：邮路包含的所有非重复节点：包含的支局节点数：县局的邮路总距离：邮路的运行成本，单位为元/公里：邮车最大承运的邮件袋：邮路的总邮件量：邮车通过邮路所经过的支局需要装载的邮件量：x的上取整：邮车通过邮路由于空车率所产生的损失：邮车通过邮路从支局到支局的空车率：邮车通过邮路从支局到支局所行使的距离：县级邮车的运行速度：区级邮车的运行速度：县局所需的最少邮车数3.5 问题一的建模与求解上述问题可分为两个小问题：（1）在考虑县级邮车容量限制和时限规定的条件下，遍历县局所有支局所需的最少邮车数。（2）在第一小问的基础上，给出合理的邮路规划及邮车的调度安排，使得县局的空车损失费用达到最低。下面分别对以上两个小问进行建模求解。（一） 模型的分析与建立1 在时限及邮车容量限制的条件下，确定最少邮车数将图1的该地区邮政局、所分布图中，每个县局、支局看作图中的节点，任意两个县局、支局之间的邮路可以看作相应节点间的边，那么整个地区的分布图可以看成邮路网络图，针对县局，可得县局及其所属支局所对应的图，为县局及其各支局对应的节点集，为相邻顶点构成的边。对于此问题，对应的连通图为，。在确定最少邮车之前，首先给出以下结论：结论1 遍历县局所有支局，至少需要设置3条邮路，即=3证明：通过计算，可得县寄达各个支局所有包裹总数为176。由于每辆县级邮车最多容纳65袋邮件，因此为了将所有包裹送达目的支局，并满足邮车的最大容量要求，遍历完县所有支局，至少需要设置条邮路。证毕。结论2 同一县局的邮车数不大于邮路数，即虽然邮车数与邮路数之间不存在确定的数学关系，但在实际情况中，邮路数少，邮车数通常较少。因此在考虑邮车容量和时限要求的前提下，我们首先确定最少邮路数，并在此基础上，进一步根据时间约束，确定遍历县局所有支局的最少邮车数。由于邮路数的确定涉及到每一条邮路的时限及包裹容量的限制，下面先讨论邮路应满足的约束条件。由于邮政运输流畅的时限规定，市局第一班车只能在8:00到达县局，在县局对邮件进行一小时的集中处理后，即9:00后县级邮车才能由县局出发。市局第二班车16:00由县局出发返回市局D，由于县级邮车回到县局时，需要在县局进行一个小时的集中处理，因此，县级邮车必须在15:00前全部返回县局，故县局的邮车实际运行时间（包括邮车在其途径的各个支局邮包的装卸时间）只有6个小时。考虑到县级邮车最多容纳65袋邮件，不可能由一辆车遍历所辖的各个支局，设此县局的总邮路数为，每辆车的邮路均形成一个包含节点的圈，记为，其中圈包含的节点集合为，则有： (11)（1）邮车按顺序遍历圈中所有节点的用时条件分析设邮车沿邮路遍历中各节点（由于邮路上可能包含重复节点，因此），根据假设3，重复节点的卸装时间不重复计算，则邮车在圈中个县支局总的卸装时间为，因此遍历邮路所需的运行时间为： = （12）故邮车按邮路由出发顺序节点，并最后返回节点，总的用时为： = （13）（2）邮车沿邮路遍历回路中节点时的邮车装载量限制分析 设为节点需装上邮车的邮袋数，为节点需卸掉的邮件数，考虑到邮路中可能存在重复的节点，因此增加权重因子，其取值为则邮车由节点出发时装载的邮袋数为。邮车由出发沿邮路运行至节点时邮车所装载的邮件数量为： =（） （14）基于以上分析，显然有以下结论：结论3 设为及中各支局节点集合，为中的个圈，若以下条件成立： （1）； （2）； （3）则个圈为遍历中各节点的条邮路，并且为的最少邮路数。因此在此基础上根据线路的运行时间调整邮车数，使之达到最少。2 在考虑空车费的条件下，规划邮路和安排邮车的运行由于每一个支局均有邮件的装卸操作，使得对于每一条可行的邮路，邮车的空车费用和其经过支局的顺序有关，因此对于可行邮路，由公式3可得邮车由出发运行至节点时邮车的空载量为：因此，邮车由节点出发运行至节点时的空载率为： =则由邮车由至的空载损失为： （4）邮车由运行至中节点的空载损失为： （15）邮车由中节点运行至的空载损失为： （16）故邮车由沿运行遍历中各节点的空载损失为：=+（17）在确定邮路的空车费之后，可以建立以下规划模型求出空车费用最低的邮政路线：s.t. ， （18）根据上面建立的规划模型，在最少邮路数确定的条件下，通过遍历县局中所有支局，即可求得空运车费最低的邮路分布方案。3.6 模型的求解通过对算法一的描述可以发现，对于每一个确定的邮路数，总运行路线最少的邮路支局分布情况实际上就转变成了多个推销员的最佳推销员回路问题，即在加权图中求顶点集的划分，遍历（）中所有节点的圈，使得各圈的边权之和最小。针对本问题的实际情况，本文给出了求解此问题的近似最优解的算法如下：算法一（邮件容量约束下的遍历县局中节点集最优圈的贪心算法）（0）初始化，设为县局邮车可用的最大时间限制，县局需遍历的节点集为，令，；（1）首先求中距节点最远的节点及其最短路径令 设中遍历中的节点数为，令（表示寄达路径P上所有节点的邮包数），；（2）求出中与最近的相邻节点，使得并且；（3）判断由节点返回是否满足时间约束若将加入路径，令 ， ， ， 转（2）继续探索；否则，直接由当前节点返回，即将至的最短路径加入回路，即获得一个由出发的圈；（4）若，则结束，否则转（1）继续求下一个圈。利用算法一找出县局总运行里程最短的邮路分布，见表1。表1 邮路规划情况表邮路支局分布情况初始邮包数运行里程（km）花费时间(h)邮路1601264.70邮路261983.68邮路3551535.51合计17636713.89通过上表可以发现，将此县局的支局分为三条邮路，由于每一条线路的时间都较长，因此一辆邮车只可能行驶在一条邮路上，而不可能两条邮路行驶同一辆邮车，因此此县局分为3条线路的做法是可行的，并且至少需要3辆邮车。综合考虑空车费用，利用算法一找出县局总运行里程最短的邮路分布，见表2。表2 空车费用最低的邮路支局分布表邮路支局分布情况初始邮包数总空车费（元）运行里程（km）花费时间(h)邮路1X1Z15Z4Z3Z2Z1Z13X16418.771585.77邮路2X1Z12Z11Z9Z5Z14X16021.941364.95邮路3X1Z6Z7Z8Z16Z10X15230.711354.92合计17687.0237715.64从表2可以发现，空车费用最低的邮路规划并不是总运行里程最短的邮路规划，而是有一定的偏差，但是偏差不会太大，这是一个比较合理的结果。 结 语本文基于无向图的