全国第四届研究生数学建模竞赛
题 目    邮政运输网络中的邮路规划和邮车调度优化研究
摘      要
本文借助于图论典型算法（如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 可能的计算，我们将无穷大取为10000
4.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.xls
disti  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次邮件。另一方面，从时间上来讲，在规定的工作时间内，用2辆邮车又不能完成任务，所以可以确定该县局至少需要3辆邮车。
图1 寻可行回路的算法流程
根据规定的作业要求，县局1X 将当天区级第一班次邮车及前一天的区级第二班
次邮车所送达的本县邮件进行集中处理，且时间为1小时。题目中假设区级第一班次邮车8点到达县局1X ，所以县局邮车只能在9点之后从县局出发。另外，题目中假
设区级第二次邮车16点从县局出发，根据作业要求，县局的邮车需要在15点之前返回县局。所以，县局发出的邮车必须在6个小时之内返回县局。此外对于邮路的形状，
我们认为应优先考虑环形回路兼顾辐射型回路，即混合回路。
该问题类似于多个Tsp回路的问题，同时又在每条弧上有经过节点的包裹增量影响每条弧的容量（不超过65袋），必须考虑到每个邮路有逆时针、顺时针两种运行方式，可能逆时针由于容量的限制走不通，而顺时针可以走通。然后我们考虑三个子巡回。如果存在一个有三个子巡回的方案，就说明了下确界取到了，进一步可以考虑如何求最优解。算法的设想如下：
抓住在每条弧上有经过节点的包裹增量影响每条弧的容量（不超过65袋）这一约束，定义出规则库，生成满足约束的回路库，然后建立特殊的映射以及调用规则，得到松弛问题的可行解域，利用空载费用来充当检验数从而求出最优解。具体设想流程如图1所示。
4．3 问题二分析
先考虑第一辆区级班车，6：00出发到达县局后必须于11:00前返回市局，到达县局时的卸装时间为10分钟，依据flody算法给出的Mind(i,j)，分4-5个不同的方向给出区级班车的运行线路，先给出一个区级班车的运行线路。而后给出第二个区级班车的运行线路，以此类推。在给出第一个区级班车的线路时，现依据Mindij的规律，以x1为例，屏蔽掉显然不可能经过的点(到x1的距离超过Mind(x1,D))的那些点，形成由县局、县区支局、市区支局、市局形成的子图，然后将市区的支局按照Mind(x1,ｊ)分级，这些点必须停留一次，再将县区支局类似分级（县区的支局区级班车尽可能），（＊类似于动态规划的方法求解求出＊），从各级点中遍历路径，完成第一个子图的一个路由，然后在ｘ１县邮政网络图中，完成一＼二个县级班车的运行，县级班车在第一辆区级班车到达一个小时以后发车，且在下午１５：００之前返回县局。这样就完成第一个方向的安排任务。其他方向以此类推。每完成一个方案，可以生成总路程和费用，最后从中择优。
4．4 问题三分析
本问题在问题二的基础上，考虑部分距离本县局距离较远而相对于邻接县局的距离较近的支局在打破行政区域划分时，可以划分到邻接的县区（县级邮政区域）中去。当然这些点如果度数较小处理起来效果会更好。在新的分区基础上，回到问题二进行讨论，应该得到的结果好于第二问。
解决问题的必要性在问题二的可行方案中会有所体现。某些与县局距离较远的点必须到达（连通），会
严重影响县区网络的时限、费用。将他们按照距离与连通性（主要体现在顶点的度数上）相结合的办法予以协调，以寻求较优解。
解决问题的方法是抓住全局网络图的瓶颈之一县局x5（因为它与市局D）的最短距离严重制约着留给该县区网络内部规划调度。我们的想法是形成x1地区较为均衡的两个回路解决x5县区的几个较为孤立的支局所在的区域，然后顺时针展开调整。以减少一路邮车为目的，从而起到降低总费用的目的。
4.5问题四分析
由于历史文化等方面的因素，也许问题三的解决方案会与传统意义上的行政区域相抵触。故考在各县区内部考虑行政区域的划分。
本问题是问题二的延续，在不改变行政区域划分的基础上，改变县级邮政中心的位置，此时应该考虑一方面县局与市局的距离接近了可能会引起县区内部的邮路总行程增加，从而引起总费用的增加；另外一方面县局与市局的距离变远了，可能使得县区内部的邮路总行程减少了，但是县局与市局的邮路行程增加了，从而引起总费用的增加。问题是如何寻求一种均衡使得总费用降低。得到的结果应该好于第二问的结果。
解决问题仍然要抓住关键邮路的瓶颈问题，以x5县区为例，县局的距离与市局

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。