07年数学建模]邮政运输网络中的邮路规划和邮车调度

《07年数学建模]邮政运输网络中的邮路规划和邮车调度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、邮政运输网络中的邮路规划和邮车调度第二周培训论文摘要对小规模TSP问题，建立了可精确求解方案的0-1规划模型，并在满足邮政运输需求的前提下给出了最佳方案。问题一首先以县支局、县局为顶点构建无向赋权图，通过Floyd算法求解各局间的最短距离；然后以Fijk为决策变量，以邮车工作时间、车辆运载能力为主要约束，以总空载损失费用最小为目标0-1非线性规划模型，运用规划软件Lingo求解。问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本

2、最小为目标，邮车工作时间为约束条件的0-1非线性规划模型求解;然后,建立各县区的最短路矩阵,同样建立0-1非线性规划规划模型求解各县运输方案。关键词：无向赋权图Floyd算法0—1非线性规划问题重述我国的邮政运输网络采用邮区中心局体制，即以邮区中心局作为基本封发单元和网路组织的基本节点，承担着进、出、转口邮件的处理、封发和运输任务，在此基础上组织分层次的邮政网。邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线

3、。邮路的结构形式有三种：辐射形、环形和混合形。某地区的邮政局分为地市中心局（简称地市局）、县级中心局（简称县局）和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案并进行邮车的合理调度。为了满足邮政的时限要求，必须尽可能地保证各

4、县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。该地区的邮政运输流程及时限规定如下：Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。Step2:县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮

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

6、以后，最终返回地市局D的时间必须在18:00之前。假设区级两个班次邮车的行驶路线相同，要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z58,Z59,……,Z73和5个县局X1，……，X5。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公路网分布见表1，并且县级邮车平均时速为30km/h，区级邮车的平均时速为65km/h，邮车在各支局卸装邮件耗时5分钟，在各县局卸装邮件耗时10分钟。问题1：以县局X1及其所辖的16个支局Z1,Z2,……,Z16为研究对象，假设区级第一班次邮车0

7、8:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？（邮件量见表2，空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量(袋))/邮车最大承运的邮件量(袋)，单车由于空车率而减少的收入为（空车率*2元/公里））问题2：采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本。考虑投入

8、车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络（县的划分不能变更），请你给出邮路规划和邮车调度方案。请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。（每条邮路的运行成本为3元/公里）问题分析对于问题一，由于题中仅提供了两支局间直达距离，但这不一定是最短距离。因此，首先需要利用Floyd算法把各支局间的最短路径矩阵D求出。估计最少三辆车可以完成任务，因为县局开出去的车总共要带上176袋邮件，而每辆车最