（管理科学与工程专业论文）基于蚁群算法的分销网络优化研究.pdf

重庆大学硕士学位论文中文摘要 摘要 随着市场压力的增大，客户需求日益多样化，许多企业不得不重新评价他们 的配送策略。在面向客户的制造环境中，企业的驱动力己由生产转向通过分销和 服务提供的附加值。因此，合理地建立分销网络，加强对分销环节的管理，是在 当前客户驱动的竞争环境下，提高客户的满意度，增强企业竞争力的重要途径。 然而，在分销网络优化中经常出现组合优化问题或者是最优s t e i n e r 树问题，传统 的算法很难解决此类n p 难题，而往往求助于近似算法或者是智能仿生算法。为此， 本文利用蚁群算法对于n p 完全问题具有的抵御组合爆炸的能力进行求解该类问 题。 本文将蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 在t s p 问题上的应用做了研 究，与传统求解t s p 问题的近似解法( 对角线算法) 和精确解法分别在求解的精 确性和求解的速度方面进行了比较，并给出了a c o 解t s p 问题的具体算法步骤和 程序设计，其实例结果表明a c o 在求解的速度方面优于传统的精确解法，在求解 的精确性即寻找最优解的能力方面好于传统算法。并且，通过实例仿真研究和程 序设计，指明在a c o 的具体运用时应注意参数的选择等问题和a c o 的应用范围 即n 较小时宜采用传统算法，当n 值很大时a c o 更好。主要成果有： 用a c o 求解分销网络优化中的双层分销网络模型，给出了a c o 求解的模式、 解如何构造和具体算法步骤，并通过文献 4 】中的实例及该文献运用改进分枝定界 和伏格尔法相结合解该模型得到的结果进行了比较，实例结果表明，本文提出的 基于a c o 解决分销网络优化中出现的n p 难题，能够得到更好的解。 提出了在分销网络优化中出现的重构分销网络以使得分销网络运营成本( 费 用或时间) 的问题，在以往的双层生产一分销模型的基础上提出了面临突然需求 或市场需求不平衡情况时的三层结构模型，增加了分销中心的物流流动和生产中 心的协调功能。然后指出以上两个问题都是同一类问题，可以引入中转点( 即s t e i n e r 点) 求解。通过模型简化，然后将最优s t e i n e r 树的概念引入分销网络优化中，利用 改进的蚁群算法求解，并给出了实例比较和程序运行结果，并验证了本文提出的 基于蚁群算法的s t e i n e r 树寻找方法能达到分销网络优化的目的。 关键词：蚁群算法，分销网络优化，最优s t e i n e r 树，组合优化 重庆大学硕士学位论文英文摘要 a b s t r a c t w i t l lt h ea r g u m e n to ft h ep r e s s u r eo fm a r k e ta n dd i v e r s i f i c a t i o no fd e m a n do f c u s t o m s ，m a n yc o r p o r a t i o n s h a v et o r e a p p r a i s e t h e i rd i s t r i b u t i o n s t r a t e g y t h e m a n u f a c t u r e e n v i r o n m e n ti nw h i c ht h ec o r p o r a t i o n sh a v et u r n e dt h ed i r e c t i o no f i n c r e a s i n ga d d f i o nv a l u ef r o mm a n u f a c t u r et od i s t r i b u t i o na n ds e r v i c e t h u s ，i nt h e c u s t o m d r i v e ne n v i r o n m e n t , r e a s o n a b l ed i s t r i b u t i o nn e t w o r ka n ds t r e n g t h e n i n gt h e m a n a g e m e n to fd i s t r i b u t i o nn e t w o r ka r ei m p o r t a n ta p p r o c ht oi m p r o v ec u s t o m s s a t i s f i c a t i o na n db u i l d u pt h ec o m p e t i t i o np o w e ro fc o r p o r a t i o n b u t ，w ea l w a y sc o m eu p a g a i n s tt h ec o m b i n a t i o no p t i m i z a t i o no rn o n d e t e r m i n i s t i cp o l y n o m i n a lp r o b l e m s ( y p ) i nt h ed i s t r i b u t i o nn e t w o r ko p t i m i z a t i o n ( d n o ) ，t h e ya r eh a r d l yc o m eo u tb yt h e t r a d i t i o n a lm e t h o d sa n dm a n ys c h o l a r st u mt oa p p r o x i m a t ea p p r o a c ho rs i m u l a t i n g b i o l o g yi n t e l l i g e n ta l g o r i t h m s a n tc o l o n yo p t i m i z a t i o n ( a c o ) ，w h i c hi si n t r o d u c e d i nt h i sp a p e rb e c a u s eo ft h ea b i l i t yo fr e s i s t i n gc o m b i n a t i o ne x p l o s i o nt on p - h a r d p r o b l e m n o wi su s e dt os o l v et h ep r o b l e mo fd n o 1 1 1 em a i nr e s u l t so ft h i sp a p e r i n c l u d et h ec o n t e n tb e l o w f i r s t l y , w ea p p l ya c o t os o l v et h et s pa n dc o m p a r e dt h ea c c u r a c yo fa l g o r i t h m 嘶md i a g o n a la l g o r i t h m ，w h i c hi sat r a d i t i o n a la p p r o x i m a t ea p p r o a c h ，a n dc o m p a r e d t h es p e e do fa l g o r i t h mw i t ht h et r a d i t i o n a la c c u r a t ea p p r o a c h b yd a t as i m u l a t i o na n d e x p e r i m e n t , w en e e dt op a yv e r ya t t e n t i o nt oc h o o s et h ep a r a m e t e ra n dt h ea p p l i c a t i o n a r r a n g eo f a c o ，i e ，t h et r a d i t i o n a lm e t h o d sa r eb e t t e rw h e nt h eni sl i t t l es c a l ea n da c o w i l lb eb e t t e rw h e nt h eni sv e r yl a r g es c a l e s e c o n d l y , a c oi su s e dt os o l v et h eb i - l e v e ld i s t r i b u t i o nn e t w o r km o d e li nt h e d n o ，p u tf o r w a r dt h ec a l c u l a t em o d eo f a c o a n dt h em e t h o do fs o l u t i o ns t r u c t u r ea n d c o n c r e t ep r o c e s so fa l g o r i t h m a tl a s t ，c o m p a r e dt h er e s u l tc o m i n gf r o mm e t h o da b o v e w i t hh y b r i d i z eh e u r i s t i ca l g o r i t h mw i t hc o n v e n t i o n a lb r a n c h - - a n d - - b o u n dm e t h o di n l i t e r a t u r e 4 t h ee x p e r i m e n tr e p r e s e n t s ，t h em e t h o db a s e do na c oi nt h i sp a p e rc a n s o l v et h en ph a r dp r o b l e mi nt h ed n oa n dc a ng e tb e t t e rs o l u t i o nt h a nc o n v e n t i o n a l m e t h o d s t h i r d l y , t h ep r o b l e mo fr e e n g i n e e r i n gt h ed i s t r i b u t i o nn e t w o r kt or e d u c et h ec o s t i n c l u d e st i m eo re x p e n s e sh a v eb e e np r e s e n t e di nt h i sp a p e r f u r t h e r m o r e ，w ea d dt h e f u n c t i o no fl o 舀s t i cm o v i n ga n dt h ei n f o r m a t i o nc o o r d i n a t i o nf u n c t i o no fm a n u f a c t u r i n g c e n t e r sa n dp u tf o r w a r dt h et r i p l e 1 e v e lm o d e lb a s e do nt h eb i l e v e lf o rt h es u d d e nn e e d i i 重庆人学硕士学位论文 英文摘要 o rm a l a d j u s t m e n to fm a r k e tn e e d m o r e o v e r , t h et w op r o b l e mp r e s e n t e da b o v ea r et h e s a m ep r o b l e ma n dc a r lb es o l v e db yi n t r o d u c e dt h es t e i n e rt r e e 。h o w e v e r , s e a r c h i n g s t e i n e rt r e ei si m p o r t a n tf o ro p t i m i z i n gt h ed i s t r i b u t i o nn e t w o r k s ，w h i c hi sp r o v e dt o b en p c o m p l e t e w es i m p l i f yt h em o d e la n dm a k eu s eo ft h ei m p r o v e da c ot os e a r c h t h es t e i n e rt r e ei nt h ed n o t h er e s u l t so fe x p e r i m e n ta n dc o m p a r i s o ns h o wt h a ta c o a n ds t e i n e rt r e ea r ef e a s i b l et oo p t i m i z et h ed i s t i l b u t i o nn e t w o r k s k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n ，d i s t r i b u t i o nn e t w o r k0 p t i m i z a t i o n ，s t e i n e rt r e e ， c o m b i n a t i o no p t i m i z a t i o n 重庆大学硕十学位论文1 绪论 1 绪论 本章主要介绍了分销网络优化中关于建立分销中心和分销点问题，提出了引 入中转点使得网络分销成本最小的思想，提出了当面临突然需求或市场需求不平 衡时分销网络重构及优化的问题。介绍了分销网络优化的意义及其研究进展，蚁 群算法的研究进展及其在分销网络优化中的应用，分销网络优化的概述及其问题 模型。最后列出了本文的研究内容和创新点。 1 1 问题的提出及研究的意义 1 1 1 问题的提出 随着市场压力的增大，客户需求日益多样化，许多企业不得不重新评价他们 的配送策略。特别是近年来信息技术的迅速发展以及新物流观念的产生，制造企 业逐渐形成了多供应商、多地点制造、多客户的新供应链模式。而对供应链的研 究主要包括三个阶段，即采购、制造和分销。在传统制造环境下的供应链管理中， 重点考虑的是对采购和制造环节的管理。进入2 0 世纪8 0 年代，供应链的重心正逐 渐向需求方转移，供应链表现为由市场和客户需求驱动的“需求链”。在面向客户的 制造环境【； j ，企业的驱动力已由生产转向通过分销和服务提供的附加值。因此， 合理地建立分销网络，加强对分销环节的管理，是当前客户驱动的竞争环境下， 提高客户的满意度，增强企业竞争力的蓐要途径。为了满足小批量多品种和实现 及时送货的服务目的，生产商往往采取将库存地点建在市场周边，形成了生产 分销模式，这是生产商扩大市场占有率和增加销售量的应变措旌。与此同时，包 括生产商、批发商和零售商在内的生产分销环节都遇到了产品库存管理方面的问 题，一方面，存货过多，增加了仓储成本；另一方面，存货不足白白错失商机， 或者增加订货次数使得订货成本增加【“。 为了在满足合理的需求分配和必要的约束条件下，达到建设运营总成本、配 送总成本、生产总成本之和为最小的目的，必须解决如下问题 1 卅：1 ) 应该从现有 的需求点中，具体选择哪些需求点建设成分销配送中心。2 ) 每个分销配送中心除了 为自己供货外还负责为哪些分销点供货。3 ) 各个分销配送中心的每类商品由哪些供 应点负责供货，供应多少，各供应点如何根据需求状况，确定供应商品的种类和 数量。而对于大规模的数量的需求地选择分销中心和分销点问题属于组合优化问 题，足n p 难题。 在分销网络中，为了降低运费和降低运送时间，增加某些中转点可能使得从 整体上系统总的运营费用或更快响应顾客需求。对于增加中转点以优化已有分销 重庆大学硕士学位论文1 绪论 网络的运输费用最少或者时间最少问题实际上等价于最优s t e i n e r 树问题，s t e i n e r 树问题是从图论中引申出来的一个优化问题：在一个连通图中，给定一个节点子 集，要求在图中找到一棵覆盖给定节点子集的费用最小的生成树1 5j 。而在1 9 7 2 年 k a r p 等证明了最小s t c i n e r 树问题是n p 完全问题n 众所周知，市场本身是变化的，顾客的需求也是随着时间和空间的不同而变 化的，市场机会稍纵即逝。当某个或者某些区域面临突然需求( 超出市场预测的 大量需求，库存不能满足需求) ；或者是市场需求不平衡( 某些区域销售情况看好， 库存太少和生产中心的产品太远，而另外一些地区销售情况不好，库存积压严重， 急于降低库存) 。以上两个情况都要求及时调度其他分销中心可利用的库存，另外 部分分销中心可能不能够供应货物，但可以作为中转点使得整体的运营成本( 包 括时间或者费用) 最少，这样又回到以上的最优s t e i n e r 树问题。 1 1 2 研究的意义 1 ) 实际应用的意义：分销网络的设计、优化、管理是供应链管理中的一个子 系统。供应链管理指的是对各个设施点之间的物流及信息流进行管理，如供货商、 制造商、加工商、分销中心等。由于供应链管理的复杂性，在早期对其进行优化 的过程中，一般是将供应链的三个阶段分别加以研究，并以足够的库存作为各阶 段之m 的缓冲。但随着研究的深入，人们认识到如果对供应链的各个阶段加以集 成和协调，以客户需求为驱动来对分销网络进行管理和设计、协调和调配，将会 明显地降低整个供应链的运营费用，提高客户服务水平，从而增强企业的竞争力。 另外，如果对以上提出的两个问题能够加以研究，可以增加供应链的快速响应顾 客需求和增加供应链的柔性( 援引柔性制造系统f m s 的概念) 水平。 2 ) 方法论探讨的意义：分销配送网络的优化设计是流通领域中十分重要的课 题，也是供应链优化设计研究中的热点。在传统的分销网络设计中一般均不考虑 客户对各个分销点的选择行为。事实上，某个客户的需求不但可以由多个分销中 心共同满足，而且由每个分销中心配送的货物量取决于客户的选择行为，同时这 种选择行为在很大程度上具有较高的随机性。尤其是在现代物流系统中，客户的 需求应该放在首位。而传统的分销网络优化模型仅从网络规划人员自身角度出发， 来考虑网络中设施位置及流量安排。而实际上，网络中的流量是根据客户的选择 行为变化的，也就是说供应链网络中上下游企业各自的决策互相影响，互相制约， 对其进行研究必须考虑双方的共同行为【1 】。因此采用的分销网络模型是双层1 1 刊或 者是典型的0 1 混合整数规划问题，随着需求点、商品种类和供应点等数量的增加， 待选择的可能组合数按指数上升，用常规方法求解很困难【“。一般来说，双层规划 问题的求解都是非常复杂的，原因之一就是由于双层规划问题是一个n p - h a r d 问 题，b e n a v e d 和b 1 a i r 深入探讨了这一问题，指出：即使是很简单的双层线性规划 2 重庆大学硕士学位论文1 绪论 问题也是n p - h a r d 问题，不存在多项式求解算法。双层规划的非凸性是造成双层规 划问题求解异常复杂的另一重要原因，即使上层问题和下层问题均是凸问题，整 个双层问题仍然为非凸问题的可能性非常大。而双层问题的非凸性表明：即使能找 出双层问题的解，通常也只可能是局部最优解而非全局最优解。而对于实际问题 解决所带来的管理和经济方面的意义是重大的，这激发了许多的学者对这一问题 进行研究【“7 叫“。求解双层规划问题的关键在于找到反应函数的具体形式，由于 智能仿生算法在求解时不依赖于梯度信息，因而特别适用于传统方法解决不了的 大规模n p 问题。本文也是因为蚁群算法不需要求出问题具体的函数形式，而直接 利用启发式因子( p h e r o m o n e ) 来寻找全局最优点这一特征，来从一个新的角度探 讨这选择分销中心和分销点的问题。另外，以上对问题的描述已经指明对分销网 络的优化过程中可能会遇到最优s t e i n e r 问题，通过运用蚁群算法来解决这类n p 问 题，也可以为解决s t e i n e r 树问题提供一种可行的方法。 1 2 研究现状 1 - 2 1 分销网络优化的国外、国内研究现状及研究动向 根据不同的问题采用不同的解决方法，国内和国外在解决网络优化方面的方 法主要有：运筹学、图论理论、智能仿生算法( 包括基因算法、神经网络、遗传 算法、进化规划、禁忌表搜索、蚁群算法、模拟退火算法、d n a 算法等) ，以及 这些算法的混合和结合得到的许多算法。解决分销网络优化设计问题与其他一些 网络优化问题一样，都有共同的特点，只是针对不同的问题模型对相应的算法进 行改进和结合，具体见2 1 、2 2 和2 3 。 1 2 1 1 国外研究进展 人们针对不同的背景、目标和要求对分销配送网络优化设计进行了研究，如 b u m s 等人，简化生产过程，重点研究销售系统，考虑了销售的协调，以降低成本 f 8 l ：c o h e n 等人则提出了一个包括材料控制、生产控制、产成品库存、销售网络 控制的模型框架1 9 。关于求解模型的算法研究，目前为止，尽管发展了许多优化技 术和方法，但随着求解优化问题及模型的不同，采用的优化技术和方法也不同 【伸，1 1 1 ，对于某些较复杂的模型，需要将多种优化技术结合起来使用才能求解 1 “。 m a r t i n r e i k e 等d t 提出了两层控制水分销方法。上层将用户的需求转换为网络 中点的水流量和质量；下层通过反馈控制器得到这些点的数字和类比分析。通过 实验表明这种方法可以较精确的模拟水分销系统。 j o h ngk l i n c e w i c z 等 18 】提出了大规模多点计划模型。该模型通过物流系统随 时间而变化，为了真实的反映实际问题，许多实际的特征也体现在该模型中。 j a ye a r o n s o n 等 ”1 提出前向网络单一算法解决多阶段网络流模型，指出标准 重庆人学硕士学位论文1 绪论 的网络优化编码未能指出问题多阶段的结构，并通过实验表明该方法比标准的网 络优化编码更有效。 m a l a c h y 等 2 0 】建立的多阶段网络模型，并且利用网络本身的结构特点发展了一 种迭代算法来解决模型。 l i l i a ng a o 等2 ”提出通用的模型和二元分支定界方法解决单梯度、两梯度和 多行为定点问题。通过将问题规范化为a r b n e t ( a r b o r e s c e n t f i x e d c h a r g en e t w o r k ) 规划模型，继而求解。并且发展了一种有效的通用的分销系统规划的决策支持系 统。 yk w o n g ，等2 2 1 运用d i j k s t r a 的算法t r a n s p o r t a t i o n 算法来优化分站的大小和 服务领域。并且运用a a c i r ( t h e a v e r a g e a n n u a lc u s t o m e r i n t e r r u p t i o n r a t e ) 作为可 靠性指标给出了可选择的分站。 l u i sc a s t i l l o 等运用遗传算法来寻找最优网络的特征，并给出了针对具体问 题的遗传算予。 s m a t h i e s 等2 4 1 给出了三种方法：一种是基础分割的单一算法，第二种是用在 次梯度优化中采用拉格朗日算子解决对偶问题，最后通过降低约束条件采用纯嘲 络的算法。 d a v i dk s m i t h 等【2 5 1 运用基于遗传算法的进化方法来解决无向网络中寻最优 树的问题。 m a k a s h e m 等【2 q 提出了系统的支流结构变形技术来发展了一种开关设计来 最小化分销网络中的损失。在3 3 公共汽车系统中进行测试，并且与b a r a na n dw u 的算法( b a r a nm e ，w uf f n e t w o r kr e c o n f i g u r a t i o ni nd i s t r i b u t i o ns y s t e m sf o rl o s s r e d u c t i o n a n d l o a d b a l a n c i n g i e e e t r a n s p o w e r d e l i v e r y ，1 9 8 9 ；4 ( 2 ) ：1 4 0 1 1 4 0 7 ) 进行了比较。 1 2 1 2 国内研究进展 会海和等【7 1 在考虑需求分配的情况下，提出了分销配送网络的优化模型。为 了求解优化模型，提出了基于混合遗传算法求解混合0 1 整数规划问题的算法，它 是用遗传算法搜索0 1 变量的最优解，将单纯形法融入遗传算法中，对非0 1 变量进 行求解的种算法。最后通过两个算例进行了仿真实验，验证了优化模型的难确 性和算法的有效性。模型简明、客观，算法易于扩展并具有鲁棒性、通用性。 赵晓煜和汪定伟f 3 j 1 提出了供应链中二级分销网络优化设计的模糊机会约束规 划模型。模型中将各个需求地对产品的需求量以及各分厂的生产能力等难于确定 的参数看成是模糊参数，并进一步讨论了如何将模型中的机会约束清晰化。还讨 论了采用启发式算法同分枝定界法相结合以提高问题的求解速度。 常良峰等 1 3 , 2 7 1 改进了成本模型，并考虑了间接投资成本分摊，以顾客订货量中 4 重庆入学硕士学位论文1 绪论 可调整部分为决策变量，建立了分销商的利润优化模型，采用进化规划算法，并 进行仿真分机。 孙会君和高自友从供应链集成的角度出发，利用双层规划模型描述了二级分 销网络优化问题，充分考虑了网络决策部门及客户双方的自身及共同利益。同时 设计了启发式求解算法，最后用简单算例验证了模型及其算法的有效性。 文献 2 1 将货点和订货量作为决策变量，就分销系统的分布式库存订货问题进行 分析，提出了一种比较实用的自适应g a 方法，在可行域范围进行较全面的搜索。 文献1 4 1 从理论上讨论分销系统协调调度与控制的可行性：文献”l 采用模拟退 火算法确定订货点和订货量，这种方法搜索范围大，但精确性不高；文献u 6 是在 先确定订货点和安全库存的情况下采用g a 方法和随机模拟方法确定订货量，搜索 精度高，但搜索范围受到了限定。 高峻峻等【2 8 提出一种分销系统的最小成本模型，运用该模型研究两个制造商 两个分销商组成的分销网络成本优化问题，把分销商满足市场需求时的服务水平 作为优化问题的约束条件。综合考虑库存成本、订货成本、运输成本和缺货成本， 给出了求解满足约束的最优订货量的算法。 杨呖等【2 9 1 根据a t m 网络承载业务的特性，提出了以最小化全网平均信元丢失 率为e t 标函数，以途径交换节点数目为约束的优化路由准则，并应用进化规划方 法求解此优化问题。 液压集成块孔道网络优化设计问题属于组合优化的n p 问题，长期以来没有得 到良好的解决田树军等f 3 0 】该问题的数学优化模型，提出对布线顺序的处理策略， 采用模拟退火算法实现了自动寻优的液压集成块孑l 道网络连通设计，并在工程实 际中得到验证。 童小娇等【3 1 一类非线性网络优化问题提出了信赖域算法，在一般条件下，证 明了由算法产生的序列的任一聚点均为问题的k u l m t u c k e r 点的全局收敛结果。 1 2 2 蚁群算法的国外、国内研究现状及研究动向 关于蚁群算法的研究从最初诞生到至今，其研究主要针对以下几个方面： 1 )蚁群算法自身算法的改进：最优参数的寻找、算法结构改进以避免出现停 滞、模型的改进，从最初只能解决离散问题到连续性问题的解决等； 2 )蚁群算法与其他启发式算法的结合； 3 )蚁群算法基础上建立的新算法； 4 )蚁群算法应用于不同的工程和实践领域以及随之建立的相关的算法、与其 他启发式算法和传统算法在具体应用中的实验验证与比较。 具体介绍见1 2 2 ，1 和1 2 2 ，2 。 重庆大学硕士学位论文 1 绪论 1 2 2 1 国外研究进展 c o l o m i 3 2 , 3 3 1 两篇关于a c o 的最早的出版物，第一篇介绍了a c o 并描述了3 种a c o ( 蚁周模型、蚁密模型和蚁量模型) 用于t s p ，蚁周模型作为最优解决3 0 城市和很好解决5 0 和7 5 城市的算法。第二篇为先前的蚁周模型考查了 3 3 1 相应的 参数设置，经验计算复杂性和解决t s p 的结果的质量分析。 关于t s p 的更全面的阐述来自于d o r i g o 3 4 】，除了重述早期工作之外，还将蚁 周算法与禁忌表搜索( t s ) 和模拟退火( s a ) 进行比较。另外，还将a c o 用于非对 称t s p 、二次指派问题和车间调度问题。 d o r i g o 和g a m b a r d e l l a 3 5 1 为t s p 和非对称t s p 建立了蚁群算法。蚁群算法结 合了详尽的搜索和蚂蚁的路径选择机制，强调蚁群的更关注于最好解的搜索并且 修改信息素。通过修改他们的算法，在许多大型非对称t s p 问题中获得最好的解。 s c h o o n d e r w o e r d i ” 等将a c o 用于电路转换通信网络的静态路由( 负荷平衡) 。 他们的a c o 优于早期的多代理方法( m u l t i a g e n ta p p r o a c h 3 7 1 ) 和改进变量的多代理 方法。 d ic a r o 和d o d g o 3 8 , 3 9 1 将a c o 用于包转换网络的动态路由中。实验结果表明 蚁群算法在平均网络延迟方面比互联网和文献已有的算法更好，特别是在运输条 件困难的时候。另外，文章还说明了健壮的行为总是能快速达到好的稳定的效果。 o l i v e rb r u n 和j e a n m a r i eg a r c ia 删提出一种新的方法来进行通信网中带宽的分 配，最短路路由是传统的解决该类问题的方法，但是这会导致差的网络效果。新 的算法通过两步：第一步，相应的负荷分配问题通过非线性规划技术最优化解决， 然后，一种基于蚁群算法的启发式算法用于得到最初问题的可行的解。 g r i s e l d an a v a r r ov a r e l a 和m a r kc s i n c l a i r l 4 1 1 提出了三种变量：局部更新，全局 更新距离，全局更新占有。三种扩展了通常蚂蚁只被自己群体的信息素吸引的通 常做法，还加入了人工蚁同样排斥其他蚂蚁的信息素。并且指出，全局更新占有 这种方式在小型和巾型的网络中具有优势。 t h o m a ss t f i t z l e 和h o l g e rh h o o s 【4 2 1 提出了一种源于蚁群系统的蚁群优化算法 m m a s 系统。m m a s 与蚁群系统在几个重要的方面不相同，我们通过实例验 证其有用性。另外，阐述了m m a s 的具体的特征之一是利用一种比蚁群系统更贪 婪的搜索，通过组合优化问题的分析来搜索解空间。在t s p 和q a r 上的计算结果表 明，m m a s 是目前解决该类问题的最好的算法。 l mg a m b a r d e l l a 、e dt a i l l a r d 和md o r i g o 4 3 将混合蚁群算法和局部搜索算法 用于二次指派问题，称为h a s q a p ( ah y b r i da n tc o l o n ys y s t e mc o u p l e dw i t ha l o c a l s e a r c h a p p l i e dt ot h eq u a d r a t i ca s s i g n m e n tp r o b l e m ) 7 1 i 像传统的蚁群算法用信息迹的 信息构造全部的解，h a s q a p 用信息迹的信息对q a p 的解进行修改。h a s q a p 与 6 重庆大学硕士学位论文 1 绪论 其他一些能最好的解决q a p 的算法进行分析和比较：两种版本的列表搜索( 也就 是r o b u s t 和r e a c t i v e 列表搜索算法) 、混合遗传算法和模拟退火算法。实验结果显示， h a s q a p 和混合遗传算法由于它们发现好的解的结构的能力，在真实世界、不规 则和结构化的问题中表现得最好。而对于随机、规则和非结构化的问题，h a s q a p 则表现较差。 1 2 2 2 国内研究进展 蚁群算法是一种新型的随机优化算法。蚁群算法与其它随机优化算法同样存 在收敛速度慢易于限于局部最小点等缺陷。王颖等【“】提出一种自适应的蚁群算法 以克服上述缺陷。通过自适应地改变算法的挥发度等系数，算法可以在保证收敛 速度的条件下提高解的全局性，通过对t s p 问题的仿真证明该算法相对与原始的 蚁群算法收敛速度和解的性能都有一定的提高。另外王颖等| 45 提出一种改进的蚁 群算法，并将其与启发式方法相结合以解决多点路由问题中出现的s t e i n e r 树问题。 仿真证明，基于改进蚁群算法的多点路由算法模型可以稳定地获得优于现有启发 式算法的解，是一种有效的多点路由算法，同时该算法也适用于并行执行和应用。 改进的蚁群算法能稳定地得到优于k m b 算法f 4 6 】的解，是种有效的、具有实际意 义的多点路由算法。 香港大学的k w a n g m o n gs i m 和w e n g h o n g s u n 【47 j 提出了多蚁群算法( m u l t i p l e a n t - c o l o n y o p t i m i z a t i o n ，m a c o ) 用于网络路由，并且与传统的路由方法在多个方 面作出比较，指出该方法的特征，优点和在网络路由中的应用。 中国台湾的c h e n g f at s a i 8 8 等提出一种用于大型数据库的有效的聚类方法， 模拟结果表明新的方法( a n tc o l o n yo p t i m i z a t i o nw i t hd i f f e r e n tf a v o ra l g o f i t h m ) 比快 速自组织地图与k 均值方法的组合( f a s ts e l f - o r g a n i z i n gm a p ( s o m ) c o m b i n e s k - m e a n sa p p r o a c hf f s o m + k - m e a n s ) ) 、遗传的k 均值算法( g e n e t i c k - m e a n sa l g o r i t h m ( g k a ) ) 效果更好。另外，在他们所有的研究中，他们的算法l ? , f s o m + k - m e a n s 和g k a 产生的错误更少。 庄吕文【4 9 等基于蚁群的协同工作机制，提出了一种其内涵扩充了的增强蚁群 算法o a c s ) 。利用此新算法设计了一个开关盒( s w i t c h b o x ) 布线程序，并用j a v a 语 言加以实现。针对几个算例计算的结果，证明该程序可获得比w e a v e r 、m i g h t y 、 b e a v e r 、g a p 基准例低的计算复杂度。 为了克服蚁群算法中计算时间较长的缺点，吴庆洪等 5o 】给出一种新的蚁群算 法具有变异特征的蚁群算法。在基本蚁群算法中引入变异机制，充分利用了 2 交换法简洁高效的特点，使得该方法具有较快的收敛速度，节省计算时间。计算 机仿真结果表明该方法是行之有效的。 陈烨1 5 1 】针对蚁群算法搜索速度慢，且容易陷入局部最优。该文针对的问题提 重庆大学硕士学位论文1 绪论 出了一种改进算法。该算法通过引入遗传算法中用到的杂交算子来改善蚁群算法， 使其对应的问题的解更加优良。用改进算法求解的结果表明改进算法足有效的。 郝晋等【5 5 4 l 设计出一种新颖的随机扰动蚁群算法，并将其应用于求解复杂 t s p 问题。该算法包含了两个重要方面：一是提出了采用倒指数曲线来描述的扰 动因子：二是设计出了相应的随机选择策略和扰动策略。数值模拟表明：该算法 可以有效地克服基本蚁群算法的计算时间较长和容易出现停滞现象的缺陷，具有 更好的全局搜索能力。此外，还对该算法中参数的取值范围及选取方法进行了研 究和探讨。 张宗永等 5 5 】在介绍蚁群算法解决旅行商( t s p ) i h 题的模型上：，对蚁群算法做了 相应的改进。配合随机分布技术，以上海市整个内河航道和集装箱运输为研究对 象，对内河航道进行规划，得出上海市内河集装箱集散系统合理的分配方案，并 提出为满足该合理系统所须进行的相应的河道改造。 工件排序问题中如何使加工效率最高，一直是一个非常重要而且又非常困难 的问题。特别是问题的规模很大时，目前各种算法计算就非常困难，有的甚至无 法得到合理的方案。陈义保等 5 6 1 根据工件排序问题的特点，建立了在不同种类的 并行机上加工一批不同种类工件的优化数学模型。在蚁群算法的基础上对其进行 了改进，成功地把改进的蚁群算法用于工件排序问题的优化中。通过与其他算法 的仿真比较，表明基于蚁群系统的算法是有效的，特别是问题规模很大时更显示 其较快的收敛速度和较高的精度。 李勇等【57 提出了一种动态蚁群算法并用于解决t s p 问题。该文对蚁群算法的 改进主要在以下三个方面：( 1 ) 动态目标城市选择：( 2 ) 信息素挥发系数动态变化； ( 3 ) 最差路线上的信息素弱化；实验表明改进后的算法比基本蚁群算法及改进的 蚁群算法m m a s ( m a x m i n a n ts y s t e m ) 总体性能有了一定的改善。 针对蚁群算法不太适合求解连续性优化问题的缺陷，陈峻等 5 即提出用蚁群算 法求解连续空间优化问题的一种方法。该方法将解空间划分成若干子域，在蚁群 算法的每一次迭代中，首先根据信息量求出解所在子域，然后在该子域内已有的 解中确定解的具体值。以非线性规划问题为例所进行的计算结果表明。该算法比 使用模拟退火算法和遗传算法具有更好的收敛速度。 魏平等 59 利用蚁群算法求解一般函数优化，通过实验收到良好的效果。 林锦等【删对混合蚁群算法做适当改进，用于解凸整数规划问题。结果表明：用 该算法求目标函数为正定二次型的整数规划问题的最小值，找到的解比多起始点 局部搜索方法好得多，比原来的混合蚁群算法找到更好的解。 高尚等【6 1 1 提出了基于蚁群算法思想的求解算法，并与网格法作了比较。数值 试验计算结果表明该方法比较有效，并具有通用性。 重庆大学硕士学位论文1 绪论 1 2 3 蚁群算法及其在分销网络优化中的应用研究进展2 j 白蚁群算法提出以来，就以t s p 为测试基准，取得巨大的成功。随后在二次分 配问题( q a p ) 、工件排序问题、车辆调度问题等方面也表现出了相当好的性能。 蚁群算法在最优树问题上表现出独特特性，如管道铺设、电路设计、通信系统、 计算机网络等问题，蚁群算法表现出了极好的优化思想。我国学者马良等人采用 一种融合局部搜索机制的策略，对中国1 4 4 城市t s p 求解结果为3 0 3 5 1 ( 最优解 3 0 3 4 7 ) ，优于近几年公布的用模拟退火算法和遗传算法得到的结果。 在最近的文献中，蚁群算法还未在分销网络中有应用，因此，本文选择这个 方向，方面扩展蚁群算法的应用范围，研究蚁群算法在该领域中应用时应考虑 的些问题和对问题的特征进行描述；另一方面对分销网络的优化方法进行探讨， 以为后面的研究提供一种新的思路。表1 1 总结了近年来蚁群算法及其网络优化应 用中研究成果。 表1 1 蚁群算法及其网络优化应用中研究成果 研究 研究者算法命名时间 问题 d o r i g o ，m a n i e z z o ，c o l o m i a s1 9 9 1 旅行商问 g a m b a r d e l l aa n dd o r i g o a n t - q ，a c sa n da c s - 3 - o p t 1 9 9 5 一1 9 9 8 题( t s p ) s t i z l ea n dh o o sm m a s1 9 9 6 b u l l n h e i m e ra n dh a r t la s r a n k1 9 9 7 马良中国1 4 4 城市t s p 1 9 9 9 分配问题m a n i e z z o ，c o l o m i ，d o r i g oa s q a p ，a n t s - q a p ，a s q a p1 9 9 4 ，1 9 9 8 ，1 9 9 9 ( q a p )g a m b a r d e l l a ，t a i l l a r d ，d o r i g oh a s q a p b 1 9 9 7 s f i z l ea n dh o o s m m a s - q a p 1 9 9 7 m a n i e z z o ，c a r b o n a r o a n t s f a p1 9 9 8 r a m a l h i n h o ，l o u r e n c o ，s e r r a m m a s g a p1 9 9 8 t a x i ，r o u x ，f o n l u p t ，r o b i l l a r d p a c2 0 0 l 调度问题 c o l o m i ，d o f i g o ， m a n i e z z oa s j s p1 9 9 4 ( s p ) s t i z l ea s f s p 1 9 9 7 b a u e re ta la c s s m t t p1 9 9 9 d e n b e s t e n ，d o f i g o ，m a n i e z z o a c s s m t w