（计算机应用技术专业论文）智能优化算法在智能物流平台中的应用与研究.pdf

摘要 随着改革开放的深入，物流运输近年来在中国得到迅速的发展，在国外先进 的物流理念不断引入中国，并在中国得到进一步应用的同时，物流的信息化脚步 也在不断的发展智能物流平台正是在这样的背景下提出的。 智能物流平台采用了先进的面向服务的体系结构，简化复杂的物流应用软件 系统，为其开发提供一个基本框架。此框架封装了物流核心业务、标准化程度高 的业务，为软件开发人员提供了多种物流业务组件和智能组件。有了这样的物流 业务组件和智能组件的支持，在智能物流平台之上开发的智能物流管理软件就可 以降低复杂性，省去很多基础性的研发工作，从而大大缩短研发周期，提高研发 效率。 物流业务智能组件是智能物流平台中十分重要的一个组成部分，这是由于很 多物流业务所涉及的优化问题所建立的模型都是十分复杂的，很多优化问题都是 n p 完全问题，如何有效地解决这些使用普通算法所很难解决的问题也是本文关 注的焦点。 与此同时，智能优化算法在近年来得到高速发展，由于其算法的特性，已经 在很多领域得到实际应用，并取得了良好的效果。本文针对物流业务中实际的应 用情况，分别使用三种不同的智能优化算法，对其中三大问题进行了深入的研究。 使用细胞自动机，分别对两点之间的最短路径，单源多节点最短路径和多源多节 点最短路径进行建模，并设计算法求解。用普通的遗传算法解决车辆路径问题， 并在此基础上提出改进算法，平衡了涉及车辆数量与最优路径的问题。使用新进 研究的鱼群算法解决货物装载问题，并针对鱼群算法本身的不足，提出改进算法， 实验结果证明了改进的有效性。 本文以智能物流平台为载体，以物流业务智能组件为对象，以物流业务问题 为实际研究内容，建立相应的模型，应用改进的智能优化算法进行求解，取得了 很好的效果。 关键词 细胞自动机，遗传算法，鱼群算法，车辆路径问题，货物装载问题 w i t ht h ep r o g r e s so fr e f o r m i n ga n do p e n i n g - u pp o l i c y , l o g i s t i c si sd e v e l o p i n g v e r yr a p i d l yt h e s ey e a r si na l i n a w h e nt h ea d v a n c e dt h e o r i e so fl o g i s t i c sa l el a r g e l y i n t r o d u c e di n mc h i n aa n dt h e s et h e o d e sa r ew e l la p p l i e d ，i n f o r m a t i o n a l i z a t i o no f l o g i s t i c si n d u s t yi sa l s od e v e l o p i n g a p t i t u d el o g i s t i c sp l a t f o r mi sp u tf o r w a r du n d e r t h i sk i n do f b a c k g r o u n d a p t i t u d el o g i s t i c sp l a t f o r ma d o p t sa d v a n c e ds e r v i c e o r i e n t e da r c h i t e c t u r e , s i m p l i f i e st h ec o m p l i c a t e dl o g i s t i c sa p p l i c a t i o ns o f t w a r es y s t e ma n ds u p p l i e so n es o r t o fa r c h i t e c t u r ef o ri t s d e v e l o p m e n t t h i sa r c h i t e c t u r ee n c a p s u l a t e sp i v o t a ll o g i s t i c s o p e r a t i o n a n do f f e r sd i v e r s e l o g i s t i c so p e r a t i o nc o m p o n e n t sa n da p t i t u d e c o m p o n e n t s w i t ht h es u p p o r to ft h i sk i n do fc o m p o n e n t s ，t h ed e v e l o p m e n to f a p t i t u d el o g i s t i c sm a n a g e m e n t啪b es i m p l i f i e da n dt h ec o m p l e x i t yc a nb e r e d u c e d ，s ot h ec y c l eo fd e v e l o p m e n tm a yb es h o r t e n e da n de f f i c i e n c ym a yb e i m p r o v e d l o g i s t i c so p e r a t i o na p t i t u d ec o m p o n e n ti so n eo ft h em o s ti m p o r t a n tc o m p o n e n t s i nt h ea p t i t u d el o g i s t i c sp l a t f o r m ；b e c a u s em a n y o p t i m i z i n gp r o b l e m sw h i c hc o n c 宅i l l t o l o g i s t i c so p e r a t i o na r e n p - c o m p l e t e n e s sp r o b l e m s h o wt o s o l v eo u tt h e s e p r o b l e m se f f i c i e n t l yi sp a i da t t e n t i o ni nt h et h e s i s m e a n w h i l e , a p t i t u d eo p t i m 垃i n ga l g o r i t h m i sw e l l d e v e l o p e d i nt h e s e y e a r s ，b e c a u s eo ft h ei t sc h a r a c t e r i s t i c s ，i ti sa p p l i e di nm a n yf i e l d so fa p p l i c a t i o n t h i s t h e s i sw h i c hf o c u s e so nt h ea c t u a la p p l i c a t i o no fl o g i s t i c so p e r a t i o n sr e s e a r c ho nt h e t h r e ep r o b l e m sb yu s i n gt h r e ek i n d so fa p t i t u d eo p t i m i z i n ga l g o r i t h m m o d e l i n go n t h es h o r t e s tp a t hp r o b l e ma n dd e s i g n i n gt h ea l g o r i t h mt os o l v eo u tt h i sp r o b l e mb y u s i n g c e l l u l a ra u t o m a t ai st h ef i r s tr e s e a r c hd i r e c t i o n s o l v i n go u tt h ev e h i c l er o u t i n g p r o b l e mb yu s i n gn o r m a lg e n e t i ca l g o r i t h ma n dd e s i g n i n gt h ei m p r o v e dg e n e t i c a l g o r i t h mi st h es e c o n do n e f i n a l , c a r g ol o a d i n gp r o b l e mi ss o l v e do u tb yu s i n g a r t i f i c i a lf i s hs c h o o la l g o d t l u na n dt h ei m p r o v e do n e t h i st h e s i si sb a s e do na p t i t u d el o g i s t i c sp l a t f o r m ，r e s e a r c h st h ec o n t e n to ft h e p r o b l e m so fl o g i s t i c so p e r a t i o n , e s t a b l i s h e st h em o d e lo ft h r e ep r o b l e m sa n dd e s i g n s t h ed i f f e r e n ti m p r o v e da l g o r i t h mb a s e d0 1 1a p t i t u d eo p t i m i z i n ga l g o r i t h mt ot h e s e p r o b l e m s w i t ht h ev e r i f i c a t i o no fe x p e r i m e n t ，a l lt h ei m p r o v e m e n ti si ne f f e c t k e yw o r d s c e l l u l a ra u t o m a t a , g e n e t i c a l g o r i t h m , a l - t i f i c i a lf i s hs c h o o la l g o r i t h m ，v e h i c l e r o u t i n gp r o b l e m , c a r g ol o a d i n g p r o b l e m 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名： 学位论文授权使用声明 本人完全了解华东师范大学有关保留，使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者签名：导师签名： 日期：日期： o r i g i n a l i t yn o t i c e i np r e s e n t i n gt h i st h e s i si np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h em a s t e r s d e g r e ea te a s tc h i n an o r m a lu n i v e r s i t y ，1w a r r a n tt h a tt h i st h e s i si so r i g i n a la n da n y o ft h et c c l m i q u e sp r e s e n t e di nt h et h e s i sh a sb e e nf i g n r e do u tb ym e a n yo ft h e r e f e r e n c et ot h ec o p y r i g h t t r a d e m a r k ，p a t e n t - s t a t u t o r yr i g h t ，o rp r o p r i e t yr i g h to f o t h e r sh a v eb e e ne x p l i c i t l ya c k n o w l e d g e da n di n c l u d e di nt h er e f e r e n c e ss e 圮t i o na t t h ee n do ft h i st h e s i s s i g n a t u r e ： c o p y r i g h tn o t i c e ih e r e i na g r e et h a tt h el i b r a r yo fe c n us h a hm a k ci t sc o p i e sf r e e l ya v a i l a b l ef o r i n s p e c t i o n if u r t h e ra g r e et h a te x t e n s i v ec o p y i n go ft h et h e s i si sa o w a b l eo n l yf o r s c h o l a r l yp u r p o s e , i np a r t i c u l a r ，s t o r i n gt h ec o n t e n to ft h i st h e s i si n t or e l e v a n t d a t a b a s e s ，a sw ea sc o m p i l i n ga n d p u b l i s h i n gt h et i t l ea n da b s t r a c to ft h i st h e s i s ， c o n s i s t e n tw i t h f a i rb s e ”a sp r e s c r i b e di nt h ec o p y r i g h tl a wo ft h ep e o p l e s r e p u b l i co fc h i n a s i g n a t u r e ： 华东师范大学计算中心2 0 0 8 年硕士毕业论文 1 1 课题研究背景 第1 章绪论 中国经济的快速发展带动了物流运输的发展，而第三方物流市场发展高于物 流的发展水平，在物流行业面i f 缶的整个环境总体长期向好的大环境下，预计物流 行业r r 投资将呈现出加速度增长态势。纵观几年来物流行业的发展，r r 投资始 终处在加速增长的态势。 受中国经济发展不平衡的影响，目前东中部地区物流企业的1 1 r 投资占到整 个物流行业r r 投资的7 5 以上。这种区域的不平衡会随着国家西部大开发和振 兴东北战略逐步深入而逐渐缩小。 物流行业没有统一的行业归口管理和信息化建设的规划，具有一定规模的物 流企业借鉴国外先进的物流管理思想，参考知名物流企业的信息化建设和应用先 进经验，结合自身的业务和资源特点，开始规划自己的信息化建设。 物流行业信息化建设的重点除围绕基本的计算机应用外，业务系统的整合将 成为物流企业信息化建设的重点，特别是随着客户( 供贷方和收获方) 信息化建 设的不断提升，物流企业主动的或者被动的进行自己信息化建设和应用的提升， 产业链信息化建设和应用的互动促进了物流行业信息化建设的重点变化。除基本 的信息化建设重点外( 网络建设、办公自动化、财务管理等) ，运输管理系统、 货物跟踪系统、客户关系管理系统、配送服务系统等将成为物流企业信息化建设 的重点。 目前物流行业盯投资的重点仍是基本业务的信息化，受物流企业投资规模 的限制，物流企业r r 投资中软件和服务与硬件基本相当。2 0 0 5 年物流行业r r 投资中，硬件投资比例为5 2 ，软件投资占4 0 ，服务( 含培训) 占8 。1 1 r 产 品采购的重点主要集中在网络，终端和外设设备上，这部分产品占r r 硬件投资 的7 0 以上另外，服务器和存储产品占到物流企业1 1 r 硬件投资的2 0 。 物流行业r r 市场发展前景光明，用户需求多样化发展。 中国物流成本占到g d p 的2 0 以上，中国经济保持快速稳定的增长就要求 物流行业不能低于经济的增长速度，中国物流市场的需求十分巨大。正以每年 2 5 的速度在增长，与此同时物流业务的自动化与信息化已经成为中国现代物流 行业的发展瓶颈，物流行业盯市场前景非常乐观。结合中国物流行业的外部环 境和行业自身特点，预计未来几年物流行业的1 1 r 市场机会中：中小型物流企业 华东师范大擘计算中- 心2 0 0 8 年硕士毕业论文 r r 市场机会主要以硬件和通用软件为主，大型物流企业盯市场机会主要以业务 系统整合为主，大中型传统物流企业转型以管理流程再造为主。 1 2 研究意义 在物流系统中，配送运输管理有着至关重要的地位它一方面完善了运输及 整个物流系统，提高了侠应保证程度；另一方面提高了物流末端物流的经济效益， 可使企业实现低库存甚至零库存。 1 3 研究内容 本文主要集中在对配送运输管理系统的智能化的研究，在基于对物流配送业 务作详细介绍的基础上，从可持续发展的角度，用系统的观念，来研究物流配送 体系，使配送体系合理化。 研究主要集中在3 个方面： 配送车辆路径最短问题研究 配送车辆路线优化问题研究 配送车辆装箱优化问题研究 这3 个问题都是自动配送运输计算的关键问题。配送路径最短问题的研究目 的是使得两点之间，一点到其他点之间，所有节点之间的距离最短。这是最基本 的路径问题，也是配送路线优化问题的基础；配送路线优化问题指的是合理分配 车辆，从一个配送中心出发，满足不同个节点的需求，研究目的是在使用最少车 辆次数的情况下，使得所有车辆经过的总路径最短；配送装箱问题是对物品进行 装箱，目的是使用最少的车辆，使得车辆空间的利用率最大这三个问题互有联 系，而且都直接关系到配送运输中的关键问题，即成本问题。如果能很好的解决 这三个问题，菲但能为企业节省大量资金，而且也能减少车辆排放的废气对环境 造成的污染程度。 1 4 研究方法 本文的研究方法如下： 第一章介绍智能物流平台开发的背景，意义，本文在智能物流平台中的研究 内容，研究方法。 第二章简要概述职能物流平台，介绍其特点，完成对智能物流平台的需求分 析，明确本文的研究内容。 华东师范走擘计算中譬2 0 0 8 年硕士毕业论定 第三章介绍本文使用的使用算法之一，即细胞自动机。并用细胞自动机理论， 解决车辆路径最短问题，包括单源到单目的地问题，单源到多节点问题，及多源 到多节点问题。 第四章介绍本文使用的另一个算法，即遗传算法并对遗传算法中的多个过 程包括构造染色体的方法，初始种群的生成，交叉算子，变异算子的改造，使 得其更有利于解决配送车辆路线优化问题。并给出实验数据，证明改进的有效性 与实用性 第五章首先介绍鱼群算法，然后用构造鱼群算法的各种行为，设定各种参数 以求解配送车辆装箱优化问题。并且通过对鱼群算法的改造，提出自己的求解方 案。 。 第2 章智能物流平台 2 1 智能物流平台总体概述 2 1 1 智能物流平台概述 目前，平台的概念目前基本上有三种，一种是基于快速开发目的技术平台， 第二种是基于业务逻辑复用的业务平台。第三种平台基于系统自维护，自扩展的 应用平台。技术平台和业务基础平台都是软件开发人员使用的平台，而应用平台 则是应用软件用户使用的平台 智能物流平台是物流业务基础软件平台，是以物流业务导向和驱动的、可快 速构建物流应用软件的软件平台。 智能物流平台采用面向服务的体系结构( s e r v i c e - o r i e n t e da r c h i t e c t u r e ， s o a ) ，为复杂物流应用软件系统的开发提供了一个基本框架，这个框架对物流 核心业务、标准化程度高的业务进行封装，为软件开发人员提供了多种物流业务 组件和智能组件。有了这样的物流业务组件和智能组件基础，在智能物流平台之 上开发智能物流管理软件就可以降低复杂性，省去很多基础性的研发工作，从而 大大缩短研发周期，提高研发效率。 2 1 2 智能物流平台特点 1 是基于面向服务的体系结构( s e r v i c e o d e a t e da r c h i t e c t u r e ，s o a ) 的智 能物流平台 智能物流平台采用面向服务的体系结构( s o a ) ，对物流核心业务、标准化 程度高的业务进行封装组件化，建立了以物流业务为驱动的组件服务体系。 2 提供物流业务的业务敏捷性和灵活性 智能物流平台组件服务体系是以业务驱动服务，服务驱动技术，并且组件问 实现松散耦合。松散耦合组件服务体系可依据企业物流业务需求和流程，灵活 便捷的组合，搭建符合企业物流业务需求和流程的物流管理软件。 3 提供了一个跨平台多层b s 架构。这个架构有以下三个含义： 平东师范大擘计算中心2 0 0 8 年硕士毕业论文 跨平台：v p 具有跨操作系统平台和跨数据库平台的能力，能在l i n u x 、 a i x 、s o l a r l s 、b s d 、w i n d o w s 等系统上运行，并且支持o r a c l e 等各种类型的 数据库 多层架构：v p 是一个由数据层、1 1 层业务层、表示层组成的多层架构的 信息系统平台 b s 架构：v p 是基于互联网应用的b s 架构 4 提供物流业务智能组件 智能物流平台不仅对物流核心业务、标准化程度高的业务进行封装，同时提 供库存仿真、路线优化、仓储布局优化等多种智能组件，极大地方便软件开发人 员根据用户的情况，利用物流业务智能组件开发智能物流管理软件，缩短软件开 发周期。 5 提供面向物流业务组件 智能物流平台针对物流企业的业务，提供了多种物流业务组件，这些物流业 务组件是对物流核心业务、标准化程度高的业务进行的封装。软件开发人员可根 据用户的具体业务流程，将自己需要的物流业务组件组合在一起，即可搭建出符 合用户需求的智能物流管理软件。 6 易于扩展 智能物流平台还可以根据需要，增加物流业务组件和物流业务职能组件，日 趋完善。 7 灵活性高 通过业务基础软件平台提供的开发与管理工具，软件开发人员能很方便地满 足用户个性化的需求，以及用户在发展过程中各种各样变化的需求。 8 数据无关性 对软件系统来说，数据和数据操作是最基本的两个要素。智能物流平台通过 核心层的数据集成组件统一访问数据，可以支持多种数据库、支持不同数据库之 间的事务处理和分布式查询，实现数据载体无关性和数据的存放地点无关性，通 过智能物流平台，开发人员不用花很多精力专注于数据方面的处理，可以集中于 具体业务的实现上 2 2 物流需求分析 2 2 1 自建物流系统需求 自营物流是指企业自身投资建设物流的运输工具、储存仓库、由企业内部人 年东师苑大学计算中心2 0 0 8 年硕士毕业论文 员参与并由企业承担配送过程中的全部费用的物流方式 按照企业性质，可以区分以下两类企业： 生产制造企业 商贸企业 企业物流又可以区分为以下具体的物流活动： 供应物流一生产物流一销售物流一回收与废弃物流 供应物流、生产物流、销售物流、回收与废弃物流在不同性质、不同行业、 不同规模的企业中，有着各自不同的体现形式。 生产制造企业物流系统需求特点： 生产制造企业产品专业化强，品种比较集中。 分销渠道比较广，客户分散，为降低物流成本，通常采用多层组织多物流 中心结构 对于跨区域的运输和市内配送，存在外包物流的形式。 为实现j i t 配送，必须实现跨区域的销售信息快速收集。 为降低生产原料和外购件的库存成本，必须实现销售信息的快速反馈。 商贸企业物流系统需求特点： 产品范围广，品种比较松散。 根据商贸企业的规模，通常有单物流中心、单物流中心多仓库、多层组织 多物流中心多种结构 对于跨区域经营，会出现单品多供应商现象。 于跨区域的运输和市内配送，存在外包物流的形式。 为实现j i t 配送，必须实现跨区域的销售信息快速收集。 为降低生产原料和外购件的库存成本，必须实现销售信息的快速反馈。 2 2 2 第三方物流系统 第三方物流指企业通过与第一方或第二方的合作来提供其专业化的物流服 务，它不拥有商品，不参与商品买卖，而是为顾客提供以合同约束、以结盟为基 础的、系列化、个性化、信息化的物流代理服务包括设计物流系统、e d i 能力、 报表管理、货物集运、选择承运人，货代人、海关代理、信息管理、仓储、咨询、 运费支付和谈判等 第三方物流系统需求特点： 第三方物流是为多个货主提供物流服务，在仓储，配送过程中同一种货物会 存在多个货主的情况，需要在作业过程中加以区分 第三方物流是为多个货主提供配送服务，在配送，需要在作业过程中加以区 华东师苑大学计算中心2 0 0 8 年硕士毕业论文 分共运共配和专运专配。 需要根据不同客户的需求提供灵活的，多样的物流服务，要求在仓储和配送 过程中可以为不同性质的货物提供物流的解决方案。 第三方物流依靠优质服务来赢取客户，获得最大的利益。所以要求在物流作 业的时效性，准确性有着很高的要求。 第三方物流采用多样复杂的计费方式。第三方物流企业的利润来源不是在于 提供仓储保管的服务，而是希望提高仓库物品周转率，以仓储作业( 如：收货、 上架、补货、拣货、包装、发运) 为基准向客户收取服务费用。 第三方物流的客户为了使效益和效率的最大化，必须实现物流信息的快速反 馈，使销、产、供和物流信息动态同步。这就要求第三方的物流企业能够及时给 企业提供其所需的信息服务。 2 2 3 多层组织多物流中心体系结构 在多物流中心的运作当中，由于每一个物流中心都兼具有理货保管与配送运 输功能，其信息系统必须要提供完整与实时的物流信息。 图互1 树状结构图 h o ( h e a d q u a r t e r ) ：物流总部 r d c ( r e g i o nd i s t r i b u t i o nc e n t e 0 ：区域物流中心( 有仓库) f d c ( f r o n td i s t r i b u t i o nc e n t e r ) ：前端物流中心洧仓库) 2 3 业务集成组件 2 3 1 概述 业务集成组件是智能物流平台的业务集成组件中的核心组件，智能物流平台 将物流核心业务、标准化程度高的业务进行封装。开发人员在利用智能物流平台 开发复杂物流应用软件系统时，通过业务集成组件，屏蔽了业务实现的具体技术 华东师范夫学计算中心2 0 0 8 年硕士毕业论文 细节，使开发人员关注的焦点在于业务逻辑、管理模式，而不用关心采用何种技 术来实现。 目前，智能物流平台业务集成组件可以分为以下2 类 1 ) 物流业务基础组件 2 ) 物流业务智能组件 2 3 2 物流业务基础组件 智能物流平台根据物流业务流程，将物流业务组件区分为仓储管理、配送运 输管理、物流费用管理、采购管理和信息查询五中类型。每种类型都对应这一种 物流业务基本环节。 1 1 仓储管理组件 仓储是物流业务一个重要环节，总是出现在物流各环节的接合部，例如生产 与销售之间，批发与零售之间，采购与生产之间，不同运输方式转换之间等等。 仓储环节集中了上下游流程整合的所有矛盾，仓储管理就是在实现物流流程的整 合。 仓储管理活动通常可以分为追、收、查、储、拣、发、盘、退八个环节，智 能物流平台针对这八个环节的业务进行封装，组成仓储管理组件。使开发人员能 为为企业提供仓储管理的追、收、查、储、拣、发、盘、退各环节的一揽子解决 方案，而不必过于关注，各个环节业务具体实现的技术细节。 2 ) 配送运输管理组件 物流运输是一个传统行业，业务流程和运作模式可以千差万别。智能物流平 台将合理的业务流程的固化，封装成配送运输管理组件，以帮助开发人员，快速 搭建符合用户企业流程的运输管理系统。 目前，配送运输管理组件能为开发人员提供以下几种业务支持。 a ) 排车调度 b ) 路线安捧 c ) 地理信息系统( g i s ) 支持 d ) 成本核算 ， 3 ) 物流费管理组件 提供物流服务是第三方物流的主要收费方式，且收费标准各不相同。所以， 物流计费系统提供灵活的收费标准成为必然的要求。基于此，智能物流平台向开 发人员提供一种计费方案的开发平台。通过这个平台，丌发人员能以为用户提供 面向货主计费方案的物流计费系统。 a ) 实现计费方案管理 年东师范大学计算中心2 0 0 8 年硕士阜业论文 b ) 提供计费方案配置工具 钔采购管理组件 采购管理是计划下达、采购单生成、采购单执行、到货接收、检验入库、采 购发票的收集到采购结算的采购活动的全过程，对采购过程中物流运动的各个环 节状态进行严密的跟踪、监督，实现对企业采购活动执行过程的科学管理。 采购管理组件主要包括采购计划、订单管理及价格管理三个组件 a ) 采购计划管理组件 对企业的采购计划进行制定和管理，为企业提供及时准确的采购计划和执 行路线。采购计划包括定期采购计划( 如周、月度、季度、年度) 、非定期采购 任务计划( 如系统根据销售和生产需求产生的) 通过对多对象，多元素的采购 计划的编制、分解，将企业的采购需求变为直接的采购任务。 采购计划管理组件组件支持企业以销定购、以销定产、以产定购的多种采 购应用模式，支持多种设置灵活的采购单生成流程 b ) 采购订单管理组件 采购订单管理组件以采购单为源头，对从供应商确认订单、发货、到货、检 验、入库等采购订单流转的各个环节进行准确的跟踪，实现全过程管理。 采购订单组件可进行多种采购流程选择，如订单直接入库，或经过到货质检 环节后检验入库等，在整个过程中，可以实现对采购存货的计划状态、订单在途 状态、到货待检状态等的监控和管理。 采购订单组件可以直接通过电子邮件系统发向对应的供应商，进行在线采 购。 c ) 价格管理组件 价格控制是采购管理中重要的内容。 价格管理组件提供灵活多样采购价格控制。 5 1 物流信息查询组件 物流信息查询组件封装了多种物流业务查询处理逻辑，为企业决策层提供决 策信息。 库存智能仿真 历史库存追溯 入库信息追溯 出库信息追溯 仓储信息查询 配送信息追溯 华东师范走学计算中心2 0 0 8 年硕士毕业论文 2 3 3 物流业务智能组件 物流业务智能组件是智能物流平台引入先进的物流管理思想，结合数据挖掘 等信息技术构建的物流业务数据管理和分析工具。 物流业务智能组件能够实时的对企业不同部门，不同时期的物流业务数据进 行采集、抽样、整合和转化，建立物流业务数据分析模型，进行多维、深度分析， 在数据分析模型的基础上做出判断，通过丰富的图形和立体报表灵活的展现数 据。 目前，物流业务智能组件包括以下几种： 库存仿真组件 库存仿真组件能以根据货品库存成本、近期销售量、同期销售量、采购成本、 采购周期等业务数据，进行深度分析，帮助企业安排合理的库存，在保证未来一 段时期销售的前提下，降低库存成本。 路线优化组件 路线优化组件能以结合g i s 系统，充分考虑车辆、司机、到货时间等情况， 实现多目标运输路线优化运输，帮助汽车运输部门提高运输效率，降低运输成本。 仓储布局优化组件 仓储布局优化组件能够根据货品库存仓储条件、近期销售情况、同期销售情 况以及分拣情况等，对仓库的库存货品进行整体布局优化，帮助仓管部门实现仓 储、分拣、出库线路最优化，降低仓储员工工作强度，提高效率。 华东师范大擘计算中心2 0 0 8 年硕士毕业论文 第3 章车辆最短路径研究 3 1 细胞自动机简介 细胞自动机( c c n u h ra u t o m a t a ，简称c a ) 。是一时间和空间都离散的动力系 统。散布在规则格网( l a u i c cg r i d ) 中的每一细胞( c e l l ) 取有限的离散状态，遵循 同样的作用规则，依据确定的局部规则作同步更新。大量细胞通过简单的相互作 用而构成动态系统的演化。不同于一般的动力学模型，细胞自动机不是由严格定 义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规 则的模型都可以算作是细胞自动机模型。因此，细胞自动机是一类模型的总称， 或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限 多个状态，且其状态改变的规则在时间和空间上都是局部的。 3 1 - 1 自动机 自动机( a u t o m a t o n ) 通常指不需要人们逐步进行操作指导的设备。例如，全自 动洗衣机可按照预先安排好的操作步骤作自动地运行；现代计算机能自动地响应 人工编制的各种编码指令。完成各种复杂的分析与计算；机器人则将自动控制系 统和人工智能结合，实现类人的一系列活动另一方面，自动机也可被看作为一 种离散数字动态系统的数学模型。例如，英国数学家a m t u r i n g 于1 9 3 6 年提出 的图灵机就是一个描述计算过程的数学模型f r u r m g am ，1 9 3 6 ) 。它是由一个有 限控制器、一条无限长存储带和一个读写头构成的抽象的机器，并可执行如下操 作： 读写头在存储带上向左移动一格； 读写头在存储带上向右移动一格； 在存储的某一格内写下或清除一符号： 条件转移。 图灵机在理论上能模拟现代数字计算机的一切运算，可视为现代数字计算机 的数学模型实际上，一切”可计算”函数都等价于图灵机可计算函数，而图灵机 可计算函数类又等价于一般递归函数类。 根据存储带是否有限，可将自动机划分为有限带自动机( f i n i t ea u t o m a t o n ) 和 华东师范走擘计算中心2 0 0 8 年硕士毕业论文 无限带自动机( i n f i n i t ea u t o m a t o n ) 由于图灵机有无限长的存储带，所以为一种 无限带自动机有限带自动机常用作数字电路的数学模型，也用来描述神经系统 和算法9 而无限带自动机主要用来描述算法，也用来描述繁殖过程( 如细胞型自动 机和网络型自动机) 有限自动机是一种控制状态有限、符号集有限的自动机。是一种离散输入输 出系统的数学模型可将有限自动机设想成由一条划分为许多方格的输入带和一 个控制器组成的机器：在输入带的每一个小格中可以容纳一个符号，这些符号取 自一个有限符号集s - 控制器具有有限个可能状态( 构成集合q ) 。并在每一时刻仅 处于其中的一个状态q ；控制器有一个读入头，可以从输入带中读入符号；时间是 离散的，初始时控制器处在状态；控制器的功能是根据其当前状态g 和读入头从 输入带上得到的符号a ，来确定控制器的下一时刻的状态实现从状态q 到状态q ， 实现从状态q 到状态铲q 的转移，并将读入头右移一格。控制器另一功能是识别 终止状态( 它们构成q 的一个子集f ) ，也可将该识别功能视为有限自动机的输出。 从数学上来定义，有限自动机是一个五元组： i a ；( q ，s ，d ，q o ，f ) 其中，q 是控制器的有限状态集、s 是输入符号约有限集、d 是控制状态转 移规律的q x s 到q 的映射( 可用状态转移图或状态转移表表示) ，q 0 是初始状态、 f 是终止状态集。若d 是单值映射，则称m 为确定性有限自动机；若d 是多值映 射，则称m 为非确定性有限自动机。 3 1 2 细胞自动机的定义 对细胞自动机的含义存在不同的解释，物理学家将其视为离散的、无穷维的 动力学系统；数学家将其视为描述连续现象的偏微分方程的对立体，是一个时空 离散的数学模型；计算机科学家将其视为新兴的人工智能、人工生命的分支；而生 物学家则将其视为生命现象的一种抽象。下面给出几种常见的定义： 1 细胞自动机的物理学定义 细胞自动机是定义在一个由具有离散、有限状态的细胞组成的细胞空间上， 并按照一定局部规则，在离散的时间维上演化的动力学系统。 具体讲，构成细胞自动机的部件被称为”细胞”，每个细胞具有一个状态。这 个状态只能取菜个有限状态集中的一个，例如或”生”或”死。，或者是2 5 6 中颜色 中的一种，等等；这些细胞规则地摊列在被称为”细胞空间”的空间格网上；它们各 自的状惫随着时间变化。而根据一个局部规则来进行更新，也就是说，一个细胞 在某时刻的状态取决于，而且仅仅取决于上一时刻该细胞的状态以及该细胞的所 有邻居细胞的状态；细胞空间内的细胞依据这样的局部规则进行同步的状态更 年东师范大学计算中心2 0 0 8 年硕士毕业论文 新，整个细胞空间则表现为在离散的时间维上的变化。 2 细胞自动机的数学定义 美国数学家l p h u r d 和k c u l i k 等人在9 0 年代初，对细胞自动机分别从集合 论和拓扑学等角度进行了严格地描述和定义( i s 惠民，1 9 9 4 ；c u l i l 【，k ，1 9 9 0 ； 李才伟，1 9 9 乃 1 1 基于集合论的定义 设d 代表空问维数，k 代表细胞的状态，并在一个有限集合s 中取值，r 表 细胞的邻居半径。z 是整数集，表示一维空间，t 代表时间。 为叙述和理解上简单起见，在一维空间上考虑细胞自动机，即假定d = 1 那 么整个细胞空间就是在一维空间，将整数集z 上的状态集s 的分布，记为s z 。 细胞自动机的动态演化就是在时间上状态组合的变化，可以记为： f ：s ；一s 磊； 这个动态演化又由各个细胞的局部演化规则f 所决定的。这个局部函数f 通 常又常常被称为局部规则。对于一维空间，细胞及其邻居可以记为s 2 r + l ，局部 函数则可以记为： f t 冀州s m 对于局部规则f 来讲，函数的输入、输出集均为有限集合，实际上。它是一 个有限的参照表。例如，i = - 1 ，f 的形式则形似如下：【o ，0 ，o 】- o ；【o ，0 ，1 】- 如；【0 ， 1 ，0 卜 l ；【1 ，0 ，o 】 o ；【0 ，1 ，1 】- 1 ；【1 ，0 ，l 】- 0 ；f 1 ，1 ，0 】 0 ；【1 ，1 ，1 】- o 对细胞空间内的细胞，独立施加上述局部函数，则可得到全局的演化： 尹( 文1 ) 一厂r 名，扣) d 表示在位置i 处的细胞，至此，我们就得到了一个细胞自动机模型。 2 ) 细胞自动机的拓扑学定义 为描述和理解方便。同样假定维数d 为1 。设s 为k 个符号约有限集。z 为 整数全体的集台，称z 到s 的映射的全体s z 为构形空间。显然s z 就是用s 中 的符号组成的双侧无限的符号序列的全体，即一维细胞自动机的所有构形的集 合称a 丸1 a o a l ，) 为构形空间中的点。 在s z 中引进任意两点x 和y 之间的距离 矗( z y = 艿( 墨，册) 2 一吲 其中当x i = y i 时d ( x i ，y i ) = o ，当x i ? y i 时d ( x i ，y o = 1 。然后。在s z 中可以建立 起开、闭、紧等拓扑概念。 在s z 中定义移位算子d 为d ( x i ) = x i 1 ，i z 。若连续映射f ：s z - s z 产与d 可 交换，即f d - d f 。或对任意的x s z 有f ( ( 嗽) ) = d ( f ( x ) ) ，则称f 为细胞自动机。 对于以上定义，我们很容易将它扩展到一个任意维空间，所要做的工作只是 将s z 记为s z “d ，s 2 r + l 记为s ( 2 r + 1 ) “d 等，同时对一些描述作相应改变即可。 半末师范走幸计算中心2 0 0 8 年硕士毕亚论文 3 1 3 细胞自动机的构成 细胞自动机由最基本的细胞、细胞空间、邻居和规则四部分组成。简单讲， 细胞自动机可以视为由一个细胞空间和定义于该空间的变换函数所组成。 1 细胞 细胞又可称为单元或基元，是细胞自动机的最基本的组成部分。细胞分布 在离散的一维、二维或多维欧几里德空间的晶格点上 2 状态 状态可以是 0 ，1 的二进制形式或是( s o ，s 2 ，s i s k 整数形式的离 散集，严格意义上。细胞自动机的细胞只能有一个状态变量。但在实际应用中， 往往将其进行了扩展。例如每个细胞可以拥有多个状态变量。李才伟在其博士论 文工作中，就设计实现了这样一种称之为”多元随机细胞自动机”模型。并且定义 了细胞空间的邻居i g l i 关系。由于邻居关系，每个细胞有有限个细胞作为 它的邻居； 3 细胞空间( l a t t i c e ) 细胞所分布在的空间网点集合就是这里的细胞空间。 o ) 细胞空间的几何划分：理论上，它可以是任意维数的欧几里德空间规则划 分。目前研究多集中在一维和二维细胞自动机上。对于一维元抱自动机。细胞空 间的划分只有一种而高维的细胞自动机。细胞空间的划分则可能有多种形式。 对于最为常见的二维细胞自动机。二维细胞空间通常可按三角、四万或六边形三 种网格排列。 这三种规则的细胞空间划分在构模时各有优缺点： 三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用；其缺点是 在计算机的表达与显示不方便，需要转换为四方网格。 四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表 达显示；其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型 中的h p p 模型。 六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然 而真实，如格气模型中的f h p 模型：其缺点同三角网格一样，在表达显示上较为 困难、复杂。 ( 2 ) 边界条件：在理论上，细胞空问通常是在各维向上是无限延展的，这有利 于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这 一理想条件，