（管理科学与工程专业论文）基于蚁群算法的粮食加工企业物流配送路径优化研究.pdf

武汉科技大学硕士学位论文第1 页 摘要 我国是一个农业大国，粮食产业是我国农业中具有巨大潜力的一大产业。与粮食生产 息息相关的粮食加工业是促进粮食增值和社会经济发展的重要途径。而物流配送作为粮食 加工企业提高经济效益和服务水平的重要环节，正越来越受到人们的重视。物流配送车辆 的路径优化是物流配送中的一个关键环节。设计合理的车辆运输路线方案，尽量减少配送 里程数和配送时间，可以有效地减少车辆的空驶率和增加车辆的利用率，降低运输成本， 节约运输时间，提高客户服务水平，提高经济效益和维护企业良好的形象。 基于此，作者以粮食加工企业的物流配送路径优化问题为研究对象，在分析粮食物流 的特点及粮食配送现状的基础上，建立了粮食加工企业物流配送路径优化问题的基于直观 描述的数学模型，该模型考虑了较为接近实际的约束条件，具有简单、直观、易于理解、 易于求解及可扩充性强等优点。并通过对蚁群算法的研究学习，设计并实现了求解粮食加 工企业物流配送路径优化问题模型的蚁群算法。然后对b 市米业公司的物流配送路径优化 问题进行实证分析，在概述该公司基本情况和物流配送中存在的主要问题的基础上，通过 实地考察、调查走访、网上收集等方法收集和整理了该公司的客户位置、需求量以及时间 窗等数据，对于配送中心与客户、客户与客户之间的距离运用灵图电子地图u u 3 1 软件中 的驾驶导航功能计算出实际道路和桥梁分布情况下的客户之间以及客户与配送中心之间 的最短距离，而不是简单的求两者之间的直线距离。并应用蚁群算法对模型进行求解，得 出了一套路径优化的方案。最后论文在理论研究和实证分析的基础上，提出了b 市米业公 司物流配送路径优化问题的建议。 关键词：粮食物流；物流配送；路径优化；蚁群算法 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t c h i n ai sac o u n t r yb a s e do nt h ea g r i c u l t u r a la n dg r a i ni n d u s t r yi sap r o m i s i n gi n d u s t r y g r a i ni n d u s t r yi sc l o s e l yr e l a t e dt ot h eg r a i np r o c e s s i n gi n d u s t r y , w h i c hi st h ei m p o r t a n tw a yt o p r o m o t es o c i o - e c o n o m i cd e v e l o p m e n ta n dg r a i nv a l u e a d d e d a n dt h el o g i s t i c sa n dd i s t r i b u t i o n i st h ei m p o r t a n tp a r tf o rg r a i np r o c e s s i n ge n t e r p r i s e st oi m p r o v ee c o n o m i ce f f i c i e n c ya n d s e r v i c el e v e l s ，w h i c hh a sb e e np a i dm o r ea n dm o r ea t t e n t i o n t h ed i s t r i b u t i o nr o u t e o p t i m i z a t i o ni st h ek e yl i n ki nl o g i s t i c sa n dd i s t r i b u t i o n w e l l d e s i g n e dp r o g r a mo fv e h i c l e t r a n s p o r t a t i o nr o u t e sw i l lm i n i m i z ed i s t a n c ea n dd e l i v e r yt i m e ，c a ni n c r e a s et h er a t eo fv e h i c l e u t i l i z a t i o ne f f e c t i v e l y , r e d u c et r a n s p o r t a t i o nc o s t s ，s a v et r a n s p o r t a t i o nt i m ea n di m p r o v e c u s t o m e rs e r v i c el e v e l sa n de n h a n c ee c o n o m i ce f f i c i e n c ya n dm a i n t a i nag o o dc o r p o r a t ei m a g e b a s e do nt h i s ，t h ea u t h o rm a k e st h er o u t eo p t i m i z a t i o np r o b l c r no fl o g i s t i c sa n d d i s t r i b u t i o ni n g r a i np r o c e s s i n ge n t e r p r i s e a st h er e s e a r c h o b j e c t b ya n a l y z i n gt h e c h a r a c t e r i s t i c so f 向o dl o g i s t i c sa n df o o dd i s t r i b u t i o n , t h ea u t h o re s t a b l i s h e sam a t h e m a t i c a l m o d e lf o rt h er o u t eo p t i m i z a t i o np r o b l e mo fl o g i s t i c sa n dd i s t r i b u t i o ni ng r a i np r o c e s s i n g e n t e r p r i s ew h i c hi sd e s c r i b e db ym a t h e m a t i c a lm o d e l sb a s e do ni n t u i t i v e t h em o d e lc o n s i d e r s m o r er e a l i s t i cc o n s t r a i n t sa n dh a sm a n ya d v a n t a g e ss u c ha ss i m p l e ，i n t u i t i v e ，e a s yt ou n d e r s t a n d a n ds oo n t h r o u g ht h es t u d yo fa n tc o l o n ya l g o r i t h m ，t h ea u t h o rd e s i g n sa n di m p l e m e n t st h e a l g o r i t h mf o rs o l v i n gt h ep r o b l e m t h e nt h ea u t h o rm a k e sap o s i t i v ea n a l y s i so nr o u t e o p t i m i z a t i o np r o b l e mo fl o g i s t i c sa n dd i s t r i b u t i o n i ng r a i np r o d u c t i o nc o m p a n yi nbc i t y , i n t r o d u c e st h eb a s i cs i t u a t i o no ft h ec o m p a n y , c o l l e c t st h ep o s i t i o no fc u s t o m e r sa n dt h e d i s t a n c eb e t w e e nt w oc u s t o m e r s ，a sw e l la st h et i m ew i n d o w s f o rt h ed i s t a n c eb e t w e e nt w o c u s t o m e r s ，a u t h o ru s e so fe l e c t r o n i cm a pu u 3 1t oc a l c u l a t et h ea c t u a ld i s t r i b u t i o nb a s e do n r o a d sa n db r i d g e s ，r a t h e rt h a ns i m p l ys e e k i n gs t r a i g h t - l i n ed i s t a n c eb e t w e e nt h e m f i n a l l y a p p l i e sa n tc o l o n ya l g o r i t h mt os o l v et h em o d e l ，a n do b t a i n sa s e to fr o u t eo p t i m i z a t i o np r o g r a m , a n d p r o p o s e ss o m em e a s u r e sf o r t h ec o m p a n yl a s t l y k e yw o r d s ：g r a i nl o g i s t i c ；l o g i s t i c sa n dd i s t r i b u t i o n ；r o u t eo 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 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下。独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外。本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体。均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：金垦旄日期：冶望应o -论文作者签名：乃汆侈耽日期：加吖应 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定。 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对外服务。 论文作者签名：分昌旁色 指导教师签名：璺它些量 e t 期：霉：! 兰：垒 武汉科技大学硕士学位论文第1 页 1 1 研究背景与意义 第一章绪论 近年来，“三农 问题一直是我们国家工作的重心。2 0 0 9 年中央财政拟投入7 1 6 1 亿 元于三农问题，比上年同期增加1 2 0 6 亿元，中央对加强三农工作也进行了全面部署【l 】。 国内外的成功经验表明，走农业产业化道路是解决“三农 问题、建设社会主义新农村的 有效途径。而发展农产品加工业是农业产业化经营的重要一环，依托农产品加工龙头企业 带动一片、搞活一方，进而促进社会经济的全面发展和人们生活水平的根本提高。农产品 加工业正在成为农村经济发展新的增长点和新兴的战略产业。此外，农产品加工与物流协 同发展能有效地提高与实现农产品价值、降低农产品流通成本、解决农户单个家庭小生产 和社会大市场的矛盾，是加快地方农业经济发展的重要战略举措【2 】。商品化加工可以大大 提高农产品的附加值，高效率的流通是实现农产品价值的必然途径。以物流保证商流，促 进商流，带动生产是现代农业经济发展的必然选择。 粮食是国家重要的战略物资，直接关系到国民经济的运行和发展。粮食也是广大农民 的重要收入来源。进入2 l 世纪以来，与粮食生产息息相关的粮食加工业也发生了巨大的变 化，经济效益大幅增长、技术水平明显改善、生产效率大大提高，取得了令人瞩目的成绩。 粮食加工业的繁荣在很大程度上得益于中国城镇化的加速，未来很长一段时间，只要城镇 化加速不变，粮食加工业前景将依然看好。但是，我们也应该看到我国粮食加工业存在的 问题与潜伏的危机。2 0 0 8 年，全国大部分地区的水稻出现了滞销的现象。水稻的滞销根源 在于稻强米弱。2 0 0 8 年早籼稻收购的价格在短时间内从每斤0 8 元上涨n 1 元，同一时期内 大米的价格从每斤1 1 元上涨到每斤1 2 元，大米上涨幅度低于稻谷的上调幅度，意味着大 米加工企业利润空间缩小，部分小型大米加工企业出现零利润甚至亏损，不少企业处于停 产或者半停产状态【3 】。因此，不少粮食加工企业将目光转向降低物流成本上，物流是“第 三方利润源泉，降低物流成本能增加企业利润，进而提高企业的生产积极性，解决水稻 滞销问题。物流配送车辆的路径优化，是物流中的一个关键环节。但是，大部分粮食加工 企业的配送还处于手工配货阶段，司机往往是自己决定配送路线，运输路线的选择因而具 有一定的盲目性。设计合理的车辆运输路线方案，尽量减少配送里程数和配送时间，可以 有效地减少车辆的空驶率和增加车辆的利用率，降低运输成本，节约运输时间，提高客户 服务水平，提高经济效益和维护企业良好的形象。 蚁群算法是9 0 年代初由意大利学者 1 1 d o r i g o 提出，并被成功地应用于求解著名的 n p h a r d 问题旅行商问题。目前蚁群算法在各领域都得到了广泛的应用。蚁群算法是 模拟真实蚁群行为而提出的，由其基本原理可知，蚁群算法具有正反馈、分布式计算等特 点，其正反馈过程使得算法能够发现较好解，分布式计算使该算法易于并行实现。这些特 点为更好地解决复杂的组合优化问题提供了可能。除了其上述的优越性外，对于求解路径 优化问题，蚁群算法还有如下两个优点：蚁群算法是一种在图中搜索的启发式算法，而路 第2 页武汉科技大学硕士学位论文 径优化问题很容易用图表示；蚁群算法的搜索机制使得算法能够较容易地满足路径优化问 题复杂的约束条件，从而获得可行解【4 1 。 基于此，本文以粮食物流路径优化问题为研究对象，选择蚁群算法对路径优化问题进 行求解，希望对企业物流配送提供有价值的参考。 1 2 国内外研究现状 在粮食物流、车辆路径问题、蚁群算法及将蚁群算法应用于粮食物流路径优化等方面， 国内外不少学者从不同角度作了不同程度的研究，且取得了不少成果。 1 2 1 粮食物流的研究现状 2 0 世纪8 0 年代，物流概念传入中国，经过几十年的发展物流业进入快速发展期，并 与快速消费品、电子、汽车、家电等诸多行业结合，发展势头良好，但物流与粮食行业结 合并得到重视却是近几年的事。尽管如此，国内学者对粮食物流也作了不少研究，主要集 中在以下几个方面。 ( 1 ) 对粮食物流内涵的界定。目前学者们主要是从粮食物流的功能环节出发来定义粮 食物流，强调各环节的有机结合和实体流动基础上的有效管理、协调和控制，但是学者们 对于是否将粮食生产纳入粮食物流环节这一问题存在争议。候立军等认为粮食物流是指粮 食从生产、收购、储存、运输、加工到销售服务的整个过程中的实体运动以及在流通环节 中的一切增值活动，是包含粮食运输、仓储、装卸、包装、配送、加工和信息应用的一条 完整的环节链【5 】。王遐见认为粮食物流就是根据不同需求，选择最佳的运输工具和运输路 线组合进行粮食实体移动，以达到最佳的经济效益和社会效益的活动【6 】。笔者认为，应该 将粮食生产纳入粮食物流，因为粮食物流是一条完整的环节链，粮食生产也包括其中。 ( 2 ) 对粮食物流成本的研究。目前对粮食物流成本的研究并不多见，更多的是对粮食 流通成本进行分析研究。翁鸣和陈劲松认为在我国的粮食价格成本构成中，生产成本在总 成本中的比重最大，流通成本所占总成本比重次之，但流通费用越来越成为影响农产品价 格和竞争力的一个较为重要的因素r 7 1 。卜轶彪对我国小麦流通成本做了分析，认为小麦流 通成本包括收购环节成本、储存环节成本、加工环节成本、运输环节成本和销售环节成本。 此外，要降低粮食运输成本就要努力做到同一品种粮食就近取粮、就近供应来满足不同消 费者，使粮食从产地沿着最短路径运输，避免对流【8 】。马志强提出要通过优化资源配置来 降低粮食流通成本，认为粮食流通资源必须是市场导向下的优化配置【9 】。 ( 3 ) 农产品加工方面的研究。目前学者在农产品加工方面的研究主要是对政策、加工 技术和加工增值途径的研究。倪锦丽指出吉林省在确保国家粮食安全的前提下，应不断深 化粮食加工产业的发展，大型粮食加工企业要走精深加工之路，中小企业要加强联动，打 造产业集群，另外，应提高农业科研机构和企业的自主创新能力，重点扶持生物质能源的 发展【i o l 。程力指出作为粮食主产区，应结合本地区实际，制定粮食加工业发展规划，突出 对重点领域、区域和企业的扶持，突出推进粮食加工业集聚，加强粮食加工业政策的导向 武汉科技大学硕士学位论文第3 页 研究，制定相关的粮食加工业政策【1 1 1 。总之，要把握好这个历史与现实的机遇，进一步拓 宽发展思路，以推动粮食加工业又好又快发展。刘奇洪指出在城市化加速和经济全球化形 势下，粮食加工企业既面临千载难逢的机遇，又面临粮食价格变动越来越大的风险。针对 粮食加工企业存在的各种问题，提出了可供粮食加工企业选择的战略方向【1 2 1 。万忠民指出 粮食加工作为粮食物流的重要组成部分，是产后粮食管理的重要一环，是粮食物流增值的 有效途径。作者还从粮食加工的各个环节，如推广优良品种、改进加工工艺、提高粮食品 质、开展粮食深度加工等方面出发，围绕增值的目标分析了粮食加工实现粮食转化增值的 主要途径【1 3 】。 i 2 2 车辆路径问题的研究现状 车辆路径问题最早是由d a n t z i n g 和于r a m s e r 于1 9 5 9 年提出的，由于该问题将运筹学理 论应用于企业物流活动，自提出后便引起各学科专家和管理者的重视，成为运筹学和组合 优化领域的前沿和热点问题【1 4 】。作为一个组合优化的热点问题，国内外学者对其作了大量 而深入的研究，应用了很多算法进行求解，总结起来，这些算法大体上可以分为两类：精 确算法和启发式算法。 精确算法主要有：动态规划算法、分支定界法、割平面法、网络流算法等，但精确算 法只能有效地求解小规模的车辆路径问题。龚国清采用分支定界法对旋转货架的存取路径 优化，有效解决了旋转货架在面对多品种多储位存取时的存取路径优化问题，可大大提高 存取效率，节约劳动力和存取时间【i5 1 。e i l o n 曾通过递归的形式利用动态规划法求解具有 固定车辆数的车辆路径问题【1 6 】。陶波和朱玉琴针对物流配送中的重点车辆路径的选择 进行了研究，建立了物流配送路径优化问题的数学模型，在动态规划法的基础上进行改进， 改进后的算法能最大限度地提高车辆的装载率，减少运输的车次，在实际运用中取得了良 好的效果【i7 1 。张明善和唐小我探讨了在一般条件下的多车场满载的车辆路径问题，建立了 它的网络流模型，并给出了一种基于该网络流最优解的算法【1 8 】。该算法的一个明显特征是 对每一条行车路线的确定总是基于修改后的网络流模型的最优解，大大提高了算法结果的 优化质量。 启发式算法是指研究人员根据某种启发式的信息，对已知的可行解进行改善，通过若 干次的迭代获得相对满意的解。由于现实中的车辆路径问题规模一般很大，想在能够接受 的运算时间内，找到最优解是不可能的，而启发式算法能够在相对较短的时间内找到满意 解，所以启发式算法在大规模复杂的车辆路径问题上应用十分广泛。管亚丽基于建立一种 多目标物流配送车辆调度模型的基础上，采用d n a 进化算法求解该问题，客服传统算法的 求解速率低、易陷入局部最优的问题，为进一步研究物流配送优化调度问题提供参考【1 9 1 。 齐名军在建立物流配送路径优化问题的数学模型基础上，构造了求解问题的粒子群优化算 法l z u j 。计算结果表明可以有效地求得问题的最优解。肖燕综合我国物流配送的特点，在车 辆类型、车辆载重、客户时间窗等约束条件下，建立多配送中心、多车型的物流配送车辆 优化调度模型，并综合应用启发式算法中的卜w 节约法和精确算法中的动态规划法进行算 第4 页武汉科技大学硕士学位论文 例分析，验证所建模型的正确性 2 1 1 。余碉和胡宏智为提高中小企业在市场中的竞争力，提 出了基于遗传算法的智能化解决方案【2 2 1 。建立了物流配送路径问题的数学模型和求解流 程，论述了基于遗传算法的物流车辆配送系统的设计与实现，详述了基于自然数编码的遗 传算法在物流车辆调度中的运用等关键技术。计算结果表明，用遗传算法进行最短路径优 化，可以方便有效地求得问题的最优解或近似最优解。模拟退火算法是求解车辆路径问题 的有效方法之一，其最初的思想m e t r o p o l i s 在1 9 5 3 年提出，k i r k p a t r i c k 在1 9 8 3 年成功地将 其应用在组合最优化问题中【2 3 1 。李松在对配送路径优化问题进行描述的基础上，建立物流 配送路径优化问题的数学模型，提出了一种求解车辆路径问题的混合禁忌搜索算法【2 4 】。在 该混合算法中，通过车辆任务分配结构的划分，将大规模问题拆分成可并行计算的若 干小规模问题，减少了算法的计算时间。并通过理论分析和仿真算例，证明了该混合禁忌 搜索算法的有效性。 1 2 3 蚁群算法及其在路径优化中的研究现状 继遗传算法、模拟退火算法、禁忌搜索算法等智能算法迅速发展和应用之后，意大利 学者d o r i g o 等人提出了一种新型的启发式算法一蚁群算法。由于蚁群算法具有强鲁棒 性、分布式计算和易于与其他算法相结合的特点，越来越受到人们的关注，目前已被应用 于求解各种复杂的组合优化问题。 l k 1 g a m b a r d e l l a 和m d o i r g o 于1 9 9 6 年提出了一种修正的蚁群算法，他们提出了所谓 的精英策略，以强化精英蚂蚁的影响，结果发现，对精英蚂蚁数而言有一个最优的范围： 低于此范围，增加精英蚂蚁数可较早地发现更好的路径，高于此范围，精英蚂蚁会在搜索 早期迫使寻优过程始终在次优解附近，导致性能变差【2 5 1 。l m g a m b a r d e l l a 和m d o i r g o 在 2 0 0 0 年提出了混合型蚁群算法，在该算法中，经过每次循环蚂蚁建立各自的解，再以各自 的解为起点用某种局部搜索算法求出局部最优解，从而可以迅速提高解的质量【2 6 】。魏平和 熊伟清通过对目标函数的自动适应来调整蚂蚁的路径搜索行为，同时通过路径选择过程中 的多样性来保证得到更多的搜索空间，以快速找到函数的全局最优解，从而提出了一种求 解函数优化的蚁群算法【2 7 】。 在将蚁群算法应用于路径优化问题方面，国内外学者也作了不同程度的研究。1 9 9 9 年 b u l l n h e r m e i 等人首先将蚁群算法应用于求解车辆路径问题中，从而提供了一种解决车辆 路径问题的新思路【2 8 】。m a r c 等人于2 0 0 4 年提出了种质量和求解速度上都有很大提高的算 法d a n t s 算法，它主要是把比较大的问题分解成小块来求解【2 9 1 。b e l l 和j o h n 在2 0 0 4 年 提出了另一种改进的蚁群算法来求解车辆路径问题，其基本思想是在蚁群算法中结合两阶 段交换法和候选城市列表的路径优化策略对车辆路径问题进行联合求解【3 0 】。甄彤等认为粮 食物流过程的调度是一个组合优化问题【3 。他们通过对粮食物流现状的分析，提出了基于 蚁群的物流优化调度算法，实现粮食物流过程中粮食的动态分配，用蚁群共同测试不同的 组合，并选择一个优化的解决方案，采用该方案能够按时运输更多的粮食，同时也使粮食 运输成本降低。研究及模拟实验结果表明蚁群算法在粮食物流过程中具有良好的性能。许 武汉科技大学硕士学位论文第5 页 德刚等人针对粮食物流中的车辆路径优化问题，提出了一种新的更加忠实于真实蚁群信息 系统的蚁群算法，克服了蚂蚁之间协作不足，存在滞后的缺陷，通过旅行商问题与传统蚁 群算法进行仿真对比，证明了算法有效性【3 2 1 。王训斌等人针对物流配送路径优化问题的特 点，分析了基本蚁群算法的不足之处，并对原有蚁群算法进行改进。同时引入“扰动因子 和“奖惩机制，建立数学模型，进而对物流配送车辆路径问题进行了实验仿真【3 3 1 。结果 表明，改进后的蚁群算法提高了全局寻优能力与收敛速度，取得了较好的效果。 1 3 本文的研究方法与思路 本论文在写作的过程中采取的研究方法主要有：文献分析法、统计调研法、运筹优化 建模分析方法、智能优化算法分析等等。 本文共分为六章，具体的章节及内容安排如下： 第一章绪论。概述本文的研究背景和意义、国内外研究现状以及本文的研究方法和 思路。 第二章相关理论基础。介绍粮食物流的概念与特点，物流配送和蚁群算法的理论基 础。 第三章粮食加工企业物流配送路径优化问题的建模。首先对粮食加工企业物流配送 路径优化问题进行问题描述，接着进行目标描述，最后建立基于直观描述的数学模型。 第四章设计求解模型的蚁群算法。设计蚁群算法的有关参数，并设计求解本文中粮 食加工企业物流配送路径优化问题数学模型的蚁群算法。 第五章b 市米业公司物流配送路径优化问题的实证研究。首先介绍b 市米业公司的 基本情况，接着收集整理该公司物流配送的相关数据，并分析该公司物流配送中存在的问 题，接着运用蚁群算法对模型求解，得出一套路径优化方案，最后提出b 市米业公司物流 配送的建议。 第六章总结与展望。总结本文的主要工作和难点以及对未来工作的展望。 第6 页武汉科技大学硕士学位论文 论文的写作思路如图1 1 所示。 l 文献收集整理调查研究 、 一研究多。 上 撰写开题报告 1r 粮食物流、物流配送以及蚁群算法的理 论研究 1r 粮食加工企业物流配送路径优化问题建模 1r 设计求解模型的蚁群算法 1r b 市米业公司物流配送路径优化问题的实 证分析 上 结论与展望 图1 1 论文写作思路 武汉科技大学硕士学位论文第7 页 2 1 粮食物流的概念及特点 2 1 1 粮食物流的概念 第二章相关理论基础 目前，粮食物流的概念有很多，不同的学者从不同的角度给粮食物流下了不同的定 义，有代表性的观点如下： 基于供应链的角度给出的粮食物流的定义有：侯立军认为作为全社会物流的一个 重要组成部分的粮食物流是指粮食从生产、收购、储存、运输、加工到销售服务的整个过 程中的实体运动以及在流通环节中的一切增值活动【3 4 j 。它是涵盖粮食运输、仓储、装卸、 包装、配送、加工和信息应用一条完整的环节链。廖红丰等认为，粮食物流是指粮食 从生产、收购、储存、运输、加工到消费领域的整个流通过程以及其中的一切增值活动， 它涵盖粮食生产布局、品种流向的确定、购销粮食的摆布、粮食实体运动所必须的装卸储 运及加工增值的环节链系绀3 5 】。 从用户的角度出发给出的粮食物流的定义有：朱明德认为粮食现代物流是以国际 化、市场化、产业化为导向，以计算机信息网络技术为手段，来保证粮食“从田地到餐桌 高效率流动，包括粮食收购、运输、装卸、储存、加工、包装、配送、信息管理等在内的 所有的用户服务过程【3 6 】。吴志华等认为粮食现代物流是指粮食从供应地到接收地以及 进口和出口的流动过程中，根据市场需要将粮食收购、集并、储存、运输、流通加工、配 送、信息处理等功能有机结合，通过计划、执行、控制等系统化管理，实现用户要求的全 过程【3 7 1 。 从经济效益的角度出发给出的粮食物流的定义有：王遐见认为粮食物流就是根据不同 需求，选择最佳的运输工具和运输路线组合来进行粮食实体移动，以达到最佳的经济效益 和社会效益的活动【6 】。 比较上述几种观点，我认为侯立军给出的粮食物流的定义能够比较全面的揭示粮食物 流的内涵。所以本文采用他的观点，即粮食物流是指粮食从生产、收购、储存、运输、加 工到销售服务的整个过程中的实体运动以及在流通环节的一切增值活动【蚓。它是涵盖粮食 运输、仓储、装卸、包装、配送、加工和信息应用的一条完整的环节链。 2 1 2 粮食物流的特点 在我国，粮食是人们的生活必需品，是提供维系人们正常生存所需热量的唯一有效途 径，是我国经济正常发展的根基，是我国赖以生存的立国之本。由于粮食具有生产的季节 性和消费的常年性，且粮食商品具有保质期和受保管条件的限制，所以粮食物流与其他商 品物流相比具有其突出的特点。 第8 页武汉科技大学硕士学位论文 ( 1 ) 粮食物流的广泛性 粮食主要包括水稻、大豆、小麦和玉米，是人们的生活必需品。中国是个农业大国， 拥有八亿农民，粮食的产量大，农民生产出来的粮食除了一部分自用以外，大部分都要变 成商品销往全国各地，便形成了巨大的粮食物流量。另外，目前我国的粮食主产区主要集 中在东北地区、黄淮地区和长江中下游地区，而粮食消费相对集中在东南沿海经济发达地 区和京津地区，这种产销格局使得我国的粮食物流具有数量大、范围广等特点。 ( 2 ) 粮食物流的时间性 由于粮食具有保质期和受保管条件的限制，所以粮食商品必须在保质期内及时流通出 去，才能保证其社会价值和经济价值的实现。另外，对于粮食加工企业来说，粮食在企业 内留存的时间较长，库存成本比较大，粮食加工企业必须及时准确地把握不同场所的价格 信息和供求信息，及时地将粮食商品流通出去，才能有效地降低库存成本，提高企业利润。 ( 3 ) 粮食物流的独立性 粮食物流的独立性主要体现在基础设施、仓储条件、技术手段和质量、品质保证等方 面所具有的相对独立的特性。粮食商品的特殊性以及自身的生化特性决定了粮食物流相对 于其他商品物流来说具有更高的技术要求。例如在粮食储存方面，为使粮食的使用价值得 到保证，需采取低温、降水、烘干、除杂、害虫防治等一系列技术措施，这并非是铁路、 交通及其他部门都能做到的。 ( 4 ) 粮食物流的绿色性 随着社会的发展、人们消费水平的提高以及经济全球一体化，食品质量安全问题越来 越受到社会的普遍关注。同时，随着社会文明程度的日益提高，保护环境、实现人与自然 的可持续发展已成为社会经济发展的必然选择。在这些背景下，发展现代粮食物流必须注 重其绿色性，以实现人与自然的和谐发展。 2 2 物流配送及路径优化问题概述 2 2 1 物流配送的概念及分类 物流配送是现代流通业的一种经营方式。物流是指物品从供应地向接收地实体流动 的过程。在物的流动过程中，根据实际需要包括运输、储存、装卸、包装、流通加工、配 送、信息处理等基本功能活动。配送是指在经济合理区域范围内，根据客户要求，对物品 进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动【3 8 1 。物流 与配送关系紧密，在具体活动中往往交结在一起，为此人们习惯把物流配送连在一起表述。 由于物流配送要满足不同的顾客的要求，所以其按照不同的运作特点和方式可以划 分为多种不同的类型。 ( 1 ) 按物流配送的主体分类 自营配送。自营配送是指企业依据自身的情况选择合适的地点建造一个或多个配 送中心，并依靠自己构建的网络体系开展物流配送业务，以实现对企业内部及外部货物配 武汉科技大学硕士学位论文 第9 页 送的模式。 外包配送。外包配送是指企业不建配送中心，而是把自己的配送业务以某种契约 或合同的形式外包给专门从事配送业务的第三方物流配送公司，通过该企业与生产企业建 立广泛的代理或买断关系，而与第三方物流配送公司形成一种相互合作的伙伴关系。 协同配送。协同配送是指把过去按不同货主、不同商品分别进行的配送，改为不 区分货主和商品集中运货的“货物及配送的集约化 ，也就是把货物都装入在同一条路线 运行的车上，用同辆车为更多的顾客送货【3 9 】。 ( 2 ) 按配送商品的种类和数量分类 多品种少批量配送。多品种少批量配送是指根据客户的具体要求，将所需的各种 物品( 每种物品的需要量不大) 配备齐全，凑整装车后由配送中心送达客户的配送模式。这 种配送模式由于伴随多用户、多批次的特点，配送频度往往较高，是一种高技术、高难度 的配送模式，但这种配送方式能够满足顾客的个性化需求，因而得到了许多发达国家的推 出 尔o 少品种大批量配送。少品种大批量配送是指对于企业需要量较大的商品，由于 单独一个品种或几个品种就可达到较大输送量，可使车辆满载实行整车运输而不 需要再与其他商品进行搭配的配送模式。在这种配送模式下，配送中心的内部设置、 组织、计划等工作较为简单，因此配送成本较低。 成套配送。成套配送是指根据企业的生产需要，尤其是装配型企业的生产需要， 把生产每一台( 件) 产品所需要的全部零部件配齐，按照生产节奏定时送达生产企业，生产 企业随即可将此成套零部件送入生产线以装配产品的配送模式。 ( 3 ) 按配送时间及数量分类 定时配送。定时配送指按规定时间和时间间隔进行配送，但配送的品种和数量不 固定的配送模式。在这种配送方式下，顾客可以根据自己的经营情况，按照最理想的时间 进货，也易于安排接货力量。定时配送也有利于配送企业合理安排工作计划和规划运输路 线，还可以对多个客户实行共同配送以减少成本。 定量配送。定量配送指按规定的批量进行配送，但不确定严格的时间，只是规定 在一个指定的时间范围内配送。定量配送由于每次配送的品种、数量固定，备货工作较为 简单；由于配送时间不严格规定，可以将不同客户的货物凑整装车后配送，从而提高车辆 利用率。 定时定量配送。定时定量配送指按照规定的配送时间和配送数量进行配送，兼有 定时、定量两种方式的优点，是一种精密的配送服务方式。但是由于定时定量配送要求有 较高的服务质量水平，组织工作难度很大且成本较高，所以它不是一种普遍适用的配送方 式。 定时定量定点配送。定时定量定点配送是指根据客户要求按规定的时间、规定的 数量、规定的客户收货点进行配送的一种配送方式。这种配送方式有利于保证重点需要和 降低企业库存，主要适用于重点企业和重点项目。 第1 0 页武汉科技大学硕士学位论文 即时配送。即时配送是指完全按照用户突然提出的时间、数量方面的配送要求， 随即进行配送的方式。采用这种方式，客户可以将安全库存降低为零，以即时配送代替安 全库存，实现零库存经营。 2 2 2 路径优化问题概述 路径优化问题是运筹学与物流管理决策的一个重要问题，它的研究重点是如何将车辆 有效的使用并决定其最经济的行驶路线，使商品能在最短的时间内送到顾客手中【删。该问 题一般可描述为对一系列的顾客需求点设计适当的路线，使车辆有序地通过它们，在满足 一定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、 时间限制等) 下，达到一定的优化目标( 如里程最短、费用最少、时间尽量少、车队规模尽 量小、车辆利用率尽量高等) 【4 l 】。另外，路径优化问题一般要满足以下条件： ( 1 ) 每条配送路径上各需求点的需求量之和不超过车辆载重量； ( 2 ) 每条配送路径的长度不超过车辆一次配送的最大行驶距离； ( 3 ) 每个需求点必须满足，且只能由一辆车送货； ( 4 ) 每辆车均从配送中心出发，完成任务后又全部回到配送中心。 以上列出的约束条件只是路径优化问题的一部分，在具体操作时要视具体情况而设定 模型。 路径优化问题图示如图2 1 所示。 图2 1 路径优化问题图示 配送中心 客户 车辆行驶路线 口。 武汉科技大学硕士学位论文 第1 1 页 2 3 蚁群算法概述 2 3 1 蚁群算法的原理 蚁群算法是意大利学者m d o r i g o 等人在2 0 世纪9 0 年代通过模拟自然界中真实蚁群 觅食行为而提出的一种模拟进化算法。蚂蚁是一种群居昆虫，单个蚂蚁的能力和智力非常 简单，但蚂蚁群体却能够完成筑巢、觅食等较复杂的群体活动。蚂蚁基本上是没有视觉的， 但是蚂蚁群体在觅食活动中却能够很容易地找到蚁穴到食物源之间的最短路径【4 2 1 。这是 因为蚂蚁在觅食的过程中，能够在它所经过的路径上留下一种称之为信息素的物质，并且 能够感知这种物质的存在与强度，蚂蚁就是以信息素作为媒介与其它的蚂蚁进行信息沟通 的。一条路径上通过的蚂蚁越多，则留下的信息素越多，从而导致后来蚂蚁选择该条路径 的概率提高，蚂蚁个体之间通过这种信息交流来达到快速搜索食物的目的【4 3 】。蚁群算法 的提出正是借鉴和吸收了蚂蚁种群的这种行为特征。蚂蚁群体的路径搜索原理和机制如图 2 2 所示。 cd 图2 2 蚂蚁群体的路径搜索原理和机制 如图2 2 所示，设a 为巢穴，f 为食物源，c d 为一障碍物，蚂蚁要想从巢穴到达食物 源，或者由食物源返回巢穴，只能由b 或e 绕过障碍物，所以有两条路径a b c - e - f 和 a b d e f 。各点之间的距离为：a b = c b ：c e = e f = 1 ，b d = d e = 2 。蚂蚁在单位时间内可移动一个 单位的距离，在路径上留下的信息素为l 。蚂蚁的数量为4 0 只。 t = o 时，4 0 只蚂蚁从巢穴出发向食物源移动。 t = l 时，4 0 只蚂蚁到达b 点，b c 和即均无信息素存在，所以它们以相同的概率选择 肋和b c 两边，则两边各有2 0 只蚂蚁通过。 t = 4 时，选择b c 边的蚂蚁到达食物源将返回，选择肋边的蚂蚁位于e d 中点。 t = 5 时，两组蚂蚁在e 点相遇，此时c e 和d e 上的信息素数量相同，返回的2 0 只蚂 蚁将有1 0 只选择c e ，1 0 只选择d e 。另外一组蚂蚁继续向食物源移动。 t = 7 时，后一组蚂蚁到达食物源后返回到e 点，此时e c 和e d 上的信息素都为3 0 ，所 第1 2 页武汉科技大学硕士学位论文 以有1 0 只蚂蚁选择e c ，1 0 只蚂蚁选择e d 。 t = 8 时，有1 0 只蚂蚁返回了巢穴，叻中点、e d 中点和c 点各有1 0 只蚂蚁。 t = 9 时，最先回到巢穴的1 0 只蚂蚁又回到b 点，此时b c 上的信息素为4 0 ，而即上 的信息素为3 0 ，因此将有较多的蚂蚁选择b c ，从而增强了该路线的信息素。随着时间的 推移，两条路径上的信息素差距越来越大，直至最终绝大多数蚂蚁都选择了最短的路径， 这样蚁群便找到了由蚁巢到食物源的最短路径。 2 3 2 基本蚁群算法描述 蚁群算法首先成功应用于旅行商问题，下面以旅行商问题为例介绍蚁群算法【蜘。首 先定义如下符号：m ：蚁群中蚂蚁数量；刀：城市的数量；c ：循环次数：虬一：最大 循环次数；d u ：城市f 和城市之间的距离；岛o ) ：f 时刻位于城市珀勺蚂蚁数量；o ) ： f 时刻在路径玎上的信息量：a r ；：蚂蚁后在本次循环中留在路径耖上的信息量：p ；o ) ： 蚂蚁七在f 时刻由位置f 转移到位置j 的概率；r 打：路径( f ，) 的能见度，反映蚂蚁由城市i 转移到城市，的启发程度；口：信息启发式因子；：期望值启发式因子；p ：信息素的 持久性；1 一p ：信息素的衰减度。 初始时刻，设各路径上的信息素都相等，靠( 0 ) = c ( c 是个常数) 。将m 只蚂蚁随机 的放在刀个城市的上。蚂蚁k 在运动过程中，根据各条路径上的信息素的大小以一定的概 率p ；o ) 选择转移方向，p ；o ) 表示为公式2 1 。 p ；o ) = f 孑o ) 叩岁o ) f ：o ) 刁善o ) 8 e a l l o w e d & 0 舯铲半 a l l o w e d t 公式( 2 1 ) 否则 公式( 2 2 ) a l l o w e d 。表示f 时刻蚂蚁七下一步允许选择的城市，在蚁群算法中，人工蚁群具有记 忆功能，已经经过的城市就不再选择。 当蚂蚁k 经过所有的城市之后，按照公式2 3 、公式2 4 、公式2 5 对各路径上的信 息素进行更新： 1 6 f + 1 ) = p x r o ) + f 1 6 f ) 公式( 2 3 ) 武汉科技大学硕士学位论文第1 3 页 a r 扩o ) = o ) 蟛m 公式( 2 4 ) 如果蚂蚁k 在本次循环中经过路径 公式( 2 5 ) 否则 其中q 表示蚂蚁循环一周所释放的总信息量，是一个常数；丘表示第尼只蚂蚁在本 次循环中所走的路径的总长度。 再将m 只蚂蚁随机的放在刀个城市的上，重复上述步骤直至达到最大循环次数或者所 有的蚂蚁最终选择同一条路径，最后输出最短路径。 基本蚁群算法的流程【4 5 】如图2 3 所示。 n 图2 3 基本蚁群算法的流程 n 第1 4 页武汉科技大学硕士学位论文 3 1 问题描述 第三章粮食，j n - r 企业物流配送路径优化问题的建模 不考虑时间窗的车辆路径优化问题，在实际应用中非常广泛。如邮政服务、快递等， 这些都是不需要考虑时间限制的，中国邮政一般是邮件抵达后电话通知客户来取货，大多 数快递公司是送货上门，顾客对货物到达的时间没有十分严格的限制。但本文研究的问题 是大米加工企业将大米运送给各个超市，由于各个超市对收货的时间都有严格的规定，运 输车辆必须在规定的时间内将货物送达，否则就需要等待或者退货，产生一些额外的损失， 包括赔偿客户损失、服务质量和信誉损失、车辆等候造成人员闲置成本和机会成本损失等。 因此，本文将时间效应成本也纳入到考虑的范围之中。 由于超市对收货时间的限制是时间段限制，而不是时间点限制，所以本文采用软时间 窗模型，通过惩罚函数来表达顾客对于配送车辆到达时间的期望及满意度。在规定的时间 段内，惩罚值为0 ；当违反时间窗约束程度越大，其惩罚值也相对越大；当配送车辆运达 时间超过顾客所能容忍的范围时，顾客将拒收货品或施以重罚，惩罚值趋向于无穷大。通 常情况下，惩罚成本的额度是根据企业与客户之间签订的合同而定的，可能随着缺货数量 而成抛物线或者指数增长，但它们的共同特征为车辆到达时间偏离约束时间窗越多，其惩 罚成本越高。因此，本文为了简化问题假定惩罚成本为线性增加