邮政运输中邮路规划和邮车调度问题研究分析.docVIP

第38卷第14期 2008年7月 数学的实践与认识 MATHEMATICS IN PRACTICE AND THEORY Vol.38　No.14　 July, 2008　 邮政运输中邮路的规划和邮车调度问题的研究 金　钢,　师群昌,　刘小麟 (西南财经大学经济信息工程学院,成都　610074) 摘要:　以邮政运输网络中运输效益最优为目标,建立了分步规划的图论模型.运用Floyd算法、Kruskal算 法对模型进行分步求解并逐步优化,通过Matlab、Lingo、SPSS软件求解,提出三种优化邮路、降低邮车调度 成本的方法.模型对解决邮路问题、单旅行商、多旅行商等相关问题具有普遍适用性,可以推广到点数更多 TSP的问题. 关键词:　邮路规划;分步规划图论模型; Floyd算法; Kruskal算法 0　引　　言 收稿日期:2008-04-01 　　截至2006年年底,中国邮政共有局所、代办点6.3万处,其中设在农村的有4.4万处;中 国邮政覆盖全国城乡3万多个网点,邮路总长度(单程)340.6万公里,并与世界200多个国 家和地区建立业务联系.如何继续发挥中国邮政的这种本土发展起来的“得天独厚”的优势, 进一步降低邮路运输的成本,成为中国邮政防御快递公司和外资巨头双边竞争的首要任务. 本文将以某地的邮政网点分布图为例(具体数据参见07年研究生数学建模竞赛D题),在以 下假设条件下,提出三种优化邮路、降低成本的方法: 图1 1　问题假设 1.1　条件假设 1.邮政网点分布如右图所示,假设区级两个 班次邮车的行驶路线相同,要求区级邮政运输网必 须至少覆盖该地市附近的16个支局Z58,Z59,…,Z73 和5个县局X1,…,X5;各县级邮政运输网必须覆盖 本县内区级邮车不到达的支局;从地市局到县局每 天两班车,从县局到支局每天仅有一班车:区级第 一班次邮车从地市局出发将邮件运送到各县局和 沿途支局,并将各县局和沿途支局收寄的邮件运送 回地市局;区级第一班次邮车出发时间必须在 06:00之后,必须在11:00之前返回地市局;区级第 二班次邮车(路径与第一班邮车相同)从地市局出发将邮件运送到各县局和沿途支局,并将 各县局收寄的邮件(包括当日各县级邮车运回县局的邮件)和沿途支局收寄的邮件运送回地 市局;区级第二班次邮车在县局卸装完邮件后的出发时间必须在县局的全部县级邮车返回 县局并集中处理1小时以后,最终必须在18:00之前返回地市局;2.县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件 进行集中处理,按寄达支局装上相应的县级邮车;县局Xi对邮件的集中处理时间为1小时 (包括邮件的卸装、分拣封发等处理时间).区级第二班次邮车必须在县局Xi的全部县级邮 车返回县局并集中处理1小时以后才能出发,最终返回地市局D的时间必须在18:00之前; 3.假设区级邮车速度为65km/h,县级邮车的速度为30km/h;邮车在各支局卸装邮件耗 时5分钟,在各县局卸装邮件耗时10分钟; 4.邮车的发车、到达等所有时间数据均精确到分钟. 1.2　符号假设 D,X1,…,X5,Z1,…,Z73:标记地市局、县局和支局点;Si:寄达局为Zi点邮件量;Ri:支 局Zi收寄的邮件;Ti:遍历区域i需要的时间;t1:表示邮车在支局点停留需要的时间;t2:表示 邮车在县局点停留需要的时间;yij:表示邮局i与j之间邮车通过的次数;xij:0-1变量,0代 表i、j点之间是否有邮车经过;qij:邮车运行在Zi到Zj路程上是的邮包数量;v1:县级邮车的 速度;v2:区级邮车的速度. 2　优化邮路、降低成本方法综述 2.1　在全地区范围内,寻找满足时间约束的路径最短的邮路 2.1.1　问题分析及模型的准备 1)问题中的目标约束 实际中,采用尽可能少的、尽可能短的邮路,可减少邮政部门车辆和人员等的投入,从而 降低全区邮政运输网的总成本;从而在解决问题中尽量使所有邮车走过路程之和最短为目 标,即: min　∑ 76 i=1∑ 76 j=1 C·yij·Kij 其中:C为每条邮路的运营成本;K为邮局间距离形成的邻接矩阵,Kij表示第i个邮局与j 个邮局间的距离,具体表达为: Kij=+∞　(当邮局i与邮局j不直接相连) k　(当邮局i与邮局j直接相连,k即为邮局i与邮局j间的距离) 　　2)运行时间约束 对于区级邮车:每条邮路一天发车两次,并且区级邮车1运行时间必须满足在6:00- 11:00范围内,则区级邮车单次运行时间T0n必在5(11 - 6 = 5)小时范围内,区级邮车2的 返回时间最晚为18:00,发车顺序为区级邮车1早于区级邮车2,同时,在每一个县局邮局邮 车停留10分钟,在每一个支局邮车停留5分钟,则有: T0n=D0nv2+t160·N0n+t2