蚁群算法在配货车辆调度中的应用研究

《蚁群算法在配货车辆调度中的应用研究》由会员分享，可在线阅读，更多相关《蚁群算法在配货车辆调度中的应用研究（69页珍藏版）》请在金锄头文库上搜索。

1、广东工业大学 硕士学位论文 蚁群算法在配货车辆调度中的应用研究 姓名：黎惠成 申请学位级别：硕士 专业：计算机应用技术 指导教师：曾碧 20100501 摘要 摘要 目前，我国大部分的跑运输的车辆由于货源不固定，导致运输成本过高；另外， 生产制造企业的运输业务是我国物流总量的主体，企业专注于核心竞争力的研究， 不得不将物流业务外包给专业的运输公司。因此，中集车辆有限公司有一个构想： 基于公司在运输专用车在我国的市场份额是第一的，如果能建立一个配货平台，为 生产制造企业推荐公司的运输车辆客户，将会使三方受益。但是为了预防配货平台 里运输车辆无序竞争，有必要对车辆进行一定的调度分配。因此对配货平台

2、下的车 辆调度研究有一定的现实意义。 蚁群算法是一种新型的仿生类进化算法，是继模拟退火、遗传算法、禁忌搜索 等之后的又一启发式智能算法。蚂蚁不仅仅能在没有任何提示下找到巢穴到食物源 的最短路径，并且可以随环境的变化，适应性地搜索新的路径，产生新的选择。这 体现了蚁群算法的正反馈和负反馈的特点。应用蚁群算法求解T S P 问题、二次分配 问题和车辆调度问题取得的较好的结果，已经引起了广大研究学者的高度重视。 本论文采用蚁群算法来解决配货车辆调度的问题，正是体现了蚁群算法在求解 车辆度问题的鲁棒性，本文的研究工作主要包括以下几个方面： ( 1 ) 研究蚁群算法的基本原理，建立其数学模型，包括转移概

3、率的计算、信 息素的更新的各种规则等。通过应用蚁群算法来求解e i p 5 1 问题，采用不同的参数 组合，分析参数组合对求解最优值的影响，并且指出应用蚁群算法时，对信息素更 新规则和路径期望值的定义的重要性。 ( 2 ) 分析配货车辆的调度具体问题，建立问题的信息素的初始值、信息素的 更新规则和根据车辆回程目标点的路径期望值等；建立对分配车辆调度路线的模糊 评价函数。然后提出了解决问题的蚁群算法。最后用一个实例进行数值实验分析。 ( 3 ) 针对车辆调度完毕后，还出现剩余的未被执行的运输任务，应用蚁群算 法分析车辆的出发点选择，以及在其中一个集货点应该如何进行集货任务的选择问 题，并提出了解

4、决遗漏运输的蚁群算法，最后用实例来做进一步的说明。 ( 4 ) 研究了当运输任务带有时间窗的情况下，时间窗对定义信息素的更新和 路径期望值的影响，并通过一个实例进行了说明和验证。 广东x - , _ l k 大学硕士学位论丈 关键字：蚁群算法；配货调度；信息素因子；时间窗 A B S T R A C T A B S T R A C T A tp r e s e n t ，i nC h i n a ，f o rt h et r a n s p o r tv e h i c l e st h es u p p l yi sn o tf i x e d ，r e s u l t i n gi n h

5、 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 si s t 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

6、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 s

7、w 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

8、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

9、 r d i n gt 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 f v 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

10、 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 $ o u r c A ei nt h ea b s e n c

11、 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

12、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

13、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 sa r e f l e c t i o nr o b u s td e g r e eo fa n tc o l o n y

14、a 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 sm a t h e m a t i c

15、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 广东工业大学硕士学位论文 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

16、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 ef 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