（计算机应用技术专业论文）蚁群算法在配货车辆调度中的应用研究.pdf

ad i s t h e a p p l i c a t i o na n dr e s e ar c hf o ra n tc o l o n y o nt h ep i c k i n gv e h i c l es c h e d u l i n g m a s t e rc a n d i d a t e ：l ih u i c h e n g s u p e r v i s o r ：p r o f z e n gb r o te n g i1 m a y2 0 1 0 f a c u l t yo fc o m p u t e r g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a ， 5 1 0 0 0 6 摘要 摘要 目前，我国大部分的跑运输的车辆由于货源不固定，导致运输成本过高；另外， 生产制造企业的运输业务是我国物流总量的主体，企业专注于核心竞争力的研究， 不得不将物流业务外包给专业的运输公司。因此，中集车辆有限公司有一个构想： 基于公司在运输专用车在我国的市场份额是第一的，如果能建立一个配货平台，为 生产制造企业推荐公司的运输车辆客户，将会使三方受益。但是为了预防配货平台 里运输车辆无序竞争，有必要对车辆进行一定的调度分配。因此对配货平台下的车 辆调度研究有一定的现实意义。 蚁群算法是一种新型的仿生类进化算法，是继模拟退火、遗传算法、禁忌搜索 等之后的又一启发式智能算法。蚂蚁不仅仅能在没有任何提示下找到巢穴到食物源 的最短路径，并且可以随环境的变化，适应性地搜索新的路径，产生新的选择。这 体现了蚁群算法的正反馈和负反馈的特点。应用蚁群算法求解t s p 问题、二次分配 问题和车辆调度问题取得的较好的结果，已经引起了广大研究学者的高度重视。 本论文采用蚁群算法来解决配货车辆调度的问题，正是体现了蚁群算法在求解 车辆度问题的鲁棒性，本文的研究工作主要包括以下几个方面： ( 1 ) 研究蚁群算法的基本原理，建立其数学模型，包括转移概率的计算、信 息素的更新的各种规则等。通过应用蚁群算法来求解e i p 5 1 问题，采用不同的参数 组合，分析参数组合对求解最优值的影响，并且指出应用蚁群算法时，对信息素更 新规则和路径期望值的定义的重要性。 ( 2 ) 分析配货车辆的调度具体问题，建立问题的信息素的初始值、信息素的 更新规则和根据车辆回程目标点的路径期望值等；建立对分配车辆调度路线的模糊 评价函数。然后提出了解决问题的蚁群算法。最后用一个实例进行数值实验分析。 ( 3 ) 针对车辆调度完毕后，还出现剩余的未被执行的运输任务，应用蚁群算 法分析车辆的出发点选择，以及在其中一个集货点应该如何进行集货任务的选择问 题，并提出了解决遗漏运输的蚁群算法，最后用实例来做进一步的说明。 ( 4 ) 研究了当运输任务带有时间窗的情况下，时间窗对定义信息素的更新和 路径期望值的影响，并通过一个实例进行了说明和验证。 广东x - , _ l k 大学硕士学位论丈 关键字：蚁群算法；配货调度；信息素因子；时间窗 h i g ht r a n s p o r tc o s t s ；w h i l e ，m a n u f a c t u r i n gc o m p a n i e so ft h et r a n s p o r tb u s i n e s s i st h e m a i nb o d yo fc h i n a st o t a ll o g i s t i c s ，a n dm a n u f a c t u r i n ge n t e r p r i s e sn o wi n c r e a s i n g l y f o c u so nc o r ec o m p e t e n c i e so fr e s e a r c h ，s ot h a tt h ec o m p a n y sl o g i s t i c so u t s o u r c et o o t h e rc o m p a n i e ss p e c i a l i z i n gi nt r a n s p o r t a t i o nl o g i s t i c s b a s e do nt h e s ec o n d i t i o n s ，t h e c i m cv e h i c l e sc o ，l t dh a sa ni d e a ：a sw ea r et h et o po n ei nt h em a r k e ts h a r e so ft h e t r a n s p o r tp r i v a t ev e h i c l e si nc h i n a ，s oi fap i c k i n gp l a t f o r mf o rm a n u f a c t u r i n ge n t e r p r i s e c u s t o m e r sr e c o m m e n d st h ec o m p a n y st r a n s p o r tv e h i c l e s ，w i l lm a k et h r e eb e n e f i t s a l s o i no r d e rt op r e v e n td i s o r d e r l yc o m p e t i t i o na m o n gt r a n s p o r tv e h i c l e s ，p i c k i n gp l a t f o r m n e c e s s a r i l y c h o o s ea p p r o p r i a t ev e h i c l e sf o rt r a n s p o r to p e r a t i o n sa c c o r d i n g t ot h e t r a n s p o r tt a s k s t h e r e f o r e ，s c h e d u l i n go fv e h i c l e so nt h ep i c k i n gp l a t f o r mh a si m p o r t a n t p r a c t i c a ls i g n i f i c a n c e a n tc o l o n ya l g o r i t h mi san e wc l a s so fb i o m i m e t i ce v o l u t i o n a r ya l g o r i t h m ，a n d a n o t h e rs m a r th e u r i s t i ca l g o r i t h m , f o l l o w i n gt h es i m u l a t e da n n e a l i n g ，g e n e t i ca l g o r i t h m , t a b us e a r c ha n ds oo n a n tn o to n l yf i n d st h es h o r t e s tp a t ht of o o d u r c ei nt h ea b s e n c e o fa n yp r o m p tn e s t ，a n da d a p t st os e a r c hf o rn e wp a t h s ，c r e a t en e wo p t i o n sw i t ht h e c h a n g eo f t h ee n v i r o n m e n t t h i sr e f l e c t st h ea n tc o l o n ya l g o r i t h m sf e a t u r e sw i t hp o s i t i v e f e e d b a c ka n dn e g a t i v ef e e d b a c k i nt h ea p p l i c a t i o no fa n tc o l o n ya l g o r i t h mf o rt s p p r o b l e m , q u a d r a t i ca s s i g n m e n tp r o b l e ma n dt h ev e h i c l es c h e d u l i n gp r o b l e mw i t hg o o d r e s u k sa c h i e v e d ，a n tc o l o n ya l g o r i t h mh a sa t t r a c t e dg r e a ta t t e n t i o no ft h em a j o r i t y s c h o l a r s i nt h i st h e s i s ，u s i n ga n tc o l o n ya l g o r i t h mt os o l v et h ep i c k i n gp l a t f o r mv e h i c l e s c h e d u l i n gp r o b l e m si sar e f l e c t i o nr o b u s td e g r e eo f a n tc o l o n ya l g o r i t h mf o rs o l v i n gt h e v e h i c l e ss c h e d u l i n gp r o b l e m s t h i sr e s e a r c hw o r ki n c l u d e st h ef o l l o w i n ga s p e c t s ： ( 1 ) s t u d yt h eb a s i cp r i n c i p l eo fa n tc o l o n ya l g o r i t h m , e s t a b l i s hi t s m a t h e m a t i c a l m o d e l , i n c l u d i n gt h et r a n s i t i o np r o b a b i l i t yc a l c u l a t i o n , t h ev a r i o u sp h e r o m o n eu p d a t e m 广东工业大学硕士学位论文 r u l e s t h r o u g ht h ea p p l i c a t i o no fa n tc o l o n ya l g o r i t h mt os o l v et h ep r o b l e me i p 51 ， a n a l y s i sp a r a m e t e r sf o rs o l v i n gt h eo p t i m a lv a l u eb yu s i n gd i f f e r e n tp a r a m e t e r s ，a n d p o i n to u tt h ei m p o r t a n c eo ft h el l e f i h i t i o no ft h ep h e r o m o n ea n dt h ep a t he x p e c t a t i o n s w h e nu s i n gt h ea n tc o l o n ya l g o r i t h m ( 2 ) a n a l y s i so fs p e c i f i cp r o b l e m sp i c k i n gt h ev e h i c l es c h e d u l i n g ，e s t a b l i s ho fi s s u e s p h e r o m o n ei n i t i a l i z a t i o n ，p h e r o m o n eu p d a t i n gr u l e sa n dt h ev e h i c l e sp a t ho fr e t u r n e x p e c t a t i o n su n d e rt h et a r g e tp o i n ta n ds oo n e s t a b l i s ht h ef u z z ye v a l u a t i o nf u n c t i o nf o r t h ed i s t r i b u t i o nv e h i c l es c h e d u l i n gl i n e t h e np r o p o s et h ea n tc o l o n ya l g o r i t h mt os o l v e t h ep r o b l e m f i n a l l ya ne x a m p l ei sp r e s e n t e d ( 3 ) s t u d yw h e ns c h e d u l i n gf o ra l lt r a n s p o r tv e h i c l e sh a sb e e nc o m p l e t e d ，t h e r ea r e r e m a i n i n gt a s kn o tp e r f o r m e d u s ea n tc o l o n ya l g o r i t h mt oc h o o s et h es t a r t i n gp o i n to f t h ev e h i c l e ，a n dh o wt oc h o o s et h ep i c k i n gt a s k s ，a n dt h e np r o p o s ea n tc o l o n ya l g o r i t h m t os o l v em i s s i n gt r a n s p o r t a t i o n f i n a l l ya ne x a m p l ei sp r e s e n t e d ( 4 ) s t u d yh o wt i m ew i n d o w st oe f f e c tt h ed e f i n i t i o no fp h e r o m o n eu p d a t e sa n dt h e p a t he x p e c t a t i o n sw h e nt h e r ea r es o m et r a n s p o r t a t i o nt a s k sw i t ht i m ew i n d o w s a n e x a m p l ei se x p l a i n e d k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；p i c k i n gs c h e d u l i n g ；p h e r o m o n e ；t i m ew i n d o w i v c o n t e n t s v i l i 第一章绪论1 1 1 研究背景。l 1 2 课题的来源3 1 3 国内外研究现状4 1 3 1 国外调度方法概述4 1 3 2 国内调度方法概述5 1 4 本文的主要工作和组织结构6 第二章车辆调度问题概述8 2 1 车辆调度问题的概念和分类8 2 1 1 车辆调度问题的概念8 2 1 2 车辆调度问题的分类8 2 2 车辆调度问题的数学模型9 2 3 配货运输车辆的调度问题1 l 2 4 求解车辆调度问题的主要算法简述1 2 2 4 1 禁忌搜寻法1 2 2 4 2 模拟退火算法1 3 2 4 3 遗传算法1 4 2 4 4 蚁群算法15 2 4 5 算法的比较1 5 2 5 本章小结一1 5 第三章蚁群算法。1 6 3 1 蚁群算法的基本原理1 6 v 广东工业大学硕士学位论文 3 1 1 蚁群算法原理1 6 3 1 2 蚁群算法的反馈原理1 8 3 1 3 人工蚂蚁和真实蚂蚁的区别矗j 1 8 3 2 蚁群算法的数学模型1 9 3 3 基本蚁群的算法过程描述2 1 3 4 蚁群算法参数介绍和分析2 1 3 4 1 信息素启发因子2 2 3 4 2 期望值启发因子2 2 3 4 3 残留信息系数2 3 3 4 4 最大信息素2 4 3 5 蚁群算法的优缺点2 5 3 6 本章小结2 6 第四章蚁群算法在配货车辆调度的应用2 7 4 1 集货点信息素初始化。2 7 4 1 1 集货点地图建立2 7 4 1 2 运输任务的信息表2 8 4 1 3 信息素的初始化2 8 4 2 车辆转移信息素的更新2 9 4 2 1 车辆转移的方式2 9 4 2 2 纯集货作业时信息素更新。3 0 4 2 3 纯卸货作业时信息素更新3 l 4 2 4 集卸一体化时信息素更新3 2 4 2 5 集货对运输任务的负反馈3 2 4 3 车辆转移的确定3 4 4 3 1 路径期望值的定义3 4 4 3 2 车辆转移的确定3 5 4 4 评价函数的确定3 6 4 4 1 多因数的模糊评价。3 6 4 4 2 单个车辆调度评价3 7 4 4 3 调配车辆的整体评价3 8 v l 4 6 1 遗漏运输的定义4 6 4 6 2 两个期望因子的定义4 7 4 6 3 算法的设计和流程图4 8 4 6 4 实例分析5 0 4 7 本章小结5 l 第五章带时限的配货车辆调度问题5 2 5 1 带时间窗问题的定义5 2 5 1 1 时间窗的定义5 2 5 1 2 时间窗问题的分类5 2 5 1 3 时间窗问题的转换5 3 5 2 时间窗对期望值的影响5 4 5 2 1 对信息素期望值的影响5 4 5 2 2 对路径期望值的影响5 4 5 3 实例分析5 5 5 4 本章小结5 8 结束语5 9 参考文献一6 0 攻读学位期间发表论文6 3 独创性声明6 4 封c谢6 5 v 广东工业大学硕士学位论文 c o n t e n t s a b s t r a c t ( c h i n e s e ) i a b s t r a c t ( e n g l i s h ) i l l c o n t e n t s ( c h i n e s e ) v c o n t e n t s ( e n g l i s h ) v i i i c h a p t e r1i n t r o d u c t i o n 1 1 1t h er e s e a r c hb a c k g r o u n d 1 1 2t h es o u r c eo f t h i sp a p e r 3 1 3r e s e a r c ha c t u a l i t yi nh o m e l a n da n do v e r s e a s 4 1 3 1s c h e d u l i n go v e r v i e wi no v e r s e a s 4 1 3 2s c h e d u l i n go v e r v i e wi nh o m e l a n d 5 1 4t h er e s e a r c hw o r ka n ds t r u c t u r eo f t h i sp a p e r 6 c h a p t e r2o v e r v i e wo fv e h i c l er o u t i n g p r o b l e m 8 2 1c o n c e p t sa n dc l a s s i f i c a t i o no f v r p 8 2 1 1c o n c e p t so ft h ev r p 8 2 1 2c l a s s i f i c a t i o no f t h ev r p 8 2 2m a t h e m a t i c a lm o d e lf o rv r p 9 2 3t h es c h e d u l i n gp r o b l e mf o rt h ep i c k i n gt r a n s p o r tv e h i c l e s 11 2 4i n t r o d u c i t o no ft h em a i na l g o r i t h m sf o rt h ev r p 。l2 2 4 1t a b us e a r c h 1 2 2 4 2s i m u l a t e da n n e a l i n g 1 3 2 4 3g e n e t i ca l g o r i t h m 1 4 2 4 4a n tc o l o n ya l g o r i t h m 15 2 4 5c o m p a r i s o no ft h ea l g o r i t h m s 15 2 5b r i e fs u m m a r y 15 c h a p t e r3a n tc o l o n ya l g o r i t h m 1 6 3 1b a s i cp r i n c i p l eo f a n tc o l o n ya l g o r i t h m 1 6 v i i i c o n t e n t s 3 1 1p r i n c i p l e so f a c a 1 6 3 1 2n e g a t i v ef e e d b a c ko ft h ea n tc o l o n y 18 3 1 3d i f f e r e n c eb e t w e e na r i f i c i a la n t s a n dn a t u r a la n t s 18 3 2t h em a t h e m a t i c a lm o d e lo f a c a 1 9 ：；3t h ep r o c e s sd e s c r i p t i o ni nt h eb a s i ca c a 2 1 3 4t h ei n t r o d u c t i o na n da n a l y s i so f t h ea c a p a r a m e t e r s 2 1 3 4 1t h ep h e r o m o n es t i m u l a t i n gf a c t o r 2 2 3 4 2t h ee x p e c t a t i o n ss t i m u l a t i n gf a c t o r 2 2 3 4 3c o e f f i c i e n to fp h e r o m o n e 2 3 3 4 4t h em a x i m u mp h e r o m o n e ：1 0 i ：i 5a d v a n t a g e sa n dd i s a d v a n t a g e so f t h ea c a 2 5 3 6b r i e fs u m m a r y 2 6 c h a p t e r4t h ea p p l i c a t i o n o fa c af o rp i c k i n gv e h i c l e ss c h e d u l i n g 2 7 4 1t h ei n i t i a l i z a t i o no f t h ep h e r o m o n ef o rt h ep i c k i n gp o i n t s 2 7 4 1 1t h em a pc o n s t r u c t i o no f t h ep i c k i n gp o i n t s 2 7 4 1 2t h ei n f o r m a t i o nt a b l e o f t h et r a n s p o r t a t i o nt a s k s 2 8 4 1 3t h ei n i t i a z a t i o no f t h ep h e r o m o n e s 2 8 4 2t h ep h e r o m o n eu p d a t i n gf o rt h ev e h i c l et r a n s f e r r i n g 2 9 4 2 1t h ef o r m sf o ev e h i c l et r a n s f e r r i n g 2 9 4 2 2t h ep h e r o m o n eu p d a t i n gw h e np u r ep i c k i n g 3 0 4 2 3t h ep h e r o m o n eu p d a t i n gw h e np u r ed e l i v e r i n g 31 4 2 4t h ep h e r o m o n eu p d a t i n gw h e np i c k i n ga n dd e l i v e r i n g 3 2 4 2 5t h en e g a t i v ef e e d b a c ko fp i c k i n gf o rt h et o t a lt a s k s 3 2 4 3d e t e r m i n a t i o no f t h et r a n s f e ro f v e h i c l e s 3 4 4 3 1t h ed e f i n i t i o no f t h ep a t he x p e c t a t i o n s 3 4 4 3 2d e t e r m i n i a t i o no f t h et r a n s f e ro f v e h i c l e s 3 5 4 4d e t e r m i n a t i o no f t h ee v a l u a t i o nf u n c t i o n 3 6 4 4 1f u z z ye v a l u a t i o no f m u l t i - f a c t o r s 3 6 4 4 2e v a l u a t i o no fs i n g l ev e h i c l es c h e d u l i n g 3 7 4 4 3o v e r a l le v a l u a t i o no ft h ed e p l o y m e n tv e h i c l e s 3 8 广东工业大学硕士学位论文 4 5t h ea l g o r i t h md e s i g nf o rt h ep i c k i n gv e h i c l es c h e d u l i n g 3 9 4 5 1t h em a t h e m a t i c a lm o d e lf o rt h ep r o b l e m 3 9 4 5 2a l g o r i t h md e s i g na n df l o wc h a r t 3 9 4 5 3c a s es t u d y 4 2 4 6d e a l i n gw i t ht h eo m i s s i o nt r a n s p o r t 4 6 4 6 1t h ed e f i n t i o no f t h eo m i s s i o nt r a n s p o r t 4 6 4 6 2t h ed e f i n t i o no ft h et w oe x p e c t a t i o nf a c t o r 4 7 4 6 3a l f o r i t h md e s i g na n df l o wc h a r t 4 8 4 6 4c a s es t u d y 5 0 4 7b r i e fs u m m a r y 51 c h a p t e r5t h ep i c k i n gv e h i c l e ss c h e d u l i n g p r o b l e m sw i t ht i m ew i n d o w s 5 2 5 1t h ed e f i n i t i o no f t h et i m ew i n d o w s 。5 2 5 1 1t h ed e f i n i t i o no f t h et i m ew i n d o w s 5 2 5 1 2c l a s s i f i c a t i o np r o b l e m sw i t ht i m ew i n d o w s 5 2 5 1 3t h ec o n v e r s i o nf o rt h et i m ew i n d o w sp r o b l e m s 5 3 5 2a f f e c to f t h et i m ew i n d o w st ot h ee x p e c t a t i o n s 5 4 5 2 1a f f e c tt ot h ep h e r o m o n ee x p e c t a t i o n s 5 4 5 2 2a f f e c tt ot h ep a t he x p e c t a t i o n s 5 4 5 3c a s es t u d y 5 5 5 4b r i e fs u m m a r y 5 8 c o n c l u s i o n ：! ；9 r e f e r e n c e s 6 0 p u b i s h e dp a p e r sa n dp r o j e c td u r i n gs t u d y 6 3 o r i g i n a ls t a t e m e n g t 6 4 a c k n o w l e d g e m n t s 6 5 x 1 1 研究背景 第一章绪论 物流【l 】是指利用现代信息技术和设备，将物品从供应地向接收地准确的、及时 的、安全的、保质保量的、门到门的合理化服务模式和先进的服务流程。物流是随 商品生产的出现而出现，随商品生产的发展而发展。 目前，物流可以分为自营物流和第三方物流。自营物流主要是指企业自己营业 的物流，但它的主要的经济来源不在于物流。例如海尔公司【2 】就是自营物流，虽然 它的最大利润源不是物流，但它有能力自身承担物流业务并且从中获利。然而对于 我国大部分的生产制造企业来说，自营物流必须投入大量的资金用于运输、仓储等 基础物流设备以及人力资本，这必然会减少企业对核心业务的投资，从而削弱企业抵 御市场风险的能力；此外企业自建物流，难以形成规模，而物流的作用只有通过规模 才能发挥出来【3 1 。因此没有能力承担物流业务的企业便把其物流业务外包给专业的 第三方物流公司。 第三方物流公司相对于发货方和收贷方而言的，是由其承担企业物流活动的一 种物流形态，它通过与第一方或第二方的合作来提供其专业化的物流服务，它不拥有 商品，不参与商品买卖，只是为顾客提供以合同约束，以结盟为基础的，系列化、个 性化和信息化的物流代理服务。目前对于我国现在物流市场的发展，呈现出这样的 发展现状：物流基础设施规模迅速扩大、全社会货物运输量持续增加、物流技术 装备水平迅速提高等，但是物流服务业作为社会化的第三方独立行业还未形成一 定规模，现有的社会化物流服务企业十分零散，服务质量不高。这间接造成了我 国运输企业系统效率低，运输成本高的不良发展状况。数据统计得知：在我国， 物流成本占商品价值的4 0 ，而在美国物流成本仅占商品价值的1 0 左右，高昂的 物流成本正是落后的物流服务业发展水平所导致的，这一现状同时制约了制造业的 发展。 1 9 9 8 年美国埃森哲咨询公司率先提出了第四方物流【4 】的概念，指出：是专门为 第一方、第二方和第三方提供物流规划、咨询、物流信息系统和供应链管理等活动。 广东工业大学硕士学位论文 第四方并不实际承担具体的物流运作活动。可以这样理解：第四方物流是一个供应 链的集成商，是供需双方及第三方物流的领导力量。它不是物流的利益方，而是通 过拥有信息技术、整合能力以及其他资源提供一套完整的供应链解决方案，以此获 取一定的利润。它能帮