邮政运输中邮路的规划和邮车调度问题的研究

《邮政运输中邮路的规划和邮车调度问题的研究》由会员分享，可在线阅读，更多相关《邮政运输中邮路的规划和邮车调度问题的研究（8页珍藏版）》请在金锄头文库上搜索。

1、第 38 卷第 14 期 2008 年 7 月 数学的实践与认识 MATHEMATICS IN PRACTICE AND THEORY Vol.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 题),在以 下假设条件下,提出三种优化邮路、降低成本的方法: 图 1 1 问题假设 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 变

6、量,0 代 表 i、j 点之间是否有邮车经过;qij:邮车运行在 Zi 到 Zj 路程上是的邮包数量;v1:县级邮车的 速度;v2:区级邮车的速度. 2 优化邮路、降低成本方法综述 2.1 在全地区范围内,寻找满足时间约束的路径最短的邮路 2.1.1 问题分析及模型的准备 1)问题中的目标约束 实际中,采用尽可能少的、尽可能短的邮路,可减少邮政部门车辆和人员等的投入,从而 降低全区邮政运输网的总成本;从而在解决问题中尽量使所有邮车走过路程之和最短为目 标,即:min 76i=1 76 j=1 CyijKij 其中:C 为每条邮路的运营成本;K 为邮局间距离形成的邻接矩阵,Kij 表示第 i 个

7、邮局与 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+t160N0n+t260M0n 5

8、 其中:T0n:第 n 辆区级邮车单次运行时间(小时);D0n:第 n 辆区级邮车单次运行的路程 (km);N0n:第 n 辆区级邮车单次运行中通过的支局个数;M0n:第 n 辆区级邮车单次运行中通 过的县局个数; 对于县级邮车:每天的出发时间最早只能在区级邮车 1 到达 1 小时后开出,同时返回县 局的最晚时间必须在区级邮车 2 离开该县局的前 1 小时前,故有县局车的运行时间 Tmn 在 18 18514 期金 钢,等:邮政运输中邮路的规划和邮车调度问题的研究- 6 - 12 -T0n= 10 -T0n 范围内,则有: T0n=Dmnv1+t160Nmn+t260Mmn 10 -T0n(m

9、= 1,2,5) 其中:Tmn:第 m 地区第 n 辆区级邮车单次运行时间(小时);Dmn:第 m 地区第 n 辆区级邮车单次运行的路程(km);Nmn:第 m 地区第 n 辆区级邮车单次运行中通过的支局个数;Mmn:第 m 地区第 n 辆区级邮车单次运行中通过的县局个数. 3)覆盖点的约束 全市的所有邮局每天都必须覆盖所有的点,则有: 5m=0nNmn+ 5m=0nMmn= 78 并且: 5m=0nNmn= 73, 5m=0nMmn= 5 2.1.2 模型的建立与求解 对问题二的研究仍然可以归结为多旅行商的分步图论规划模型.我们所需考虑的是在 一天的调度中,在满足邮车运行时间的限制的情况下,

10、使所有车通过的路径之和最短,则可 以建立如下规划模型:min 76i=1 76 j=1 CyijKij s.t 5m=0nDmn= 76i=1 76 j=1 yijKij T0n 5 Tmn 10 -T0n 5m=0nNmn= 73 5m=0nMmn= 5(m= 1,2,5) (2.1)由于此模型不是规范的规划模型,直接求解难度会很大,故而在模型的求解中我们采用 分步规划,首先考虑市局邮车的安排情况和所走的路程.1)区级邮车路径的选择模型:运用单旅行商模型分步求解 首先对市区邮车所走的邮路进行规划,首先根据邮局间任意两点间的最短距离得出区 车遍历所有市区点和 5 个县局所需通过的最短距离为 D

11、is,初步得出所需的区车数为: n= Dis v2+t1N0n60+t2M0n60T(2.2)在由 D,X1,X5,Z58,Z73 构成的图 G0 中,根据克鲁斯卡尔算法求出的该图的最小 支撑树,将该图分为 n 个子图 G0k(k= 1,2,n),在每一个子图中,相当于解决单旅行商问 题,建立寻找区车的最短回路模型1:min i,jG0kKijhij 186 数 学 的 实 践 与 认 识 38 卷 s.tjG0khij= 1 iG0k,(限制每一个顶点的出度为 1) jG0khji= 1 iG0k,(限制每一个顶点的入度为 1) ui-uj+nhij n- 1,2 ij n xij= 0,1

12、, i,j= 1,2,n (2.3) 其中:hij=0 (表示点 i 与点 j 间无连接) 1 (表示点 i 与点 j 间有连接) 2)县级邮车路径的选择模型: 在确定好区级邮车所走路径后,我们利用寻找区级邮车路径的相似方法,求出每个县邮 局点构成的图 Gm(m= 1,2,5)的最小支撑树,并将图 Gm 划分成适当个数的子图 Gmk(k 为图 Gm 划分出的子图个数).同样利用解决单旅行商问题的方法,建立寻找县车最短路径模 型: 2.1.3 问题的求解 问题中,寻求最优的邮路路径实际上相当于解决一个多旅行商的问题,多旅行商问题的 最优解旅行路线的总路程达到最小,但是路线的均衡性可能相当差.因此

13、,当要求均衡性较 好的解还需要做大量的调整工作.对于本题的规模(包括邮局共有 79 个点)要想求得真正的 最优解是不现实的.为此在求解中,我们采用分步图论规划方法求解. 1.邮车数量的确定 1)区级邮车数量的确定 根据邮局间任意两点间的最短距离得出区车遍历所有市区点和 5 个县局所需通过的最 短距离为 721km,初步得出所需的区车数为 2.57 辆.则初步取 3 辆区车运行. 2)县级邮车数量的确定 根据县内邮局点构成图的最小支撑树,在使每个县尽量使用较少邮车以及全区运行总 路程最小的约束下,进行邮路区间的划分,划分后,使每一个邮路区间内一辆邮车能够覆盖 完所有的邮局并且邮路路程尽量短. 图

14、 2 各地市局区域内支局点与县局点生成的最小支撑树 在这种情况下得到的县内邮路区间的个数即为该县所需县级邮车的数量. 2.最小支撑树的求解 使用克鲁斯卡尔(Kruskal)算法2,利用 Matlab 求解,得到最小支撑树. 1)区内邮局与各县局 构成图的最小支撑树 对于由邮局 D,X1,X5,Z58,Z73 构成的图 G0, 通过 matlab 求解,求得其最 小生成树见图 2(左). 2)各县局内邮局构成 图形成的最小支撑树 对于由各县邮局分布 图,通过 matlab 求解,求得 18714 期金 钢,等:邮政运输中邮路的规划和邮车调度问题的研究其最小生成树见图 2(右). 3.邮车邮路路径

15、及邮车调度 1)单旅行商问题求解 车辆的数量最少是三辆,当车数为三辆时. 问题转化为单旅行商问题的求解,应用 Lingo 软件,程序建模求解:Min i,jAdijxij s.t.jVxij= 1,iV,(每个点出度为 1) jVxji= 1,iV,(每个点入度为 1) ui-uj+nxij n- 1,2 ij n xij= 0,1,i,j= 1,2,n (1.4)在求单个旅行商的最短路径时,首先假设该最短路径不包含辐射型邮路,第二步,将所 有节点的数据代入 lingo 单旅行商最短路径算法,求解;若无法求得可行解,则说明最短路径 一定含有辐射形邮路,通过 matlab 求节点度算法求得度的节

16、点,将度为 1 的节点筛出并剔 除,并将其它数据重新代入步骤二的操作. 经过六次调整以后发现三辆车在限定的时间内无法完成到达五个支县的任务. 改用四辆车运行初次规划可求得的区级邮车最短路径. 2)逐步寻优 对求出的路径根据如下规则进行局部调整: A、调整区车的行走区间,看能否减少县车的数量; B、调整区车,使区车经过其行走路径附近邮局,看能否减少总的行使路径. 3)求解结果 求解得所需区级邮车为 4 辆,县级邮车 11 辆,最小运营路程为 2272km/天,最小运营成 本为 6816 元/天. 邮车行使路径图 图 3 邮车行使路径 最短路径长度及其所耗时间(由于行使路径图中已提及,考虑篇幅原因略) 邮车时间调度 188 数 学 的 实 践 与 认 识 38 卷表 7 问题二中各县车发车时间约束表 该邮局最早发车时间 X1X2X3X4X5 邮车最晚返回初始点时间 10:11 8:47 8:21 10