（管理科学与工程专业论文）车辆路径问题研究.pdf

中文摘要 摘要 随着电子商务的飞速发展，物流产业也发生了新的变革。配送是物流系统中 一个直接与消费者相连的重要环节。运输费用在物流总费用中的比例约5 0 ，因此 降低物流配送的运输成本成为首要考虑的问题。运输线路是否合理对配送的速度、 成本、效益有着直接影响。合适的运输路线，可以加快对客户需求的响应速度， 提高服务质量，增强客户满意度，降低运营成本。本文针对配送中的核心问题一 车辆路径问题( v e h i c l er o u t i n gp r o b l e mv r p ) ，采用遗传算法进行了研究。这对 物流配送企业实现配送路径优化、降低成本和提高物流经营管理水平、更快的响 应顾客，最终增加企业的竞争力具有一定的参考价值。 本文从旅行商问题出发，介绍了车辆路径问题的一般描述及特点；详细介绍 了遗传算法的基本概念，基本原理及流程，遗传算法的应用。将遗传算法的基本 操作用图例表示，使其变得简单易懂；通过遗传算法的基本操作及改进策略相关 详述，为以后算法的改进打下了理论基础。 本文在认真分析国内外对v r p 研究的基础上，运用改进遗传算子策略，对遗 传算法进行了一系列的改进，如采用自然数编码、引入罚函数对约束进行处理、 在遗传算予中选用轮盘赌选择法；p v x 方法进行交叉操作；逆转变异算子。对交叉 算子和变异算子操作产生的不合法个体进行相应改进操作，直到得到合法的子代 个体方可进行下一次迭代。通过m a t l a b 实现该算法，并通过实例证明了该算法 是求解v r p 的一个很好方案。 关键词：遗传算法；车辆路径；选择；交叉；变异 英文摘要 r e s e a r c ho nv e h i c l er o u t i n gp r o b l e m a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fe - c o m m e r c e ，1 0 9 i s t i ci n d u s t r yh a sa l s oe x p e r i e n c e d an e wr e f o r m d i s t r i b u t i o ni sa l li m p o r t a n tl i n ki ni o g i s t i c s ，w h i c hi sj o i n e dt o c o n s u n l c l - sd i r e c t l y , a n dt h ec o s to ft r a n s p o r t a t i o no c c u p i e s5 0 o ft h a ti nw h o l e l o g i s t i c s s o ，r e d u c i n gt h ec o s to f l o g i s t i c sb e g i n sw i t hr e d u c i n gt h mo f t r a n s p o r t a t i o no f i o g i s t i c sd i s t r i b u t i o n i nt h ep r o b l e m ，w h e t h e rt h et r a n s p o r t a t i o nr o u t ei sr a t i o n a lw i l l a f f e c tt h es p e e d ，c o s ta n db e n e f i to fd i s t r i b u t i o n s e l e c t i n gr a t i o n a lv e h i c l e s r o u t ec a n h e l pt oa c h i e v eq u i c k e rr e s p o n s es p e e dt oc u s t o m e r s ，i m p r o v et h eq u a l i t yo fs e r v i c e ， i n c r e a s ec u s t o m e r s s a t i s f a c t i o nt oi o g i s t i c ss y s t e ma n dr e d u c eo p e r a t i o n a lc o s to f s e r v i c em e r c h a n t s t h i sp a p e rh a ss t u d i e dt h ec o r ep r o b l e mo ft h ed i s t r i b u t i o n - v r pb y u s i n gg e n e t i ca l g o r i t h m s ( g a ) s o ，i th a ss o m ev a l u et oi o 百s t i ce n t e r p r i s e st od e c r e a s e t h ec o s t ，t oi m p r o v et h el e v e lo fl o g i s t i c sm a n a g e m e n t ，t or e s p o n s ec b s t o m e r sm o r e q u i c k l ya n dt oi m p r o v et h ef i v a l s h i pp o w e ro f t h ee n t e r p r i s e t h ee s s a y , b e g i n n i n gw i t ht h eg e n e r a la c c o u n to ft s p ，i n t r o d u c e sv r pg e n e r a l d e s c r i p t i o na n df e a t u r e ；e x p l a i n st h eb a s i cc o n c e p t ，p r i n c i p l ea n dp r o c e d u r eo ft h e g e n e t i ca l g o r i t h m i ta l s od i s p l a ys o m em a j o rp r o c e s si nt a b l e sw a y s ，m a k i n gt h eg e n e t i c a l g o r i t h mc o m p r e h e n s i v e t h r o u g ht h eg e n e t i ca l g o r i t h m b a s i c o p e r a t i o n a n d i m p r o v e m e n t , t h ee s s a yl a i dm e t h o df o u n d a t i o nf o r t h el a t e ri m p r o v e m e n to f a l g o r i t h m t h i sp a p e r p u t sf o r w a r da ni m p r o v e dg e n e t i ca l g o r i t h mo nt h eb a s eo fa n a l y s i n g t h er e s e a r c ho nv r pi nc h i n aa n da b r o a d t h ei m p r o v e dg e n e t i ca l g o r i t h mu s e sn a t u r a l c o d i n g ，p e n a l t yf u n c t i o nt os o l v ec o n s t r a i n t s ，i m p r o v e s c r o s s o v e ro p e r a t o r sa n d m u t a t i o no p e r a t o r sa n du s e ss o m eo p c r a t i o u st od e a lw i t hi l l e g a li n d i v i d u a l su n t i lt h e y a r el e g a l a tl a s tw er e a l i z e st h ei m p r o 矾圮g e n e t i ca l g o r i t h mb ym a t l a b t h e a l g o r i t h mg i v e n i nt h i sp a p e rc a no b t a i na l lo p t i m i z e ds o l u t i o ne f f e c t i v e l ya n dh a sb e e n p r o v e dt ob eag o o ds c h e m e t os o l v e 潆 k e yw 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 g ；s e l e c t i o n ；c r o s s o v e r ；m u t a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：奎牺蹬焦闷壁班窟：。除论文中已经注明引用的内容外， 对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文 中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成 果。 本声明的法律责任由本人承担。 论文作者签名：姊年0 7 年弓月加日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 本学位论文属于：保密口 不保密口( 请在以上方框内打“”) 蝌一名；彳旦巧 日期： d 7 年歹月如日 车辆路径问题研究 第1 章绪论 1 1 选题背景及意义 随着网络技术的飞速发展，计算机网络革命给市场带来了新经济。世界通过因特网 变得越来越亲近，每个人的生活都或多或少受其影响。电子商务的知识对今人和未来的 人们在新的全球经济社会中的生存和竞争是必不可少的。值得注意的是中华人民共和 国国民经济和社会发展第十一个五年规划纲要提出了现代物流发展的内容。要求把“物 流配送”作为一个发展的重点，提出“积极发展连锁经营、特许经营、物流配送等现代 流通方式和组织形式”。“十一五”期间是我国信息化建设加速发展的重要时期，在此 期间我国信息技术应用水平将有显著提高，我国电子商务的发展将会登上新的台阶。 根据m i c 研究资料显示，目前适合通过互联网销售的商品可分为两大类：第一类 为数字化商品，如电子书籍、在线音乐及在线游戏等；第二类为信息丰富的商品，如理 财服务及旅游服务等。我国的电子商务水平将会随着网上购物的范围扩大，信息化建设 的加速发展而发展。 尽管如此，物流系统运行低下也是我国电子商务发展的绊脚石，众所周知，电子商 务的交易活动是以i n t e m e t 为主要介质的，然而，物流部分却仍然要采用传统手段。因 此，在加强信息化建设的同时，必须同时建立集信息流、商流、资金流、物流与一体的 现代化的物流配送中心。这就是要建立和完善现有物流配送渠道。研究物流是为了有效 地管理和控制物流的全过程，在保证服务质量的前提下，实现消耗总费用最小的目标。 目前由国家发改委牵头的物流部际协调工作，大力推动第三方物流的发展，发展现代物 流体系。物流业作为企业的“第三利润来源”，备受关注。 据分析研究发现：配送成本在物流的各项成本当中占有相当高的比重，显而易见配 送几乎是物流的半壁江山。物流配送的核心部分，主要就是进行配送车辆优化调度。车 辆路径问题( v e h i c l er o u t i n gp r o b l e mv r p ) 是物流配送调度中具有广泛应用的优化组 合问题，在现代物流中居于中心地位。v r p 成为运筹学与组合优化领域的热点问题。研 究车辆路径问题的特点及算法具有重要的实际意义。 第1 章绪论 所谓的车辆路径问题，简单的说就是车辆和路径的恰当选取，运输规划的合理制定 向题。合理解决车辆路径闯题，不仅可以简化配送程序、降低配送的空载率，减少配送 次数，尤为重要的是可以降低现实世界的交易成本，带来更大的经济效益，而且可加快 对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运 作成本，消除电子商务发展的安全障碍，确保网上交易者获得全面、安全和高质量的服 务也起着不可缺少的作用。如何合理安排车辆路径问题就显得更加重要 1 2 论文的主要工作 在前人关于物流配送中的车辆路径问题、遗传算法、组合优化等问题的求解方面所 做的大量工作的基础上，论文在遗传算法改进方面并将其应用于v r p 中进行了探索和 尝试。本文主要工作如下： ( 1 ) 在考虑v r p 的目标及其各种约束条件的基础上建立了数学模型。 ( 2 ) 根据物流配送的特点和要求，提出了车辆路径设计方案。 ( 3 ) 针对基本遗传算法在应用中遇到的局部搜索能力差、计算量大、早熟收敛等问 题，根据v r p 实际问题的具体情况，通过对基本遗传算法进行改进，提出了相应的改 进遗传算法。 ( 4 ) 将改进遗传算法应用于v r p 求解，并采用m a r l a b 完成了对其算法的实现。 通过具体数据计算分析，验证了改进的遗传算法在v r p 应用中的可行性。 运用遗传算法，不得不谈遗传算法的历史。以下介绍遗传算法的产生与发展。 1 ，3 遗传算法的产生与发展 生命科学与工程科学的相互交叉和渗透产生了基于人工智能的进化优化算法。这类 算法的核心思想源于这样一个基本认识：生物进化过程本身是一个自然的、并行发生的、 稳健的优化过程。这一优化过程的目标是对环境的自适应性；生物种群通过遗传变异来 达到进化的目的， 遗传算法是一种宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与 进化过程，通过模拟达尔文“优胜劣汰、适者生存”的原理鼓励产生更好的结构，同时 车辆路径问题研究 通过模仿孟德尔遗传变异理论在迭代过程中保持已有的结构，并寻找更好的结构。遗传 算法也是通过繁殖、变异、竞争和选择这四种基本形式实现的。 2 0 世纪4 0 年代，有学者开始研究如何利用计算机进行生物模拟的技术。 6 0 年代，h o l l a n d 教授认识到了生物的遗传与自然进化现象与人工自适应系统的相 似关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方 式进行自适应搜索【l l 。 1 9 6 7 年，h o l l a n d 教授的学生b a g l c y 在其博士论文中首次提出了“遗传算法”一词 2 1 ，后来他还发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了 双倍体的编码方法，创立了自适应遗传算法的概念。 7 0 年代初，h o l l a n d 教授提出了遗传算法的基本定理模式定理( s c h e m a t h e o r e m ， 从而奠定了遗传算法的理论基础。 1 9 7 5 年，h o l l a n d 出版第一本系统论述遗传算法和人工自适应系统的专著自然系 统和人工系统的自适应性( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) 【3 】。 1 9 7 5 年，d e j 0 n g 在其博士论文中结合模式定理进行了大量的纯数值函数优化计算 试验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论【4 1 。他还建 立了著名的d e j o n g 五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。 1 9 8 9 年，d e g o l d b c r g 出版了专著搜索、优化和机器学习中的遗传算法( g e n e t i c a l g o r i t h m s i n s e a r c h , o p t i m i z a t i o n a n d m a c h i n e l e a r n i n g ) 【5 】。该书系统的总结了遗传算 法的主要研究成果，奠定了现代遗传算法的科学基础。 1 9 9 1 年，l d a v i s 编辑出版了遗传算法手册( h a n d b o o ko fg e n e t i ca l g o r i t h m s ) 一书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例 0 3 。自 上世纪7 0 年代起，我国学者也将遗传算法广泛的应用于生产实践的各个领域，并取得 许多重要的科研成果 第2 章物流业的发展前景 第2 章物流业的发展前景 2 1 物流业的发展现状 随着科学技术的进步和生产力的发展，顾客消费水平不断提高，企业之间的竞争日 益加剧，加上政治、经济、社会环境的巨大变化，使 ：导整个市场需求的不确定性增加。 企业面对着变化迅速且无法准确预测的市场经济，为了提高竞争力，所有企业都在不断 探索降低费用、提高利润的有效途径我国的物流业尽管起步较晚，但是发展迅速。表 2 1 是我国从1 9 9 6 年至2 0 0 5 年我国物流总额及增长率。 表2 1 中国1 9 9 6 年至2 0 0 5 年物流总额及增长率 t a b 2 1l o g i s t i ct o t a la n di n c r e m e n t a ir a t ef r o m1 9 9 6t o2 0 0 5i nc h i n a 年份( 年)总额( 万亿元)增长率( ) 1 9 9 6 1 1 o 1 9 9 71 2 41 2 7 1 9 9 81 2 94 0 1 9 9 91 3 97 8 2 0 0 01 7 12 3 2 0 0 11 9 51 4 2 0 0 22 3 31 9 5 2 0 0 32 9 52 6 6 2 0 0 4 3 8 43 0 2 2 0 0 54 8 12 5 2 信息来源：中国物流与采购联合会 由表2 1 可以发现我国社会物流总额保持快速增长。2 0 0 5 年我国物流总额达到4 8 i 万亿元，是1 9 9 6 年物流总额的4 倍之多。表明我国正处于物流需求高增长期，且这一 时期还将持续一段时间。但物流总额增幅有所放慢( 除2 0 0 5 增幅有所回落以外) 。 下表2 2 是中国1 9 9 6 年至2 0 0 5 年物流总费用及其各项在g d p 中的比重。它反映了 中国物流总费用在g d p 占有的比例一直在2 1 以上。 车辆路径问题研究 表2 ，2 中国1 9 9 6 年至2 0 0 5 年物流总费用及其各项在g d p 中的比重 t a b 2 2l o g i s t i c st o t a ls h a r ea n dr e l a t i v ec o s ts h a r ei ng d pf r o m1 9 9 6t o2 0 0 5i nc h i n a 年份运输费用保管费用管理费用物流总费用运输费用物流总费用 ( 年)( )( ) ( ) ( )( ) 1 9 9 61 1 2 7 5 3 3 2 2 05 0 9 0 1 9 9 71 i ，07 73 52 2 24 9 5 0 1 9 9 8i i 0 6 8 3 5 2 i 35 1 6 0 1 9 9 91 1 66 23 62 1 45 4 2 0 2 0 0 01 1 2 6 5 3 6 2 1 35 2 5 0 2 0 0 11 1 26 。43 52 1 15 3 1 0 2 0 d 21 1 5 6 4 3 4 2 1 45 4 2 0 2 0 0 3 1 2 0 6 33 12 l45 6 1 0 2 0 0 41 2 1 6 2 3 0 2 1 35 6 8 0 2 0 0 5 1 0 2 5 82 61 8 65 4 8 0 物流运输的费用主要有三项，分别是管理费用、保管费用和运输费用，从表2 2 中 经计算发现，2 0 0 5 年运输费用的增长率低于同期物流费用总额的增长率，但是运输费 用长久以来一直在物流运输总费用中占有很大的比重，其值高达5 0 之多这说明我国的 社会总费用尽管高，但是经济增长方式明显落后，物流业服务水平不高、物流效率低下、 价值链偏短的本质。 另据统计，2 0 0 1 年美国物流成本占d g p 的9 5 ( 美国c a s s 信息服务公司和p r o l o g i s 公司共同发布的2 0 0 1 年度美国国家物流报告) ，而这个数字在中国是1 6 7 ( 世界银 行估算) 由此可见：与发达国家地区比较，中国企业通过缩减物流支出、增加利润的 空间更为广阔。中国的企业仅通过优化物流就能够获碍实现大量缩减成本、增加利润的 机会；提高竞争力，求得长远生存与发展。 第2 章物流业的发展前景 2 2 物流配送对电子商务发展的重要作用 物流配送是对整个物流过程实行统一的信患管理和调度，按照用户订货要求，在配 送中心进行理货工作，并将配好的货物送交需求顾客点的一种物流方式。它对电子商务 发展的作用主要体现在以下几个方面： ( 1 ) 物流配送是电子商务中必不可少的环节 众所周知：电子商务一网上信息传递一网上交易一网上结算物流配送，一个完整 的电子商务交易过程必须通过四种流即信息流、商流，资金流和物流：任何一流都是 不可缺少的，对保持这一过程的畅通是同等重要的。因此，物流是其中一个重要环节， 物流电子化是电子商务的基本要素。缺少了现代化的物流过程，致使电子商务过程出现 断层，电子商务过程便不完整。 ( 2 ) 物流配送能促进电子商务的发展 电子商务的不断发展对物流业提出了更高的要求，同时，现代物流体系的良好运转 反过来又促进电子商务的发展，两者相辅相成。物流对电子商务可以起到如下作用： 物流配送能有效降低电子商务物流成本 电子商务的交易过程有大量的中介参与，交易主体往往把一个交易过程分为几个 交易环节实现，并在诸环节中把一定的业务转移给中介行业来实现，主要目的就是通过 分工实现整个交易过程的低成本。从社会宏观上看，在整个交易的构成中，实体物品的 运输费用占据了很大一部分，因此交易主体通过各种途径努力降低费用。信息的及时传 递和正确地进行物流规划，可以尽量减少不必要的实物转移，从而降低物流费用；而借 助于物流配送麓有效遗降低从一方转移到另一方的实物运输成本。 物流配送能提高电子商务对客户需求的快速反应能力 配送中心不仅与生产企业保持紧密的伙伴关系，而且直接与客户个体保持联系，能 及时了解客户的需求信息，并沟通企业和客户双方。对于现在这样一个信息高速传递、 技术进步快、消费需求多样且多变的环境，消费者要求所选购的商晶能快速获碍，以便 能获取时间效用：而对生产企业来说，为快速满足消费者的需求，同时为了降低生产成 本而采用零库存生产、敏捷制造等先进生产方式，更要求加快物流速度，缩短物流周期 一6 - 车辆路径问题研究 比缩短制造周期更重要，这就要求在物流整个供应链上，各环节之间信息传递畅通，衔 接紧密且传递环节少，强调协作以提高整体协同效用。 ( 3 ) 物流配送是实现电子商务“以顾客为中心”理念的保证 电子商务的出现最大程度地方便了最终消费者，他们可以在网上方便地搜索、查看、 挑选、支付完成购物过程。但一旦网上购买的商品迟迟不能送达，消费者必然会转向更 可靠的传统购物方式。欧洲的电子商务开展的比日本早，但他们的电子商务公司普遍不 如日本好，其原因：就在于他们缺乏像日本流通网络中的2 4 小时便利店这类送货网络 的支持。面对发展电子商务对发达的物流配送的需求，物流业可以说面临着巨大的机遇。 “全球经济一体化”、“电子商务网络化”的趋势决定了2 1 世纪将是物流业蓬勃 发展的世纪。2 l 世纪我国物流业所要面对的现代物流经济、大力发展物流配送促使电子 商务成为最具竞争力的商务形式。 第3 章车辆路径问题概述 第3 章车辆路径问题概述 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 这一名词最早是在2 0 世纪5 0 年代末期由d a n t z i g 和r a m s e 在一篇学术论文中提出的川，而后由n c h r i s t o f i d e s 对其进 行总结深化嘲。车辆路径问题是组合优化领域中著名的n p 问题之一，与众多的实际问题 都有相似性，如铁路运输、公交调度、水道航线、路由选择等，v r p 研究具有相当大的 实际意义。 3 1 旅行商问题 旅行商问题【9 1 ( t r a v e l i n gs a l e s m a np r o b l e m 简称t s p ) 是最著名的同时也是最简单的 车辆路径问题：旅行商问题是v r p 问题的一个特例( 即当v r p 问题中只包括一条路径， 且没有能力约束的时候，就成为旅行商问题) ；t s p 问题是运筹学、图论及组合优化中的 著名难题，由于其有广泛的应用背景，引起了人们的极大兴趣，现己归入n i p 问题类。 t s p 本身可以直接用于解决类似t s p 的最优巡回线路等问题。t s p 一般描述为：旅行商 从驻地出发，经每个目标城市至少一次后返回原地，应如何安排其旅行线路，才能使总 的旅行距离( 或时间、费用等) 最少。旅行商问题之所以著名，有两方面的原因：一是实 际中有很多应用问题都可以归结或转化为旅行商问题，如物资运输路线问题、管道铺设 问题等等，同时它又是许多复杂模型的基础；二是由于旅行商问题的难于求解性，特别 是对规模较大的问题，从而吸引了许多有志者从事其有效求解算法的研究。 最简单的车辆调度问题旅行商问题( t s p ) 通过扩展旅行商的数目进而可以得到多 旅行商问题( 郎m - t s p ) ，m 个旅行商要遍历所有城市且每个城市只被一个旅行商访问。 在m - t s p 问题中，给每个旅行商( 车辆) 加上容量约束就得到了一般车辆调度问题 ( v r p ) ，然后继续将各种约束条件加入到问题的实际模型中，就可以得到各种车辆调度 问题。这是一个理论研究逐渐逼近实际问题的过程。事实上对于车辆路径问题的研究， 考虑的约束条件越丰富，往往越接近实际运输问题，但是解决问题的难度也随之大大增 加。 车辆路径问题研究 3 2 车辆路径问题研究状况 因为车辆路径问题( v e h i c l er o u t i n gp r o b l e m ,v r p ) 有着其现实的经济意义和学术 意义，自d a n t z i g 和r a m s e r 在1 9 5 9 年提出v r p 以后，国内外的专家学者开展了广泛的 研究，己经产生出多种成熟的算法，并取得了令人瞩目的成果，为后人的继续研究提供 了极高的借鉴参考作用。典型的车辆路径问题的相关研究现状有： 1 9 6 2 年，b a l i n s k i 等人首先提出v r p 的集分割，直接考虑可行解集合，在此基础上 进行优化，建立了最简单的v r p 模型 1 9 7 4 年，w r e n , g i l l e t t 等人提出s w e e p 算法( 扫描法) 目的在于求解车辆调度问 题，并针对当时几个求解相似问题的算法进行比较，证明该算法所求得的解较优于其它 的方法。 1 9 8 1 年，n c h r i s t o f i d e s 等人提出了k 度中心树和相关算法，对固定车进行k 度中 心树松弛。后来，m l f i s h e 对这种方法做了进一步改进，可求解有1 3 4 个客户的v r p 。 1 9 9 1 年，g e n d r e a u 等人将禁忌搜索方法应用于v r p ，它是比较好的启发式算法， 可以成功地应用于许多经典的v r p 。 1 9 9 6 年，j l a w r e n c e 将遗传算法用于v r p 的研究，并可有效求解带时间窗限制的 v r p 。 1 9 9 9 年姜大立等人在分析v r p 现有启发式算法的基础上，构造了v r p 的染色体表 达，并对染色体进行可行化映射，建立了v r p 的遗传算法。 1 9 9 9 年张涛等人通过遗传算法来保证搜索的全局性，用3 - o p t 算法来加强局部搜索 能力，锝到针对v r p 的混合算法，目前己可以求解较大规模的问题 2 0 0 2 年张丽萍等人通过引入新颖交叉算子，构造了一种改进遗传算法，此算法摆脱 了对群体多样性的要求，不存在传统遗传算法常见的“早熟收敛”问题，最终总能收敛 到问题的最优解或满意解。 第3 章车辆路径问题概述 3 3 车辆路径问题的一般描述及特点 3 3 1 车辆路径问题的一般描述 物流配送活动中的配送运输路线确定问题，是近二十多年来车辆路径问题的重点研 究对象和应用领域。在配送运输中，由于配送用户多，城市交通路线又较复杂，如何组 成最佳路线，如何使配装和配送路线有效搭配等，是配送运输的特点，也是难度较大的 工作。于是采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实 现物流配送科学化的重要途径。因此，目前许多v r p 的研究工作都是以物流配送活动 为背景描述的。 v r p 的一般描述是：对一系列给定的客户( 送货点或取货点) ，确定适当的配送车辆 行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心，并在满足一定 的约束条件下( 如车辆容量限制、行驶里程限制、时间限制、顾客需求量、交发货时间 等) ，达到一定的目标( 如路程最短、费用最少、时间尽量少、使用车辆数尽量少等) 参 见图2 2 图2 2 车辆路径问蹶示意图 f i 簖2s h o wo f v e h i c | er o u t i n g v r o b l e m 3 3 2 车辆路径问题的特点 下面从几个主要方面来描述车辆路径问题的特点。 ( 1 ) 道路网 用来运输货物的道路网通常用一个图来表示，其中，圆点对应于道路交叉点、和客 户；方形对应于车场( 配送中心) ；图中的线段则表示路段，每条线段对应着一个费用， 通常表示其距离( 或运行时间) 。 车辆路径问题研究 ( 2 ) 客户 用图上的圆点表示。 需运送或收取的货物量，可能有不同的种类。 要求提供服务的时间段( 时间窗，例如由于客户只在特定的时间段内营业) 。 能用于服务该客户的车辆集合( 如由于交通管制或装卸要求等) 。 有时，每个客户的需求不可能全部得到满足。在这情况下，运送或收取的货物量可 以减少，或者是一部分客户得不到服务为了处理这类情形，可以根据其客户是部分还 是全部得不到服务，引入相应的优先权或惩罚。 ( 3 ) 车场 服务各客户的车辆行驶路线开始并终止于一个或多个车场，车场也用道路图中的圆 点来表示。每个车场的特征由所配备的车辆种类和数量、以及所能处理的货物总量来表 示。在某些实际应用中，客户被事先按照车场进行划分，于是在每次完成货物的取送任 务后，车辆必须返回它们的配属车场。在这种情况下，整个v r p 就可以分解为几个独立 的v r p 问题，每个问题都对应于一个不同的车场。 ( 4 ) 路径编排中的限制条件 给配送车辆编排行驶路线时，应满足几个取决于所运送的货物性质、服务质量水平、 以及客户和车辆的特点的运营限制条件，诸如，每条线路上，相应车辆的当前装载量不 能超过车辆的载重量；客户只要求送货、取货、或取送货兼有。 ( 8 ) 目标 车辆路径问题通常需要考虑以下几个目标： 最小化总运输成本，其大小取决于服务所有客户所需要的车辆数、总行驶距离( 或 总行驶时间) 和与所使用的车辆有关的固定费用。 均衡各线路上的行驶时间和车辆载重量。 最小化与客户的不完全服务等有关的惩罚值。 第3 章车辆路径问题概述 3 4 车辆路径问题的分类 自v r p 被提出后，l i n u s ( 1 9 8 1 ) 。b o d m 和g o i d e n ( t 9 8 1 ) ，b o d i n ( 1 9 8 3 ) 。a s s a d ( 1 9 8 3 ) ， d e s r o c h e r s ，l e n s t r a 和s a v e l s b e r g h ( 1 9 9 0 ) 等许多学者对心从不同角度，按不同的标 准进行了多种分类【3 2 】。 ( 1 ) 按任务特征分类：有纯装问题或纯卸问题( p u r e p i c k u p o r p u r ed e l i v e r y ，车辆在所 有任务点装货或卸货，即集货或送货问题) 及装卸混合问题( c o m b i n e dp i 呔u pa n d d e l i v e r y ，每项任务有不同的装货点和卸货点，即集货、送货一体化问题) ( 2 ) 按任务性质分类：有“对弧”服务问题( 如中国邮递员问题) 和“对点”服务问 题( 如旅行商问题) 以及“混合”服务问题( 如交通车线路安排问题) 。 ( 3 ) 按车辆载货状况分类：有满载问题( 货运量不小于车辆容量，完成项任务需要 多辆车) 和非满载问题( 货运量小于车辆容量，多项任务仅用一辆车) 。 ( 4 ) 按车场( 或货场、配送中心等) 数目分类：有单车场问题和多车场问题。 ( 5 ) 按车辆类型数分类：有单车型问题( 所有车辆容量相同) 和多车型问题( 执行任务 的车辆的容量不全相同) ( 6 ) 按车辆对车场的所属关系分类；有车辆开放问题( 车辆可以不返回其发出车场) 和车辆封闭问题( 车辆必须返回其发出车场) 。 ( 7 ) 按优化目标数来分类：有单目标问题和多目标问题。 ( 8 ) 按有无时间约束来分类：有“有时间窗”和“没有时间窗”问题，“有时间窗” 的问题又可分为硬时间窗口和软时问窗口。 ( 9 ) 按运送货物进行分类：可分为单一货物和多种货物，多种货物又包括可相容货 物( 指多种货物可以用一辆车进行配送) 和不相容货物。 根据上述约束条件的不同组合，v r p 问题在学术研究上产生了许多不同的延伸和形 态。包括带能力约束的车辆路径问题( c a p a c i t a t e d v e h i c l er o u t i n gp r o b l e m s 。c v r p ) 、带 时间窗的车辆路径闯题( v e b 3 e l er o u t i n gp r o b l e m sw i t ht i m ew i n d o w s , v r p t w ) 、追求 最佳服务时间的车辆路径问题( v e h i c l e r o u t i n gp r o b l e m s w i t h d e f m e d t i m e ，v r p d t ) 、 多车种车辆路径问题( f l e e ts i z ea u dm i xv e h i c l er o u t i n gp r o b l e m s ，f s v r p ) 、车辆多次 使用的车辆路径问题( v e h i c l e r o u t i n g p r o b l e m s w i t h m u l t i p l e u s e o f v e h i c l e ，v r p m ) 、 车辆路径问题研究 随机需求车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hs t o c h a s t i cd e m a n d ，v r p s d ) 、动 态车辆路径问题( d y n a m i cv e h i c l er o u t i n gp r o b l e m s ，d v r p ) 、考虑收集的车辆路径问 题( v e h i c l er o u t i n gp r o b l e m sw i t hb a c k h a u l s , v r p b ) 、满载非满载v r p 、双向v r p 等。 第4 章遗传算法 第4 章遗传算法 4 1 遗传算法的基本构成及概念 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是由美国j h o l l a n d 教授于2 0 世纪六、七十 年代研究形成的一个较完整的理论和方法，它是一种通用的解决最优化闯题的搜索算 法，是一类以达尔文自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生 型算法，该算法利用生物界自然选择和自然遗传机制，以概率论为基础，在解的空间中 进行随机化搜索，最终找到问题的最优解。其主要特征是群体搜索策略和群体中个体之 间的信息交换，它对优化对象既不要求连续，也不要求可微，目前己被广泛应用于组合 优化、人工智能、人工生命领域，并取得了良好效果。下面先介绍有关遗传算法的几个 基本概念。 4 1 1 遗传算法的几个基本概念 ( 1 ) 个体( i n d i v i d u a l ) 或染色体( c h r o m o s o m e ) 个体( i n d i v i d u a l ) 或染色体( c h r o m o s o m e ) ，是生物学中的概念。在遗传算法中通常 用一个所谓的串来表示( 有时也采用一个向量表示) ：) o x l x 驹x i 。其中x ，是串x 的基本 单元，称为基因( g e n e ) ，i 称为基因数。例如0 1 3 4 0 2 5 0 6 7 8 0 ，称为一条染色体。染色 体中每一个分量称为基因，上述染色体中的0 ，1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 都称为基因。 染色体也叫个体，多个个体组成的集合称为群体。染色体上的一个有效信息段叫基因组 ( g e n eg r o u p ) ，一般一个基因组对应于解中的一个优化参数。在遗传算法中，根据问 题的不同，个体一般可分为二迸制的0 ，l 串，整数串，实数串，复数串等【m 。 ( 2 ) 编码( c o d h l g ) 和解码( d e c o d i n g ) 遗传算法是设计用来解决遗传空间中的问题，不能直接应用于实际的解空间，所以 需要将解空间转换到遗传空间。 编码操作就是指从表现型映射到基因型，从而将实际的解空间映射为相应的可以被 遗传算法处理的遗传空间。编码的恰当与否对问题求解的质量和速度有直接的影响。 d a v i d e o o l d b e r g 提出了编码的两条基本原理： 车辆路径问题研究 所选编码方式应能够容易地生成；求解问题相关的确定位数少( 低阶) 、定义长度 短的构造块。 所选编码的方式应具有最小的字符集，能够自然地表达欲求解的问题。 解码操作是指从基因型映射到表现型，它是为了将遗传算法处理后的遗传空间映射 到实际的解空间。二者是相反的操作过程。 ( 3 ) 种群( p o p u l a t i o n ) 和种群规模n 种群即个体的集合。使用遗传算法解决问题时，从随机选择的多个初始解开始进行 迭代搜索，这多个初始解的集合以及每次迭代生成的一组新解就构成一个种群。 种群规模n 表示群体中所含个体的数量。种群规模的取值非常关键，当n 过小时， 可提高算法的运行速度，但却降低了种群的多样性，有可能引起遗传算法的早熟现象， 而当n 过大时，又会降低算法的运行速度，所以一般建议的取值范围为1 0 1 0 0 。 ( 4 ) 适应度函数( f i t n e s sf u n c t i o n ) 在研究自然界生物的遗传和进化现象时，生物学家使用适应度值来度量某个物种对 于其环境的适应程度。与此相类似，遗传算法中也使用适应度值来度量种群中各个个体 在优化计算中有可能达到或接近于或有助于找到最优解的优良程度，适应度值高的个体 遗传到下一代的概率较大。 度量个体适应度的函数称为适应度函数。是遗传操作的依据，并指导遗传算法的搜 索方向。通常，遗传算法中个体的适应度也是所研究问题的目标函数。但是，有时适应 度也可以是目标函数转换后的结果。评价个体的适应度的一般过程为： 对个体的编码进行解码，得到个体的表现型。 由个体的表现型可以得到对应个体的目标函数。 根据最优化问题的类型，由目标函数按一定的转换规则求出个体的适应度值。 遗传算法中，群体的进化过程就是以个体的适应度值为依据，通过反复的迭代，寻 求适应度值较大的个体，最终得到最优解或近似最优解。 4 1 2 遗传算法的基本操作一遗传算子( g e n e t i co p e r a t o r s ) 遗传算子作用在基因串上，是模拟种群进化过程的主要手段。常用的遗传算予有如 下三种： 第4 章遗传算法 ( 1 ) 选择算子( s e l e c t i o no p e r a t o r s ) 选择算子根据一定的选择策略作用在一个基因串上，其作用是为了从当前群体中选 出优良的个体，使它们有机会作为父代产生后代个体，适应度越高的个体被遗传到下一 代的概率较高，等待交叉和变异对其进一步演化。选择的目的是为了避免基因损失，提 高全局收敛性。选择过程分可分为两个阶段：选择阶段( 从当前群体中选择优良个体) 和 复制阶段( 把选中的个体加入下一代群体并淘汰不良个体) 。 目前，有多种不同的选择策略，如轮盘赌选择法、最优保存策略、确定式采样选择、 无回放随机选择、无回放余数随机选择、排序选择和随机联赛选择等，各种策略在原理 上是一致的，即在旧的群体中“随机”选择个体生成一个新群体，这种“随机”选择并 非完全随机，它是基于一个个体相对于整个群体的适应值，根据个体的适应值确定选择 的系数，按比倒复制生成新个体加入新种群中。其中轮盘赭选择法最为常用。 ( 2 ) 交叉算子( c r o s s o v e ro p e r a t o r s ) 在遗传算法中，交叉算子的作用非常重要。一方面，它使得在原来的群体中的优良 的个体的特性能够在一定的程度上保持；另一方面，它使得算法能够搜索新的基因空