文档介绍：..页眉.. 页脚.. 第 38 卷第 14期 2008 年7月数学的实践与认识 MATHEMATICS IN PRACTICE AND THEORY July, 2008 邮政运输中邮路的规划和邮车调度问题的研究金钢, 师群昌, 刘小麟( 西南财经大学经济信息工程学院, 成都 610074) 摘要: 以邮政运输网络中运输效益最优为目标, 建立了分步规划的图论模型. 运用 Floyd 算法、 Kruskal 算法对模型进行分步求解并逐步优化, 通过 Matlab 、 Lingo 、 SPSS 软件求解, 提出三种优化邮路、降低邮车调度成本的方法. 模型对解决邮路问题、单旅行商、多旅行商等相关问题具有普遍适用性, 可以推广到点数更多 TSP 的问题. 关键词: 邮路规划; 分步规划图论模型; Floyd 算法; Kruskal 算法 0引言收稿日期:2008-04-01 截至 2006 年年底, 中国邮政共有局所、代办点 万处, 其中设在农村的有 万处;中国邮政覆盖全国城乡 3 万多个网点, 邮路总长度( 单程) 万公里, 并与世界 200 多个国家和地区建立业务联系. 如何继续发挥中国邮政的这种本土发展起来的“得天独厚”的优势, 进一步降低邮路运输的成本, 成为中国邮政防御快递公司和外资巨头双边竞争的首要任务. 本文将以某地的邮政网点分布图为例( 具体数据参见 07 年研究生数学建模竞赛 D题), 在以下假设条件下, 提出三种优化邮路、降低成本的方法: 图11 问题假设 条件假设 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. 邮车的发车、到达等所有时间数据均精确到分钟. 符号假设 D,