文档介绍：..页眉.. 页脚.. 邮路规划和邮车调度的优化一、问题的提出本题是 2007 年全国研究生数学建模竞赛 D题,题目如下: 我国的邮政运输网络采用邮区中心局体制,即以邮区中心局作为基本封发单元和网路组织的基本节点,承担着进、出、转口邮件的处理、封发和运输任务, 在此基础上组织分层次的邮政网。邮路是邮政运输网络的基本组成单元, 它是指利用各种运输工具按固定班期、规定路线运输邮件, 并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。邮路的结构形式有三种:辐射形、环形和混合形。如图 1所示,邮路 A为一条环形邮路,邮路 B为一条辐射形邮路。图1 邮路示意图 1、辐射形邮路:是指从起点局出发,走直线或曲折线的邮路,其特点是不论用一种或几种运输工具联运,从起点到终点后,仍按照原路线返回出发地点。因此须在同一条路线上往返两个行程。这种邮路可以缩短运递时间,加快邮运速度。但它的联系点较少,需用的运输工具较多,所耗费用较大。 2、环形邮路:是指邮政运输工具走环形路线的邮路,即运输工具从起点出发单向行驶,绕行一周,经过中途各站,回到出发地点。它的特点是不走重复路线,联系点较多,运输工具的利用率高,运费也较省。但是邮件送到最后几个交接点的时间较长。 3、混合形邮路:是指包含辐射形和环形两种结构形式的邮路。某地区的邮政局、所分布如图 2所示,分为地市中心局(简称地市局)、县级中心局(简称县局)和支局三级机构,该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成,县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服务质量,我们需要对该地区的邮政运输网络进行重构,确定合适的邮路规划方案并进行邮车的合理调度。为了满足邮政的时限要求,必须尽可能地保证各县局、支局在营业时间内..页眉.. 页脚.. 收寄的多数邮件能当天运送回地市局进行分拣封发等处理,以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车,从县局到支局每天仅有一班车。该地区的邮政运输流程及时限规定如下: Step1 :区级第一班次邮车从地市局 D 出发将邮件运送到各县局 Xi 和沿途支局,并将各县局 Xi 和沿途支局收寄的邮件运送回地市局 D;区级第一班次邮车出发时间必须在 06:00 之后,返回地市局 D时间必须在 11:00 之前。 Step2 :县局 Xi 将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理,按寄达支局装上相应的县级邮车;县局 Xi对邮件的集中处理时间为 1小时(包括邮件的卸装、分拣封发等处理时间)。 Step3 : 各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局 Xi;图2 某地区邮政局、所分布图(图中代号 1至 73 依次代表支局 Z 1,Z 2, ……,Z 73) ..页眉.. 页脚.. Step4 :区级第二班次邮车从地市局 D 出发将邮件运送到各县局 Xi 和沿途支局,并将各县局 Xi 收寄的邮件(包括当日各县级邮车运回县局 Xi 的邮件) 和沿途支局收寄的邮件运送回地市局 D ;请注意区级第二班次邮车在县局 Xi 卸装完邮件后的出发时间必须在县局 Xi的全部县级邮车返回县局并集中处理 1 小时以后,最终返回地市局 D的时间必须在 18:00 之前。假设区级两个班次邮车的行驶路线相同,要求区级邮政运输网必须至少覆盖该地市附近的 16 个支局 Z58,Z59, ……,Z73和 5 个县局 X1 , ……, X5 。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公路网分布见表 1,并且县级邮车平均时速为 3 0km/h ,区级邮车的平均时速为 65km/h , 邮车在各支局卸装邮件耗时 5分钟,在各县局卸装邮件耗时 10分钟。问题 1: 以县局 X1 及其所辖的 16个支局 Z1, Z2, ……, Z16 为研究对象,假设区级第一班次邮车 08:00 到达县局 X1 ,区级第二班次邮车 16:00 从县局 X1 再出发返回地市局 D,若每辆县级邮车最多容纳 65袋邮件,试问最少需要多少辆邮车才能满足该县的邮件运输需求?同时,为提高邮政运输效益,应如何规划邮路和如何安排邮车的运行? (邮件量见表 2,空车率=( 邮车最大承运的邮件量(袋)- 邮车运载的邮件量(袋))/ 邮车最大承运的邮件量(袋) ,单车由于空车率而减少的收入为(空车率*2元/km )) 问题 2: 采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入, 从而显著降低全区邮政运输网的总运行成本。考虑投入车况较好的邮车,通常每条邮路只需要一辆邮车即能满足运载能