（管理科学与工程专业论文）应用蚁群算法进行物流配送路线优化研究.pdf

摘要 在物流诸多环节中，配送占有重要的地位。企业不仅通过该环节来实现利润， 而且通过该环节与客户直接打交道。电子商务的兴起和互联网的快速发展，使物 流配送形式趋于多元化，即小批量、多批次的货物配送开始出现，并占据了重要 的位置。配送质量的好坏，直接影响到企业的利润、形象，以及客户的满意度等。 在实际中，影响配送质量的因素很多，如配送调度货物的制定，配送路线的制定， 货物是否按时到达，货物数量是否正确等等。 物流配送路线优化问题，是配送过程中最重要的问题之。配送路线寻优通 常以最短路为基础，辅之以时间为约束条件。k i n g 等人研究表明，现实配送中距 离的6 和时间的1 2 被浪费了【l 】。尽管影响物流配送问题的因素很多，但本文主 要从“送”的角度出发，针对物流配送问题中配送路线的选择进行分析研究，考 虑实际中可能出现的约束条件：时间约束和节点约束，建立与实际配送相符合的 数学模型，将定性问题转化为定量问题。 蚁群算法是一种新必的启发式算法。它具有正反馈、并行计算、较强的鲁棒 性等诸多特点，在很多领域有着广泛的应用。利用蚁群算法对物流配送优化问题 进行求解，是本文的重点研究问题之一。通过对蚁群算法中各参数的实际意义以 及参数改进方面进行的研究，对蚁群算法的参数选择方面进行了改进，使其更能 适应实际的需要，在此基础上提出了一种基于蚁群算法的满足约束条件的物流配 送路线优化问题的解决方案。 在模型验证章节，具体解决了体现约束条件的道路节点设计问题。从仿真结 果可以看出，该算法能够在一定约束条件下，找到一条满足约束条件的优化路径， 避免了实际中司机寻找最优路径的盲目性，为物流企业的配送环节提供了参考， 具有一定的实践指导意义。 关键词：物流配送；优化；蚁群算法 a n tc o l o n ya l g o r i t h ma p p l i e st ot h eo p t i m i z a t i o no f l o g i s t i c s d i s t r i b u t i o nr o u t i n ep r o b l e m a b s t r a c t i nt h ef a c e t so f l o g i s t i c s ，d i s t r i b u t i o no c c u p i e st h ei m p o r t a n tp o s i t i o n t h eb u s i n e s s e n t e r p r i s e sn o to n l ym a k ep r o f i t sb yt h i sf a c e tb u ta l s ot o u c hw i t ht h ec u s t o m e rd i r e c t l y t h r o u g ht h i sf a c e t t h er i s eo ft h ee l e c t r o n i cc o m m e r c ea n dt h ef a s td e v e l o p m e n to ft h e i m e m e tm a k el o g i s t i cd i s t r i b u t i o ni n c l i n et ot h ed i v e r s i f i c a t i o n ，n a m e l ys m a l lb a t c h q u a n t i t ya n dm a n yb a t c hb e g i n st oa p p e a ri nt h ed i s t r i b u t i o no fg o o d s t h eq u a l i t yo f t h ed i s t r i b u t i o n ，w i l la f f e c tt h ep r o f i t s ，f i g u r e so ft h eb u s i n e s se n t e r p r i s e sd i r e c t l y ，a n d t h ec u s t o m e r s s a t i s f a c t i o ne t c a c t u a l l y ，t h e r ea r es om a n yf a c t o r sw h i c hw i l li n f l u e n c e t h ed i s t r i b u t i o n ，s u c ha st h ee s t a b l i s h m e n to f t h ed i s t r i b u t i o np l a n s ，t h ee s t a b l i s h m e n to f t h er o u t i n e ，g o o d sw h e t h e ra r r i v eo nt i m e ，g o o d sq u a n t i t yw h e t h e re x a c t i t u d ea n ds oo n t h ep m b l e mo fo p t i m i z i n gl o g i s t i c sd i s t r i b u t i o nr o u t i n ei so n eo ft h em o s t i m p o r t a n tp r o b l e m si nt h ed i s t r i b u t i o np r o c e s s e s e x p l o r i n gt h ed i s t r i b u t i o nr o u t i n e a l w a y sb a s e so nt h es h o r tp a t ha s s i s t i n gt i m ea st h er e s t r i c t i o nc o n d i t i o n s 飚n ge t c m a k et h er e s e a r c he x p r e s st h a t6 o ft h ed i s t r i b u t i o nd i s t a n c ea n d12 o ft h et i m e h a v eb e e nl o s t 【”t h e ma r el o t so ff a c t o r sw h i c hi n f l u e n c et h ep r o b l e m ，t h i sp a p e r m a i n l yd i s c u s s e sf r o mt h ea n g l eo f “s e n d ”a i m i n ga to p t i m i z a t i o n 也ec h o i c eo ft h e d i s t r i b u t i o nr o u t i n e ，a n a l y s i ss o m ef a c t o r sw h i c hr e l a t et ot h ep r o b l e m ，t h i sp a p e r e s t a b l i s h e st h em a t h e m a t i c sm o d e lw h i c hm a t c h e st h ef a c ta n dc o n v e r t st h eq u a l i t a t i v e p r o b l e mi n t oq u a n t i t a t i v ep r o b l e m a n tc o l o n yo p t i m i z a t i o n ( a c o ) a l g o r i t h mi san e wh e u r i s t i cs o l u t i o nt ot h e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m o w i n gt oi t sp o s i t i v ef e e d b a c ka n de f f e c t i v e p a r a l l e l i z a t i o na n ds t r o n gl u s t i n e s s ，a c oh a sb e e na p p l i e di nm a n yf i e l d s i ti st h ep o i n t m s e a r c hp r o b l e m so ft h i sp a p e rt h a ta p p l y i n ga n tc o l o n ya l g o r i t h mt os o l v et h e o p t i m i z a t i o no fl o g i s t i c sd i s t r i b u t i o nr o u t i n ep r o b l e m r e s e a r c h i n go f a c t u a lm e a n i n go f t h ep a r a m e t e r si nt h ea n tc o l o n ys y s t e ma n dt h ei m p r o v e m e n to ft h ep a r a m e t e r s ，w e p r o p o s et h es o l u t i o no f t h el o g i s t i c sd i s t r i b u t i o np r o b l e mb a s eo n a n tc o l o n ya l g o r i t h m a tl a s t ，w ev e r i f yt h ea c c u r a c yb yt h es y s t e ms i m u l a t i o n t h er e s u l to ft h e s i m u l a t i o ns h o w st h a tt h i sa l g o r i t h mc a nf i n da no p t i m i z e dr o u t i n eu n d e rt h er e s t r i c t i o n c o n d i t i o n s ，a v o i du n r e a s o n a b l er o u t i n ef o rd r i v e r sa n dp r o v i d es o m es u g g e s t i o n st o k e yw o r d ：d i s t r i b u t i o nr o u t i n e ；o p t i m i z a t i o n ；a n tc o l o n ya l g o r i t h m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士硕士学位论文 ：厘旦蝗登簋鎏进短堑逋配送监缮馑丝婴窟：。除论 文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经 公开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：王侄越 p o 二年j 月歹日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于： 保密口 不保密口( 请在以上方框内打“”) 论文作者签名：至镳超 导师签名：影久望兰 日期：棚辟3 月歹日 第1 章绪论 1 1 课题背景 配送是物流中的一个重要的、直接与消费者相连的环节。配送一般定义为： 将货物从物流结点送到收货人的过程。配送是在集货、配货的基础上，完全按客 户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配” 和“送”的有机结合形式。 当前物流配送模式正在从少品种、大批量向多品种、小批量转变。传统配送 主要是为企业间交易服务的，配送的对象主要是生产资料。由于生产资料品种规 格单一，需求量大，配送过程基本不需分拣、配货环节，多采用少品种、大批量 的配送模式。在如今，网络化的商务模式使企业间及企业与消费者之间的交易都 更加活跃，一方面，在电子商务环境下，消费者对生活资料需求居多，它成为电 子商务下物流配送的主流。生活资料的需求由于品种规格繁多，每次需求量小， 用户多，故要求多品种、小批量、多批次的配送。另一方面，零售商通过网络， 订货作业变得简单、快捷，成本降低，因此趋于小批量、多批次订货，以实现自 身零库存，增强市场应变能力。因此，配送模式在向小批量、多批次配送方式转 变。 物流配送主要受到三个方面的影响：一是“配”方面的因素影响，如难以制 定配送计划：二是“送”方匿的影响，如难以选择配送路线，难以按时交货，配 送绩效评价基准不明确，司机工作时间不定。易疲劳以及货品在运送过程中的遗 失和损坏等；三是社会方面的影响，如客户的分布区域、道路交通网络、车辆通 行限制、送达时闻要求等。 物流配送车辆的路线优化，是物流配送优化中的一个关键环节。正确合理地 安排车辆的配送线路，可以有效的减少车辆的空驶率，有效的增加车辆的利用率 实现合理线路运输，从而降低运输成本节约运输时间，提高客户服务水平，提 高经济效益，达到科学化的物流管理。 本文基于上述背景，通过运用物流配送相关理论，并结合物流配送实际情况， 针对当前具有多频次、小批量、多品种的城市物流配送问题，在“送”的环节上 深入研究，期望在配送路径优化方谣有所改进，从而对企业物流配送提供有价值 的参考。 1 2 物流配送路线优化研究意义 当前物流业正向全球化、信息化、一体化发展，配送在供应链中的作用显得 更加重要。由于现代配送具有多频次、小批量、多品种、高效率的特点，配送要 准确做到7 r ( r i g h tp r o d u c t ，r i g h tq u a l i t y ，r i g h tt i m e ，r i g h tp l a c e ，r i g h tc o n d i t i o n ， r i g h tc u s t o m e r 。r i g h tc o s t ) ，因此设计合理、有效的车辆运输路线方案，尽量减少配 送里程数和配送时间不仅可以减少资源浪费，提高企业的经济效益和竞争力，而且 可以更好地为客户服务，维护企业良好的形象。我国物流的现状，大部分配送中 心还处于手工配货阶段，司机往往是自己决定配送路线，运输路线的选择因而具 有一定的盲目性。 物流业从最实际的角度出发，就是要完成两大目标：( 1 ) 降低成本；( 2 ) 满足 客户需求。换句话说，就是在满足某些“约束条件”的基础上实现“最节约成本” 的配送方案。物流业的最主要成本投入有两大块：一是前期投入，建立仓库、配 送中心，安排配送工具，如卡车；二是实际运行中的管理和配送消耗。因此物流 配送的一个重要目标就是在满足客户需求( 一般是时间) 的前提下，投入最少的 配送成本( 主要是各种运输线路上的损耗) 。在网络化的今天，由于信息流通便捷， 各部门协同工作的能力越来越强，实现诸如“熬合运输”，“最低库存”，“快速反 应”的客观条件越来越现实。 因此，如何充分利用现有条件，达到物流配送的最小成本消耗已经成为一个 越来越受重视的问题。特别当传统配送模式向小批量、多批次的配送模式转变时， 更使得原来的单线的，仓库_ 单个客户一 仓库的配送模式被完全推翻，取而代之 的是每个运输单位运输不同的货物到不同的客户手中，也就是仓库一 多个客户一 仓库的配送模式；而不是像往常那样，每个配送单位分配给单个客户，把货物运 到客户手中就立即返回，造成路程上的大量浪费。因此一般的配送路线优化问题 的描述为：如何选择最优配送路线，使得投入的运输成本最低，又能满足客户的 需求。实际上，由于客户数目的巨大，这一问题的可行解数目非常巨大，甚至不 可能用类似于枚举法的方法在能够接受的时间范围内得到最优解或者较优解：并 且客观约束条件复杂而繁多，因此该问题已经成为一个公认的物流难题。 1 3 物流配送路线优化研究现状 对于配送问题的研究，一是“配”方面的研究，如配送中心选址问题，二是 “送”方面的研究，如旅行商问题( t s p ) 、车辆路线优化问题( v p r ) 。在本文中主 要讨论“送”方面的研究现状。 旅行商问题是一个典型的组合优化问题，并且是一个n p 难问题，其可能的 路径数目与城市数目n 是成指数型增长的，所以一般很难精确地求出其最优解。 目前，对t s p 问题的研究主要是通过一些启发式算法，如遗传算法、禁忌搜索算 法、模拟退火算法、蚁群算法等，都取得了一定的成果。由于它的模型比较简单， 约束条件比较少，通常在应用某一算法时，都以它来做模型，因此对该问题研究 已十分成熟，不再赘述。 国外对车辆路线优化问题作了大量而深入的研究，将此问题归结为或称之为 v e h i c l e r o u t m g p r o b l e m s 和v e h i c l e s c h e d u l i n g p r o b l e m 。该问题一般定义为：对一系 列装货点和( 或) 卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足 一定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程 限制、时间限制等) 下，达到一定的目标( 如路程短、费用最少、时间尽量少、使 用车辆数尽量少等) 。 大多数的物流配送运输调度闯题可以归结为配送车辆的分配、行车路线的组 织问题( v r p 问题) ，即根据不同要求一目标函数( 例如运距最短、配送时间最短、 运输费用最少等) ，将配送运输过程归结为表述问题的数学模型。然后用计算机求 得合理可行的优化方案，在生产中付诸实施。v r p 问题或者称作车辆路径问题是组 合优化领域中著名的n p 难题。近二十年来，无论在国内还是国外，v r p 问题都是 一个非常活跃的研究领域。表1 1 是目前已经开发并应用实践的配送车辆调度系 统。 表1 1 国外的配送调度算法具体应用 t a b 1 1a p p l i c a t i o no f f o r e i g nd i s t r i b u t i o na l g o r i t h m l 系统名称开发者运用算法 v s p x 美国i b m 启发式算法 v s s 日本富士遥节约法 l h p c a d 美国美孚扫描法 1 4 本文研究内容 作者参阅国内外大量v r p 方面的研究资料，得出如下结论，对v r p 求解往往 是建立如下几个条件来进行优化的：( 1 ) 种货物( 4 ) 单车型( 5 ) 时间约束窗等， 车辆非满载( 2 ) 单物流中心( 3 ) 单品 从上述条件可以看出，该问题对单辆车 寻求最优路径考虑不多。此外，v r p 的优化求解往往采用遗传算法和某些启发式算 法结合的方式。 本文将从不同的视角来研究物流配送路线优化问题：一是物流配送问题本身， 主要研究集中在“送”的环节上，即分析如何实现快速、有效的配送路线方案， 不再将“配”与“送”相结合进行讨论t 二是研究在一定的约束条件下如何应 用蚁群算法解决物流配送路线优化问题，尝试将蚁群算法应用到新的领域。 在物流配送问题上，分析了物流现有的配送模式，以及配送中心的作用，在 “送”的环节上存在哪些因素的影响，以及如何来如何解决这些因素的影响；在 应用蚁群算法问题上，研究蚁群算法各参数对路径搜索的影响，如何建立节点的 数据结构，如何设立实际约束条件，如何改进算法性能，并对其运行的效率和结 果进行比较分析：最后，通过系统仿真来验证蚁群算法的优化结果。 本论文从实际角度出发，拟通过分析现有配送模型，改善原有蚁群算法性能， 使之在物流配送路线优化问题的应用上取得了理想的实验结果，为解决物流配送 路线优化问题提供新的手段。 1 5 本文组织结构 本文章节及内容的安排如下： 第一章绪论 概述本文研究背景和意义、国内外研究现状以及本文主要研究问题和主要研 究内容。 第二章物流配送路线优化模型研究 结合目前配送具体实际情况，研究我国物流企业配送模式、物流配送中心作 用。研究物流配送过程中存在的制约因索，以及建立配送路线模型。 第三章应用蚁群算法进行配送路线优化的实现 概述蚁群算法的基本思想、算法流程及其特点。通过实验分析。提出了解决 概述蚁群算法的基本思想、算法流程及其特点。通过实验分析，提出了解决 1 4 本文研究内容 作者参阅国内外大量v r p 方面的研究资料，得出如下结论，对v r p 求解往往 是建立如下几个条件来进行优化的：( 1 ) 车辆非满载( 2 ) 单物流中心( 3 ) 单品 种货物( 4 ) 单车型( 5 ) 时间约束窗等，从上述条件可以看出，该问题对单辆车 寻求最优路径考虑不多。此外，v r p 的优化求解往往采用遗传算法和某些启发式算 法结合的方式。 本文将从不同的视角来研究物流配送路线优化问题：一是物流配送问题本身， 主要研究集中在“送”的环节上，即分析如何实现快速、有效的配送路线方案， 不再将“配”与“送”相结合进行讨论；二是研究在一定的约束条件下，如何应 用蚁群算法解决物流配送路线优化问题，尝试将蚁群算法应用到新的领域。 在物流配送问题上，分析了物流现有的配送模式，以及配送中心的作用，在 “送”的环节上存在哪些因素的影响，以及如何来如何解决这些因素的影响；在 应用蚁群算法问题上，研究蚁群算法各参数对路径搜索的影响，如何建立节点的 数据结构。如何设立实际约束条件，如何改进算法性能，并对其运行的效率和结 果进行比较分析；最后，通过系统仿真，来验证蚁群算法的优化结果。 本论文从实际角度出发，拟通过分析现有配送模型，改善原有蚁群算法性能， 使之在物流配送路线优化问题的应用上取得了理想的实验结果，为解决物流配送 路线优化问题提供新的手段。 1 5 本文组织结构 本文章节及内容的安排如下： 第一章绪论 概述本文研究背景和意义、国内外研究现状以及本文主要研究问题和主要研 究内容。 第二章物流配送路线优化模型研究 结合目前配送具体实际情况，研究我国物流企业配送模式、物流配送中心作 用。研究物流配送过程中存在的制约因索，以及建立配送路线模型。 第三章应用蚁群算法进行配送路线优化的实现 概述蚁群算法的基本思想、算法流程及其特点。通过实验分析，提出了解决 4 物流配送路线优化问题的蚁群算法描述和实际解决方案。 第四章仿真试验与结果分析 设计应用蚁群算法、满足实际需要的配送路线仿真系统，并对仿真结果进行 分析，以及将蚁群算法与其他优化算法的e 较。 第五章总结 总结本文的主要工作和难点以及对未来工作的展望。 第2 章物流配送路线优化模型研究 本章首先简单地介绍了物流配送的含义，对当前的配送模式和配送发展趋势 进行了阐述和分析。在此基础上，根据物流配送实际中的一些影响因素，提出了 与本文有关的物流配送路线模型的目标以及相关约束条件。 2 1 物流配送模式 2 1 1 物流配送简述 “配送”一词来源于英文的“d e l i v e r y ”，我国使用的“配送”一词原本是日 语中的两个汉字的直译，1 9 7 9 年介绍到我国，1 9 8 5 年引起关注，并很快受到了广 泛的重视。 物流与配送是息息相关的。配送是供应链的一部分( 如图2 1 所示) ，是拣选、 包装、加工、组配、配备、配置、送货等各种物流活动的有机结合。 固 abc d e 制供配分用 造应送销户 商商 中 商 心 图2 1 物流配送供需链 f i g 2 1s u p p l ya n dd e m a n dc h a i no f l o g i s t i c sd i s t r i b u t i o n 从物流来讲，配送几乎包括了所有的物流功能要素，是物流的一个缩影或在 某小范围中物流全部活动的体现。一般的配送集装卸、包装、保管、运输于一身， 通过这一系列活动完成将货物送达的目的。特殊的配送则还要以加工活动为支撑， 所以包括的方面更广。但是，配送的主体活动与一般物流却有不同，一般物流是 运输及保管，而配送则是运输及分拣配货，分拣配货是配送的独特要求，也是配 送中有特点的活动，以送货为目的的运输则是最后实现配送的主要手段，从这一 主要手段出发来看，常常将配送简化地看成运输中的一种。 从商流来讲，配送和物流不同之处在于，物流是商物分离的产物而配送则是 6 商物合一的产物，配送本身就是一种商业形式。虽然配送具体实施时，也有以商 物分离形式实现的，但从配送的发展趋势看，商流与物流越来越紧密的结合，是 配送成功的重要保障。可以从两个方面认识配送的概念： 从经济学资源配置的角度来看，对配送在社会再生产过程中的位置和配送的 本质行为可以表述为：配送是以现代送货形式实现资源的最终配置的经济活动。 从配送的实施形态角度来看，配送是按用户定货要求，在配送中心或其它物 流结点进行货物配备，并以最合理方式送交用户。 总之，配送是一项特殊的、综合性的物流运动，其运行和发展有着深刻的社 会根源和历史背景。在市场经济体系中，物流配送如同人体的血管，把国民经济 各个部分紧密地联系在一起。配送是物流中一个重要的直接与消费者相联的环节， 是将货物从物流结点送达收货人的过程，是在集货、配货基础上，完全按用户要 求( 包括种类、品种搭配、数量、时间) 等方面的要求所进行的运送，是“配” 和“送”的有机结合形式。其主要包括集货作业、配货作业、车载货物的配装、 配送路线的确定等。 2 1 2 物流配送模式 图2 , 2 为社会物流全过程示意图。从该图可以看出，社会物流中物流中心到各 个生产企业称为集货配送；物流中心到各个配送中心、配送中心到用户( 包括经 销商、超市、用户等) 称为末端运输即配送；物流基地和物流基地、物流基地和 物流中心之间的物流传送称为干线运输或者支线运输： 分销卜配送 集货配送干线运输支线运输末端运输 图2 2 社会物流全过程 f i g 2 2f u l lp r o c e d u r eo f s o c i a ll o g i s t i c s 上图中的干线输送和支线输送强调的是一次性到达、大批量的、少批次的， 任务量不是单个车辆可以承担的；末端输送即配送强调的是多次到达、小批量、 多批次的；集货配送中，由于生产企业的规模和客户的需求璧的不同，所以社会 物流中出现的配送模式应该是干线运输一次性、大批量模式和多次性、小批量模 式的结合。所以从这个角度看一般配送存在两种模式，一种是直达型，另一种则 是转运型。两者是相辅相成，缺一不可的。配送的出现是对整个输送环节的完善， 是对整个物流过程的完善。 结合我国物流发展的现状，主要呈现4 种配送模式。一是自营配送模式，某 些大型生产企业和连锁经营企业创建自营配送中心完全是为本企业的生产经营提 供配送服务；二是合作配送模式，指若干相关联或相类似的企业由于共同的物流 需求，在充分发掘利用各企业现有物流资源基础上，联合创建的配送组织形式； 三是市场配送模式，指以专业化的物流配送中心和社会化配送中心。通过为一定 市场范围的企业提供物流配送服务而获取盈利和自我发展的物流配送组织形式。 四是综合配送模式，指企业以供应链为指导思想，全面系统地优化和整合企业内 部物流资源、物流业务流程和管理流程，对生产过程的各种环节实现全方位综合 3 配送，充分提高产品制造过程的时空效应，从而形成高效运行的物流配送模式。 前面提到，末端运输即配送强调多批次、小批量，即我们所要研究的配送模 式，我们看到，配送中心在这里起到了承上启下的作用，客户的需求往往是通过 配送中心来实现的。运输车辆从配送中心出发，最终回到配送中心，因此，在配 送路线优化问题中，配送中心也是一个需要考虑的因素。特别是处理排队问题时 ( 如客户对时间有要求) ，更要考虑配送中心与客户的距离。另外，与t s p 问题不 同的是，开始节点和终止节点都为配送中心，即配送中心是一个特殊的节点。这 一问题的解决方案将在后面“物流配送路线优化的蚁群算法描述”中叙述。 2 1 3 物流配送发展趋势 ( 1 ) 电子商务为传统的物流配送观念带来深刻的革命 传统的物流配送企业需要置备大面积的仓库，而电子商务系统网络化的虚拟 企业将散置在各地的分属不同所有者的仓库通过网络系统连接起来，使之成为“虚 拟仓库”，进行统一管理和调配使用，服务半径和货物集散空间都放大了。这样的 企业在组织资源的速度、规模、效率和资源的合理配置方面都是传统的物流配送 所不可比拟的，相应的物流观念也必须是全新的。 ( 2 ) 网络对物流配送的实时控制代替了传统的物流配送管理程序 一个先进系统的使用，会给一个企业带来全新的管理方法。传统的物流配送 过程是由多个业务流程组成的，受人为因素影响和时间影响很大。网络的应用可 以实现整个过程的实时监控和实时决策。新型的物流配送的业务流程全部由网络 系统连接，当系统的任何一个神经末端收到一个需求信息的时候，该系统都可以 在极短的时间内做出反应，并可以拟定详细的配送计划，通知各环节开始工作。 这一切工作都是由计算机根据人们事先设计好的程序自动完成的。 ( 3 ) 物流配送的完成时间在网络环境下会大大缩短 在传统的物流配送管理中，由于信息交流的限制，完成一个配送过程的时间 比较长，但这个时间随着网络系统的介入会变得越来越短，任何一个有关配送的 信息和资源都会通过网络管理在几秒钟内传到有关环节，从而对物流配送速度提 出了更高的要求。 ( 4 ) 网络系统的介入简化了物流配送过程 9 传统物流配送整个环节极为烦琐，随着物流配送业的普及和发展。行业竞争 的范围和残酷性大大增加，信息的掌握、信息的有效传播和其易得性，使得用传 统的方法获得超额利润的时间和数量会越来越少。在网络化的新型物流配送中心 里计算机系统管理可以使整个物流配送管理过程变得简单。在网络支持下的成组 技术可以在网络环境下更加淋漓尽致地被使用，物流配送周期会缩短，其组织方 式也会发生变化。网络上的营业推广可以使用户购物和交易过程变得更有效率、 费用更低，从而可以提高物流配送企业的竞争力。 ( 5 ) 物流配送模式从少品种、大批量向多品种、小批量转变 传统配送主要是为企业间交易服务的，配送的对象主要是生产资料，生活资 料占的比例相对较少。由于生产资料品种规格单一，需求量大，配送过程基本不 需分拣、配货环节，多采用少品种、大批量的配送模式。随着电予商务的到来， 网络化的商务模式使企业间及企业与消费者之间的交易都更加活跃，一方面，对 消费者网上购物订购的商品要进行配送，加之商业连锁经营的发展，商业企业与 生产企业间电子商务的开展，生活资料的配送量增多，成为电子商务下物流配送 的主流。生活资料需求具有的特点，品种规格繁多，每次需求量小，用户多，故 要求多品种、小批量、多批次的配送。另一方面，企业间由于通过电子商务进行 交易，订货作业变得简单、快捷，成本降低，因此趋于小批量、多批次订货，以 实现自身零库存，增强市场应变能力。因此，生产资料配送也向小批量、多批次 配送方式转化。 当前物流配送的发展趋势，既是受外界因素影响的结果，也是物流业自身功 能不断完善的结果。物流配送方式的不断细化，为物流方面的研究提供了更多的 课题。 2 2 物流配送路线约束条件 前面提到，现代配送是近距离，小批量，品种比较复杂，按用户需要搭配品 种与数量的服务体系。从配送中心把货物送到所需的各个用户，有很多种不同的 路线选择方案。合理地选择配送路线，对企业和社会都具有很重要的意义。 对企业而言：( 1 ) 优化配送路线，可以提高配送效率，对配送车辆做到物尽其 用，尽可能的降低配送成本。( 2 ) 可以准时、快速地把货物送到客户的手中，能极 1 0 大地提高客户满意度。( 3 ) 有利于企业提高效益。 对社会而言，它可以节省运输车辆，缓解交通紧张状况，减少噪声、尾气排 放等运输污染，为保护生态平衡、创造美好家园做出贡献。 进行配送路线优化时，必须有明确的目标，遵循基本的原则。配送路线方案 目标的选择可以从以下几个方面来考虑： ( 1 ) 配送效益最高或配送成本最低。效益是企业追求的主要目标，可以简化为 用利润来表示，或以利润最大化作为目标；成本对企业效益有直接的影响，选择 成本最低作为目标值与前者有着直接的联系。当有关数据容易得到和容易计算时， 就可以用利润最大或成本最低作为目标值。 ( 2 ) 配送里程最短。如果配送成本与配送里程相关性较强，而和其他因素相关 性较弱时，配送里程最短的实质就是配送成本最低。则可考虑用配送里程最短作 为目标值，这样就可以大大简化线路选择和车辆调度方法。当配送成本不能通过 里程来反映时，如道路收费、道路运行条件严重的影响成本，单以最短路程作为 目标就不适宜。 ( 3 ) 配送服务水准最优。如准时配送要求成为第一位时，或需要牺牲成本来确 保服务水准时，则应该在成本不失控的情况下，以服务水准为首选目标。这种成 本的损失可能从其它方面弥补回来，如优质服务可以采取较高的价格策略。 ( 4 ) 配送劳动的消耗最小。即以物化劳动和活劳动消耗最小为目标，在许多情 况下，如劳动力紧张、燃料紧张、车辆及设备较为紧张的情况下，限制了配送作 业的选择范围，就可以考虑以配送所需的劳动力、车辆或其它有关资源作为目标 值。 配送路线方案的目标实际上可以是多元的，但考虑到制定方案所选择的目标 值应当容易计算，一般要尽可能选择单化的目标值，这样容易求解，实用性较 强。 配送路线方案目标的实现过程受到很多约束条件的限制，因而必须在满足约 束条件的限制下取得成本最低、或路线最短、或消耗最小等目标。其中常见的约 束有：( 1 ) 收货人对货物品种、规格和数量的要求：( 2 ) 收货人对货物送达时间或时 间范围的要求；( 3 ) 道路运行条件对配送的制约，如单行道、城区部分道路对货车 通行的限制；( 4 ) 车辆最大装载能力的限制；( 5 ) 车辆最大行驶里程数的限制：( 6 ) n 机的最长工作时阅的限制：( 7 ) 各种运输规章的限制等等。 2 3 物流配送路线模型 当在建立系统模型的时候，上一节已经提到了有许多因素( 或参数) 需要考 虑。但为了简化问题，提出以下假设： ( 1 ) 配送中心的个数( 发车点的个数) ：是一个配送中心还是多个配送中心。 前面已经提到了配送中心，我们所研究的问题是关于城市物流配送，一个城 市中一般只有一个配送中心，这样就可以把问题简化了。因此，可以假设一个配 送中心对应多个用户需求，并且配送中心之间是相互独立的，于是就不存在多个 配送中心货物重叠问题。 第一个假设：一个配送中心。 ( 2 ) 配送车辆规模：一辆车还是多辆车。 一般情况下，配送中心的配送车队往往拥有多辆汽车，但我们所研究的问题 集中在“送”货方面，由于问题局限于“小批量、多批次”的配送，那么，可以 假设一辆汽车可以满足个用户的需求。这样，可以考虑研究一辆汽车的配送路 线优化问题，从这一角度来看，它与v r p 问题有着明显的不同。 第二个假设：一辆汽车的配送路线优化。 ( 3 ) 道路性质：无向还是有向。 实际上，配送线路会受到道路是否为单行线所影响，即受运输网络是否为对 称为所影响：另外，道路的路况好坏，都会影响配送的效果。 第三个假设：运输网络为有向网络，并且路况好坏通过该路段权值反映出来。 ( 4 ) 运输车辆载重量限制 这是一个比较复杂的问题。从企业经济效益角度出发，希望最大限度的利用 车辆使用效率，但车辆有最大载重量，很明显这是一个矛盾。在实际中，车辆超 载现象十分普遍。因此，为了简化问题，暂时不考虑车辆载重量问题。 第四个假设：不考虑车辆载重量。 ( 5 ) 其他的假设： 假设货物在运输途中是不会变质损坏的，不考虑货物回收需求，不考虑司机 的工作时间，不考虑车辆每次最大行驶里程，不考虑运输时的规章制度等。 1 2 通过上面的假设分析，可以建立如下的模型： 基本条件：在某配送中心有一辆配好货物待出发的汽车，它需要给n 个客 户运送货物，顾客为嵋，u ：，屿，d 。，并且源点和客户的坐标已知。 模型目标：在满足约束条件的情况下，得到一个最优的回路； 约束条件： ( 1 ) 车辆完成任务之后要回到源点。 ( 2 ) 运输两节点间为不对称路径，即a 点到b 点与b 点到a 点所付出代价不 一定相等，并且节点问不是任意可达的。 ( 3 ) 客户对时间方面有要求，配送的货物应该及时地送到。 需要说明的是，该模型与v r p 模型非常相似，实际上，它是v r p 模型的一个 子问题，是对v r p 问题的简化，但是从“送”的角度来看，却比其研究得更深入 一些。v r p 问题一般的求解目标为使用最少的车辆来实现物流配送的优化，首先 往往要考虑车辆的载重量和货物的重量，每辆车配贷的选择，将直接影响车辆的 配送路径，以至于影响到最终的结果，因此v r p 问题只要确定了车辆的配货，就 可以认为确定了其行驶路线，但实际上车辆配货十分复杂，并不是货物只要满足 了车辆的载重量限制这么简单，很少有文献在解决v 】冲问题时考虑了这一点。另 外，v r p 问题中每辆车对应豹节点比较少，其优化效果一般；如果节点较多，那 么其局部路径优化性能就很差了。本文只讨论一辆车的配送路线，实际上是假设 了一辆车的载重量无限大，以至于个客户的需求都可以满足，因此不需要考虑 配货问题；从另一角度来看，本文所研究的内容实际是v r p 问题的局部路径优化 问题。如果要解决上述提到的v r p 问题时，可以令每一辆车负责地图上的一个区 域，那么辆车就可以负责整个地图区域，则又回到了本文即将讨论的问题上来 了。下一章我们将具体阐述如何应用蚁群算法对物流配送优化问题进行求解。 第3 章应用蚁群算法进行配送路线优化的实现 本章具体介绍了一种启发式算法：蚁群算法。通过对蚁群算法中参数的分析、 试验，讨论了蚁群算法在物流配送路线优化问题上的改进。根据上章建立的物 流配送优化模型，提出了应用蚁群算法来解决物流配送路线问题的方案。 3 1 蚁群算法 在2 0 世纪9 0 年代，意大利学者m d o r i g o ，v m a n i e z z a o ，a c o l o m i 等人从生 物进化的机理中受到启发，通过模拟自然界蚂蚁寻食的行为，提出了一种全新的 模拟进化算法：蚁群优化算法a c o a ( a n tc o l o n yo p t i m i z a t i o n a l g o r i t h m ) ，并用该 方法求解了t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 、j s p ( j o b s h o ps c h e d u l i r t gp r o b l e m ) 和 q a p ( q u a d r a t i ca s s i g n m e n tp r o b l e m ) 等问题，取得了一系列较好的实验结果。蚁群 优化算法就是对自然界中蚂蚁的寻食过程进行模拟而得出的一种模拟进化算法。 下面将介绍蚁群优化算法的基本原理。 3 。1 1 蚁群算法起源 蚂蚁是一种群居昆虫，单个蚂蚁的行为极其简单，但由这样的单个简单的个 体所组成的蚂蚁群体却表现出极其复杂的行为，能够完成复杂的任务。不仅如此 蚂蚁还能够适应环境的变化，如：在蚁群运动路线上突然出现障碍物时，蚂蚁能够 很快地重新找到最优路径。经过大量研究发现，蚁群之所以表现出复杂有序的行 为，是因为个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中， 能够在它所经过的路径上留下一种称之为信息素( p h e r o m o n e ) 的物质，而且蚂蚁在 运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂 蚁倾向于朝着该物质强度高的方向移动。蚂蚁个体之间就是通过这种信息的交流 达到搜索食物的目的。 图3 1 中n 表示蚁巢，f 表示食物所在位置，b d 为障碍物，设d 和a ，d 和c 之间的距离均为2 个单位，a 与b ，b 与c 之间的距离均为1 个单位，在一个时间 单元内有3 0 只蚂蚁由n 到达a 点，同样有3 0 只蚂蚁由f 到d 点，蚂蚁的运动速 度是2 单位距离单位时间，每只蚂蚁在其走过的路径上留下一个单位的信息量。 假设初始时刻t ：0 时各条路径均无蚂蚁走过，位于a 和c 点的各3 0 只蚂蚁选择所 走路线的概率是相同的，按照统计规律，可知有1 5 只蚂蚁选择a d ( c d ) ，另外1 5 只蚂蚁选择a b ( c b ) 。由于d a d = d d c = 2 d a b = 2 d b c ，所有经过1 个单位时间后，走过 路径a b 和b c 的蚂蚁个数是走过路径a d 和d c 蚂蚁个数的两倍。这些蚂蚁留在路 径上的信息量前者也是后者的两倍。在，= l 时，新的3 0 只蚂蚁位于a 点和c 点， 根据信息量的多少，它们选择路径a b ( c b ) 的概率是选择a d ( c d ) 的两倍，即：有2 0 只蚂蚁选择前者，只有l o 只蚂蚁选择后者。这一过程一直继续下去，最终所有的 蚂蚁都将选择由蚁巢到食物的最短路径。 d n ( e 吼) - 弋 d _ 2 1 l 脚 f ( f o o d ) 图3 ，1 蚁群搜索食物路线示意图 f i g 3 1s k e t c hm a po f a n tf i n d i n gf o o dr o u t i n e 让人工蚂蚁根据路径上的相当于p h e r o m o n e 的数字信息索的大小( 即强度) 选 择路径，并在所经过的路径上留下相当于p h e r o m o n e 的数字信息素，然后随着时 间的推移，最优路径上的数字信息素就会越来越大，从而选择它的概率也就越来 越大，最终所有的人工蚂蚁都将选择这条路径。即蚂蚁通过个体之间的信息交流 与相互协作最终找到从蚁穴到食物源的最短路径。 3 1 2 蚁群算法的系统模型 我们将选取t s p