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