邮政运输网络中的邮路规划和邮车调整.pdf

《邮政运输网络中的邮路规划和邮车调整.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、万方数据第38卷第14期Z008年7月数学的实践与认识VoI．38No．14MATHEMATICSINPRACTICEANDTHEORY邮政运输网络中的邮路规划和邮车调整高玉建，苏昊，黄飞(北京航空航天大学，北京IO0083)。摘要：主要针对我国邮政运输业中邮路规划和邮车调整问题，研究了在规定时间、规定邮车运载能力限制的条件下，单个县级邮区内的最小成本／最小空车率邮路规划以及多个邮区协同规划的策略，提出了一个用于辅助规划的邮路存在性定理，设计并实现了基于最小生成树和TSP的县级邮路规划算法．最后在打破县区行政规划的基础上。对整个市区的支局进行重新划

2、分并求解得到了优于前面邮路规划的新方案．关键词：邮路规划；邮政运输效益；TsP；最小生成树1问题介绍．邮政运输网络中的邮路规划和邮车调度问题，详见第4届全国研究生数学建模竞赛D题．2模型假设1)市邮局邮车每天早晨6点准时从市局出发前往各邮局；2)县邮局邮车在收到市邮局送来的邮件后才前往各个支邮局；3)邮车到达目标支局后会写下寄往该支局的所有邮件，并装上该支局寄送出去的所有邮件；，4)县邮局收到市邮局送来的信件后对邮件进行集中处理的时间为1小时；，5)县邮局收到各支邮局送来的信件后对邮件进行集中处理的时间为1小时；6)邮车在各支局卸装邮件耗时5分钟，

3、在各县局卸装邮件耗时10分钟；．7)各邮车匀速行驶，并且不会出现故障．3问题分析及求解’3．1问题一设Ⅳ表示X，所辖县区内的邮路数，C表示县级邮车最多能容纳的邮件袋数，M。表示X。辖区内所有支局要收取的邮件总量，Mz表示X，辖区内所有支局要寄送的邮件总量，那么最少的邮车数Ⅳ应当满足：(Ⅳ一1)×C≤M。≤N×C(Ⅳ一1)×C≤M：≤Ⅳ×C从附表1给出的数据可以计算出县局需要运送到支局的邮件量为176袋，由各个支局运送到县局的邮件量为170袋．每辆县级邮车最多容纳65袋邮件，由于65×2

4、下界为3．下面我们试着给出一种邮车数为3的邮路规划及邮车调度方案，使每辆车在不超过最大承运邮件量(65袋)并且不违反邮政运输流程及时间限制的条件下，完成该县每天的邮件运输任务，并且使由于空车率而减少的收收稿日期：2008—04—01万方数据174数学的实践与认识入达到最少．由于邮路规划受到邮车运载能力的限制，因此在设计邮路方案时不仅需要考虑一个邮路上都存在哪些支局，同时通过支局的顺序也是至关重要的．给定一组支局，我们很难直观地判断是否存在一条邮路，既满足邮车的运载能力的限制，又可以通过所有支局，针对这个问题，我们提出了如下的邮路存在性定理，以方便邮

5、路规划最优化模型的建立：定理1设邮车运载上限为C，途经邮局Z。，Z：，⋯，Z。，邮局Z，需要收取信件Car，袋，待寄邮件为Col，袋，若∑Carj之c且∑Col，0，则车上空间将会减小．设将Mi按照升序排列后得到的序列为尬，，M：，⋯，眠，若将X—Z，一Z‘．··一Z～一X作为一个邮

6、车工作的路线，则易知在停靠邮局ik后车上的邮件数为Carry巩∥。一∑Carj+J=1^’∑尬．，且车上的载重将经过一个先单调不增(M。≤o)再单调不减(M。≥o)的过程，因此，J=1邮车载重的最大值将出现在遍历出发时刻或遍历结束时刻．但由定理的条件，≥：Cari

7、出任意两个邮局(包括县局和支局)之间的最短距离，并保存该最短距离矩阵以备后面的模型求解使用．下面我们首先建立模型的一些约束条件：设Cari表示由县局X。运往支局Z．的邮件数量，Col，表示由支局Z，带到县局的邮件数量，Carryg。表示第g条邮路从支局i到支局歹运载的邮件总数，并设C表示每个邮车最多运载的邮件数，则每个Carry“∥+，应当满足：，Carryn时】

8、l≥M(3．1．2)根据如上的约束条件，我们可以建立如下的最优化模型：第g组邮车在从Z“前往Z“+。时，其空车率为：、Em