邮政运输网络中的邮路规划和邮车调度优化研究LINGO具体应用.pdfVIP

全国第四届研究生数学建模竞赛 全国第四届研究生数学建模竞赛 题号 D 题 目 邮政运输网络中的邮路规划和邮车调度优化研究 摘 要 本文借助于图论典型算法（如Flody算法），以及运筹学图上作业法等典型手法， 深入研究了一类曲面上的带附加条件的多路巡回问题。分别回答了县区、市区邮政网 络的邮路规划调度问题及其关于县区部分边界变动、和县区邮政中心变化引起的灵敏 度分析。并且针对每一问建立了相应的优化模型。 针对第一问、先回答了车辆个数的下确界，并用试探算法明确了三个子巡回可行， 并针对三个子巡回设计了新颖的算法，先将问题松弛，将约束条件转化为准则库，找 寻到经过县局的满足荷载限制的子巡回，然后定义每个子巡回的标示码、校验码、在 程序中成功定义了映射，实现了三个子巡回的邮政网络划分，找到了问题的可行解域， 然后以空载费用为目标函数，找到了空载费用为55.67的最优方案。且该方案通过了 检验。 针对第二问，针对市、县两级邮政网络图的特点，寻求局优解，借助于市区的最 小生成树、以及市局、县局的最短路径，从中心向四周辐射，安排各子巡回，以区级 车辆往返时间特点为约束，以子巡回的空余时间为罚函数，以环形回路为主兼顾辐射 型回路，优先安排快车巡回，设计了相应的算法，并且给出了初始方案，且利用我们 的方法调整方案，得到满意解，需要用 13 辆邮车完成全区的邮件任务，全区的总邮 路路程为2453公里。 针对第三问，我们以减少邮路车辆为目标，研究了县区边界需要调整的点的特点， 利用邻接区域的罚函数较大的回路破圈，重新构造子巡回。既满足时间约束，又达到 了降低费用和减少邮路车辆的目的。通过我们的工作，可以减少两个邮车，总路程变 比第二问减少了258 公里 针对第四问，我们定义了区域中心即为到达所有各点的距离之和为最小的点，但 是邮政网络中的中心不仅取决于距离，同时由它的度数以及周围区域点的度数综合决 定，我们利用 Mthematica 和 Lingo 中的 tsp 模板，借鉴第二问的表上作业法，和第 三问灵敏度分析的经验，减少了两辆邮车，减少了 284 公里的邮路。 参赛密码 （由组委会填写） 1 参赛队号 1029001 参赛学校 中国矿业大学 参赛队员姓名 姜英姿 卓金武 秦 健 一、问题重述 邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规 定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。邮 路的结构形式有三种：辐射形、环形和混合形。 辐射形邮路可以缩短运递时间，加快邮运速度。但它的联系点较少，需用的运输 工具较多，所耗费用较大。环形是不走重复路线，联系点较多，运输工具的利用率高， 运费也较省。但是邮件送到最后几个交接点的时间较长。混合型二者兼有。 某地区的邮政局分为地市局、县局和支局三级机构。该地区的邮政运输网络由区 级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地 市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县 局的县级邮车所行驶的全部邮路构成。 时限与成本是邮政运输问题的两个重要指标。时限是指邮电部规定的邮件、报刊 处理、传递的最大时间限制，时限关系到邮政通信质量的好坏；成本影响着企业