全国第四届研究生数学建模竞赛题 目 邮政运输网络中的邮路规划和邮车调度优化研究摘 要本文借助于图论典型算法（如Flody算法），以及运筹学图上作业法等典型手法，深入研究了一类曲面上的带附加条件的多路巡回问题。

分别回答了县区、市区邮政网络的邮路规划调度问题及其关于县区部分边界变动、和县区邮政中心变化引起的灵敏度分析。

并且针对每一问建立了相应的优化模型。

针对第一问、先回答了车辆个数的下确界，并用试探算法明确了三个子巡回可行，并针对三个子巡回设计了新颖的算法，先将问题松弛，将约束条件转化为准则库，找寻到经过县局的满足荷载限制的子巡回，然后定义每个子巡回的标示码、校验码、在程序中成功定义了映射，实现了三个子巡回的邮政网络划分，找到了问题的可行解域，然后以空载费用为目标函数，找到了空载费用为55.67的最优方案。

且该方案通过了检验。

针对第二问，针对市、县两级邮政网络图的特点，寻求局优解，借助于市区的最小生成树、以及市局、县局的最短路径，从中心向四周辐射，安排各子巡回，以区级车辆往返时间特点为约束，以子巡回的空余时间为罚函数，以环形回路为主兼顾辐射型回路，优先安排快车巡回，设计了相应的算法，并且给出了初始方案，且利用我们的方法调整方案，得到满意解，需要用13辆邮车完成全区的邮件任务，全区的总邮路路程为2453公里。

针对第三问，我们以减少邮路车辆为目标，研究了县区边界需要调整的点的特点，利用邻接区域的罚函数较大的回路破圈，重新构造子巡回。

既满足时间约束，又达到了降低费用和减少邮路车辆的目的。

通过我们的工作，可以减少两个邮车，总路程变比第二问减少了258公里针对第四问，我们定义了区域中心即为到达所有各点的距离之和为最小的点，但是邮政网络中的中心不仅取决于距离，同时由它的度数以及周围区域点的度数综合决定，我们利用Mthematica和Lingo中的tsp模板，借鉴第二问的表上作业法，和第三问灵敏度分析的经验，减少了两辆邮车，减少了284公里的邮路。

参赛队号 1029001 参赛学校 中国矿业大学参赛队员姓名 姜英姿 卓金武 秦 健一、问题重述邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。

邮路的结构形式有三种：辐射形、环形和混合形。

辐射形邮路可以缩短运递时间，加快邮运速度。

但它的联系点较少，需用的运输工具较多，所耗费用较大。

环形是不走重复路线，联系点较多，运输工具的利用率高，运费也较省。

但是邮件送到最后几个交接点的时间较长。

混合型二者兼有。

某地区的邮政局分为地市局、县局和支局三级机构。

该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。

区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。

时限与成本是邮政运输问题的两个重要指标。

时限是指邮电部规定的邮件、报刊处理、传递的最大时间限制，时限关系到邮政通信质量的好坏；成本影响着企业的经营。

为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案并进行邮车的合理调度。

为了满足邮政的时限要求，必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。

该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。

该地区的邮政运输流程及时限规定如下：Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局X i和沿途支局，并将各县局X i和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。

Step2:县局X i将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局X i对邮件的集中处理时间为1小时（包括邮件的卸装、分拣封发等处理时间）Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局X i；Step4: 区级第二班次邮车从地市局D出发将邮件运送到各县局X i和沿途支局，并将各县局X i收寄的邮件（包括当日各县级邮车运回县局X i的邮件）和沿途支局收寄的邮件运送回地市局D；请注意区级第二班次邮车在县局X i卸装完邮件后的出发时间必须在县局X i的全部县级邮车返回县局并集中处理1小时以后，最终返回地市局D的时间必须在18:00之前。

假设区级两个班次邮车的行驶路线相同，要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z58, Z59, ……, Z73和5个县局X1，……，X5。

各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。

该地区邮局间公路网分布已知，并且县级邮车平均时速为30km/h，区级邮车的平均时速为65km/h，邮车在各支局卸装邮件耗时5分钟，在各县局卸装邮件耗时10分钟。

问题1：以县局X1及其所辖的16个支局Z1, Z2, ……, Z16为研究对象，假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？问题2：采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本。

考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络（县的划分不能变更），请你给出邮路规划和邮车调度方案。

请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。

问题3：考虑到部分县与县交界地带的支局，其邮件由邻县县局负责运送可能会降低全区的运行成本，带来可观的经济效益。

若允许在一定程度上打破行政区域的限制，你能否给出更好的邮路规划和邮车调度方案？（在此同样不必考虑邮车的运载能力的限制，每条邮路的运行成本为3元/公里）问题4：假设县局X 1，……，X 5均允许迁址到本县内任一支局处，同时原来的县局弱化为普通支局。

重新为各个县局选址，陈述迁址理由并以书面材料形式提交省局网运处。

二、模型假设2.1 模型1的假设1) 区级邮车不经过县局1X 所辖的支局，也就是说1X 局的县级邮车必须经过其所辖的16个支局；2) 该县局邮路可以采用任何一种邮路结构形式(辐射形、环形或混合形)；3) 为保证邮车及邮件的安全，在实际运输邮件的过程中邮车绝对不可以超载；4) 邮车到达支局后，先将寄达该支局的邮件卸下，再将该支局收寄的邮件装上，整个邮件交换过程为5分钟。

2.2 模型2的假设1) 如果区级邮车经过某县局所辖的支局，那么该县局的邮车就不再经过这些个支局；2) 该地区的邮路可以采用任何一种邮路结构形式(辐射形、环形或混合形)；3) 区级第二班次邮车的行驶路线同第一班次邮车的行使路线完全相同，也需要在沿途经过的支局停车，完成与这些支局的邮件交换过程；4) 邮车到达支局后，先将寄达该支局的邮件卸下，再将该支局收寄的邮件装上，整个邮件交换过程为5分钟；5）不考虑邮车的超载情况。

6）市局的第一次班车都是从6：00出发，第二次班车都是在18：00点返回。

2.3 模型3的假设1) 县局邮局可以负责其他县局所辖支局的邮件运输问题，市局所辖的支局还必须由市局邮车来负责。

2) 其他假设同问题2的假设。

2.4 模型4的假设1) 县级邮局可以设在原县级邮局所辖的任意支局上，也可以是原县级邮局所在的邮局；2) 县级邮局不可以打破行政区域限制运送邮件，也就是说新的县级邮局仍负责其所辖的各支局的邮件运送。

3) 其他假设同问题2的假设。

三、符号说明x ——表示节点之间的连通情况ij Dist ——表示从节点i 到节点j 的路程ij ER ——表示从节点i 到节点j 的过程中邮车的空车率i Chan ——表示邮车在过节点i 后车上邮件的变化量i Up ——表示节点i 处收寄的邮件i Down ——表示寄达节点i 处的邮件p ——表示邮路的运行成本k U ——表示k 局必须负责的支局集合四、模型准备、分析本课题阐述的是曲面上多个附加条件回路（巡回）的实现问题。

某些算法（如蚁群算法）需要网络图中各点的精确坐标，而实际上，本题只给出了相对位置，我们认为如果利用Phtoshop 等软件将图形中的点生成绝对坐标会有一定的误差可能会影响结果。

为此我们找寻新的算法。

注：比如说，根据图中的点的位置，4547,Z Z 和51Z 三个点构成明显的平面三角形。

则边4547Z Z 的长度和边4751Z Z 的长度之和大于边4551Z Z 的长度。

但是4547475145511119Z Z Z Z Z Z +=+=，显然不满足平面上图形的性质。

而且表中还有很多类似的不满足平面上的图形性质的点。

故我们可以推断，题目中给出的图不是在平面上的。

4.1 数据前期预处理4.1.1生成邻接距离矩阵利用题目所给的条件，利用软件Mathematica6.0生成任意两点的距离矩阵命名为：dist 文件格式为txt 或xls。

注：为方便Lingo 可能的计算，我们将无穷大取为100004.1.2任意子图的距离矩阵生成器 newmatrix.nb为方便后续的讨论，我们利用软件Mathematica6.0定义了可以生成任意子图的距离矩阵生成器名称newmatrix.nb ，它可以计算出任何子图的邻接矩阵。

4.1.3生成最小距离矩阵 Mind.xls我们利用Flody 算法，计算出任意两点间的最小距离。

以方便后期的计算。

4.1.4生成x1县区的距离矩阵 dist1.xls为方便问题一求解先生成生成x1县区的距离矩阵4.1.5生成各区域各自的距离矩阵 disti.xlsdisti i=1 (6)4.1.6生成tsp 问题的Lingo 模板 tsptiaoshimoban.lg4由于我们在某些情形下使用矩阵生成器和tsp 问题的模板，我们将Lingo 的tsp 模板的数据路径始终指定为：DIST = @ole('e:\juzhen\santiao4','d');4.2 问题一分析问题1仅仅讨论地区1X 的邮路调度，但这里需要考虑车辆的个数限制，可以根据邮件总量和邮车满载量来确定邮车数量的下限。

县局的邮车需要把寄达局为16个支局1216,,Z Z Z L 的所有邮件寄达至相应的支局，根据题目中给的数据，可以得到，县局邮车需要从县局运出的总邮件量为176袋，而每辆县级邮车最多容纳65袋邮件，且176 2.7165≈，所以该县局至少需要在县局装3次邮件。