摘要摘要随着市场竞争的拥剧，物流已经成为企业提高市场竞争力和核心竞争力的重要手段，而运输通常是物流成本中最大的单项成本。所以，研究车辆路径问题( V e h i c l eR o u t i n gP r o b l e m ，V R P ) ，通过设计合理的运输路线，使车辆在满足服务要求的同时，成本最小化，从而减少物流整体费用，具有重要意义。根据车辆容量、车型等限制的不同，有多种类型的V R P ，本文针对两种问题进行了讨论：有时问窗的多车场车辆路径问题( t h eM u l t i d e p o t sV e h i c l eR o u t i n gP r o b l e mw i t hT i m eW i n d o w s ，M D V R P T W ) 和有时间窗的具有同时配送与回收的车辆路径问题( t h eV e h i c l eR o u t i n gP r o b l e mw i t hS i m u l t a n e o u sP i c k u pa n dD e l i v e r ya n dT i m eW i n d o w s ，V R P S D P T W ) 。V R P 已被证饔为N P 难题，对其算法的研究大部分集中在盛发式算法上，面蚁群算法是近年来新兴的启发式算法，本文采用蚁群算法对上述两个问题进行求解。本文主要工作有：1 、针对基本蚁群算法易陷入局部最优的缺陷，本文从调整起始搜索节点和交换信息素两个方面提出了改进，在基准问题上的实验表明该算法取得的目标值较优，而且取得冒标值时所需的迭代次数较少。2 、给出M D V R P T W 的数学模型，并采用蚁群算法对该模型求解。求解时采用整体法将多个车场康拟为一个车场，每次搜索及虚拟车场中隧视选择一个实际车场作为出发车场，采用S O L O M O N 的N e a r e s tN e i g h b o u r 插入式算法，搜索一条可行路径，服务结束后回到出发车场。3 、给出了V R P S D P T W 的数学模型，采用蚁群算法求解该模型时，引入一个变量解决了该问题中车辆的容量判断问题，并提出了同时考虑剩余容量符合度和时间窗的启发式函数，在此基础上给出了蚁群算法的实现过程。4 、对上述两个问题编写C + + 程序，选择V R PW e b 提供的基准问题进行实验，结果表明本文给疵的两个算法得到静结采较优，具奄较强酶实际意义，且所需计算时间也在合理范围内。关键字：车辆路径闻题多车场时闻窗同时配送与回收蚁群算法A B S T R A C TA B S T R A C TA st h ei n t e n s i f y i n go fm a r k e tc o m p e t i t i o ni nt h ew o r l d ，l o 玺s t i c sh a sb e c o m ea ni m p o r t a n tm e a nt oe n h a n c et h ec o r ea n dm a r k e tc o m p e t i t i v e n e s s I na l lc o s t s ，t r a n s p o r tc o s t sa c c o u n tf o ral a r g ep r o p o r t i o n T h r o u g ht h ed e s i g no fr o u t e s ，w i t hm e e t i n gt h es e r v i c ed e m a n d si nt h es a m et i m e ，t h ev e h i c l er o u t i n gp r o b l e mw i l lm i n i m i z et h et o t a lc o s t s B a s e do nt h ec a p a c i t yo rt y p eo fv e h i c l e s ，t h e r ea r ev a r i o u st y p e so fv e h i c l er o u t i n gp r o b l e m ，i nt h i sp a p e r ，t w oi s s u e sw e r ed i s c u s s e d ：t h em u l t i d e p o t sv e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w sa n dt h ev e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u sp i c k u pa n dd e l i v e r ya n dt i m ew i n d o w s V R Ph a sb e e np r o v e dt ob eN P h a r d ( N o n d e t e r m i n i s t i cP o l y n o m i a l ) ，m o s to fi t sa l g o r i t h m sc o n c e n t r a t e do nt h eh e u r i s t i ca l g o r i t h m ，a n tc o l o n ya l g o r i t h mw a se m e r g e di nr e c e n ty e a r s I nt h i sp a p e r , b o t ht h em a t h e m a t i c a lm o d e la n dt h ea n tc o l o n ya l g o r i t h m so ft h et w op r o b l e m sa r eg i v e n 。T h i sp a p e rm a i n l yi n c l u d e st h en e x tc o n t e n t s ：1 T ot h eq u e s t i o no fa n tc o l o n ya l g o r i t h me a s yt og e ti n t ol o c a lo p t i m u m ，t h i sp a p e rp r o p e s e dt w oi m p r o v e m e n t si n c u l d i n gt h ea d j u s t m e n to fi n i t i a ls e a r c ha n dt h ee x c h a n g eo fp h e r o m o n e E x p r i m e n t so nt h eb e n c h m a r ks h o w e dt h a tt h er e s u l t sw e r eb e t t e ra n dt h et a r g e to fi t e r a t i o n sr e q u i r e df o rl e s s 2 T h em a t h e m a t i c a lm o d e lo fM D V R P T Ww a sp r e s e n t e d ，c o m b i n i n gw i t ht h eh o l i s t i cm e t h o d ，t h ea l g o r i t h ml o o k e dan u m b e ro fc u s t o m sa sav i r t u a ln o d e ，e a c hs e a r c hs e l e c t e dar e a ln o d ef r o mt h ev i r t u a la sas t a r td e p o t ，a n dw i t ht h eN e a r e s tN e i g h b o ra l g o r i t h mb yS o l o m o n ，t h ea n tc o l o n ya l g r i t h mw a sp r e s e n t e d 3 。F o rV R P S D 州av a r i a b l ew a si n t r o d u c e dt os o l v et h ep r o b l e mo ft h ev e h i c l e s c a p a c i t y Ah e u r i s t i cf u n c t i o ni n c l u d i n gt h er e m a i n i n gc a p a c i t ya n dt h et i m ew i n d o w sW a sg i v e n W i t ht h i s ，t h ea 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 ma n dt h em a t h e m a t i c a lm o d e lw e r ep r e s e n t e d 霹。C + + p r o g r a m sf o rt h ea b o v et w oi s s u e sw e r ep r e s e n t e da n dS i m u l a t i o n a le x p e f i m e n t sw e r ed o n eo nt h eb e n c h e m a r kp r o b l e m sf r o mV R Pw e b T h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h m sp r o p o s e di nt h i sp a p e ra r eb e a e r , a n dt h ea c t u a ls i g n i f i c a n c ei ss t r o n g , t h ec o m p u t a t i o nt i m er e q u i r e di sa l s or e a s o n a b l e K e y w o r d s ：v e h i c l er o u t i n gp r o b l e mm u l t i - d e p o 钰t i m ew i n d o w sa n tc o l o n ya l g o r i t h ms i m u l t a n e o u sp i c k - u pa n dd e l i v e r y西安电子科技大学学位论文独匐性( 或创新性) 声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以终，论文中不包含其他入已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一阕工作的同志对本研究所徽的任何贡献均巴在论文中徽了麓确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，邵：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保蜜送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。( 保密的论文在解密后遵守此规