07D邮政运输网络中的邮路规划和邮车调度.doc.doc

2007 年全国研究生建模竞赛赛题 D题: 邮政运输网络中的邮路规划和邮车调度一、问题的来源及意义: 在信息技术飞速发展的今天, 互联网已经成为一种重要的通信手段, 但在我们利用 Em a il 等方式交流信息的同时, 邮政作为传统的通信手段仍然与我们的日常生活和工作息息相关, 发挥着不可替代的作用. 我国的邮政生产过程由收寄、分拣封发、邮政运输和投递四大环节组成. 邮政运输作为邮政生产过程的第三大环节, 是邮政赖以传递邮件实现实物空间转移的物质基础, 涉及航空、铁路、公路、水运等多种运输途径以及各种邮政设施. 时限与成本是邮政运输问题的两个重要指标. 时限是指邮电部规定的邮件、报刊处理、传递的最大时间限制, 时限关系到邮政通信质量的好坏; 成本影响着企业的经营. 我国将邮件按时限要求大致划分为快件和普件, 针对不同的邮件类别实施相应的运输计划. 快件主要强调传递时限短, 普件着重考虑邮件运输成本的降低. 在进行邮路规划和安排邮车运行计划时, 针对不同的邮件种类, 在不影响时限标准实现的前提下, 必须尽可能地降低成本. 邮政运输网络是邮政企业运营的重要保障, 20 世纪 60 年代以来, 发达国家随着社会经济的发展, 为了使邮政满足社会的需求, 适应相关行业之间的竞争形势, 对邮路的结构、通信组织方式及运行机制作了较大的调整, 逐步扩大网络的覆盖区域, 并按时限要求改进业务分类, 开办快件等业务. 随着 U PS 等国际性物流公司进驻国内, 我国邮政正面临极大的挑战. 我国邮政必须发挥自身优势, 在缩短邮件运输时限和降低成本的同时, 节约能耗和人力资源, 提高邮政行业的服务质量和信誉, 切实提高我国邮政的运行效益, 保持邮政行业的竞争能力和取得良好的社会效益. 二、问题描述: 我国的邮政运输网络采用邮区中心局体制, 即以邮区中心局作为基本封发单元和网路组织的基本节点, 承担着进、出、转口邮件的处理、封发和运输任务, 在此基础上组织分层次的邮政网. 邮路是邮政运输网络的基本组成单元, 它是指利用各种运输工具按固定班期、规定路线运输邮件, 并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线}. 邮路的结构形式有三种: 辐射形、环形和混合形. 如图 3 所示, 邮路 A 为一条环形邮路, 邮路 B 、辐射形邮路: 是指从起点局出发,走直线或曲折线的邮路, 其特点是不论用一种或几种运输工具联运, 从起点到终点后, 仍按照原路线返回出发地点. 因此须在同一条路线上往返两个行程. 这种邮路可以缩短运递时间, 加快邮运速度. 但它的联系点较少, 需用的运输工具较多, 、环形邮路: 是指邮政运输工具走环形路线的邮路, 即运输工具从起点出发单向行驶, 绕行一周, 经过中途各站, 回到出发地点. 它的特点是不走重复路线, 联系点较多, 运输工具的利用率高, 运费也较省. 、混合形邮路: 是指包含辐射形和环形两种结构形式的邮路. 某地区的邮政局、所分布如图 4 所示, 分为地市中心局( 简称地市局) 、县级中心局( 简称县局) 和支局三级机构, 该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成. 区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成, 县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成. 为使邮政企业实现低图 3邮路示意图图4某地区邮政局、所分布图(图中代号 1至 73依次代表支局 Z1,Z 2,…,Z 73 ) 成本运营和较高的服务质量, 我们需要对该地区的邮政运输网络进行重构, 确定合适的邮路规划方案并进行邮车的合理调度. 为了满足邮政的时限要求, 必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理, 以及每天到达地市局的多数邮件能当天运送到目的地县局、支局. 该地区从地市局到县局每天两班车, : Step 1 区级第一班次邮车从地市局 D 出发将邮件运送到各县局 X i 和沿途支局,并将各县局 X i 和沿途支局收寄的邮件运送回地市局 D; 区级第一班次邮车出发时间必须在 06: 00 之后, 返回地市局 D 时间必须在 11: 00 之前. Step 2 县局 X i 将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理, 按寄达支局装上相应的县级邮车; 县局 X i 对邮件的集中处理时间为 1 小时( 包括邮件的卸装、分拣封发等处理时间). Step 3 各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局 X i