（系统工程专业论文）达明公司物流配送系统规划与设计.pdf

达明物流配送系统规划与设计 摘要 近年来国内物流产业正在快速发展，物流市场在壮大的同时竞争亦f 1 趋激 烈，顾客对物流服务质量的要求提高，以及行业竞争使物流企业格外注重在物流 配送作业上的科学与高效管理。而信息与通讯技术的发展和应用为物流配送的高 效与精确运作提供了有力的技术支撑。 本研究根据达明公司的实际需求，为其规划和设计了关于配送作业的一套物 流配送系统，实现了该公司在配送作业上的智能运作与控制，它包括配送路线优 化、智能车辆调度与监控管理和配送信息处理等功能。并在实际运用中得到较好 的效果，为企业的物流运作节省了成本，提高了效率。 本研究在整个物流配送系统的规划与设计中，根据达明公司的物流配送运作 建立其适用的数学模型，并通过遗传算法及程序来求解该模型。通过在系统路线 优化运算模块上的应用，实证效果非常良好；通过建立基于g p s g i s g s m 等信 息通讯技术的配送系统运作平台，实现了配送系统对配送路线优化、车辆调度与 监控的智能管理和配送信息处理与存储等功能。 达明发展公司与西工大空管所在物流配送系统研发上的合作取得很好的成 果，本研究实现了初期规划与设计的目标，而后续的系统维护与升级工作依然任 重道远。希望这种企业与学府研究所的合作有一个好的开始，亦有其长远的发展 空间和前景。 关键词：物流配送系统遗传算法路径优化智能调度 达明物流配送系统规划与殴计 a b s t r a c t l o g i s t i c si n d u s t yh a sd e v e l o p e dv e r yf a s t i nr e c e n t y e a r s w i t ht i l e l o g i s t i c sm a r k c t b e c o m i n gs t r o n g e r , t h ec o m p e t i t i o n h a sb e c o m em o r ea n dm o r ed r a s t i ct h ec u s t o m e r r e q u i r eh i g h e rl o g i s t i c ss e r v i s eq u a l i t y , a l s ot r a d ec o m p e t i t i o nm a k el o g i s t i c sc o m p a n i e sp a y m o p ea t t e n t i o nt os c i e n t i f i ca n de f f i c i e n tl o g i s t i c sd i s t r i b u t i o nm a n a g e m e n tt h e d e v e l o p m e n t o fi n f o r m a t i o na n dc o m m u n i c a t i o n t e c h n o l o y o f f e r s p o w e r f u l t e c h n i c a l s u p p o r t l b rt h e e f f i c i e n ta n da c c u r a t el o g i s t i c sd i s t r i b u t i o n a c c o r d i n gt ot h ep r a c t i c a lr e q u i r e m e n to ft o p m i nd e v e l o p m e n tc ol t d ，t h i sr e s e a r c h d e s i g n s ad i s t r i b u t i o n s y s t e m i t c a l l i m p l e m e t ei n t e l l i g e n t c o n t r o lo f s u p p l y c h a i n m a n a g e m e n t i ti n c l u d e so n i m i z a t i o nr o u t e 、i n t e l l i g e n tv e h i c l e sd i s t r i b u t i o na n dc o n t r o l i n g s y s t e m 、a l l o c a t i n ga n dt r a s p o r t a t i o n 、i n f o r m a t i o np r o c e s s i n ga n ds oo n i tc a ng a i ns a t i s f i e d e f f e c ti np r a c t i c a lu s e i tc a nc u td o w nt h ec o s to f t r a n s p o r t a t i o na n di m p r o v et h ee f f i c i e n c yo f l o g i s t i c si ne n t e r p r i s e i nt h el a y o u ta n dt h ed e s i g n i n go f t h ea l l o c a t i n ga n d t r a s p o r t a t i o ns y s t e m ，t h e r e s e a r c hs e t u pas u i t b l em a t h m a t i cm o d e l a c c o r d i n g t ot h ea ll o c a t i n ga n d t r a s p o r t a t i o no ft o p m i nd e v e l o p m e n tc o ，l t d i ts o l v e st h em o d e l u s i n gt h eg e n e t i c a l g o r i t h ma n dp r o g r a m b ya p p l i e di no p t i m i z a t i o nr o u t em o d u l eo fs y s t e mr o u t e ，i tc a n g a i nt h ee x p e c t e dr e s u l t s t h o u g he s t a b l i s h i n gs u p p l ys y s t e mf l a t f o r mb a s e do ni n f o r m a t i o n t e c h n o l o g ys u c h a s g p s ，g i a n dg s m ，i tc a na c h i e v em a n yf u n c t i o n ss u c ha sr o u t e o p t i m i z a t e e d ，i n t e l l i g e n t m a n a g e m e n t a n dd i s p a t c h i n g o f v e h i c l e s t h e c o o p e r a t i o no ft o p m i nd e v e l o p m e n tc o l t da n da i rt r a f f i cm a n a g e m e n ti n s t i t u t e o fn w p uo nt h e d e s i g n i n g o f l o g i s t i c s d i s t r i b i t i o n s y s t e m h a s p e r s u i t e dg r e a t a c h i e v e m e n t s t h i sr e s e a r c hc a na c h i e v ea l l i n i t i a l g o a l s ，b u t t h e r ea r ea l s o m a n yw o r k s r e m a i n e dt om a k et h es y s t e mp e r f e c t w i s hs u c h c o o p e r a t i o nb e t w e e nc o m p a n ya n du n i v e r s i t y ag o o ds t a r ta n dab e a e r p r e v i e w k e y w o r d s ：i o g i g i e s ，d i s t r i b i t i o n s y s t e m ，t h eg e n e t i c a l g o r i t h m ，r o u t e o p t i m i z a t e d ，i n t e l l i g e n td i s t r i b u t i o n 达明物流配送系统规划与设计 1 1 研究背景及意义 第一章绪论 国内外物流产业正在快速发展，并且很有可能成为2 1 世纪中国的支柱产业 。2 0 0 2 年物流相关总支出达1 9 0 0 0 亿元，物流成本占g d p 的比重约为2 0 。2 0 0 2 年是我国第三方物流迅速发展的一年，一批超大型国有物流企业投身第三方物流 市场。7 0 的物流服务提供商在过去的三年中，年均业务增幅都高达3 0 ”1 。物 流市场在壮大的同时，竞争亦目趋激烈，而随着经济的快速发展，顾客对物流服 务质量的要求不断提升，物流企业需要在成本控制的前提下不断提高物流服务水 平。物流企业为了能将产品准时、快速、正确且完整的送达客户手中，物流配送 作业的规划与设计显得格外重要。物流配送作业的重点是如何将车辆有效的使用 并决定其最经济的行驶路线图，使得商品能在最短的时间内送到顾客的手中并且 在配送过程中对配送作业进行高效的监控和调度管理。高效的物流配送作业管理 已被许多物流公司视为节省成本和使其服务具有竞争力的关键。 信息与通讯技术( i n f o r m a t i o na n dc o m m u n i c a t i o nt e c h n o l o g y 或i c t ) 的 发展和应用为物流的高效与精确运作提供了有力的技术支撑。1 。物流企业可以通 过应用计算机信息处理与运作系统、卫星跟踪系统( g p s ) 、地理信息系统( gi s ) 、全球移动通信系统( g s m ) 建立物流配送作业系统实现信息的计算机处理及 物流运作的智能控制，以提高运作的效率和服务质量，降低成本。目前在针对物 流配送作业的系统开发与应用上，国内外的差距仍很大，由于欧美物流自动化程 度高，运作模式规范性强，物流系统的开发与应用已进入较成熟和广范应用的阶 段，如美国的d i s t r i b u t i o nl o g i s t i c sm a n a g e m e n ts y s t e m 和d i s t r i b u t i o n o p e r a t i o n sm a n a g e m e n ts y s t e m ，其系统功能涉及配送需求、计划控制、车辆及 运输管理应用系统。软体功能完备，并具备b a rc o d e 识别、e d i 资料传送、r f 资料处理、c a p s 等系统。国内目前开发的系统主要借览于国外经验。如高达公 司的g o l d e nd i s t r i n b u t i o ns y s t e m ，。利玛的l o g i s t i c ss t y s t e m 系统企业能 够安排运输任务，查询车辆状态和每一车辆收支利润情况 4 】。我国物流行业运作 达明物流配送系统规划与设计 模式呈现多样化、缺乏规范化性造成物流系统的通用性不强，大多物流企业仍通 过系统升发公司或研究机构开发适合自身企业运作特点的系统。 1 2 研究的动机与目的 达明发展公司是一家从事进出口业务代理及物流配送业务的公司，主要为东 莞来料加工及进出口企业办理进出口通关手续及承担其物流业务。目前在东莞主 要码头( 鹬洲) 、港口( 沙田港) 、海关监管区( 东莞海关) 、交通枢纽地( 常平 火车站) 设有四个配送中心面积十余万平方米，拥有2 吨至4 0 吨各型货运车辆i 0 0 多辆，各种专用装卸设备2 0 余台客户覆盖东莞及各镇区( 见图1 1 ) 。由于原有配 送活动仍是以人工的经验法则决定，通常是出货人员依据订单将货物装运上车， 然后车辆调度人员依据订单及需求点的位置，指派配送路线或是司机依本身经 验来完成配送。但是由于配送活动的不断扩张以及道路网的错综复杂，以往人 工的方式已渐渐不能负荷目前的需求而且在车辆的监控与调度管理上无法进行， 因此需要建立一套基于计算机与信息通讯技术的物流配送系统以实现一个快速 准确有效率的配送路径规划及车辆的调度与监控。 图i 1 达明发展公司配送中心与主要客户分布图 2 0 0 1 年西工大空中交通管理系统研究所就达明公司物流配送系统项目进行 研究和开发工作。本研究根据达明公司物流配送业务的运作及管理需求，研究开 达明物流配送系统捌划与设计 发一套以满足企业的物流配送运作要求为目的物流配送系统，实现配送作业的智 能运作和控制，它包括配送路线优化、智能车辆调度和监控和配送信息处理等功 能。在整个系统的建立和应用中，主要针对企业的实际情况和要求，选择和开发 合适的系统架构、运算模型和软硬件配置以实现系统在企业中的实际运作。 1 3 研究工作的主要内容与章节安排 本研究以达明公司物流配送为背景，针对该公司配送系统的建立进行规划与 设计并实现系统在配送作业中的实掩与应用。主要的研究工作如下： 1 分析达明公司的物流配送的运作，建立适合公司配送系统运作的数学模 型，并运用遗传算法及程序求解配送系统模型。 2 通过数学模型及运算验证达明公司物流配送系统的路径的优化功能，为 企业配送计划及调度提供路径及车辆调度方案，达到优化配送、节省成 本、提高效率的目的。 3 应用g p s 、g i s 、g s m 等技术，实现信息采集、命令发送及信息共享，实现 企业物流配送系统的自动化及物流配送监控智能化。 4 合作开发达明物流配送系统运作平台，包括软硬件、各运作模组、数据 库等。 一 5 完成整套系统在公司物流配送中的安装调试及应用分析，实验证明效果 较好，具有应用推广价值。 根据问题的性质和内容，本研究的章节安排如下： 第一章就本研究选题的背景、意义与动机作简要的说明。物流业的发展与信 息、通讯技术的应用结合使物流运作的电脑化与智能化成为物流业节省成本、提 高效率和竞争力的关键。本研究正是在这一背景下，对达明发展公司的物流配送 系统进行规划与设计。 第二章主要介绍了有关物流方面的理论以及巡回旅行商途径问题( t s p ) ， 探讨在后几章将用到的有关在物流配送方面的数学模型及遗传算法。 第三章根据达明公司物流配送的实际情况就配送作业建立数学模型、通过参 数的设定分析，运用遗传算法求解模型，运算出多客户点的最优路径途程选择。 第四章运用g p s g i s g s 5 l i 技术和软硬件系统设计达明公司配送系统的运作平 达明物流配送系统规划与设计 台，包括g p s 网络、通信平台及配送系统控制管理中心。实现系统配送途程最优、 车辆智能监控、信息通讯与存储等功能。 第五章介绍了配送系统在配送作业中的实际应用情况。 最后对本文所做的主要工作进行总结，并指出本文所做工作和主要创新点， 总结所做工作的不足，指出了在今后的研究工作中要继续深入的环节及系统要完 善的地方，并作展望。 达明物流配送系统规划与设计 2 1 物流理论 第二章理论基础 随着物流业的发展，物流理论己形成了一个体系，物流的管理与运作在实践中4 i 断提 5 1 。物流理论在物流实践总结中发展并指导物流运作的发展方向。本研究就物流配送系统所 席用的物流背景及相关物流理论进行探讨。 ， 2 1 1 物流与供应链管理 2 1 1 1 物流的概念、功能与发展 物流可以从不同角度进行定义，在国际上，最普遍采用的是美国物流协会 ( t h ec o u n c i lo fl o g i s t i c sm a n a g e m e n t ，简称c l m ) 的定义。而其观念会因为环 境时间的演变而有不同的解释“3 。 在1 9 6 2 年的定义是包括制成品由制造商运送到顾客的活动与功能。1 9 7 6 年 则扩大范围，把原料、制程中存货的运送、储存的功能也都包含了进去。1 9 8 6 年 c l m 对物流定义为符合顾客的需要，对原料、制程中存货、制程品与相关信息， 从其起运点至最终消费点之间所做的讲求效率与成本节省的规划、执行与控制的 过程。1 9 9 1 年c l m 对物流管理的定义除了原本实体部分的管理外，也同样重视 无形服务与信息流的管理。由以上我们可以了解物流管理不仅强调有形的实体流 还重视无形的信息流，涵盖的范围则包括两大部分，从供货商提供原料给制造商 生产的实体供给，以及从工厂生产物品运送到顾客手上的实体配送。这两大部分 也就是p o r t e r ( 1 9 8 5 ) 价值链分析中所提到的入向物流( i n b o u n dl o g is t i c s ) 与出 向物流( o u t b o u n dl o g i s t i c s ) 。 物流的功能包括运输、储存、包装、装卸搬运、流通加工、信息处理。其内 容包括” 1 物品的移动，需使用搬运的工具、设备，而有装载、卸货的活动。 2 在装载之前，需有集货、包装的活动。 3 在移动之前，可能需有暂时停留、储存，即保管的活动。 4 输送是指大量运输( t r a n s p o r t a t i o n ) 或少量配送( d i s t r i b u t i o n ) 活动。 5 流通加工是指依照客户的要求，对制成品的包装状态加以改变，例如：替 达明物流配送系统规划与设计 客户标价、依客户指定的个数重新包装等作业。 6 物流与信息可谓是一体的两面，密不可分，因此信息是物流机能最重要的 支持活动。 狭义的物流( p h y s i c a ll o g i s t i c s ) 定义指的是实体配送的部分，也就是如何 将产品以最有效率的方式由工厂送到消费者的手中：广义而言，整合的物流管理 ( b u s i n e s sl o g i s t i c s ) 即为供应链管理，国外部分学者并认为物流j 一词与供 应链管理j 同义”1 。一般而言，物流与供应链管理的关系代表一连串的演进过程。 r o s s 认为”1 ：过去三十年来，物流已经从单纯的作业功能演变成今日主要的制 造及配销公司的基本策略要素。他也进一步将供应链管理的发展沿革分成四个阶 段： 第一阶段( 1 9 6 0 s 以前) ：此阶段为仓储与运输阶段( 主要是对下游的实体配 送) ，组织采分布式功能，物流功能包含于其它企业流程中。管理焦点着重于作 业绩效。第二阶段( 1 9 7 0 s 1 9 8 0 s ) ：全面成本管理阶段，功能集中化，管理焦 点着重于作业最佳化，并强调成本与顾客服务。第三阶段( 1 9 8 0 s 1 9 9 0 s ) ：整 合物流管理阶段，将相关的物流功能( 如物料管理、采购、生产计画) 整合。管理 焦点着重于战术性策略性物流规划。第四阶段( 1 9 9 0 s 2 0 0 0 + ) ：供应链管理阶 段，主要根据供货商、制造商、物流商与顾客，发展伙伴关系或虚拟组织设计以 成为联盟关系。管理焦点着重整体供应链的愿景及目标。 2 1 1 2 供应链管理的内涵 供应链管理相关的用语繁多，各个学者的定义也不尽相同，以下将列举数位 学者对于供应链管理所下的批注： d a v i d 等学者( 2 0 0 0 ) 0 1 ：供应链管理为一连串整合的方法，用以有效率 的整合供货商、制造商、仓储业与零售业，并使得商品在适当的数量、地点与时 间被生产与配送，且在满足服务水准的前提下，使得整个系统的成本最小。j m a b e r t 和v e n k a t a r a m a n a n 嘲认为在今日全球经济竞争的影晌下，供应链所 扮演的角色越来越重要，而且供应链将会构成一个动态且复杂的管理程序。供应 链的产品流，必须透过价值链( v a l u ec h a i n ) 来完成顾客所需的产品与服务。 供应链就是利用整合的方式使得制造更有弹性、配送更有效率以及提高信息的可 用性，同时避免传统上只追求各别活动绩效而忽略整体系统活动绩效的弊病。他 达明物流配送系统舰划与设计 们并指出供应链是一流动的网络架构，其内容活动包含有：产品发展的执行、供 应商物料的采购、设备问物料的流动、产品的制造、完成品的配销、售后服务的 支持和保证等功能。而供应链强调的是一个有效整合的过程，整合对象包括产品 流、信息流、以及市场销售服务功能。供应链的作业架构可分为血大阶段，此五 个阶段说明了一件产品从原物料到顾客手中的所有程序，分别是搜( s o u r c i n g ) 、 入向物流( i n b o u n dl o g i s t i c s ) 、制造( m a n u f a c t u r i n g ) 、出向物流( o u t b o u n d 1o g i s t i c s ) 、售后服务( a f t e r m a r k e ts e r v i c e ) 等阶段。每一阶段的决策， 所要考虑的因素很多，而且一旦作出决策将会影响其它层级的绩效和成 败，所以如何将供应链中每一层级的决策作有效的链接，将是管理上的一大挑战。 r o s s ”3 认为：供应链管理是一个连续演进的管理哲学，其目的在寻求企 业内部及所有通路中的合作伙伴之间生产性的能力及资源结合一致，使进入一具 高度竞争力，丰富化顾客的供应系统。其焦点在发展创新的解决方案并且将产品、 服务及信息的流动同步化以创造独一无二的、个人化的顾客价值j 。 b e a m o n “0 1 所提出的供应链管理流程中，所包含的复杂功能，可分为两大部 分：( 1 ) 生产与存货计划：在这个部分，主要包含了三个供应链的基本功能，也 就是从产品制造至上游产业，其中包含了供货商、制造工厂及储存工厂等三大组 成。( 2 ) 物流与运输配送：这部分的功能主要是在强调企业物流管理的重要性， 也就是如何于运输配送的过程中达到空间最佳化的效果，这里则包含了转运配 送、经销商或物流中心等机能。 s u p p l i e s m a n u f a c t u r i n l d i s t r i b u t i o n i 需求者用户i 1 供应商 上 t l l运输 l 配送中心 i 1 l ， l1 l 生产与存货 l 运输l 配送中心i 图2 1 供应链流程图 达明物流配送系统规划与设计 2 1 2 第三方物流与配送中心 2 1 2 1 第三方物流概念及在供应链中的作用 第三方物流是指制造企业等生产经营企业为集中精力搞好主管、i k 务，把原 来属于自己处理的物流活动，以合同形式委托给专业物流服务企业，同时通过信 息系统与物流服务公司保持密切联系，以达到物流活动全过程管理和控制的一种 现代物流作业方式。第三方物流供应方可提供多种物流功能、全方位的服务及协 调所有物流功能的亲系。其主要目标是为供应商及客户降低物流费用，同时提高 顾客服务水平。它是第一方( 供应商或生产商) 和第二方( 买主或顾客) 联系的 桥梁。 第三方物流存在的价值体现在以下几方面“”： 1 高物流运作效率物流服务供应商需要有比客户客户更高的运作效率 并能提供较高的成本服务比运作效率提高意味着对每一个最终形成物流的单独 活动进行开发( 如，运输，仓储等) ，并通过作业水平的提高以低成本提供更好的服 务 2 客户运作的整合。第三物流能引入多客户运作，从而使资源得到共享 如由多客户的仓储或运输网络，客户运作可以利用相似的结合起来的资源整合 运作的规模效益成为能取得其它资源共更高的价值，产生递增效益物流供应商 在配送规模下建立物流中心，将货流集合合起来，整合运输通过整合服务合物流 过程的效益与间接成本效益大大增加，不仅使物流配送中心的用户提高了竞争能 力，更提高了服务质量 3 协助发展客户的运作 物流运作的专门化，使物流运作的水平进入整个物流系统综合分析，设计的 层而，第三方物流公司可能在专门技术和系统领域内超越最有潜力的客户的能力 因为客户还要分配资并同时关注其它几个领域在大多数情况下，通过在同一系 统下运作多个客户的运作，供应商可以以更低的费用提供物流服务，一体化整合 使其可能减少运输费用并抵冲资源资金流量的季节性和随机性变动这说明，供 应商的战略是在优秀的表现上竞争而不在于价格上的竞争。 达明物流配送系统规划与设计 2 1 2 2 流配送中心 在物流配送系统中，物流配送中心的成立可以有效的简化配送程序与减少配 送的频率( 如图2 22 3 ) s 1 s 2 s 3 s i s 1 s 2 s 3 s i 供货商( s )零售商( r ) 图2 2 非配送中心的配送模式 供货商( s ) 困 3 r j 零售商( r ) 图2 3 以配送中心为主的配送模式 配送中心“。”“1 是以组织配送性销售或供应，执行实物配送为主要职能的流 通型结点。在配送中心中为了能更好地做送货的编组准备，因此必然需要采取零 星集货、批量进货等种种资源搜集工作和对货物的分整、配备等工作，因此，也 具有集货中心、分货中心的职能。为了更有效地、更高水平的配送，配送中心往 往还有比较强的流通加工能力。配送中心还必须执行货物配备后的送达到户的使 0 ，i 、j = l 、2 、3 、 一n 。有一个推销员从某一城市出发，访问各城市一次且仅一次，再回到原出 发城市，要求找一条最短的巡回路线。用数学模式来说，就是要在一张完全图上 达明物流配送系统规划与设计 找出一条最短的汉弥蹲回路( h a m i t o n 、c y c l e ) 。t s p 问题原属于作业研究中的动 态规划求解其目的也仅只于使旅行总距离最短，但因实际问题的不断扩大，求解 目标的多元化，使用动态规划的作法也因计算的太过繁琐且计算效率太低，渐渐 的不被采用。近来已有渐多的研究在于开发t s p 问题的解法，以求取更佳的求解 效果与效率。几十年来，出现了很多近似优化算法，如近邻法( n e a r e s tn e i g h b o r ) 贪心算法( g r e e d ya l g o r i t h m ) 、最近插入法( n e a r e s ti n s e r t i o n ) 、最远插入 法( f a r t h e s ti n s e r t i o n ) 、双极小生成树法( d o u b l em i n i m u ms p a n n i n gt r e e ) 等等。近年来，有很多解决该问题的较为有效的算法不断被推出，例如f i o p f i e l d 神经网络方法、模拟退火方法及遗传算法。t s p 搜索空间随着城市数n 的增加而增 大，所有的旅程路线组合数为( n 一1 ) ! 2 。5 个城市的情形对应1 2 0 1 0 = 1 2 条路 线，1 0 个城市的情形对应用于6 2 8 0 0 2 0 = 1 8 1 4 4 0 条路线，1 0 0 个城市的情形则对应 有4 6 6 6 3 1 0 “5 条路线在如此庞大的搜索空间中寻求最优解，对于常规方法和现 有的计算工具而言，存在诸多的计算困难借助遗传算法的搜索能力解决t s p i ；j 题 是很自然的想法遗传基因算法是人工智能上一个新的搜寻技巧，它最大的优点 在于其具盲目搜寻以及其同时搜寻各局部最佳解( l o c a lo p t i m a l ) 的优越能力， 使问题即使在简单的已知条件下，一样能快速的获得整体的最佳解。当以遗传算 法则解决巡回旅行商问题这类的组合问题，必须对基本基因法则中的一些运算技 巧有所修改，以符合问题的需求。以g a 解决巡回旅行商问题的技巧，在编码上 有很大的差异，如之前所述，通常编码的型态有两种：二进位型与非二进位型。 解决巡回旅行商问题时，通常所用的即是非二进位型，以下即是常用的二种编码 表示方法”。 ， 1 路径表示法( p a t hr e p r e s e n t a t i o n ) ： 使用非二进位型的字符串表示，来代表城市间的路径顺序。例如个巡回路 径( 2 、1 、5 、4 、3 ) 表示由城市2 出发，接着l 一5 4 3 ，再回到城市2 。 2 邻接表示法( a d j a c e n c yr e p r e s e n t a t i o n ) ： 以第i 个位置所代表的值j 表示下一个将要被拜访的城市位置，例如：一编 码表示为( 3 、5 、2 、1 、4 ) ，其巡回的关系如下： 第1 个位置之值为3 ，( i ，j ) = ( 1 ，3 ) 第2 个位置之值为5 ，( i ，j ) = ( 2 ，5 ) 达明物流配送系统规划与设计 第3 个位置之值为2 ，( i ，j ) = ( 3 ，2 ) 第4 个位置之值为l ，( i ，j ) = ( 4 ，1 ) 第5 个位置之值为4 ，( i ，j ) = ( 5 ，4 ) 即表示其城市的巡回顺序为l 一3 2 5 4 1 。 由于此类型的组合问题在编码上有所不同，所以其运算予也有所差异。为了 维持原有的特性，此类的运算子通常较为复杂，而且常必需针对不同定义的需要 j f i 改变。以下我们将针对巡回旅行商问题，作各种运算子的探讨。 巡回旅行商问题中，各类运算予的变化要以交叉运算子为最火，至于复制及 变异运算子基本上下班变化不大。通常较常见的有顺序交叉运算子( o r d e r r o s s o v e r ：o x ) 、循环交叉运算予( c y c l ec r o s s o v e r ；c x ) 、部分相对交叉运算子 ( p a r t i a lm a p p e dc r o s s o v e r ；p m x ) 、选择交叉运算子( r o p tc r o s o v e r ) 以及链 接重组交叉运算子( e d g er e c o m b i n a t i o nc r o s s o v e r ) 2 3 2 5 2 8 ，而变异运算 子在对此种非2 进位型的编码方式通常采用的是反转运算子( i n v e r s jo n o p e r a t i o n ) 。”。以下将一说明。 1 顺序交叉运算子( o x ) ： n h d a v i s 。”5 = 1 9 8 5 年时所创的，执行0 x 之前需先决定两个交叉点的位置， 如图25 所示，假设切点分别为3 和6 ，位于两切点之间的基因组合完全的移转 到后代相同的位置上，其余的组合取决于第二母染色体，决定的方式为由第一切 点处的基因为起始位置，以不重复的方式顺序决定出后代剩下位置的基因n 们 母：abc ：ghf ：de 母：hde ：fgc ：ba 子： ecb ：ghf ：ad 图2 l 5 顺序查艾子说明 2 循环交叉运算子( c x ) ： c x 最初由o l i v e r 1 所创，它的运作原理是经由一个随机选取的基因为开始点，并依此起点找寻 达明物流配送系统规划与设计 所谓的循环圈，如图2 6 所示，比较母染色体l 与母染色体2 ，假设随机选取母染 色体l 中第四个位置的基因d 为起始点，则以d 取代j 、j 取代e 、e 取代h 、h 取 代g 、g 取代t 、i 取代b 、b 取代f 、f 再回到d 。使得d j e h g i b f 成一循环圈，此 循环圈之基因依照母染色体l 中原有的位置，原封不动的挪入后代。同埋，随机 选取母染色体2 中第一个位置的基因c ，以c 取代a 、a 又回到c ，故c a 成一循环， 在依第二母染色体中的排列植入后代中即完成。 母：abcdefghij 母：cfajhdigbe 子：cbadef6 - hij 图2 6 循环交叉运算子说明 3 部分相对交叉运算子( p m x ) ： 金白格。2 1 有详尽的介绍p 凇，p m x 在执行时与0 x 有点类似，先将随机 选取两切点间的基因组合移转至后代，剩下的则取决于母染色体2 ，但必须依照 f 面两个步骤：第一步骤，不在切点区域中的第二母染色体基因与第一母染色体 有相同位置者( b c ) ，亦移转至后代的相同位置上。第二步骤，其余的以相对于第 一染色体的基因在第二染色体的位置上取代之。”，如图2 7 所示。 母：fbc ：ahg ：de 母：abc ：def ：gh 子：dbc ：ahg ：fe 图2 7 部分相对交叉遣算子说明 4 选择交叉运算子( r o p t ) ： r o p t 有将t s p 中的城市间的距离关系并入考量，一开始先选取母染色体l 中第一个基因为起始点，再来以与邻接城市问的距离大小为判断原则，距离小者 达明物流配送系统规划与设计 为优先。以卜- 图( 2 8 ) 为例，a 为起始点，a 邻接c 、a 邻接g ，且a 、c 距离为1 4 故z k c ，依此类推即可。 罟u - ：acgfbd e 母。， ：g efd cba 子 ： acbgfd e abcdefg a _ _ - 3 91 2窑o4 22 01 4 b3 8 - _ - 5 13 28 36 81 0 c1 25 l _ _ 2 29 l7 35 9 d8 03 22 2 - _ _ - 1 52 96 0 e4 28 39 11 5 _ 4 4 7 5 f2 0鹋7 32 94 4 一- -3 4 o1 41 05 96 07 53 4 _ _ _ 图2 8 选择交叉算子说明 5 链接重组交叉运算予( e d g er e c o m b i n a t i o n ) ： 当t s p 中各个城市间的通路并非完全时，链接重组交叉运算子是一个可行的 运算员，必须先得知如图2 9 的边界图，城市a 与b 、f 、c 、e 相连，城市b 与 a 、c 、d 、f 相连，有了这些讯息后，再依以下的演译法则进行，并以a 、b 、c 、 d 、e 、f 及b 、d 、c 、a 、e 、f 两个母旅程为例，举例说明如下。“： 母一：abcde f 母二：bdcaef 由邻接图中可知 a 邻接城市有bcef b 邻接城市有acdf c 邻接城市有abd d 邻接城市有bce e 邻接城市有adf f 邻接城市有abe 1 从a 、b 中随机选取b 。 达明物流配送系统规划与设计 2 b 之邻接城市有a 、c 、d 、f 。其中c 、d 、f 各拥有两个邻接城市，随机选取c 。 3c 邻接有b 、d 、a 三者，删去b 后尚有d 、a ，故取d 。 4d 邻接有e ，故取f 。 5 e 邻接有f 、a 两者，随机选取a 。 6 仅剩f ，故取f 。 最后所得后代为8 、c 、d 、e 、a 、f 。 图2 9 边界图示 e 6 反转运算子( i n v e r s i o no p e r a t o r ) ： t s p 此种组合性的问题在编码上是采用非二进位的型式，因此无法采用二进 位编码型式下的“0 ”与“1 ”补码互相交叉的变异方式，因此而改采此种反 转对换的方式。假设一母染色体其排列方式如下，并随机选取2 、6 为其对换位 旨：abcdefgh ，则在两对换位置内的端点基因( c 与f ) 做对换，结果如： abfd ecgh ，如此即完成了变异的运算。”。 2 3 物流配送数学描述 物流管理中，配送问题研究可以说是延伸巡回旅行商问题( t z l a v e n g s a l e s m a np r o b l e m ；t s p ) 研究，下面在上一节基础上，建立物流配送问题的数学 描述。 达明物流配送系统规划与设计 2 31 研究模型的建立 本节将为配送中心车辆配送途程问题建立一个解析模式，以作为配送中心发 展智能配送及车辆配送途程决策之基础。 2 3i 1 目标函数之建立 由于现今的环境是讲求顾客服务满意，因此企业必须具备有完整的供应链体 系和信息运筹管理的能力来辅助。而物流配送活动在其管理决策上将扮演重要的 角色，配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路线图， 使得商品能在最快速的时间送达顾客的手中。因此，本研究将以整体车辆途程距 离为解析模式的目标函数。目标函数一所有车辆总配送途程距离”。 2 3 1 2 数学模式 在建立途程闯题解析模式上，由于本研究希望总配送途程距离能最小化，及 在车辆负载限制下能满足顾客的需求，因此本模式的目标函数为各个客户问距离 总和的最小化。 整个解析模式为： m jn j m jz e ： 睦岛l ， l i = ij ( 2 1 ) ( 2 2 ) 吒= ” ( 2 3 ) v rv f w i 属于n ；j 属于n 一 物流中心节点 集合；i ，j 皆大于o ( + q ) - 1 i ，j 属于n ；i ，j 皆大于0 ( 2 4 ) ( 2 5 ) e j ， 邢 峨 默 碟 。 w lw 于属f属 达明物流配送系统规划与设计 i ，k 属于n ，且i k ；i ，k 皆大于o x ：蔓1 v 属于v 掣= o 或1 i ，j 属于n ；i ，k 皆大于o 碟= o 或1 ( 2 6 ) ( 2 7 ) ( 2 8 ) 2 3 1 3 决策变量与限制式 基于以上的数学模式，本节将解释本模式所使用的决策变量及各限制式意 义。 决策变量描述如下： 1 节点：指配送中心及各个顾客点。 2 路径：路径为由物流中心出发经过一个以上的顾客点，再回到物流中心的完整 回路，具有方向性。 3 子路径：路径的子集合。 4 力：有需求的顾客点总数 5 朋所有顾客点之节点集合包含配送中心。 6 雎可使用车辆的集合，含自有车辆及外包车辆。 7 函：车辆的最大装载量。 8 q 。：客户点所需要的产品数量。 9 钟：将节点i 直达节点j 的子路径指派给路径r ，其值为0 或l 。 1 0 碟：将路径r 指派给v 车，其值为。或1 。 l1 4 ：由顾客点i 直接到达顾客点j 所需的距离。 限制式各项描述如下： 1 方程式( 2 2 ) ： 达明物流配送系统规划与设计 每一个路径其所含顾客需求量受每辆车辆负载容量的限制。其中v 属于车辆 集合v ；i ，j 属于节点集合n 。 2 方程式( 2 3 ) ： 每一个顾客需求均需满足，因此所有路径所含之顾客点总和等于顾客点总 数。i 属于n 即表示所有节点；j 属于不含物流中心节点之客，_ 点集合。 3 方程式( 2 4 ) ： p 由于路径有方向性且不可有重复的节点，因此若节点i 与节点j 存在直达之 子路径，则其至多只可存在一条子路径。i ，j 属于节点集合n 。 4 ，方程式( 2 5 ) ： 因为各路径内的节点有接续性，即若存在节点i 至节点j ，则节点j 至另一 节点k 也会存在，且节点i 与k 为不同的节点。其中i 、k 属于节点集合n ，且i k 。 5 方程式( 2 6 ) ： 每一个路径仅能指派给一辆车辆。v 属于车辆集合v ；若值为0 、表示该路径 r 尚未指派给任何车辆，必须将该路径内的顾客点指派给新增的车辆去配送。 6 方程式( 2 7 ) ： 每一个节点i 至节点j 的子路径只有指派及不指派两种状况，以0 表示不指 派：以1 表示指派。i ，j 属于节点集合n 。 7 方程式( 2 8 ) ： 对车辆来说，每一个路径亦只有指派及不指派两种状况，以0 表示不指派； 以1 表示指派。 2 3 2 运算法则的架构及设计 本节首先对途程问题作一个描述，并探讨基因算法在途程问题上的应用，接 着将依照基因算法各个运算单元在本研究中的操作方法作一个介绍。 2 3 2 1 问题描述 本研究的问题定义为：有n 个顾客，顾客与顾客间来去的距离并不一定相等， 试着用基因算法找出一条路径能够到达每一个顾客一次且满足其需求，使得该 路径之距离为最小。基因算法与途程配送专有名词对照如表2 2 ： 达明物流配送系统规划与设汁 表2 2基因演算法与途程问题专有名词对照表 基因演算法 物流途程问题 染色体( c h r o m o o m e ) 巡回路径 基因( g e n e ) 顾客点 等征值( f e a t u r ev a l u e ) 顾客编号 基因型( g e n o t y p e ) ， 路径巡回结构 2 3 2 2 编码、适应函数 使用基因算法求解问题时，必须先将搜寻空间的节点或可行解以编码的方式 表示出来，经过编码后的可行解在自然系统中统称之为染色体，在基因演算过程 中统称之为字符串，每一个染色体由数个基因组成，每一个基因所代表的意义称 之为特征值 在最佳化问题中，因参数本身可能以实数或整数型态出现，所以必须先经过 二进位或其它方式编码后才可以成为染色体。本研究本身由于较偏向于组合上的 问题，因此编码方式直接以节点( 顾客) 编号排列即可，如有8 个节点( 顾客) 的 问题可直接编码为1423 587 6 。 适应函数直接决定了每一个染色体( 字符串) 适应环境的能力，也就是是否 可以生存下去的依据，适应函数的选取通常会依系统设计的要求而来。如果各染 色体( 字符串) 的目标值差距不大或非常接近，则其适应函数值的差距亦可能非 常小，进而导致无法分辨其中的优劣关系，为了凸显染色体之优劣，有些研究借 着加入一些变化以扩大字符串适应函数值的差异。而通常较常用的适应函数调整 方式有下列几项，本研究将不加入以下的扩张方式来调整。 表2 3 基因演算法中适应函数的扩张方式 扩张方式方法描述 线性调整将群体中各字串之适应度函数值差异，以线性关系扩大 乘幂调整利用群体的平均适应度函数值对其标准差之差异来修饰服字串之 适应度函数值 s i g m a 截取将原适应度函数值，以级数倍成长来扩大群体中各字串的差异 达明物流配送系统