（系统工程专业论文）基于改进蚁群算法的配送路线优化研究.pdf

基于改进蚁群算法的配送路线优化研究 研究生：沈轰导师：赵林度教授东南大学 摘要 随着信息技术的发展，现代物流作为“第三个利润源泉”正受到同益广泛 的重视，并面临前所未有的发展机遇。在现代物流中，配送是一个重要的与消 费者直接相连的环节，其体现了企业的核心竞争力。而物流配送路线优化研究， 是配送系统优化中的重要一环。通过配送路线优化，可以提高企业的运作效率， 降低配送成本，实现物流科学化。因此，本文对配送路线的优化研究主要依据 蚁群算法从以下几方面展开： 1 、对基本蚁群算法进行了改进。基本蚁群算法是2 0 世纪9 0 年代提出的一 种新型模拟进化算法，针对该算法易陷入局部最优解、求解速度较慢的缺陷， 本文对基本蚁群算法的全局信息素更新公式进行了改进，并在算法的实现过程 中动态调整q o 值。通过对旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 的仿 真对比，得到了较为满意的结果，体现了改进蚁群算法的相对优越性。 2 、在实际应用中，本文以江苏省科技攻关项目一生鲜加工配送体系食品安 全关键技术研究与开发( b e 2 0 0 4 3 1 1 ) 为应用背景，结合苏果超市有限公司“苏 果生鲜加工配送管理信息系统”的设计，将改进蚁群算法引入到配送子系统的 程序开发中。根据苏果配送的实际需求构建系统模型，对苏果配送路线进行优 化，主要解决车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) ，即确定最佳配送 路线，使车辆的总行驶里程最少。参照b e m d b u l l n h e i m e r 的利用基本蚁群算法 求解v r p 问题的算法实现思想，本文将改进蚁群算法运用到苏果v r p 问题的 求解中，设计出相应算法( 简称算法一) ，以实现配送路线的优化。 3 、由于算法一在实际配送中没有考虑到车辆的满载率，本文在算法一的基 础上对其进行了改进。将原有算法一的小循环结束标志一一蚂蚁只要一经过配 送中心无论其载重已装多少都认为其一次小循环已经结束，改为蚂蚁只有在货 物满载的情况下直接返回最初的起始点。根据这思想，本文重新设计出相应 的求解苏果v r p 问题的算法( 简称算法二) 。 通过算法二与算法一、节约算法对同一苏果配送实例的求解分析，证明了 算法二在计算时间、计算准确率、车辆满载率上都要明显高于其它算法。同时， 为了证明其通用性，本文还利用算法二对经典v r p 问题进行了系统仿真，亦取 得了较满意的结果。 4 、本文将算法二应用到苏果配送子系统中，最终形成了一个功能完善的配 送管理信息系统，该系统提高了苏果配送中心的配送效率，优化了系统管理， 在实际运用中取得了较好的效果。 关键词：物流配送蚁群算法配送路线优化车辆路径问题( v r p ) 优化仿真 v e h i c l er o u t i n gp r o b l e mb a s e do na n i m p r o v e da n t c o l o n ya l g o r i t h m g r a d u a t e ：s h e ny a o s u p e r v i s o r ：p r o f z h a o l i n d us o u t h e a s tu n i v e r s i t y a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n f o r m a t i o n ，l o g i s t i e s ，t a k e na s “t h i r dp r o f i t r e s o u r c e ”，h a sb e e np a i dm o r ea t t e n t i o na n di sg r o w i n gt ob ef a c e dt oas e r i e so f o p p o r t u n i t i e s i nl o g i s t i c s d i s t r i b u t i o ni s c r u c i a la n dd i r e c t l yl i n k e d 谢t 1 1t h e c u s t o m e r s w h e r e a s ，t h eo p t i m i z a t i o no fv e h i c l ep l a n n i n go ft h ed i s t r i b u t i o ns y s t e m i sak e yp a r to ft h ew h o l es y s t e m b yt h eo p t i m i z a t i o no fv e h i c l ep l a n n i n g ，t h e e n t e r p r i s e sc a r ti m p r o v et h e i rn u c l e u sc o m p e t i t i v e n e s sa n da c h i e v es c i e n t i f i cp r o c e s s o fl o g i s t i c s s ot h er e s e a r c h e sa b o u tt h eo p t i m i z a t i o no fv e h i c l ep l a n n i n go ft h e d i s t r i b u t i o ns y s t e mw h i c hi sb a s e do na n tc o l o n ya l g o r i t h ma r ea sf o l l o w s ： 1 、a n tc o l o n ya l g o r i t h mi si m p r o v e d a n tc o l o n ya l g o r i t h mi san o v e ls i m u i a t e d e v o l u t i o n a r ya l g o r i t h mw h i c hi sp r o p o s e df i r s ti nt h en i n e t i e s f i r s t l y , t h ea l g o r i t h m i si n t r o d u c e db yi t sp r i n c i p l ea n da p p l i c a t i o ni nar e a ld e t a i l t oa v o i dt h ep r o b l e m t h a tt h ea l g o r i t h me a s i l yt e n d st os t a g n a t i o nb e h a v i o ra n di t sc a l c u l a t i n gs p e e di st o o s l o w , an e wg l o b a lu p d a t i n ge q u a t i o ni sd e s i g n e d t h e n ，b ys o l v i n gt r a v e l i n g s a l e s m a np r o b l e m ，t h ei m p r o v e da n tc o l o n ya l g o r i t h mw h i c hg e t sg o o dr e s u l t si s p r o v e dt ob em o r ee f f e c t i v et h a nt h eo r i g i n a la n tc o l o n ya l g o r i t h m 2 、i na c t u a la p p l i c a t i o n ，b yt h eb a c k g r o u n do f “t h ep i v o t a lr e s e a r c ha n d e x p l o i t a t i o no ff r e s hf o o dc o l dc h a i np r o c e s si ns u p e r m a r k e t ，w h i c hi s a n i m p o r t a n tp r o j e c t i nt h e k e yt e c h n o l o g i e sr & dp r o g r a m so fj i a n g s up r o v i n c e ( b e 2 0 0 4 311 ) t h e i m p r o v e d a n t c o l o n ya l g o r i t h m i sc o m b i n e dw i t ht h e d i s t r i b u t i o nm a n a g e m e n ti n f o r m a t i o ns y s t e mi ns u g u os u p e r m a r k e t a n db a e s e d o nt h ea n a l y s i so ft h ep r e s e n td i s t r i b u t i o ns y s t e man e wd i s t r i b u t i o nm o d e li ss e tu p t h i sm o d e li sm a i n l yt oc a r r yo u tr o u t eo p t i m i z a t i o n t h ev e h i c l er o u t i n gp r o b l e m w h i c hf o c u s e st od e s i g nt h el e a s td i s t a n c eo fo p e r a t i n gv e h i c l e si st h em a i np a r to f i i r o u t eo p t i m i z a t i o n t h ea l g o r i t h m lw h i c hr e f e r st ob e r n d b u l l n h e i m e r st h o u g h ti s d e s i g n e dt ot h ed i s t r i b u t i o ns y s t e m 3 、a st h ea l g o r i t h m ld o n tc o n s i d e rt h ef u l ll o a do f t h ev e h i c l e s ，i ti sr e p l a c e d b yt h ea l g o r i t h m 2w h o s ea i mi s t o i m p r o v et h ef u l ll o a do fe v e r yv e h i c l e i n a l g o r i t h m lt h ea n tw i l lf i n i s hac i r c l ew h e ni tp a s sb yt h e d i s t r i b u t i o nc e n t e r i na l g o r i t h m 2t h ea n tw i l lf i n i s hac i r c l eo n l yw h e ni t sl o a di sf u l l a n dt h ea n tw i l lr e t u r nt oi t sf i r s ts t a r t b yc o n t r a s t i n gt ot h ea l g o r i t h m la n dt h es a v i n gm a t r i xm e t h o d ，t h ea l g o r i t h m 2 r a p i d l yi n c r e a s e st h ec a l c u l a t i n gs p e e da n dg e t sg o o dr e s u l t sw i t hf u l ll o a dm o r e a c c u r a t et h a nt h eo t h e ra l g o r i t h m s t op r o v ei t su n i v e r s a l i t y , t h ea l g o r i t h m 2i su s e d t oi m p l e m e n tt h ec l a s s i c a lv r pa n db r i n g sa b o u tf i n ee f f e c t 4 、t h ea l g o r i t h m 2i sa p p l i e dt ot h ep r o j c o to ft h es u bd i s t r i b u t i o ns y s t e ma n da p e r f e c td i s t r i b u t i o nm a n a g e m e n ti n f o r m a t i o ns y s t e mh a sb e e n u s e di ns u g u o s u p e r m a r k e r t h i ss y s t e mh a si m p m v e d t h ee f f i c i e n c yo fd i s t r i b u t i o n ，o p t i m i z e dt h e m a n a g e m e n ta n do b t a i n e dp r e f e r a b l ee f f e c ti nf a c t u a la p p l i c a t i o n k e yw o r d s ：l o g i s t i c sd i s t r i b u t i o n a n tc o l o n ya l g o r i t h m r o u t eo p t i m i z a t i o nv e h i c l er o u t i n gp r o b l e m o p t i m i z a t i o na n ds i m u l a t i o n v 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 研究生签名：；也盘e l 期：! 竺i ： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：也蕾导师签名日期：一6 3 e 雨人学硕士学位论文第一章绪论 第一章绪论 1 1 本文研究的意义和背景 在全球经济一体化的进程中，世界经济正处于深刻变革的重大转折时期。 在这一发展变革之中，出现了一系列与高科技相结合和实行现代管理的新兴产 业。现代物流就是其中的重要产物之一。物流作为“第三个利润源泉”，是一种 先进的组织方式和管理技术，已被世界各国广泛采用，并形成产业化，从而在 国民经济中发挥越来越重要的作用。 在我国，物流的概念是2 0 世纪8 0 年代初引入的，在此之前，中国的经济 研究中几乎没有使用过“物流”一词，但物流各环节的运作很早就存在于国民 经济的各个领域。在2 0 0 0 年至2 0 0 1 年，物流开始真正引起了我国各界的注意。 由于我国物流市场的开发潜力巨大，随着经济的发展和经济体制改革的进一步 深化，物流业正成为我国市场经济中竞争最为激烈的行业之一，其在现代经济 发展中的地位和作用，比任何时期都更加重要。现阶段，物流业已贯穿于我国 生产、分配、流通、和消费的各个领域，社会对物流需求的数量、质量正在不 断提高。在我国国民经济和社会发展“十一五”计划中，已将“物流配送”作 为重点支持和发展的服务产业。这些都为我国物流与国际物流接轨并溶入全球 物流一体化提供了条件。 物流配送作为物流体系中最为重要的一环，对整个物流系统的效率起着关 键的作用。先进高效的物流配送系统能为企业创造出更高的经济效益，是企业 增强自身竞争力的重要手段。 本文是以江苏省科技攻关项目一生鲜加工配送体系食品安全关键技术研究 与开发( b e 2 0 0 4 3 1 1 ) 为实际应用背景，与苏果超市有限公司共同研制“苏果 生鲜加工配送管理信息系统”。苏果超市有限公司是江苏省内超市零售业最大的 商贸流通企业。在南京，苏果超市占据着超市业态5 0 以上的市场份额。马群 配送中心是苏果超市有限公司最大的物流配送中心，其占地面积1 7 万平米，包 括商品加工与配送中心和配送分拣储藏库，年配送额达到6 0 个亿，是中国一流 的现代化物流中心。现阶段，苏果马群配送中心承担了苏果各大型社区店的商 术蔺凡学顺士学位论文 品配送工作。 与传统的商业形式相比，苏果超市连锁经营的优势就在于它集中管理了许 多个规模较小的店铺，统一进货、集中存储，统一管理、统一定价，从而实现 规模效益，使每个店铺的成本低于独立经营的成本。对苏果超市而言，高效率 的配送中心是其经营发展的关键。而苏果马群配送中心可以有力地支持各个门 店的市场营销体系，实现物流系统化和规模经济的有机结合。配送中心通过集 中配送的方式，按一定的规模集约，有利于获取规模效应；通过电子订货系统， 可以将各个门店的零星要货汇总，由供应商集中送货到配送中心，再由配送中 心按照各个门店的需要配货，这样做可以大大降低商品的库存成本，并使整个 苏果连锁经营体系的成本大幅度下降。 本文基于这样的背景，为苏果超市有限公司设计和规划了“苏果生鲜加工 配送管理信息系统”。该系统在苏果配送中心原有w m s 配送系统的基础上，对 其配送流程进行整合，从订单子系统到配送子系统设计出一套符合实际需要的 生鲜配送业务流程。同时，在该系统的设计中还将符合当代信息技术发展趋势 的食品安全管理理念引入到业务流程中，开发出具有实用性、先进性、可扩充 性、高可靠性的物流管理信息系统。 “苏果生鲜加工配送管理信息系统”主要分为苏果主页、苏果安全信息网、 订单子系统、配送子系统等四大部分。订单子系统与配送子系统可以合成为一 个完整的业务流程。各个门店通过订单子系统向配送中心上传指定格式的需求 信息。这些需求信息经分类汇总后，再转入配送子系统。配送子系统则根据订 单报表安排批次和配送计划，制订出合理的配送路线。 本文所作的研究工作主要是设计并完成配送子系统中的配送路线优化问 题，通过研究车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) ，力求确定最佳的 运输路线，在提高车辆满载率的同时，使车辆运输距离达到最小化，完善苏果 马群配送中心现有的配送系统，从而使配送环节的总成本降低，提高配送的效 率，综合增强苏果超市的核心竞争力。 1 2 相关文献综述 在本课题中，对配送路线的优化问题可以归结为对配送车辆行车路线的组织 i 、商凡学硕二1 学位论文 第一章绪论 优化问题车辆路径问题( v r p ) ，即根据不同的要求一一目标函数( 例如行 车路线最短) ，将配送过程归结为表述问题的数学模型。然后利用计算机求得合 理可行的优化方案，并在配送中付诸实施。 v r p 问题于1 9 5 9 年吐t d a n t z i g 和r a m s e r 首次提出。自此，很快引起运筹学、 应用数学、组合数学、图论、网络分析、物流科学、计算机应用等学科的专家与 运输计划制定者和管理者的极大重视，成为运筹学与优化组合领域的前沿与研究 热点问题，是组合优化领域中著名的n p 难题。各学科专家对该问题进行了大量 的理论研究与实验分干斤【”。 在1 9 8 3 年b o d i n 、g o l d e n 等人在他们的综述文章中就列举了多篇文献。在 c h r i s t o f i d e s ( 1 9 8 5 ) ，g o l d e n 和a s s a s ( 1 9 9 8 ) 编辑的论文集，以及a l t i n k e m e r 和g a v i s h ( 1 9 9 1 ) ，l a p o r t e ( 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章中都进行了详 尽的阐述。该领域的代表人物有b o d i n ，c h r i s t o f i d e s ，g o l d e n ，a s s a d ，b a l l ， l a p o r t e ，r i n n o o yk a n ，l e n s t r a ，d e s t o s i e r s 和d e s r o c h e r s 等。 现阶段，对v r p 问题的研究己产生出多种成熟的算法。典型的车辆配送路线 优化问题的相关文献有： c l a r k e 和w r i g h t 在1 9 6 4 年首次提出了节约算法( s a v i n gm e t h o d ) ，该方法成为 早期解决v r p 问题最为经典的方法。对于该算法应首先计算包括配送中心在内的 各个客户相互之间的最短距离，然后计算各客户之间可节约的配送距离，按照节 约配送距离的大小顺序连接各配送地并规划出配送路线。节约算法所规划出的配 送路线并不一定都是最优解，有时也有近似解，但对于客户比较多、规模比较大 的情况，它比人工计算要快得多。现阶段，许多成功的车辆调度软件就是根据该 方法或其改进方法开发的 3 4 】。 g i l l e t 和m m e r 在1 9 7 4 年提出了扫描法( s w e e pm e t h o d ) ，该算法先把结点或 弧的需求进行分组或划群，然后对每一组按旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 进行求解，设计出一条经济的路线。其目的在于求解车辆调度问 题，并与当时几个求解相似问题的算法进行比较，从而证明该算法所求得的解较 优于其它的方法8 1 。 w i l l a r d 在1 9 8 9 年首次将禁忌搜索算法应用于配送路线优化问题上，该算法设 计出重复的虚拟物流中心，然后将车辆路线优化问题转换成旅行商问题( t s p ) ， 尔南丈学硕士学位论文 第一蕈绪论 利用2 o p t 或3 一o p t 方法求解最优车辆路线 6 】。 c h r i s m f i d e s $ 口g i l b e r tl a p o r t e 在1 9 9 2 年将l i n 和k e m i g h a n 于1 9 7 3 年提出的分 支交换探索算法进行了推广，使得该算法在始终保持解的可行性的同时而又力图 向最优解逼进。在每一步，都改变一个可行解而减少总费用，直到这个过程继续 到不再可能使费用减少为止“。1 。 g e n d r e a u 、h e r t z 和l a p o r t e 在1 9 9 4 年使用插入法来求解旅行商问题( t s p ) ， 同时再用贪心算法( g r e e d ym e t h o d ) 对路线进行切割，从而产生初始解，在初 始解的不断优化基础上，逐步求出最优解“。 b a r b a r o s o g l u 和o z g u r 在1 9 9 9 年利用禁忌搜索算法为士耳其某物流公司构建 一决定货车配送点顺序的方法d e t a b a ，以二种乱数选取结点的方法产生一系列 解从中找出最佳的解作为初始解，再以插入法( i n s e r t i o np r o c e d u r e ) 作为搜寻 邻近解的移步方法，最后再以2 o p t 改善方法找到最优解的值 i ”。 c t s u 和h h c h e n 在1 9 9 9 年成功地将自组织影射网络应用在车辆配送区域 及路线规划问题的求解上，其算法的主要概念是利用类神经网络的快速运算、自 我组织与平行处理的特性，配合m 个一维环状网络拓扑来表现车辆路线优化问题 【1 2 1 。 f i l i p e c 、s k r l e c 和k r a j c a r 在1 9 9 8 年将遗传算法用于求解配送路线优化问题， 在选择、交叉、变异等遗传操作后，引入混合算子，并根据适应度对新产生的染 色体进行平行操作。系统仿真表明该算法明显增强了种群的演化质量。通过与其 它算法的比较，进而证明该算法收敛速度较快，具有较高的求解效率，所求结果 相对稳定“。 以上对v r p 问题的求解算法各有优缺点，本文将蚁群算法引入到v r p 问题 中，对蚁群算法进行了一系列改进。 蚁群算法是由意大利学者m d o r i g o 、a c o l o m i 、v m a n i z z o 等在9 0 年代初提 出的一类新的仿生算法。该算法的特点是模拟自然界中蚂蚁的群体行为。自然蚁 群总是能够发现从蚁巢到食物源的最短路径。蚂蚁在行走过的路上会留下一种挥 发性的激素，蚁群就是通过这种激素来进行信息交流，而蚂蚁会趋向于走激素积 累较多的路径。找到最短路径的蚂蚁总是最先返回巢穴，从而在路上留下了较多 的激素。山于最短路径上积累了较多的激素，选择这条路径的蚂蚁就会越来越多， 东南大学颐t 学位论文第一章绪论 到最后所有的蚂蚁都会趋向于选择这条最短的路径“。 m d o r i g o 将蚁群算法应用于求解t s p i n j 题、分配问题、j o b s h o p 调度问题， 均取得了较好的结果。d c o s t a l 手i a h e r t z 在m d o f i g o 等人研究成果的基础上，提 出了一种求解分配类型问题( a s s i g n m e n t t y p ep r o b l e m ) 的一般模型，并用来研 究图着色问题。g b i l c h e v 等研究了求解连续空间优化问题的蚁群系统模型，并用 来解决某些实际工程设计问题。为了克服基本蚁群算法的不足，提高搜索效率， 避免过早停滞，一系列改进蚁群算法相应提出，其中主要的一些算法如下： m d o r i g o 和m a n i e z z o v 在1 9 9 6 年提出了a m t qs y s t e m ，在该算法中对每一只 蚂蚁个体的移动规则进行了修改，并修改了全局更新公式。同时算法研究t a n t - q s y s m m 的性质，以及参数a 、b 、q o 对算法性能的影响。该算法比蚁群算法更具有 一般性，有利于实现全局搜索【1 5 】 1 6 【1 7 】。 t h o m a ss t u t z l e 和h o l g e rh o o s 在1 9 9 7 年提出了m m a s ( m a x 2 m i na n ts y s t e m ) 算法，其基本思想是：在蚁群算法中仅对每一次循环中的最优蚂蚁所走路径上的 信息素进行调整容易出现停滞现象，为了避免停滞，将九分支因子引入，使其作 为衡量群体多样性的一个指标。当九分支因子低于某一数值时，便对各个路径上 的信息素浓度进行动态调整，以避免过早出现停滞。但九分支因子计算较为复杂， 且对其界限不容易把握，不便于实际应用【1 8 】。 l m g a m b a r d e l l a $ 1 m d o r i g o 在2 0 0 0 年提出了混合型蚁群算法h a s ，在该算 法中，经过每次循环蚂蚁建立各自的解，再以各自的解为起点用某种局部搜索算 法求出局部最优解，从而可以迅速提高解的质型1 9 1 。 w j g u t j a h r 在2 0 0 0 年提出了一种以图为基础构建的蚁群系统框架，在一定条 件下每次迭代所得到的解能以近似于1 的概率向最优解收敛2 0 1 。 在参考文献 2 l 】中，作者提出了基于蚁群算法的分段求解算法，对蚁群算法 进行并行化处理，从而提高了蚂蚁的搜索速度口“。 在参考文献 2 2 1 中，作者提出了具有变异特征的蚁群算法，该算法有机地结 合了2 o p t 方法，提高了算法的性能。 在参考文献 2 3 】中，作者提出了基于粗粒度模型的蚁群优化并行算法，该算 法将搜索过程并行化，把所有蚂蚁划分为q 个子群，由这些子群并行地完成搜索， 再从所有子群中找到全局最优解，使用该方法可以使搜索速度大幅度提高口。 舟= = 两大学硕士学位论文第一章绪j 芑 在参考文献 2 4 中，作者对遗传算法与蚁群算法的机理和性能进行了研究， 将两种算法融合，提出一种新算法a c a g a ，通过遗传算法来优化蚁群算法中的 控制参数，并运用m m a s ( m a x 2 m i na n ts y s t e m ) 算法来确定蚂蚁状态转移规则， 实现对搜索空间的高效寻优2 ”。 1 3 本文研究的主要内容 本论文的研究工作是在苏果超市有限公司项目“苏果生鲜加工配送管理信 息系统”的资助下完成的，主要研究苏果超市的物流配送环节，为其设计出高 效率的物流配送子系统。概括起来，本文主要作了如下方面的研究： 1 、通过对相关文献的分析和总结，本文从物流配送中车辆路径问题( v r p ) 的基本理论出发，阐述了v r p 问题的相应分类，深入分析了v r p 问题的数学 模型，着重介绍了解决v r p 问题的节约算法模型及求解步骤。 2 、在详细介绍了基本蚁群算法的原理及其相应模型的基础上，对算法的复 杂度进行分析，给出了基本蚁群算法的实现步骤与计算机伪代码。针对其实现 过程中的不足，从全局信息素的更新机制和q o 的动态变化两方面对其进行改进， 并给出相应改进蚁群算法的复杂度分析、收敛性分析、以及算法的实现步骤与 计算机伪代码。通过系统仿真，对基本蚁群算法与改进蚁群算法的结果进行了 详细的比较。 3 、本文将改进蚁群算法引入到“苏果生鲜加工配送管理信息系统”的开发 中，结合苏果马群配送中心的实际需求设计出相应的v r p 模型，与基本v r p 模型相比新模型加入了对路径的限制，使实际的路径根据各种参数变为模拟路 径，从而参照b e m d b u l l n h e i m e r 的利用基本蚁群算法求解v r p 问题的算法实 现思想，综合设计出了解决配送路线优化问题的算法一。 为了进一步提高配送车辆的满载率问题，本文在算法一的基础上对其进行 了一系列改进，综合提出了算法二。通过对算法二的系统实现，得出了明显优 于算法一的相应结果。同时，本文利用节约算法对同一实例进行仿真，通过三 种算法的对比分析，进一步证明了算法二的优越性。为了证明算法二的通用性 与准确性，本文还对经典v r p 问题进行了系统仿真，选取具有较大结点数的 g r a p h 8 8 图为基本仿真数据，亦得到了较好的结果。 午南犬学硕士学位论文 4 、最后，总结研究工作的成果，并对今后进一步的工作提出了一系列设想。 论文的总体结构如图1 - 1 所示。 第一章绪论 ： ( 1 ) 求最短送货路径 ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) 东南大学硕士学位论文第二章物流配送中的乍辆路径问题研究 ( 2 ) 每条路径上的各个分仓库的货物总供应量不超过这条路径的送货车容量 ( 3 ) 每条路径上的分仓库数量不超过总共的仓库数量 ( 4 ) 每一个分仓库都得到车辆的送货服务 ( 5 ) 每条路径所经过的分仓库的集合 ( 6 ) 每个分仓库的货物仅能由一辆车来运送 2 4 y r p 问题的求解算法 综合v r p 问题的各种求解算法，可主要分为精确算法( e x a c ta l g o r i t h m ) 和启发式算法( h e u r i s t i c s ) 两种。其中精确算法包括树状寻优算法、动态规划 和整数规划。启发式算法则多是来源于对t s p 问题的求解算法，如局部优先算 法、插值法等一系列算法可以不用修改地直接用于求解一些典型v r p 问题。 2 4 1 精确算法 精确算法是基于运筹学的优化算法，一般运用线性规划( 包括经过了专门 处理的分枝定界法、割平面方法和标号法) 和非线性规划等数学规划技术，以 便求得问题的最优解。在v r p 问题研究的早期，主要是单源点( o n e p o i n t ) ( 即 配送中心、车场等) 派车，研究如何用最短路线( 或在最短时间内) 对一定数 量的需求点( 即用户) 进行车辆调度，主要运用最优算法，求出问题的最优解。 随着配送路线系统的复杂化和对调度的多目标要求，获得整个系统的精确优化 解越来越困难，而且用计算机求解大型优化问题的时间和费用太大。因此，精 确优化方法及其简化算法现只常用于配送路线的局部优化问题。 解决v r p 的精确算法可以分为以下四种： l 、分枝定界法( b r a n c ha n db o u n da p p r o a c h ) ； 2 、割平面法( c u t t i n gp l a n e s a p p r o a c h ) ； 3 、网络流算法( n e t w o r kf l o w a p p r o a c h ) ： 4 、动态规划方法( d y n a m i cp r o g r a m m i n g a p p r o a c h ) 等。 在以上算法中，最为常用的是动态规划方法，而具体求解时效率最高的方 法是分支定界法。它可以在不很长的计算时间内求解多至8 0 个结点的v r p 问 题，但是采用分支界法的v r p 问题必须在其模型中限制设施的数量。一旦所涉 蚓萄大学硕士学位论文 第一章物流配送中的车辆路径问题研究 奠的v r p 问题的规模扩大，精确算法就不实用了。 精确算法随着运输系统的复杂和调度目标的增加，其计算量是呈指数递增， 从而使得获取整个系统的精确最优解越来越困难，而用计算机求解大型优化问 题的时间和费用又太大。因此，此类优化方法和算法现在一般仅用于求解运输 调度的局部优化问题。 2 4 2 启发式算法 为了克服精确算法的不足，可以运用一些经验法则来降低优化模型的数学 精确程度，并通过模仿人的跟踪校正过程来求取运输系统的满意解。启发式算 法则能同时满足详细描绘和求解问题的需要，较精确算法更加实用。 启发式算法求解车辆路径问题可分成三个阶段：第一阶段是从1 9 6 0 年到 1 9 7 0 年，属于简单启发式算法，包括有各种局部改善启发式算法和贪心算法 ( g r e e d y ) 等；第二阶段是从1 9 7 0 年到1 9 8 0 年，属于一种以数学规划为主的 启发式算法，包括指派法、集合分割法和集合涵盖法；第三阶段是从19 9 0 开始 至今，属于较新的方法，包括利用严谨启发式算法、人工智能方法等。 现阶段的多种启发式算法，其主要区别在于求解过程的收敛速度和收敛程 度不同。一般来说，可以把现阶段的启发式算法分为以下四类i l l ： 1 、构造算法 根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有的点 都被安排进线路为止。该类算法的每一步，把当前的线路构形( 很可能是不可 行的) 跟另外的构形( 也可能是不可行的) 进行比较并加以改进，后者或是根 据某个判别函数( 例如最短行车路线) 会产生最大限度的节约的构形，或是以 最小代价把一个不在当前构形上的需求对象插入进来的构形，最后得到一个较 好的可行构形。构造算法是最早提出的用来解决旅行商问题( t s p ) 的算法。 这些方法一般速度较快，也很灵活但这类方法有时找到的解离实际的最优解相 差较远。 2 、两阶段算法 两阶段算法是对构造算法进行的一系列改进。该算法在第一阶段得到一个 可行解，第二阶段则对可行解进行调整。通过对点的调整，在保持解是可行的 东南大学硕士学位论文 第一章 物漉配送中的车辆路狰问题研究 基础上，尽力向最优解接近，每一步都用产生的新可行解取代原来的可行解， 使目标函数值得到改进，一直继续到目标函数值再也得不到改进为止。两阶段 常用的算法为： 第一阶段常用构造算法； 第二阶段常用的改进技术为交换法，这是一种在解的邻域中搜索，对初始 解进行某种程度优化的算法，用以改进初始解。一些基于数学规划的算法也属 于两阶段法，这些算法把问题直接描述成一个数学规划问题，根据其模型的特 殊构形，应用定的技术( 如分解) 进行分划，进而求出最优解。 3 、不完全优化算法 精确算法中的决策原则在规模很大的问题中易导致计算量的指数增长。而 在不完全优化算法中，用启发式准则来代替精确算法的决策原则可以有效缩小 解的收缩空间。 4 、改进算法 从一个初始解开始，通过对当前的解进行反复的局部扰乱，以求得问题的 满意解。 在启发式算法中最具有代表性的就是e hc l a r k e 和w r i g h t 提出的节约算法 ( s a v i n gm e t h o d ) 1 2 。 节约算法的基本原理如下( 3 1 1 4 1 ： 设配送中心为p o ，n 个用户分别为p l ，p 2 ，p n ；p i 和p j 之间的最短 距离是蛳，且d i j 已知( i ，j = 1 ，2 ，n ) 。 如果发送车辆的吨位已知，并且每一辆车都可以满载，则研究的目标可以 转化为使所有参加配送的车辆行驶距离在满足约束条件的基础上达到晟小。 ( b ) 节约算法的基本原理 ：jj 、学硕士学位论文 第一章物流配送中的车辆路径问题研究 节约算法的基本原理如图2 2 所示，在( a ) 中配送中心的两条运输路线由 p o p i 一1 _ p i p o 和p o p j p j + 1 - - p 0 组成。在图( b ) 中，将配送路线改为 一条p o _ _ p i 一1 一p 卜- p j p i + 1 - - p 0 ，则改动之后的节约量是： s ( i j ) = d ( 0 ，i ) + d ( o d ) - - d ( u ) ( 2 - 1 ) 式( 2 一1 ) 称为节约量公式。将节约量大的两个用户连接起来采用巡回方式 送货，则可以获得较大的节约里程。在车辆负荷允许的条件下，将其它客户与 已在巡回路线中的用户按节约量的大小依次连接入巡回路线，直至车辆满载时 为止。余下的客户则放入下辆车，按照同样的办法来寻求巡回路线。 节约算法在物流配送车辆路径问题上的求解过程： 设配送中心p 0 向客户p j ( j = 1 ，2 ，n ) 送货，各客户需求量为p j ，客 户与配送中心最短距离为d ( o j ) ，客户之问的距离为d ( 巧) ( i - l ，2 ，n ； j = l ，2 ，n ) ，送货车辆按其载重量的大小不同有m 种，载重量为q k ( k = 1 ，2 ，m ) 的送货车有x k 台，且q k 1 q k p ，绯 假定： p 1 p j q o 时，使用随机选择的方式选择下一条路径，该方式称为开发方式 ( e x p l o i t a t i o n ) ； 当q - q o 时，根据式( 3 2 ) 选择概率最高的路径( 即信息素浓度最大的路 径) ，该方式称为探险方式( e x p l o r a t i o n ) ； 图3 - 2 轮盘选择示意图 图3 2 是蚂蚁选择下一条路径的轮盘选择示意图。由图可知，蚂蚁从城市 a 点移动到城市b 点，在b 点蚂蚁将面临三条路径选择，c 路径、d 路径和e 路径，在各条路径上经计算后的转移概率分别为o 3 ，0 5 和o 2 。假设q o = 0 4 ， q 是均匀分布在 o ，1 1 _ 1 ：的一个随机变量。 当q = 0 2 时，q _ q o 蚂蚁通过随机概率选择的方式选择下一条路径，即3 0 的概率选择c 路径，5 0 的概率选择d 路径，2 0 的概率选择e 路径。 局部更新规则： 每只蚂蚁在建立一个解的过程中也同时进行信息素的局部更新过程，对它所 经过的路径上的各条弧按下式调整信息量强度： r ( r ，s ) = ( 1 - p ) r ( r ，s ) + p a r ( r ，s ) ( 3 3 ) 其中，p 表示局部信息素的挥发因子，则1 _ p 表示信息素的保留率，为了防止信息 的无限累积，p 的取值范围限定在( 0 ，1 ) 之间。a r ( r ，j ) 为信息素增加量，即蚂 蚁k 在时间段t 到( t + n ) 的过程中，在从城市r 到城市s 的路径上的增加的信息素浓 度。 9 笨甫人学硕士学位论文 第三章改进蚁群算法研究 全局更新规贝i j ： 当所有的蚂蚁都完成一次循环后，只有生成了全局最优解的蚂蚁( 即从一开 始到现在构建了最短路径的蚂蚁) 才有机会进行全局更新，按下式对最优蚂蚁经 过的所有路径上的信息素进行全局更新，不属于最优蚂蚁走过的路径其信息素更 新为0 ： r ( r ，s ) = f ( 1 一口r 名5 + 口7 ( 3 4 ) 其中，仪表示全局信息素的挥发因子，1 一表示全局信息素的保留率，a 的取值 范围在( o ，1 ) 之间。a r = i l b ，l b 为该算法已求出的最短路径长度( 这里的 最短路径仅指在这一次循环中所取得的最短路径) 。 当每只蚂蚁都完成一次上述操作时，就称该算法进行了次周游 ( i t e r a t i o n ) 。循环以上步骤，直到周游次数达到指定次数或在一定时间内没有 新的更优解出现为止。 根据具体算法的不同，磋、a r ( r ，s ) 、a r 的表达形式可以不同，一般由具 体问题来设定。 m d o r i g o 曾给出三种不同的模型：a n t c y c l es y s t e m 、a n t - q u a n t i t ys y s t e m 、 a