邮政运输网络中的邮路规划和邮车调度研究.pdf

《邮政运输网络中的邮路规划和邮车调度研究.pdf》由会员分享，可在线阅读，更多相关《邮政运输网络中的邮路规划和邮车调度研究.pdf（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第3 9 卷第1 7 期数学的实践与认识V 0 1 3 9N o 1 72 0 0 9 年9 月M A T H E M A T I C SI NP R A C T I C EA N DT H E O R YI l l，、；应用i-t t t t t t t t t t t，邮政运输网络中的邮路规划和邮车调度研究卢晓珊1，何伟2，贺永金3指导老师：杨丰梅1(1 北京化工大学理学院，北京1 0 0 0 2 9)(2 北京化工大学信息科学与技术学院，北京1 0 0 0 2 9)(3 北京化工大学化学工程学院，北京1 0 0 0 2 9)摘要：邮政运输网络是邮政企业运营的重要保障，而邮路规划和邮车调度

2、设计是决定邮政运输网络效率的关键因素，问题1 的邮路规划问题归结为带返程货的车辆路由问题，该问题是N P 难的，采用改进蚁群算法，通过对单环路旅行商问题进行断环分析，将运行线路的好坏反馈给蚁群算法的目标函数，求取最终的优化路径第二问邮路规划扩展到了全区，采用有优先级的分县优化途径寻求最佳邮路最后，给出模型的评价及改进方向关键词：邮路规划；邮车调度；车辆路由；蚁群优化1问题的提出我国的邮政运输网络采用邮区中心局体制，即以邮区中心局作为基本封发单元和网路组织的基本节点，承担着进、出、转口邮件的处理、封发和运输任务，在此基础上组织分层次的邮政网为使邮政企业实现低成本运营和较高的服务质量，需要对问题中

3、地区的邮政运输网络进行重构，确定合适的邮路规划方案并研究合理的邮车调度方案问题1：以县局X，及其所辖的1 6 个支局z。，z 2 一，z。为研究对象，假设区级第一班次邮车0 8：o o 到达县局x，区级第二班次邮车1 6：0 0 从县局X。再出发返回地市局D，若每辆县级邮车最多容纳6 5 袋邮件，最少需要多少辆邮车才能满足该县的邮件运输需求?同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行?问题2：在县的划分不能变更的前提下，应如何构建该地区的邮政运输网络(邮路规划和邮车调度方案)，以降低全区邮政运输网的总运行成本2 模型的建立与求解2 1 模型假设1)定义区中心邮局管辖的附近支局

4、为中心县支局；2)每辆邮车走环形路线，开始且中止于同一点；3)每个支局恰好接受一辆邮车的一次服务；4)每条邮路只需要一辆车即能满足运载能力要求；收稿日期：2 0 0 8 0 5 1 4基金项目：国家自然科学基金(7 0 8 0 1 0 0 3，7 0 7 0 1 0 0 3)通讯作者：杨丰梅 万方数据1 7 期卢晓珊，等：邮政运输网络中的邮路规划和邮车调度研究6 75)区级两个班次邮车的行驶路线相同；6)运行成本为与路线长度成正比，因空车率而减少的收入也与空车率成正比；7)每辆县级邮车最多容纳6 5 袋邮件(仅限第一问)；8)县局x。的邮车最早9：0 0 开出，最晚当天1 5：0 0 回到县局

5、(仅限第一问)；9)区级第一班次邮车出发时间必须在0 6：0 0 以后，返回地市局D 的时间必须在1 1：0 0以前，第二班次邮车必须在晚8 点以前返回地市局D 2 2 符号说明V 一 可。，V l，”，秽。秽。是中心局，口。，秽2，“，秽。是县局，其他顶点为各支局；E 一(口。，V，)l 可，V，V)弧集，表示各局之间的公路；D 一 d i，)D 是距离矩阵，d i，表示i，J 两点间距离；C 一C，)C 是成本矩阵，D，表示i，J 间的运输成本；n 车辆k 的行驶路线；m 派出的车辆数；以t 第k 辆车上的初始邮件量；M a x 县级邮车最多容纳的邮件量；g i 支局i 收寄邮件量；q i

6、 寄达支局i 的邮件量；y 第k 辆车在i，J 之间运行的空车率；k。单位距离单位空车率的损失；五。单位距离的运行成本；秒，县级邮车的平均时速；训：区级邮车的平均时速；艿i 在邮局i 卸装邮件的时间；f 县局对邮件的集中处理时间；$i i 处邮车最早的出发时间；z。i 处邮车最晚的归局时间；f1车辆k 经过支局if1车辆k 从顶点让行驶到顶点V，抽l0否贝04。60否贝0f1采用路线“f1路线n 经过支局i_【0否则”l0否则2 3 问题1 模型的建立定义图G 一(y，E)，艿。一0，d。一一艿。一1 6，艿。一一艿，。一1 1 2，若为中心局或II县局，则s i 一5 0+坚+t，Z，一Z

7、o 一塑一t U 2 U 2图G 上的邮政路线问题实际上是顶点集y 的剖分问题，它可以用一个0 1 规划来表示，任何一条满足要求的路线成为可行路线，它们的全体记为R，这个集合剖分问题的目标是求一组总距离最短的路线集R。，数学模型描述如下：m i nm”l+6n。+Y 膳(g，一q 1)M a x，gki 一7d 叫+d。(z。一一1)z i 一$i9 i，J 一1，7，2 2，gk(1 2)i，m4 l+6口。一q。，k=1i 嚣7Y z 一 0，1)(1 3)(1 4)目标是车辆数最少；(1 1)表示邮车最大装载限制；(1 2)表示县局车一天在外工作的时间限制；(1 3)是合理性约束，所有邮

8、车的初始邮件总量等于寄达各支局的邮件量总和在已知县邮局当天发出的车辆数的情况下，求解最佳行车路线，即为下面的优化问题：万方数据6 8数学的实践与认识3 9 卷(7 i j k x d 州k+x l i k d 删k)k(1，J)r k(i，j)r k。一1，i=7，2 2k7 R。+6以+Y 馒(毋一q i)M a x，Vkd 珊(1 5)(1 1)+3 i(L 7 C 珊一1)z，一s。，i，J=1，7，2 2，Vk(1 2)i，m”l+6口；=q i，k 一1i=7Y i 女，z 珊，z。一 O，1)，r k R(1 3)(1 6)模型目标是使运输成本加上因空车率而减少的损失总和最小，(1

9、 5)表示每个支局恰好接受一辆邮车的一次服务2 4 改进的蚁群算法及求解问题1 的邮路规划问题归结为带返程货的车辆路由问题 1 ，假设只派一辆车，暂不考虑时间和容量约束，那么就变成了旅行商问题，目的是要找到最短哈密尔顿回路，此处的哈密尔顿回路是可以遍访图中每个点一次仅一次的闭合回路，利用蚁群算法 z-5 寻到这条最佳邮路，若不考虑容量和时间限制，最短路径为2 7 9 k m，而考虑邮车容量和时间限制时，搜寻到的最短路径为2 8 5 k m，仅仅相差6 k m，从另一方面可以说明我们的解已经非常接近最优解了估计最少三辆车可以完成任务，因为县局开出去的车总共要带上1 7 6 袋邮件，而每辆车最多承

10、一一载6 5 袋邮件，故最少需要f1 7 6 6 5f 一3 辆车，通过枚举两条返回县局的路径和两条从县局出发的路径来截断这条路，从而形成三条环路(见图1)从构成三条邮路的多种可能的路径选出符合约束的路径，将可行路径数和路径长度变成惩罚项增加到蚁群算法的目标函数中 6 ，通过编程运行这种改进后的蚁群算法，选出最优的邮车调度方案如表1，行驶路线如图2 表1 县局X。最佳邮路和邮车调度方案车次123车次123X 1X 1X 1Z 1 4Z 1 0Z 55 54 36 0Z 1 2Z 9Z 46 04 56 1Z 1 1Z 8Z 35 55 06 0负责支局路径到达支局邮件量姨Z 1 5Z 7Z 2

11、5 25 25 9Z 1 6Z 6Z 15 45 65 8X 1X 1Z 1 36 0X 1费用元5 7 7 3 84 7 5 2 96 9 4 1 4初始邮件量袋6 15 16 4总费用元1 7 4 6 8耗时h4 4 8 3 33 8 8 3 35 2 6 6 7总车次3 万方数据1 7 期卢晓珊，等；邮政运输网络中的邮路规划和邮车调度研究6 9一够图1对T S P 问题的最短环路加截断路径构成多条回路i、：、，一“、j”图2 行驶路线图2 5 问题2 模型的建立与求解问题2 是有时间限制的带返程货的车辆路径问题，考虑到该问题变量太多，直接用蚁群难以全局求解，而且会变成多中心的问题，无法直

12、接用上面改进的蚁群求解我们将问题分解为多各县求解，先考虑区中心邮车的运转，这样能有效的利用区中心的地理位置和区车过非中心县支局的装卸能力先考虑区中心派出的最少邮车数和最佳邮路规划，与第一题方法相同，具体情况是区级第一班次邮车出发时间必须在0 6：0 0 之后，返回地市局D 时间必须在1 1：0 0 之前，也就是第一班次邮车在外运行时间不超过1 1 6 5 个小时，由于假设第二班次与第一班次的行驶路线相同，优化第一班次的邮路即可再用蚁群算法规划各县局的邮路，第二班次邮车在县局X，卸装完邮件后的出发时间必须在县局X，的全部县级邮车返回县局并集中处理1 小时以后，最终返回地市局D 的时间必须在晚八点

13、之前，故各县局邮车在外运行时间不超过2 0 6 511 7 小时得到的整体邮路优化和邮车调度结果如表2 所示注意到最优结果中中心局还负责了Z 1 2、Z 2 7、Z 3 1、Z 4 1、Z 5 2 这五个非中心县支局，若中心县开出的邮车只负责区中心邮局附近的1 6 个支局z 刚z。，z，。和5 个县局x l，一，x。，那么这些支局所在县局就要负责他们的邮件运送，增加的路程会超过距离Z 1 2、Z 2 7、Z 3 1、Z 4 1、Z 5 2 最近点到这些点的一个来回总和3 模型评价与改进本文通过改进的蚁群算法将N P 一难的问题简化，算法灵活性强，适用不同的目标函数和多复杂限制条件的问题，求得较

14、优的解；将总体邮路规划问题分而治之，合理地分解为局部邮路规划，得到局部最优结果后，对边界支局的归属县局进行微调，改进整体最优解模型假设区级两班车的行驶路线相同，但是实际中两班车的路线可能不同，所以下一步可以考虑在区级两班车的行驶路线可以不同的情形下讨论；第二问的讨论中，没有考虑空车率，也可同一r，、一一一-一-、，、，万方数据7 0数学的实践与认识3 9 卷时考虑空车率，规划最佳邮路；可拓展假设同一支局可以被多邮车服务参考文献：表2 全区最佳邮路和邮车调度方案车次12341Z1ZDDDDX 1X 1X 2X 2Z 7 2Z 7 0X 2Z 6 6Z 1 4Z 3Z 1 8Z 1 9Z 7 3Z

15、 7 1Z 1 2”Z 6 7Z 1 0Z 2Z 2 1Z 1 7负Z 6 0Z 6 9X 1Z 6 3Z 1 1Z 1Z 2 2责Z 4 1*Z 6 5Z 2 7“Z 6 2Z 1 5Z 1 3Z 2 3运X 4Z 6 4X 3Z 5 9Z 1 6Z 2 4送DDZ 3 1 X-Z 5 8Z 9Z 2 5的Z 6 8Z 5 2-X Z 8Z 2 6县支DX 5Z 7Z 2 0局Z 6 1Z 6DZ 5Z 4X 1X 1X 2X 2耗时h4 8 14 8 74 7 74 9 36 3 23 9 76 6 72 7 0运费元3 2 7 68 1 37 6 8车次11212X 3X 4X 4X 5

16、X 5Z 2 8Z 3 6Z 4 3Z 5 lZ 5 3负Z 2 9Z 3 5Z 4 2Z 4 6Z 5 7责Z 3 0Z 3 4X 4Z 4 4Z 5 6运送Z 3 2Z 3 7Z 4 5Z 5 5的Z 3 3Z 3 8Z 4 7Z 5 4县X 3Z 3 9Z 4 8X 5支Z 4 0Z 4 9局X 3Z 5 0X 5耗时h6 8 23 0 36 1 35 0 8运费元4 0 28 1 99 1 2总运费元6 9 9 0总车次1 3-；6 代表区车负责卸载的非中心县支局 1 D a n t z i gGB，R a m s e rRH T h et r u c kd i s p a t c h

17、 i n gp r o b l e m J M a n a g e m e n tS c i e n c e，1 9 5 9，6：8 0 9 1 2 D o r i g oM O p t i m i z a t i o n，L e a r n i n ga n dN a t u r a lA l g o r i t h m s M P hDT h e s i s，D e p a r t m e n to fE l e c t r o n i c s 万方数据1 7 期卢晓珊，等：邮政运输网络中的邮路规划和邮车调度研究 3 E 4 E 5 6 P o l i t e e n i c od iM

18、i l a n o，I t a l y，1 9 9 2 段海滨蚁群算法原理及其应用 M 北京：科学出版社，2 0 0 6 M a r c oD o r i g o，T h。m a sS t u t z l e 著，张军，胡晓敏，罗旭耀等译A n tC o l o n yO p t i m i z a t i o n 蚊群优化 M 北京；清华大学出版社，2 0 0 7 滕玮基于蚁群算法的车辆调度问题研究E D 华中师范大学硕士论文，2 0 0 6 陈宝林最优化理论与算法E M 3 北京：清华大学出版社，2 0 0 5 R e s e a r c ho nR o a dP l a n n i n

19、ga n dV e h i c l eS c h e d u l i n go ft h eP o s tT r a n s p o r t a t i o nN e t w o r kL UX i a o s h a n l H EW e i 2 H EY o n g j i n 3A d v i s o r：Y A N GF e n g m e i l(1 C o l l e g eo fS c i e n c e，B e i j i n gU n i v e r s i t yo fC h e m i c a lT e c h n o l o g y，B e i j i n g1 0 0

20、 0 2 9，C h i n a)(2 C o l l e g eo fS c i e n c e，B e i j i n gU n i v e r s i t yo fI n f o r m a t i o nS c i e n c e sa n dT e c h n o l o g y，B e i j i n g1 0 0 0 2 9，C h i n a)(3 C o l l e g eo fC h e m i c a lE n g i n e e r i n g，B e i j i n gU n i v e r s i t yo fC h e m i c a lT e c h n o l

21、 o g y，B e i j i n g1 0 0 0 2 9，C h i n a)A b s t r a c t：P o s tT r a n s p o r t a t i o nn e t w o r ke n s u r e st h eo p e r a t i o no ft h ep o s tc o r p o r a t i o n，w h i l eb o t hr o a dp l a n n i n ga n dv e h i c l es c h e d u l i n garei m p o r t a n tf a c t o r sr e l a t e dt

22、on e t w o r ke f f i c i e n c y T h ef i r s tp r o b l e mr e d u c e st oar o u n dv e h i c l er o u t i n gp r o b l e m，w h i c hi sN P h a r d W eo b t a i ni t ss a t i s f a c t o r ys o l u t i o n sb yi m p r o v e da n tc o l o n yo p t i m i z a t i o na l g o r i t h m T h a ti s，a n

23、a l y z i n gt h eT S Pb yb r e a k i n gt h et r a v e l i n gc i r c l e，t h e nf e e d i n gb a c kt h ec i r c u i t r yi n f o r m a t i o nt ot h eo b j e c t i v e N e x t，e x t e n dt h i sp r o b l e mt ot h ew h o l ed i s t r i c t W es o l v ei tb y o p t i m i z i n ge a c hc o u n t yw

24、 i t hp r i o r i t yl e v e l F i n a l l y，m o d e le v a l u a t i o na n di m p r o v e dd i r e c t i o narep r e s e n t e d K e y w o r d s：p o s tr o a dp l a n n i n g；p o s tv e h i c l es c h e d u l i n g；v e h i c l er o u t i n g；a n tc o l o n yo p t i m i z a t i o n 万方数据邮政运输网络中的邮路规划

25、和邮车调度研究邮政运输网络中的邮路规划和邮车调度研究作者：卢晓珊，何伟，贺永金，杨丰梅，LU Xiao-shan，HE Wei，HE Yong-jin，YANGFeng-mei作者单位：卢晓珊,杨丰梅,LU Xiao-shan,YANG Feng-mei(北京化工大学,理学院,北京,100029)，何伟,HE Wei(北京化工大学,信息科学与技术学院,北京,100029)，贺永金,HE Yong-jin(北京化工大学,化学工程学院,北京,100029)刊名：数学的实践与认识英文刊名：MATHEMATICS IN PRACTICE AND THEORY年，卷(期)：2009,39(17)被引用次

26、数：1次 参考文献(6条)参考文献(6条)1.Dantzig G B;Ramser R H The truck dispatching problem 19592.Dorigo M Optimization,Learning and Natural Algorithms 19923.段海滨 蚁群算法原理及其应用 20064.Marco Dorigo;Thomas Stutzle;张军;胡晓敏,罗旭耀 Ant Colony Optimization.蚁群优化 20075.滕玮 基于蚁群算法的车辆调度问题研究学位论文 20066.陈宝林 最优化理论与算法 2005 本文读者也读过(9条)本文读者也

27、读过(9条)1.胡震宇.吴华玉.唐燕.HU Zhen-yu.WU Hua-yu.TANG Yan 邮政运输网络中的邮路规划和邮车调度期刊论文-数学的实践与认识2008,38(14)2.于文涛.马钰昕.刘泷.杨振华.YU Wen-tao.MA Yuxin.LIU Long.YANG Zhen-hua 邮政运输网络中的邮路规划和邮车调度期刊论文-数学的实践与认识2008,38(14)3.李晓磊.张承进.LI Xiao-lei.ZHANG Cheng-jin 邮政运输网络中的邮路规划和邮车调度问题评注期刊论文-数学的实践与认识2008,38(14)4.金钢.师群昌.刘小麟.JIN Gang.SHI

28、Qun-chang.LIU Xiao-lin 邮政运输中邮路的规划和邮车调度问题的研究期刊论文-数学的实践与认识2008,38(14)5.汤志高.王继利.曹颖瑛.曹华林.梁希泉.TANG Zhi-gao.WANG Ji-li.CAO Ying-ying.CAO Hua-lin.LIANG Xi-quan 邮路规划与邮车调度最优化理论研究期刊论文-数学的实践与认识2008,38(14)6.高玉建.苏昊.黄飞.GAO Yu-jian.SU Hao.HUANG Fei 邮政运输网络中的邮路规划和邮车调整期刊论文-数学的实践与认识2008,38(14)7.张蕾.陈笑蓉.陈笑筑 基于蚁群算法的多邮车调度问题研究期刊论文-福建电脑2008,24(8)8.万彬菲.田东红.王景辽 基于多旅行商问题的最优邮路规划期刊论文-中国民航飞行学院学报2008,19(5)9.岳扬.Yue Yang 邮路规划问题研究以彭泽县为例期刊论文-科技广场2009(2)引证文献(1条)引证文献(1条)1.陈盖凯.王瑛.张毅 基于二元语义的高原地区航材配送中心选址决策研究期刊论文-数学的实践与认识2011(20)本文链接：http:/