（产业经济学专业论文）基于遗传算法的物流运输中的车辆路径问题研究.pdf

对髓鼻犬鞭士论文 y8 6 1 9 9 8 本文建立了基于遗传算法的车辆路径优化闯题的数学模型，用笔者在此基础上编 写的程序来计算实际案例时，可明显提高运输效益。 本文主要研究的是物流运输中的车辆路径优化问题，采用的研究方法是遗传算法。 以遗传算法为依托，通过对车辆路径问题的细致分析，建立起了车辆路径问题的数学 模型，从而得到了车辆路径问题的抽象表示。现代物流是企业继降低物质消耗、提高 劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品 市场竞争力的重要途径。我国物流发展潜力巨大，但是与国外相比有明显的差距。车 辆路径问题对降低物流运输成本具有重要作用以及实际的经济意义，国内外很多学者 对其作了广泛而深入的研究和论述。本文利用车辆路径问题的数学模型，提出了基于 遗传算法的解决方法。看4 用自然数序列作为车辆路径问题的编码方式；遗传算法的个 体选择方法有很多，本文采用了轮盘赌选择法；在交叉算子上引进了“新颖”交叉算 予，并放弃了传统上的单一概率制，转而采用了自适应概率，使在遗传过程的交叉和 变异两大重要过程中，根据个体适应度值的不同采用不同的交叉概率和变异概率；在 进化停止的判断方法上采取了双重判断法。在实际的案例分析中，通过本文方法所得 到的解决方案比案例中原有的解决方案更加优越，所得成本低于案例中原有成本。 关键字：遗传算法车辆路径问题自适应算法“新颖”交叉算子 对井经贸大学磺士论文 a b s t r a c t i nt h i sp a p e r , i ti sa b o u tt h ev e h i c l er o u t i n gp r o b l e m ( v l 强) i nt h el o g i s t i c ，t h es t u d yi s b a s eo i lg e n e t i ca l g o r i t h m 。t h em a t h e m a t i c a lm o d e lo ft h ev r pf o rg ai sb u i l d i nt h i s p a p e r ，ai m p r o v e dg e n e t i ca l g o r i t h mi sp r o p o s e df o rt h ev r p ，t h eg a a v o i d se f f e c t i v e l yt h e c o l n m o ne f f e c t so fe a r l yc o n v e t g e n c ea n dt h ed i v e r s i t yo fp o p u l a t i o ni n t r a d i t i o n a lg e n e t i c a l g o r i t h m m a k eu s eo ft h ec c d i n gm e t h o do ft h en a t u r a ls e q u e n c ef o rt h ev r p ；t h e i n d i v i d u a lc h o i c em e t h o di sl o t s , t h i st e x ta d o p t e dad i s hw a g e rc h o i c em e t h o d ；g a v eu pt h e t h et r a d i t i o np r o b a b i l i t ys y s t e m ，b u ta d o p t e df r o ma t u o a d a p t i o np r o b a b i l i t ys y s t e m ，m a k ea t i n h e r i tt h ep r o c e s st ot h ec r o s sa n dt h ev a r i a t i o nw h i c ha r et w oi m p o r t a n tp r o c e s s e so f ， a c c o r d i n g t ot h ev a l u eo ft h ei n d i v i d u a lo r i e n t a t i o no fa d o p t i o nt oc r o s sd i f f e r e n t l ya l lr a t e a n dv a r i a t i o na l lr a t e i m p r o v et h ee x i s t e n c ea b i l i t yo ft h ee x c e l l e n ti n d i v i d u a l ，g u a r a n t e e d t h ew h o l eh e a l t h yo ft h ee v o l u t i o nt h a tg r o w sa tt h es a m et i m e t h i sa l g o r i t h mc a nf i n dt h e o p t i m a l o rn e a r l yo p t i m a ls o l u t i o nt ot h ev e h i c l er o u t i n gp r o b l e me f f e c t i v e l y ，w h i c hi s p r o v e db yan u m b e ro fe x p e r i m e n t sp r o v i d e db yt h i sp a p e r k e y w o r d s ：g e n e t i ca l g o r i t h m ；v e h i c l er o u t i n gp r o b l e m ；a u t o a d a p t i o n a r i t h m e t i c ，c r o s s o v e ro p e r a t o r ； 2 对外妊贸大学磺士论文 第一章缭论 在刚刚闭幕的两会上，国家提出了“十一五规划”的宏伟蓝图，提出了经济建设 的新的习标和要求。相信在未来的五年中，我困的经济增长会上一个新的台阶。 在现代的经济发展中，榜流所起的作用越来越重要，如何有效地降低物流成本， 提高物流效率是众多专家学者专研的问鼷。本文研究的是物流运输的一个薰要方丽， 车辆路径优化问题。本文应用遗传算法，提出了车辆路径优化问题1 的有效解决方案。 通过多方面的案例分析，最终证明了本文的解决方案是切实可行的，是可以有效降低 物流运输成本的。 1 1 研究的意义和背景 物流通常是指有经济意义的物质实体从产品供应方向需求方的移动过程。简单地 说，物流是介于生产与消费之间的经济活动，包括运输、保管、装卸、配送、流通加 工、物流信息处理等多项基本活动。当前，现代物流是企业继降低物质消耗、提商劳 动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产晶市 场竞争力的重要途径。现代物流业包括信息业、配送业、仓储业、多式联运业和商品 交易业。我国对物流的专业研究起步较晚，而物流业的发展也只是近几年才开始受到 关注的。中国运输协会指出，中国居高不下的货物运输成本需要引起高度重视我国 的货物运输成本是西方发达国家的3 倍，物流费用占货品总成本多达3 0 噼。 物流配送是物流系统中的一个重要环节，物流配送过程主要包括以下几个作、环 节： 1 、从生产工厂进货或运达并集结的集货作业； 2 、根据各个客户的不同需求，在物流中心将所需要的货物挑选出来的分货和配货 作业； 3 、考虑配送货物的重量和体积，充分利用车辆的载重和容积的货物配装作业： 4 、合理确定车辆配送路线弗及时送货的作业。 就我周汽车零配件生产来漉，其加工装配时间仅为2 ，其余9 8 的时间为原材料、 零配件的储存、装卸和搬运时间3 。此外，在各种产品的生产和流通环节中还有大量原 材料、零部件和产品的“库存”。这些费用和时间上的消耗和大量存在的“库存”l f 是潜在的实施物流管理的领域，同时也为物流的发展留下了巨大的空闰j 。在这种形势 f ，研究如何通过实施科学的物流管理，以提高物流效率、降低物流成本、提高服务 质量是十分必要的。 1 乍辆路幢优化问藤往相关的学术掰f 究中一般称为乍辆路径问题，奉义沿用。 2 中园物流信息中心2 0 0 4 年报 3 蕻延光多重运输闷鼯的遗传算法及其遗传局部搜索系统工程理论与实践1 9 9 7 年 对外经贸太学礤士论文 一般说来，物流配送运输调度是指配送中心按照不同客户的多频度、小批薰的订 货要求进行组织配送，其主要内容指根据确定的配送货物量分配车辆和选择优化路线， 这也就是广受关注的v r p 问题( v e h i c l er o u t i n gp r o b l e m ，即车辆路径问题，也是本 文研究的重点) 、v s p 问题( v e h i c l es c h e d u l i n gp r o b l e m ，即车辆调度问题) 和湃s p 问题( m u l t i p l et r a v e l i n gs a l e s m a np r o b l e m ，即多路旅行商闻题) 。由于从事物流配 送的汽车货运工作尤其是从事城市配送的汽车货运工作条件复杂，不仅货运点多、货 物种类繁多、道路网复杂，丽且运输服务地区内运输网点的分布也并不均匀，同时， 很多客户还针对配送时问提出了要求。因此，如何应用现代数学方法及计算机快速求 解优化调度方案是国内外专家学者普遍探索的熏要课题。 本文主要研究的是车辆路径优化问题，即v r p 问题。通逮对车辆路径问题的系统 研究，建立起数学模型。同时，利用遗传算法，用自然序列编码方式以及新颖交叉算 子，构建一个车辆路径问题的遗传算法解决方案。在遗传算法中的重要环节交叉概率 和变异概率的选择上，没有采用传统的定值方式，而是采用了自适应算子，可以根据 个体的适应度值动态改变交叉概率和变异概率，在保证了优良个体可以发挥优势作用 的同时又进一步避免了早熟收敛现象的发生。这对我国物流行业改良车辆运输路线方 案有蓿积极的作用，也对基于遗传算法的物流的车辆路径问题的研究有着重要的参考 价值。因此，本论文可以说具有较强的理论和实践意义。 1 2 问题描述 通常车辆路径闽题可以描述如下。假定配送中心最多可以用m 辆车对n 个商店进 行运输配送，每个车辆载重为b i 0 = i ，2 ，3 ，b ) ，每个商店的需求量为d i ( i = l ，2 ，d ) ， 商店i 到商店j 的运输成本为g 。，商店i 到配送中心的成本为c i o 或c o 。( i , j = 1 2 ，n ) ， 车辆的载重能力可以满足任意一个商店的要求。忽略体积因素，在满足各商店配送需 求且不超载的情况下，如何安排每辆车的行驶路径，使总的运输成本最低。 1 3 国内外的相关研究状况 因为车辆路径问题有着其现实的经济意义和学术意义，所以因内外的专家学崩开 展了广泛的研究，并取得了令人瞩目的成果，为后来人的继续研究提供了搬商的借鉴 参考作用。 同时，遗传算法由于其应用广泛、易于操作、收敛性商的特点，也被普遍的应用 与人工智能的各个领域，在n p 问题方面也有很深入的研究成果。 书节简要介绍车辆路径问题和遗传算法研究的影响比较大的研究成梁，x ， 暂 的详细介绍将在后面的章节展开。 对外经贸大学颈士论文 1 。3 1 车辆路径问曩研究状况 车辆路线p - j l ( v e m d e r o u t i n g p r o b l e m ，v l t p 撤广泛讨论。自d a n t z i g 和r a m r 在1 9 5 9 年提出v r p 以后，己经产生出多种成熟的冀法。典型的车辆路线问题的相关 文献有： g i l l c t m i l l e rf 1 9 7 4 ) 提出的扫描法( s w e e pm e t h o d ) 4 ，目的在予求解车辆调度问题， 并针对当时几个求解相似问题的算法进行比较，证明该算法所求得的解较优于其它的 方法。 w i l l a r d ( 1 9 8 9 ) s 首先将禁忌搜寻法应用于车辆路线问题上，设计重复的虚拟物流中 心，将车辆路线问题转换成旅行商问题( t s p ) ，利用2 - o p t 或3 - o p t 方法求解车辆路线。 g e n d r e a u ，h e r t za n dl a p o r t e ( 1 9 9 4 ) 6 使用插入法求解旅行蔼问题，荐用贪婪法 f g r e e d ym e t h o d ) 进行路线切割，从而产生初始解。 b a r b a r o s o g l u & o z g u r ( 1 9 9 9 ) 7 乖j 用禁忌搜寻法为土耳其某物流公司构建一决定货车 配送点顺序的方法d e r a b a ，以二种乱数选取节点的方法产生初始解，找到其中最佳 的解作为初始解，再以插入法( i n s e r t i o np r o c e d u r e ) 作为搜寻邻近解的移步方法，最 后以2 o 口t 改善方法找到最伉解的值。 s u c h e n ( 1 9 9 9 ) 8 成功地将自组织影射网络应用在车辆配送区域及路线规划问题 的求解上，其算法的主要概念是利用类神经网络快速运算、自我组织与平行处理的特 性，配合m 个一维环状网络拓手卜来表现车辆路线配送问题。 1 3 2 遗传算法的研究状况 近几年，遗传算法全局收敛性分析取得了突破性进展。g o l d b e r g 和s e g r e s t 首先使用 m a r k o v 链分析了一个极为简单的遗传算法的性能；e i b e n 等用m a r k o v 链证明了4 类基 于保留最优个体的抽象g a 的全局收敛性；f o g e l 分析了没有变舜算子的g a 的渐近收敛 性；s u z u k i 用m a r k o v 链状态转移矩阵的特征根分析了g a 的收敛行为；q i 和p a l m i e r i ：基 4 m f i l e r l r a n db e g i l l e t h e u r i s t i ca l g o r i t h mf o r 【b ev e h i c l e d i s p a t c hp r o b l e m o p e r a t i o n r e s e a r c h l c l 1 9 7 4 v o l2 2 ：3 4 0 - 3 4 9 3 w i l l a r d ，ja g v e h i c l er o u t i n gu s i n gp - o p t i m a lt a b us e a r c h m s t h e s i s c 】，m a n a g e m e n t s c h o o l i m p e r i a lc o l l e g e l o n d o n 。1 9 8 9 6g e n d f c a u m a h e r t z t a n dg l a p o r t e at a b us e a r c hh e u r i s t i cf o rl b cv e h i c l er o u t i n gp r o b l e m m a n a g e m e n t s c i e n c e c 1 1 9 9 4 v 0 1 4 0 ：1 0 t 2 7 6 1 2 9 0 b a d ) a r o s o g t u tga n dd o z g u r a l a b us e a r c ha l g o r l t h a lt o t f h cv e h i c l er o u t i n gp r o b l e m ( ；o m p u t c r s & o p e r a t i o n sr e s e a r c h f m i 1 9 9 9v 0 1 ：2 6 2 _ 5 5 - 2 7 0 8c t s ua n d h h ( ：h e n ；v c h i c l e r o u t i n g d e s i g n o f p h y s i c a l d i s t r i b u t i o n c e n t e r ，j t ) u i u a lo f t h e c h i n e s e l n s t i t u t e o 4 i n d u s t r i a le n g i n e e r s t j 1 9 9 9 v 0 1 1 6 ：3 ，4 t 0 4 1 7 对外经贸大学颧士论文 于m a r k o v 链对浮点数编码的遗传算法进行了严密的数学分折，但其分析基于群体无穷 大这一假设；r d u o l p h 用齐次m a t k o v 链证明了标准遗传算法收敛不到全局最优解，若采 用保留最优个体的选择机制，则改进的g a 全局牧敛；王鼹薇等用类分析方法分析了g a 的收敛性；李书全锌用随机泛涵分析证明了保留最优个体g a 的全局收敛性；田军用 m a r k o v 链和随机摄动理论证明了g a 进入最小能量集的条件滦艳謇等用m a r k o v 链研 究了慕于扩展串的等价遗传算法的收敛性：张讲社等提出了一类非齐次、保证收敛且容 易判断是否收敛的新型g a , 证明了算法收敛的充要条件。该算法收敛速度快，有极强的 避免早熟的全局优化能力，具有合理的停机标准。 4 对井经贸大学碗士论文 第二章物流的发展状况 按照1 9 9 8 年，美国物流管理协会( c o u n c i lo f 她i s t i c sm a n a g e m e n t , c i m ) 对物流 的定义，物流是“供应链过程中的一部分，是以满足客户需求为目的的，以高效和经济 的手段来组织产品、服务以及相关信息从供应到消费的运动和储存的计划、执行和控 制的过程”。 2 。1 发达国家的物漉发展状况 2 0 世纪8 0 年代以后，随着人们对物流的认识逐渐深入，物流业成为西方发达国家 社会发展中最引人注目和极具价值潜力的薪领域，受到各国政府、企业和研究部门的 高度重视，并取得了巨大的发展。 发达国家的物流发展状况主要几种的表现在以下四个方两。 一、第三方物流的蓬勃发展。 第三方物流( t h i r dp a r t y 【d 画s t i c s 仰l ) 的快速增长是美国现代物流发展的最显著 特征，根据阿姆颤特朗物流咨询公司( a r s t r o n g a s s o c i a t e ) 的统计，1 9 9 7 年美国第三 方物流企业的总收入为3 4 2 亿美元，而1 9 9 8 年则达到了3 9 4 亿美元，增长率为1 5 ，2 0 0 0 年则达到5 0 0 亿美元，预计今后3 年内将以平均2 3 的速度增长。 欧洲的第三方物流的发展也是极为迅速的，各国的t p l 在整个国内市场占据的比 例大部分在2 0 以上，英国更是达到了3 5 的恐怖数字。 此外，日本、新加坡、香港的四l 业都相当发达，日本的讦l 占整个物流市场的 比率己经达到了8 0 。1 1 p l 的业绩和物流市场化程度已经成为各国或地区现代物流业 发展水平的一个重要标志。 二、各种层次的物流节点数量增多、功能增强。 物流节点可分为配送中心、物流中心或物漉基地等几个层次。其中发达圈家配送 中心的发展最有代表性。美国的配送中心有数力| 家，仅公用性的大型配送中心就自2 5 0 家。据估计，发达国家的食品、服装、家电等产品配送率已高达5 0 一9 0 ，部分原材 料的供应也在纳入配送的范围之内，传统批发业正被现代的配送中心所取代。 例如零售业巨子沃尔玛在全美设有3 0 个配送中心。其中，商品公司所耩的配送中 【二、投资舰模为7 0 0 0 力美元，建筑面积达1 2 乃n 1 2 。还甜h 本在各大城市建奇。j 近3 ( j 个物流中一0 或物流基地。为了提高物流效率，在东京近郊的东西南北分别建屯了葛龋、 对外经贸大学硕士论文 和平岛、板桥和足力四个现代化的物流基地。其中，和平岛物流基地占地5 0 万m 2 ， 耗资5 7 2 亿目元。 三、策略联盟是嗣两；物流业的新趋势。 2 0 世纪9 0 年代初。美国经济学家哈爨提出了“核心能力”理论。在“核心能力” 理论的指导下，西方企业的多元化经营思想也开始受到冲击。为了既保持竞争优势又 减少经营风险。越来越多的企业开始走向策略联盟，丽相当一部分企业的策略联盟就 是从物流领域开始的。沃尔玛的成功经验之一，就是在物流方面与供应商建立了策略 联盟，始终使自己保持低成本经营的状态。 专业的物流企业开展物流配送，既可以依托下游的零售( 连锁) 企业，成为众多零售 店铺的配送中心，也可以依托上游的生产企业，成为众多生产企业的物流总代理。在 发达国家，这两种类型的企业相互配合、共同发展。 事实上，除了工商企业与物流企业之闻和工商企业内部的物流联盟外，各类物流 企业之间的结盟也在兴起。2 0 世纪9 0 年代以_ 柬，世界级的大型物流企业的并蚴、重组 和联合已屡见不鲜。为了适应其他经济行业大合并的需要，整个第三方物流业的策略 联盟已势在必行，而且会持续较长一段时间。 四、政府积极推进，设立物流协作机制。 由于包括发达国家在内的绝大多数国家的传统物流业都是分部门、分行业进行管 理的，所以现代物流发展过程中的协调机制必须依靠政府的参与才能实现。 现代物流在日本经济中占有重要地位。于1 9 9 7 年联合制定了综合物流施政大纲， 提出了一系列加快物流业发展的改革措施。同年日本运输省和通产省还共同筹建了物 流电子信息交换委员会，中央设立了由有关省厅组成的综合物流施策促进会。 韩国于2 0 0 0 年初决定由海运部、产业资源郝、交通部、贸易协会、货主协会。海 运和航空公司等部门和单位组成一个“官民”体的“物流改善协议会”。该协议会将 对海运法进行修改，删掉货物运费辟j 由运输公司单方面决定的原有条文。协议会还将 定期召开会议，充分听取物流供应商、货主、外贸部1 的意见，加强协商，使韩国的 物流费用标准与国际物流费用标准接近，从而提高本国产品在国际市场上的竞争力。 目前，美国和许多欧洲国家都设有政府参与的物流费用协商机构，其参加的j i 体 为食业，组织机构较为松散。：其t 要任务足协凋物流供需价格既要驶物流赞- f j “肥 6 对外经贸大学硬士论文 水”不外流，又要保证本国出口产晶的竞争力。9 2 2 我国的物流发晨状况 发达国家的物流研究和应用起步比较草，对其冀要性也有充分的认识，现在已经 取得了事硕的成果。我国的物流行业起步较晚，但是发展潜力很大，有着广阔的可发 展空间。 我国的物流行业和发达国家相比起步较晚，最早传入中国是在8 0 年代初期，当时 叫做“p h y s i c a l d i s t r i b u t i o n ”，中文直译就是“实物流通”或“实体分配”。后被称作“物 流”并一直沿用至今。2 0 0 1 年8 月l 曰，国家出台国家标准物流术语并正式实施。 在国家标准 0 ，i = l ，2 ，n ( 1 0 ) b k 加，k = l ，2 ，m( 1 1 ) m 0 , n 0( 1 2 ) 其中，式( 1 ) 表示目标函数整个配送过程中运输成本的最小化；式( 2 ) 表示某个需求点 有且仅有一辆车访问；式( 3 ) 表示各运输车辆均从配送中心出发，经过需求点后，最后要 回到配送中心；式( 4 ) 表示每个需求点都有一辆车经过；式( 5 ) 表示车辆的装载璧大予其所 访问的需求点的需求量，即不出现超载情况发生；式( 6 ) 表示i 点到j 点的运输费用与j 点 到i 点的运输费用相等；式( 7 x s x 9 ) ( 1 0 x 1 1 ) 和( 1 2 ) 均为变量的取馕范围。 3 3 其他方法 3 3 1 动态规划法 1 8 5 7 年，英国数学家汉密尔顿( h a m i l t o n ) 提出了著名的汉密尔顿回路问题，其后， 该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题，这 两个问题成为数学史上著名的难题。1 9 运输问题和工作指派问题是一类古老的问题，其 解法也相当的完善而网络运输阀题及其求解也因最小费用最大流算法的电已经基本完 成。但是其思想却被广泛应用于各类的任务分配模型中。其中值得一提的是动态规划 更是此类问题建模和求解的一个藿要的方法，这是由于这类问题多数属于撼数规划问 题，其求解也多属于n - p 问题，因此很难找到精确的解丰厅解。随着计算机技术的发展， 汁算处理能力的不断提高，动态规划思您在这类问题中的应用比将盟得同益重要。 动态规划是一种常用的运筹学方法，它适于解决这样的问题：某个大问题可以划 分为几个阶段，每个阶段形成一个子问题，各个阶段是相互联系的，每个阶段都要做 出决策，并且某个阶段的决策，常影响f 一阶段的决策，从而影响整体决策。在动态 觇划求解过程中，作为整个过程的最优策略只：行这样的性质：无论过去的：状态和决策 1 9 h o l l a n dj h 。a d a p t a t i o n i n n a m r ma n d a r t i f i c i a ls y s t e m s m i t p r c s s n 1 9 7 5 对外经贸大学硬士论文 如何，对其决策所形成的状态而言，余下的诸决策必须构成最优策略，这是动态援划 的最优化原理。利用这个原理可以把多阶段决策的求解过程看成是一个连续的递摊过 程，由后向前逐步推算在求解时，各状态前面的状态和决策，对其后面豹子问题丽 言，只不过相当予其初始条件而己，并不影响后面过程的最优策略。动态规趔| 求解问 题的一个突出弱点是：当问题中的变量个太多时，将会由于计算机存储器容量和计算 速度的限制而无法求解。 用动态规划法求解物流配送的车辆路径问题的思路如下：设有n 个城市，以l ， 2 ，n 表示，d i i 表示从i 城市到j 城市的距离。一个推销员从城市1 出发到其他每 个城市去一次且仅仅一次，然后回到城市1 ，应该如何选择行走路线，使总路程最短。 设s 表示到达l 城市之前中途所经过的城市集会。选取( ，s ) 作为描述过程的状态变 量，定义f k ( i ，s ) 为从l 城市出发经由k 个中问城市的s 集到i 城市的煅短路线的 距离，则 k ( i ，s ) = r a i n ( f k ，1 ( i ，s 、j + d j i ， ( k = l ，2 ，n - 1 ，i = 2 ，3 ，n ) 边界条件为f o ( i f ) = d “ p k ( i ，s ) 为最优决策函数，它表示从1 城市出发经k 个中间城市的s 集到i 城 市的f k ( i ，s ) 壹至求出f n 1 ( i ，n 1 ) ，其中n 1 表示从l 城市出发回到l 城市的所有 最短路线上紧挨着i 城市前面的城市。这样，我们可以从k = 0 出发依次求出中闻城 市集合。 3 3 2 启发式算法 启发式源自英文单词h e u r i s t i c s ，启发式方法意为通过对过去经验的归纳推理以及 试验分析来解决问题的方法，即借助于某种直观推断或试探的方法。启发式方法要求 分析人员必须运用自己的感知和洞察力，从与研究问题有关而比较基本的模型及算法 中寻求其问的联系，从中得到启发，去发现适于解决该问题的思路和途经。辟j 启发式 方法解决问题时强调“满意”，常常是得到满意解，决策者就认为可以了。而不去追求 最优解和探求最优解。之所以这样，其原因是： ( 1 ) 很多问题不存在严格最优解( 例如目标之间矛盾的多目标问题) ，这时，对日 际的满意性常比最优性更能准确地描述人们地选择行为。 ( 2 ) 对有些问题，得到它的最优解所花的代价太大。 ( 3 ) 从实际决策的需要出发，有时要求解具有过商的精度没有意义。启发式方法 7 对井经贸大学磺士论文 能够比较快地得到满意解，这对解决n p 难愿来说有着不可估量的作用。 用启发式方法求解问题是通过迭代过程实现的，因而需拟定出一套解的搜索规则。 为能得到满意解，在整个迭代过程中要不断吸收新的信息，必要时改变原来拟定的不 合适的镱略，建立新的搜索规则，注意从失败中吸取教训，并逐步缩小搜索范围。 c - w 节约启发式算法c w 算法由c l a r k e 和w r i g h t 提出，该算法简单易用，它 的基本思想是酋先把各点单独与源点o 传：场) 相连，构成1 条仅含一个点的线路。然 后计算将点j 和j 连接在一条线路上费用的“节约值”s ( i ，j ) ，s ( i ，j ) 越大，说明把i 和j 连接在一起时总路程减少越多。构造线路时，根据s ( i ，j ) 从大n d , 的顺序进行， 实现时可在表上操作。 此外还有扫描法，禁忌搜索算法、模拟遇火算法、神经网络法等。这些算法的也 现为求解物流配送的车辆路径问题提供了新的工具。 扫描法是由g i l l e t 和m i l l e r 于1 9 7 4 年提出的2 0 ，该方法的基本思路是采用逐次逼 近的方法求解物流配送的车辆路径闷题。利用扫描法求解物流配送的车辆路径问题时， 物流中心及客户的位置都用极坐标表示，其中物流中心位于坐标原点。 禁忌搜索( t a b us e a r c h ，t s ) 算法，也称列表寻优法，是局部搜索算法( 爬山算法) 的 推广。g l o v e r 在1 9 8 6 年首次提出这一概念2 1 ，进而形成一套完整算法。禁忌搜索算法 的特点是采用禁总技术。为了隧避局部邻域援索易陷入局部最优的不足，禁忌搜索算 法用一个禁忌表记最下己经到达过的局部最优点，在下一次搜索中，利用禁忌表中的 信息不再或有选择地搜索这些点，以此来跳出局部最优点。 模拟退火( s i m u l a t e d a n n e a l i n g ，s a ) 算法也是局部搜索算法的扩展，其特点是以 定的概率选择邻域中目标函数值较差的状态。模拟退火算法的思想最早由m e t r o p o l i s 在1 9 5 3 年提出2 2 ，k i r k p a t r i c k 在1 9 8 3 年成功地将其应用在组合优化问题中婶】。 人工神经网络方法基于以下基本原理：大脑皮层每一点的活力是由其它点势能释 放的综合效能产生。这一势能与下面的因素有关：相关其它点的兴奋次数；兴奋 的强度；与其不相连的其它点所接受的能量2 3 。该原理是构造人工神经网络模型的基 “g i l l e tb e a n d m i l l e r l r a h e u r i s t i e a l g o r i t h m f o r t h e v e h i c l e d i s p a t c hp r o b l e m o p n s r e s m 1 9 7 4 2 2 “o l o v e ref u t u r ep a t h sf o ri n t e r g e rp r o g r a m m i n ga n dl i n k st oa r t i f i c i a li n t e l l i g e n c e c o m p u t e r s a n do p cr m i o n s r e s e a r c h l j i 1 9 8 6 ( 1 3 ) ：5 3 3 5 4 9 m e t r o p o l i sn ，r o s e n b l u t ha r o s e n b l u t hm e ta 1 e q u a t i o no fs t a l ec a l c u l a t i o n sb yf a s tc o m p u t i n gm a cj 1 l l l e n i o u m a lo f c h e m i c a lp h y s i c s j t 9 5 3 ( 2 1 ) ：1 8 7 1 0 9 2 ”j a m e sw p s y c h o l o g y ( b r i e f e rc o u m ) m n e wy o r k ：h o l t 1 9 8 0 对外经贸丈学硪士论文 本依据。 上述几种现代优化计算方法中，神经弼络方法在前几年比较热，但现在已经明鼹 降温，因为它只用一个反传算法，从中很难更深入地开发恩想和信息。丽禁惫搜索算 法、模拟退火算法、遗传算法在求物流配送的车辆路径问题中的应用则刚剐开始，虽 然已有一些研究成果，其潜力还有待于进一步挖掘。 本文将采用遗传算法对物流配送的车辆路径优化问题进行分析。 1 9 对外经贸大学硬士论文 第四章车辆路径瓣穗的毅进遣传算法设计 车辆调度问题( 、，c h i d er o e t i n gp r o b l e m 简称为v r p ) 是一个n p 完全闷邂，只膏在需 点数和踌段数较少时才有可能寻求其精确解。先后涌现出一大批启发式算法，这些算_ 去 为求解车辆路径问题提供了有效的方法，但也存在一系列问题。近年来遗传冀法、神经 网络、禁忌搜索和模拟退火等智能化启发式算法的出现为求解v r p 问胚提供了新的t 具，并且在理论上也取得了一些较好的效果。 4 1 设计的总体流程 本文采用遗传算法设计的解决方案具体流程如下图所示：( 1 ) 通过随机函数初始 化种群得到酋代个体；( 2 ) 计算每个个体的适应度值；( 3 ) 记录下最当代适应度最 大的个体的适应度值，基因代码，函数值：( 4 ) 判断进化代数是否达到了要求，如果 达到则停l e 计算，输出结果，否则则继续进化；( 5 ) 根据适应度值，采用轮虢赌方法 选择下代个体，根据交叉概率进行交叉：( 6 ) 交叉后的个体，根据变异概率进行变 异，最终的到新一代的个体，形成新的种群，并返回( 2 ) 。如图4 1 所示。 异最终的到新一代的个体，形成新的种群，并返回( 2 ) 。如图4 1 所示。 对外经囊大学碛士论文 是 是 图4 1 总体流程 ( 资料来源：本文研究整理) 4 2 构造个体产生初始种群 _ i l一 叶i 三 采用自然数编码，即每个个体( 记为i ) 为1 到n 的自然数的一个全排列，其中各自 然数对应于配送系统中的商店编号。隧机产生p o p s i z e 个如此个体作为初始种群。各个 体中自然数的顺序即为各运输车辆的实际配送顺序，运输车辆的运行起点和终点均为 配送中心，即每次从配送中心出发，完成配送任务后返回配送中心。在算法啤t 引入j 新颢交义算子，即使由两个相同个体进行交叉，依然能产生新的个体，从而摆脱j 传 统交义算f 对群体多样性的要求，同时避免了早熟现象，降低了结粜为0 祁鬣优解的 可能。 囱番番宙阳 对井经贸大学硪士论文 4 3 适应度的计算 根据各商店的需求量及车辆装载量，分别计算出每个个体对应的可行解，即可行 的车辆路径以及所需车辆数。 具体操作如下：针对每个个体，从没有参与累加的第1 个基因开始，逐个累加各 基因对应商店的配送量d i ，如果再累加就超载，即了d lsb ( 简化车辆的载重能力均为 留 x + 1 b ) ，且了d ， b ，当x m 1 ，记录下该次循环的第1 个基因和最后一个基因在集合s 中。 何 如果个体中还存在未参与累加的基因，则进入_ f 次循环，否则，结束：如果己累加到 个体的最后一个基因，但还未发生超载的情况，则将该次循环的第1 个基因和个体的 最后1 个基因，加入s 中，结束。比如个体i - “1 ，2 , 3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ”，器基因 对应商店的配送量分别为“4 8 ，3 6 ，4 3 ，9 2 ，5 7 ，1 6 ，5 6 ，3 0 ，5 7 , 4 7 ，9 1 ，5 5 ，3 8 ”，车辆载熏爨为 2 0 0 。则从第1 个基因“4 8 ”开始累加到第3 个基因“4 3 ”时，总配送量为1 2 7 2 f ) o 即超 载，则将基因“1 ”和“3 ”加入s 中，郎s = 1 ，3 ，完成1 次循环。之后，依此循环 最终得到s = 1 ，3 ，4 ，6 ，7 ，1 0 ，1 1 ，1 3 ，结束。有了个体及其对应的路径起始位， 就可以得到该个体对应的车辆数和各车辆的运行路径，从s 可以得出需运输车辆4 辆， 车辆的运行路径分别为“配送中心商店1 商店2 商店3 配送中心：配送中心商所4 商店5 一商店6 配送中心：配送中心商店7 一商店8 商店9 商店1 0 配送中心；配送中心 一商店1 1 商店1 2 商店1 3 配送中心”。计算的过程可以保证每个个体均为可行解，从阿 避免了运行过程中不可行解的产生，节约资源，提商计算速度。 在此采用适应度函数f i t n e s s ( i ) = 1 v a l u e ( i ) ，i = l ，2 , - - , p o p s i z e ，其中v a l u e ( i ) 为第i ，卜 个体的运输总成本，p o p s i z e 为种群规模。v a l u e ( i ) 的计算过程：第1 步，将个体中的基阑， 从左向右，将每相临两个基因对应商店之间所需运输成本累加；第2 步，将个体关r 商店的起止路径各基因与配送中心的运输成本累加；第3 步，将前两步结果求和；第4 步，计算个体关于商店的起止路径中，去摔开始位及最后位基因后，将剩余基因的奇 数位与其柏临偶数位之间的运输成本累加。第5 步，_ j 第三步计算结果减去第四彤汁 锋结果，即为v a l u e ( i ) 的值。以本 | i p 的例子计算加以髓明。由以上计算j 氪 行a 个体 _ “l ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ”，其对应的关于商店的起止路径s = 1 ，3 ，4 ，6 ，7 ， 对辨经贸大学硬士论文 l o ，1 1 ，1 3 ) 。点与点之闻的运输成本记为d j ，则v a l u e ( i ) = ( c 1 2 + c 2 3 1 - c 3 4 + c 4 5 + c 5 6 + c 6 7 + c 7 8 - b c - i - c g , i o + c i o , l t + c 1 1 ，1 2 + c l 五l 痧p ( c l 白帅+ c 甜铆d + c 1 0 1 0 + c 1 1 o + c ”n h c 3 4 + c c 1 0 ，1 1 ) 。从丽得 到f i t n e s s ( i ) = l v a l u e ( i ) 4 4 循环停止的判断 判断是否达到停止进化条件，如迭代的代数达到要求代数，或结果满足定要求， 若是，则结束，并选择适应度最大的个体及其所对应的路径作为原问题的优化解输出； 否则，进入下一步。 4 5 选择、交叉与变异 选择采用轮盘赌2 4 的方法迸行，选择得到的个体进入下一步交叉和变异。 在每代种群中，以一定的交叉概率对个体进行交叉重组，在此交叉概率采用自适 应概率2 5 ，具体来说自适应交叉概率的公式如下： p c = 抑一亟芒掣， f | i * , i i x 一 a v g p w f f a ，g p 。是种群中个体i l 和i 2 的交叉概率： p 。，。是种群中规定的基础交叉概率； p 。，尾为种群中适应度值大于平均值的个体所采用的精荚交叉概率； f 是个体i 1 和i 2 中适应度值大的个体的适臆度值； 矗。是种群中平均的适应度值： f m 。是种群中最大的适应度值。 这样，可以有效加强优秀个体的遗传能力，保护其进入下一代；对于适应度低_ f 平均值的个体，采用较大的交叉概率，增大弱势个体的淘汰几率。但是同时，义保讧e 了在进化初期优秀个体不会占有完全的主导地位，降低了局部最优解的出现概率。 同时日i 入一种新颖交叉算法，这种算子最大特点是当两个父个体相同时，仍能产 生新的个体，从而减弱了对群体多样性的要求，能够有效地避免传统遗传算法“早熟 收敛”的缺点，这是以往交叉算子所不具备的。该交叉算法在交叉过程中，巧：同于传 2 ” 孙平营立明 遗传算法一理论、应用与软件实地 西安受通太学m 版社2 0 0 2 年2 5 贝 2 5 。r 小中营立明 遗传算法一堡论、应用与软件实现西安变通丈学出版杜2 0 0 2 年3 0 页 对外经贸大学硕士论文 统遗传算法中，直接交换交叉段，雨是将交叉段加入至h 对方个体首都，之后逐个去掉 个体中原个体部分中与交叉段基因相同的基因，从而得到交叉后的个体。举倒说明交 叉过程。如父代两个个体i 每= “1 , 2 ，3 ，4 , 5 ，6 , 7 ，8 ，9 , 1 0 ，1 1 ，1 2 ，1 3 ”，随机产生2 个交叉点为 4 、8 ，即竭= “1 , 2 ，3 ，1 4 , 5 ，6 , 7 ，8 1 9 , 1 0 ，n ，1 2 ，1 3 ”则对2 个个体丽畜，其交叉段同为“4 ，5 、 6 ，7 ，8 ”，则将“4 ，5 ，6 ，7 ，8 ”加到对方个体的蕾部，得到i - - j = “4 , 5 ，6 ，7 ，8 ，1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，l o , l l ，1 2 ，1 3 ”之后，将个体中原个体部分i = = “1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ”中与交叉段“4 ，5 ，6 ，7 ，8 ”相同的基因逐个去掉，从畹 得到交叉后的个体为：蠲= “4 , 5 ，6 ，7 ，8 ，1 ，2 ，3 ，9 ，1 0 , 1 1 ，1 2 ，1 3 ”对于父代2 个体不同的情况与 此操作方法一样。从上例可以看出，即使两父个体相同，仍能产生新的个体，