（交通运输规划与管理专业论文）配送车辆线路优化算法研究.pdf

河海人学硕士学位论文 摘要 物流的目标在于以最少的费用满足消费者的需求，对于物流中心来说，物流配 送车辆的线路优化，是物流系统优化中一个关键的环节。正确合理的安排车辆的配 送线路，可以有效的减少车辆的空驶率，降低运输成本，提高经济效益。 物流配送车辆的线路优化问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) ，是一个典 型的有约束的组合优化问题，属于强n p 难题。传统的求解v r p 的方法有精确解法 和启发式算法，其中节约启发式算法因其简单、容易于理解，成为许多其它算法的 基础。遗传算法是一种自适应随机搜索方法，特别适合于组合优化问题，被认为是 解决n p 难题的途径。 本文研究的车辆线路优化问题，其所有节点的运输任务要求在一个时闫段之内 完成，称为宽时间窗v r p 。论文在研究大量相关资料的基础上，修正节约启发式算 法和标准遗传算法用于解决宽时间窗v r p 。并在遗传算法中融入节约启发算法思想， 成功构造新的算法一遗传节约混合算法。 本文构造的遗传节约混合算法是一个两层的伪并行搜索结构，充分利用了不同 的领域搜索方法。对遗传节约算法比较分析表明：与相关算法相比较，它的优化能 力、运行效率、可靠性均有一定提高。遗传节约混合算法对于遗传算法理论研究和 实际应用具有一定价值。 关键词： 配送车辆线路优化问题宽时间窗节约启发式算法标准遗传算法 遗传节约混合算法 河海大学硕士学位论文 a b s t r a c t t h eo b j e c to fl o g i s t i c si st os a t i s f yt h er e q u i r e m e n to fc o n s u m e rw i t hl e a s tc o s t l o g i s t i cd e l i v e r y v e h i c l e r o u t i n gp r o b l e m i sa p i v o t a lp r o b l e m t o l o g i s t i cs y s t e m o p t i m i z a t i o n t h e e x a c ta n dr a t i o n a lp l a n n i n go fv e h i c l er o u t i n gi nd i s t r i b u t i o nw i l lr e d u c e r a t eo f e m p t y d r i v i n g ，l o w e r c o s to f d i s t r i b u t i o na n dt a k eg r e a te f f e c to nt h ee f f i c i e n c y v e h i c l er o u t i n gp r o b l e mi sn o to n l ya t y p i c a lc o m b i n a t i o no p t i m i z a t i o nr e s t r a i n e db u t a l s oan ph a r dp r o b l e m t r a d i t i o n a la l g o r i t h m si n c l u d ee x a c tp r o c e d u r e sa n dh e u r i s t i c s b e c a u s es a v i n gh e u r i s t i ca l g o r i t h i n si ss i m p l ea n de a s yt ob ec o m p r e h e n d e d ，l o t so fo t h e r a l g o r i t h m s a r ec o n s t r u c t e db a s e do ni t g e n e t i ca l g o r i t h mi sas e l f - a d a p t a b i l i t ys e a r c h m e t h o d i ti se s p e c i a l l yf i tf o rc o m b i n a t i o no p t i m i z a t i o n m a n ys c h o l a r sb e l i e v et h a ti ti s t h ec u r r e n to f s o l v i n gn p h a r dp r o b l e m t h ev e h i c l er o u t i n gp r o b l e mi nt h i sp a p e rr e q u e s ta l lc o n s u m e r sw i l lb es e r v e di na t i m e ，w ec a l li tv e h i c l er o u t i n gp r o b l e mw i t hw i d et i m ew i n d o w b a s e do nr e a d i n gl o t s o fc o r r e l a t ep a p e r s ，t h ea u t h o rm o d i f ys a v i n gh e u r i s t i ca l g o r i t h ma n dg e n e t i ca l g o r i t h m c o n s t r u c t e dt os o l v ev e h i c l er o u t i n gp r o b l e mw i t l lw i d et i m ew i n d o w f u r t h e r m o r e a n e w a l g o r i t h mi sc o n s t r u c t e di nt h i sp a p e rw h i c h c o m b i n e ss a v i n gh e u r i s t i ca l g o r i t h m a n d g e n e t i ca l g o r i t h m w ec a l li tg e n e t i c - s a v i n gh y b r i da l g o r i t h m g e n e t i c s a v i n gh y b r i da l g o r i t h m c o n s t r u c t e di nt h i s p a p e r i sad o u b l e - d e c k p s e u d o - p a r a l l e l s t r u c t u r e i tm a k e st h eb e s to fs e a r c hm e t h o d si n d i f f e r e n tf i e l d s e x e m p l i f i c a t i o n sp r o v et h a tt h i sa l g o r i t h me n h a n c ec a p a b i l i t yo fo p t i m i z a t i o n ，s o l v i n g e f f i c i e n c ya n dr e l i a b i l i t yo fr u n n i n g g e n e t i c - s a v i n gh y b r i da l g o r i t h i nc o u n tf o ra c a d e m i c r e s e a r c ha n da p p l i a n c ei np r a c t i c e k e yw o r d s ：d i s t r i b u t i o n ；v e h i c l er o u t i n gp r o b l e m ；w i d et i m ew i n d o w ；s a v i n gh e u r i s t i c a l g o r i t h m ；g e n e t i ca l g o r i t h m ；g e n e t i c - s a v i n gh y b r i da l g o r i t h m i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 学位论文使用授权说明： 2 0 0 5 年3 月1 7 日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘 版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用 影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部 分内容的公布i 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ：2 0 0 5 年3 月1 7 日 河海大学硕十学位论文 第一章绪论 物流是2 0 世纪中期发展起来的一门新兴学科，也是现代较有影响的学科之一。 物流作为一种经济活动被誉为“末开发的黑大陆”、企业的“第三利润源泉”。物流 的概念最早起源于美国，1 9 3 5 年美国销售协会阐述了实物分配( p h i s i c a l d i s t r i b u t i o n ， 简称p d ) 的概念。2 0 世纪5 0 年代，p d 的概念进入日本，并被译为“物的流通”， 之后迅速被，“泛使用。二战时美军发展了后勤管理方法( 1 0 9 i s t i c s m a n a g e m e n t ) ，对美 军的采购、运输、仓储、分发进行统筹安排和全面管理，取得显著成效，战后该方 法被引入经济部门，l o g i s t i c s 逐渐取代了p d ，成为物流的代名词川。 我国使用物流一词始于1 9 7 9 年6 月，物资工作者代表团赴日本参加第三届国际 物流会议，回国后在报告中第一次引用和使用“物流”这一术语。随着1 9 8 9 年第八 届国际物流会议在北京召开，“物流”一词在我国的使用日益普遍。 社会经济领域中物流活动无所不在，物流作为一个综合系统，其基本功能包括 运输、保管、仓储、装卸、包装以及物流基础设施建设活动等方面，近年来，又增 加了流通加工和信息活动两个功能【2 l 。 物流是一门交叉性综合学科，研究物流的目标是有效的管理和控制物流的全过 程，在保证服务质量的前提下，实现消耗的总费用最小【3 1 。在全球经济一体化的今天， 对物流方面的研究丰富多彩，大多数是相关学科的研究成果在物流领域的应用，如 物流系统运输规划、库存系统理论、计算机模拟等。 1 1 选题背景 物流的目标在于以最小的费用满足消费者的最大需求，随着管理理论发展，企 业逐步完善了生产、销售方面的规划管理。但是，生产制造过程中的物流只占整个 供应链的1 0 左右，更多的物流成本消耗在仓储、运输中。而运输的费用占整个企 业物流的4 0 强【4 j 。一些大型企业为了合理规划运输，建立了大型的运输或配送中 心，同时专业化、规模化、集团化的第三方物流也开始出现，它们建立的综合型物 流中心为许多企业同时提供专业的物流服务。 对于物流中心来说，配送是其中一个重要的直接与消费者相连接的环节。配送 第一章绪论 一般定义为，将货物从物流中心送达收货人的过程。它在集货、配货的基础上按照 顾客的要求( 包括种类、数量、时问等方面) 进行送货。配送系统的优化，主要包 括集货线路优化、货物配装、送货线路优化，以及集货、配装、送货一体化优化。 在国外，类似的优化系统已广泛的应用于报纸投递、牛奶配送、电话订货、垃圾收 集、连锁店送货等方面的优化系统【5 j 。 物流配送车辆的线路优化，是物流配送优化中关键的一个环节，也是电子商务 活动不可缺少的内容。正确合理的安排车辆的配送线路，i j + 以有效的减少车辆的空 驶率，实现合理线路运输，从而降低运输成本，节约运输时间，提高经济效益，达 到物流科学化管理。 1 2 研究的目的 物流配送车辆的线路优化问题在国外被归结为v e h i c l er o u t i n gp r o b l e m ，简称 v r p ，该问题一般定义为：对一系列的装货点和( 或) 卸货点，组织合理的行车线 路，使车有序的通过它们，在满足一定的约束条件( 如货物的需求量、车辆的容量 限制、货物的送达时间、车辆的行驶时间等) 下，达到一定的目标( 如里程最短、 费用最少、使用车辆尽量少等) 6 1 。 配送车辆线路优化问题是一个典型的有约束的组合优化问题，也是离散优化的 重要内容之一，通过计算复杂性的研究可以确定求解v r p 算法的研究方向，对其计 算复杂性的研究7 l 8 】表明几乎所有类型的v r p 均为n p ( 非确定型的多项式算法) 难 题。 自从v r p 被证明为n p 难题后，许多学者进行了各种求解算法的研究。传统的 求解v r p 的方法有精确解法和启发式算法。启发式算法简单、易于操作。由于v r p 是一个强n p 难题，当问题的规模不断增大，其计算量呈指数增长，传统算法的效率 和解的质量出现急速的下降，甚至无法求解。 遗传算法是2 0 世纪6 0 年代由美国j h o l l a n d1 9 教授和他的学生j d b a g l e y 1 0 】 建立发展的，其思想源于生物遗传学的适者生存的自然规律，是一种自适应随机搜 索方法，它对优化对象相关函数既不要求连续，也不要求可微，并具有极强的鲁棒 性和内在并行机制，特别适合于非凸空间的多极值优化和组合问题 1 ”。正是遗传算 法具有独特的优点，被认为是用于解决n p 难题的一个可行途径。在求解v r p 方面 河海| 凡学硕上学位论文 也开始了一些尝试，并取得了一些成果。 遗传算法具有较强的全局搜索能力，但它的局部搜索能力却较弱。本文对遗传 算法和启发式算法进行了比较研究。在修f 应用的基础上，把遗传算法和启发式算 法融合在一起，利用两种算法的各自优点，构造出一种新的算法一一遗传节约混合 算法用于求解v r p ，以期获得求解效率和效果均较优的解决v r p 的算法。本文的研 究日的归纳为以下三点： ( 1 )修_ f 现有的节约启发式算法和遗传算法用于求解本文提出的宽时间 窗v r p ； ( 2 )构造一种新算法遗传节约混合算法，将遗传算法和节约启发式算 法相结合，用于求解宽时间窗v r p ，提高求解效率和质量； ( 3 ) 计算机编程实现节约启发式算法、遗传算法和遗传节约混合算法，并 通过算例和实例应用，比较分析遗传节约混合算法的性能。 1 3 国内外研究现状 d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出物流配送车辆线路优化问题，引起运筹学、 应用数学、物流学等学科的重视，成为诸多领域的前沿与热点问题【5 1 。 目前，v r p 问题的形式不再局限于汽车运输领域，在水运、航空、通讯、电力、 计算机等领域也有广泛的应用。其算法已经用于航空乘务员排班、轮船送运货物的 港口安排、交通车的线路安排、生产系统中的计划和控制等多种优化组合问题。 国外对物流配送车辆线路优化问题作了大量而深入的研究。例如，1 9 8 3 年b o d i n 和g o l d e n 6 在他们的文章中列举了7 0 0 余篇文章； c h d s t o f i d e s 、g o l d e n 1 3 1 、 a s s a d 1 4 1 在编辑的论文集中进行了详尽的阐述；a l t i n k e m e r 和g a v i s h 1 5 1 ，l a p o r t e f l 6 】， s a l h i f 17 】等在他们的文章中对求解方法进行了探讨和总结。该领域的代表人物有 b o d i n 、c h r i s t o f i d e s 、g o l d e n 、a s s a d 、b a l l 、l a p o r t e ，r i n n o o yk a n ，l e n s t r a ，d e s r o s i e r s 和d e s r o c h e r s 等人。 国内对v r p 的研究和应用还处于初级阶段，主要研究对象是旅行商问题( t s p ) 、 中国邮递员问题等。李大卫【1 8 1 以旅行商问题的最近距离启发式算法为基础，通过评 价函数处理时间窗约束，来求解v r p 问题；张震【1 明针对单车场满载问题，提出了考 虑运输行程约束的优化方法；靳番【2 0 j 、赵赫j 、张立明f 2 2 1 在利用遗传算法和神经网 第一章绪论 络方法对简单v r p 求解方面也取得定成果；蔡延光f 2 3 i 应用并行表搜索算法和模 拟退火算法对满载问题进行了求解：李军，郭耀煌则提出求解v r p 的标准遗传算法 2 5 1 ，同时系统的分析了各类v r p 问题和求解方法吼 对配送车辆线路优化问题，国内外许多学者按照不同的标准进行了分类2 6 _ 2 9 1 。 按照任务特征，可分为纯装、纯卸及装卸混合问题；按照任务性质，可分为对弧服 务、对点服务以及混合服务问题；按照单个货运节点所需货物量来分，有满载问题 ( 单个节点需货量大于等于车辆的装载容量，完成一项任务需要多辆车) 和非满载 问题( 单个节点需货量小于车辆的装载容量，一辆车完成多项货运任务) 。按照物流 中心( 车场) 的数目，分为单物流中心和多物流中心问题。 1 4 本文研究的问题以及工作内容 1 4 1 研究的问题 由于车辆线路优化问题( v r p ) 的形式多种多样，本文研究的车辆线路优化问 题建立在下列条件之下： ( 1 ) 车辆非满载。节点的货物需求量均小于单辆的汽车容量，一辆车完成多 项货运任务； ( 2 ) 单物流中心。所有的节点只有一个物流中心供货； ( 3 ) 单品种货物。一次安排的所有的节点所需的是同一种货物； ( 4 ) 单车型。只有一种容量的车辆参加服务； ( 5 ) 宽时间窗约束。所有节点的货运任务要求在一定的时间段内完成，同时 车辆从物流中心出发和返回中心有确定的时间要求。 为了文字简练，本文将上述条件下的研究对象称为宽时间窗车辆线路优化问题 ( 简称：宽时间窗v r p ) 。 1 4 2 主要工作内容 为了达到研究目的，作者收集并阅读了大量的国内外有关v r p 方面的研究资料， 对资料进行整理、分类和思考。在充分理解问题及其现有算法的基础上，将前人设 计的节约启发式算法和遗传算法进行修正，用于求解本文提出的宽时间窗v r p 。为 河海大学硕士学位论文 了改进算法、提高效率和质量，本文在遗传算法中结合节约肩发式算法，构造了 种新的算法一遗传节约混合算法求解宽时间窗v r p ，并运用v b 语言完成计算机对 = i t q , 算法的实现。通过算例和实例计算，对混合节约遗传算法的性能进行分析。 本文的各个章节的主要结构如下： 第一章概述本文的研究背景、目的、国内外的研究现状和本文研究的问题以及 主要工作内容； 第二：章提出宽时间窗车辆线路优化问题的模型，总结该问题的各种算法； 第三章对遗传算法进行介绍，阐述基本遗传算法和其实现的主要技术； 第四章修正前人的节约启发式算法和遗传算法，用于求解宽时间窗的v r p ； 第五章构造遗传节约混合算法，求解宽时间窗v r p ，并设计其计算步骤和流程 框图： 第六章节约算法、遗传算法、遗传节约混合算法算例比较，算法性能分析； 第七章论文的总结和对研究前景的展望。 第二章车辆线路优化问题( v r p ) 的数学模型与算往1 - q 顾 第二章车辆线路优化问题r p ) 的数学模型与算法回顾 2 1 数学模型 在日常生活和生产实际中，有许多配送问题。如有一个仓储中心，需向多个连 锁分店配送货物，每个分店对货物的需求量不同，但都小于仓储中心所拥有的配送 车辆的单车容量，配送车辆在仓储中心装货后出发，把货物送至各个分店，完成后 返回中心。又如，若干厂家生产一些产品，需要运到中心仓库，每个厂家的产品量 小于运输车辆的容量，车辆从仓库出发，到各个厂家去装货，装满后返回仓库。类 似的问题都可以归结为v r p ，它可以概括为：一个物流中心，容量为q 的车辆k 辆 ( 一般k 没有限制) ，有l 项货运任务需要完成，以1 ，2 ，l 表示，己知货运任 务i 的货运量为g i ( i _ 1 ，2 ，- l ) ，且g i o ，则模型目标是使用的车辆数最少。 模型中s 表示支路消去约束，即消去构成不完整线路的解。如图2 - 2 所示，两 第二章车辆线路优化问题f v r p ) 的数学模型与算法回顾 条支路构成的一个解满足分配约束，但没有构成一条完整的线路，因此不是v r p 的一个可行解。 3 图2 2 不完整线路示意图 2 1 2 宽时间窗v r p 的数学模型 v r p 中若每项货运任务都有时间的限制，则问题就变为有时间窗的v r p 。根据 我国目前的交通状况，车辆在不同的时间段行驶相同的线路所花费的时间可能会有 很大的差别，很难保证车辆在一个预先约定的准确时间到达某个货运节点。随着我 国经济的不断发展，客户对货运服务水平也有一定的要求。本文中讨论的v r p 是： 要求在一个较宽的时间范围内完成所有货运节点的配送任务，如一天( 1 2 小时) 之 内，或半天( 6 小时) 之内，故而称之为宽时间窗v r p 。 宽时间窗v r p 限定所有货运任务在一个时间段内完成，不仅满足了客户对服务 水平的要求，而且使得所有参与配送的车辆在一个共同的时间段内工作，有利于运 输任务合理的分配和车辆的管理。 本文中以s i 表示货运车辆到达货运节点的时问，t i i 表示车辆由货运节点i 行驶 至节点j 所需时间， s t , e t 表示完成各项货运任务的个较宽的时间范围。有以下 约束关系： s o = s t ， s t s ；e 汀( 2 4 ) 2 2v r p 的算法回顾 配送车辆线路优化问题的求解方法非常丰富，已有相当多文献提出不同的求解 方法。而且，m a g n a n t j 3 ”、b o d i n 2 7 1 、g o l d e n 1 3 、l a p o r t e 1 印和o g m r n 3 2 1 等学者对此 问题的求解方法的分类进行了研究。常见的求解方法，基本上可以分为以下五类： 入； 河海大学硕+ 学位论文 f 一1 系统仿真法( s i m u l a s t i o n ) 由g o l d e n 和s k i s c i m 于j9 8 6 年提出1 3 3 】，主要应用于行车线路与物流中心区位的 选择，优点在于可以直接观察系统安排的效率和效果，但由于实际问题的情况多变 且具有不确定性，如何将实际的配送系统逻辑化为仿真程序，仍需进一步探索。 ( 二) 人机互动法 结合人类决策和计算机计算能力，在求解过程中，通过高度的人机交换模式， 结合专家的决策信息，由计算机计算得出结果。其优点是寻优的过程中，决策者可 以很清楚的看到各约束条件直接的替代关系，以及参数变化可能导致的成本变化。 ( 三) 精确解法( e x a c tp r o c e d u r e s ) 通过严谨的数学模型或计算机数据结构规划，利用数学法则或数据结构搜寻的 方式，求得问题的解。由于两种方法都在所有可行解的集合( f e a s i b l es o l u t i o ns e t ) 寻找最优解，所以得到的解均为最优解。但是，随着变量的增加，车辆配送问题的 解集合会有组合爆炸( c o m b i n a t o r i a le x p l o s i o n ) 的现象。求解时间也星指数函数的 趋势增长，不能在有限的时间给决策者一个可行解，这是此方法最大的缺陷。常见 的精确解法有动态规划法( d y n a m i cp r o g r a m m i n g ) 、分枝定界法( b r a n c ha n db o u n d ) 与切平面法( c u t t i n gp l a n e s ) 。 ( 四) 启发式算法( h e u r i s t i c s ) 由于上述三种方法的求解效率不甚理想，部分学者致力于启发式解法的发展。 该方法在求解时可以减少搜索的次数，是一种容易且快速求解困难问题的有效方 法。s o l o m o n f 3 4 提出数个有时间窗约束车辆循环问题的启发式算法，包括节约法 ( s a v i n gm e t h o d ) 、最邻近法( n e a r e s tn e ：i g h o r ) 、插入法( i n s e r t i o n ) 以及扫描法 ( s w e e p i n g ) 。各个解法在他之前都应用于没有时间要求的v r p 问题，若应用于求 解有时间要求的v r p 问题，则在求解的过程中必须增加时间可行性的检验，以此 来确保配送达到时间能够满足顾客的要求。所以当某个货运节点被安排入线路时， 需考查该点插入后，是否违反该顾客与其后受影响的顾客的时间约束是否满足。 各种启发式算法的主要算法思想： ( 1 ) 节约法 c l a r k e w r i g h t d 5 1 于1 9 6 4 年提出该方法以求解车辆巡回问题，其思想在于按节 约值从大n d , 的顺序，在车辆的容量限制下，依序将对应的两个货运节点排入路径 9 第二章车辆线路优化问题( v r p ) 的数学模型与舒法回顾 中，直到所有的节点被插入节点为止。s o l o m o n 3 4 1 于1 9 8 3 年将此方法用于求解有时 间窗约束的车辆巡回问题，关键在于在安排节约值较大的两个顾客时，进一步考虑 时问约束。节约法将在3 1 节中继续做详细的介绍，此处不再赘述。 ( 2 ) 最邻近法 最邻近法是s o l o m o n r 3 4 于1 9 8 3 年提出的求解有时间窗的车辆巡回问题一种方 法，该方法的思想概述如下：由配送中心开始搜索，若i 为距离配送中心最邻近的 节点，则其优先安排入线路中，接着搜索另一个节点j 以安排线路的下一位，且插 入的节点必须满足以下条件： 尚未被插入其它路径 晟邻近成本c i i 最小 汽车容量约束与顾客时间约束均满足 若尚未安排的节点中皆无法找到可插入的节点，则构成另一新的子路径，直到 所有的节点都被安排入所有的子路径为止。而决定节点是否为最邻近节点的判断准 则有以下三点： 两节点间的距离d i 两节点间的运算时间t i i 配送下一个节点时所需等待服务的时问 在决定两节点间的最邻近成本时，物流中心先评估对此三要素的权重组合，且 总和为l ，所以最邻近法总成本的计算公式为： c 口= 8 , d f + 占2 0 + 甜 ( 2 5 ) 其中哦、j ：、蠡为物流中心对该节点三要素的权重，且正+ 疋+ 以= l 。 ( 3 ) 插入法 插入法最早由m o l e 和j a m e s o n 3 6 】于1 9 7 6 年提出，用于求解一般v r p 问题，其 特点是结合最邻近法与节约法的观点，依序将节点插入线路中以构成配送线路。 s o l o m o n 3 4 】于1 9 8 3 年将此方法应用于求解有时间窗的v r p 问题，因为时间限制的 加入，从而使得顾客的等待时间缩短。插入法主要包括两个步骤： s t e p l ：选取距离物流中心最远的节点为起点，从其余节点中，根据最邻近法决 定下一个被插入的顾客节点； 1 0 河海大学硕十学位论文 s t e p 2 ；以节约法决定该顾客节点应被插入的位置，在车辆容量限制下，重复进 行选取与插入的步骤，当无法再扩充路径时，则再建立另条线路，直至所有的节 点都被安排入线路。 ( 4 ) 扫描法 g i l l e t t 和m i l l e r t 3 7 1 于1 9 7 4 年所提出的求解v r p 的方法，此方法属于先分群再 安排线路的方式，分为两个阶段： 第一阶段：利用极坐标来表示各个需求点的区位，然后任取一节点为起点，以 车辆容量为分群的约束，再以该节点为零度按顺时针或逆时针的方向，进行顾客的 扫描分群： 第二：阶段：根据求解旅行商问题的方法，求解各节点群中节点的安排顺序。 同样，s o l o m o n 【3 4 _ 1 1 9 8 3 年将上述扫描法进行发展，用于求解有时间窗的v r p 问 题，与原扫描法不同的是，在第二阶段的求解各个节点安排顺序中，其以插入法进 行节点群中的节点安排，并检查时间可行性，若有节点无法满足时间窗的约束，则 先排除此节点。若所有的节点群都已经过安排，且所有的节点都已被服务，则完成 线路的建构：若有节点尚未接受服务，则沿原来的扫描方向，将剩余的尚未服务的 节点重复进行扫描与插入的步骤，直至所有的节点都被服务。 综合以上四种启发式算法，求解有时问限制的v r p 问题的关键在于掌握配送时 间和空间的关系，并在时间可行性的检验下有效解决车辆行驶线路问题、行程问题、 装载问题。 ( 五) 并行算法和亚启发式算法 基于启发式的并行算法和一些称为亚启发式的算法都由一个初始解出发，通过 对当前解的反复的局部扰乱，以达到较好的解。 用并行算法求解v r p 还处于起步阶段，a l t i n k e m e r 和g a v i s h ( 1 9 9 1 ) 15 1 、 t a i l l a r d 38 1 、f i e c h t e r d g l 等用并行算法求解了有时间限制的v r p ，他们的算法一般都 是基于启发式规则，如节约算法，插入算法等待。由于并行算法要求条件较高，一 般需要并行计算机，在现实应用中受到一定限制。 亚启发式算法包括表搜索算法、神经网络法、模拟退火算法、遗传算法等。 表搜索算法( g e n d r e a u 、h e r t z 和l a p o r t e 4 0 l ；b a t n a r p s o g l u l 4 1 1 ) 和模拟退火法 ( o s m a n 4 2 1 ；a l e xv 锄 4 3 1 ) 在求解有时间窗的v r p 方面已取得一定成果， 第二章车辆线路优化问题( v r p ) 的数学模型与算法回顾 ( o s m m l 4 2 】；，l a p o r t 和o s m a n i “1 ) 。但这些方法过于复杂，运算量大，涉及复杂的 领域转换和求解策略，在实际中不容易实现。神经网络的发展，促进了旅行商问题 的较好解决( w i l s o n 4 5 1 ) ，但在v r p 中的应用刚川开始。 遗传算法在旅行商问题中的应用已取得一定的成果( o l i v e r 和s m i t h l 4 6 】：f o g e l ) ，已经出现文献利用遗传算法对有时间约束的v r p 求解( m a l m b o r g 4 8 】；o c h i 和l u i z 4 9 1 ) ，但仅仅是开始尝试，还有待于进一步研究。 求解v r p 算法的分类，其划分并不是唯一的，有的方法同属于好几类。对于常 见的系统仿真、人机互动、精确解法、启发式解法、并行算法和亚启发式算法五大 类求解方法，其优缺点分析见表2 1 。 表2 1各类算法的优缺点比较 求解v r p 的方法分 方法优点方法缺点 类 可能无法满足实际多变的配 系统仿真法可以直接系统安排的效率和效果。 送情况。 可适时的结合专家的意见；寻优过程 中，使用者可以很清楚的看到各限制 相关的专门知识不易获得并 人机互动法 条件之间的替代关系，以及参数变化 整合：决策时间较长，虽然效 果好，但效率低。 可能导致的成本变化。 随着问题规模的扩大求解受 精确解法可求得最优解。到计算机容量的限制：求解效 率低。 可以减少搜索次数；可较快的求解困无法确保得到最优解，可能为 启发式算法 难问题，效率较高。较优解，即满意解。 并行算法和亚启发 对原有算法有所改进。不同的改进算 涉及到领域转换和求解策略 设计；有的对计算机提出较高 式算法 法具有各自独有的特点。 的要求。 海大学碘士学位论文 31 算法的产生与发展 第三章遗传算法概述 生命科学与王程科学的相互交叉和渗透产生了基于人工智能的进化优化算法。这 类算法的核心思想源于这样一个基本认识：生物进化过程本身是一个自然的、并行 发生的、稳健的优化过程。这一优化过程的目标是对环境的自适应性，生物种群通 过遗传变异来达到进化的目的。 遗传算法是一种宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生 与进化过程，通过模拟达尔文“优胜劣汰、适者生存”的原理鼓励产生更好的结构， 同时通过模仿盂德尔遗传变异理论在迭代过程中保持已育的结构，并寻找更好的结 构。遗传算法也是通过繁殖、变异、竞争和选择这四种基本形式实现的。 2 0 世纪4 0 年代，有学者开始研究如何利用计算机进行生物模拟的技术。 6 0 年代，h o l l a n d r 9 】教授认识到了生物的遗传与自然进化现象与人工自适应系统 的相似关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以 群体的方式进行自适应搜索。 1 9 6 7 年，h o l l a n d 教授的学生b a g l e y 在其博士论文中首次提出了“遗传算法” 词1 0 】，后来他还发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上 使用了双倍体的编码方法，创立了自适应遗传算法的概念。 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 n i n n a t u r a la n da r t i f i c i a l s y s t e m s ) ) ) f 9 j 。 1 9 7 5 年，d ej o n g 在其博士论文中结合模式定理进行了大量的纯数值函数优化计 算试验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论 1 l 】1 1 。 他还建立了著名的d ej o n g 五函数测试平台，定义了评价遗传算法性能的在线指标和 离线指标。 1 9 8 9 年，d e g o l d b e r g 出版了专著搜索、优化和机器学习中的遗传算法( g e n e t i c 第二章遗传算法概述 a l g o r i t t t m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ) ) 5 0 l o 该书系统的总结了遗 传算法的主要研究成果，奠定了现代遗传算法的科学基础。 1 9 9 1 年，l d a v i s 编辑出版了遗传算法手册( h a n d b o o ko f g e n e t i ca l g o r i t h m s ) 书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例【5 “。 自上世纪7 0 年代起，我国学者也将遗传算法广泛的应用于生产实践的各个领域， 并取得许多重要的科研成果。 3 2 基本遗传算法 不同的编码方法和不同的遗传算予可以构成不同的遗传算法，它们有一个共同的 特点，即对生物进化过程中的选择、交叉、变异的模仿，以此完成对问题最优解的 自适应搜索。g o l d b e r g 总结了统一的最基本的遗传算法一一基本遗传算法【5 0 1 。基本 遗传算法只使用选择、交叉、变异这三种基本遗传算子构成完备的算子集合，其遗 传进化操作过程简单、容易理解，是其它遗传算法的基础，它不仅给各种遗传算法 提供了一个基本框架，同时也具有很高的应用价值。 基本遗传算法的构成要素主要包括：染色体的编码方法、个体适应度的评价、遗 传算子( 比例选择算子、单点交叉算子和基本位变异或均匀变异算子) 、运行参数( 包 括群体大小、算法终止进化代数、交叉概率、变异概率) 。 它可以定义为个8 元组： s g a = ( c o d e ，e ，p 0 ，n ，s ，c ，m ，t ) ( 3 1 ) 式中： c o d e - - 个体编码方法e 一个体适应度评价 p o 一初始群体n 一群体规模 s 一选择算予c 一交叉算子 m 一变异算子t 一运行终止代数 对于一个需要进行优化计算的实际应用问题，一般可以按下述步骤来构造求解 该问题的遗传算法1 5 2 1 ： s t e p l ：确定决策变量及其各种约束条件，即确定个体的表现型x 和问题的解空 间： 河海大学硕士学位论文 s t e p 2 ：建立优化模型，即确定出目标函数的类型( 是求目标函数的最大值还是 求目标函数的最小值? ) ，及其数学描述形式或量化方法； s t e p 3 ：确定表示可行解的染色体编码方法，即确定出个体的基因型x 和遗传 算法的搜索空间； s t e p 4 ：确定解码方法，即确定出由个体基因型x7 到个体表现型x 的对应关系 或转换方法； s t e p 5 ：确定个体适应度的量化评价方法，即确定由目标函数值f ( x ) 到个体适应度 的转换规则； s t e p 6 ：设计遗传算子，即确定选择运算、交叉运算、变异运算等具体的操作方 法： s t e p 7 ：确定遗传运算的有关运行参数，即确定遗传算法的n 、t 、p 。、p m 等参数。 由以上步骤可以看出，可行解的编码方法、遗传算子的没计是构造遗传算法时 需要考虑的两个主要的问题，也是两个关键的步骤，而对所求问题的理解是遗传算 法应用成功的前提。 3 ，3 遗传算法实现的基本技术 3 3 1 编码方法 编码是设计遗传算法时的个关键步骤。所谓编码，就是在遗传算法中如何描述 问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索 空间的转换方法。编码方法很大程度上决定了如何进行群体的遗传进化运算以及遗 传进化运算的效率。一个好的编码方法，可以使遗传运算简单的实现和执行。而一 个差的编码方法，却可能使得遗传运算难以实现，也可能会产生许多在可行解集合 内无对应可行解的个体，即无效解。尽管有时产生无效解并不是都有害，但会影响 运行效率。 对于具体实际应用问题设计合理的编码方案是遗传算法的应用难点之一，也是其 重要研究方向。目前还没有一套既严密又完整的指导理论及评价理论准则。目前有 许多种不同的编码方法，大致可以分为三大类： 第一类：二进制编码方法。二进制编码方法是遗传算法中最常见的一种编码方法， 第三章遗传算法概述 它使用的编码集是二进制符号0 和1 所组成的二值符号集( 0 ，1 】，它所构成的个 体基闪型是一个二进制编码符号串，其长度与所解问题要求的精度有关。二进制编 码具有编码、解码操作简单易行；交叉、变异遗传操作便于实现的优点；使得问题 的描述具有最小字符集：有利于应用模式定理对算法进行分析。 第二类：浮点数编码。对于一些多维、高精度要求的连续函数优化问题，使用二 进制编码来表示个体，存在着连续函数离散化时的映射误差，而且不利于反映问题 的特定知识。为了改进二进制编码方法的这些缺点，浮点数编码应运而生。所谓浮 点数编码，是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码 长度等于其决策变量的个数。 第三类：符号编码方法。符号编码是指个体染色体编码串中的基因值取自于一个 无数值含义、只有代码含义的符号集。这个符号集可以是个字母表，如( a , b ，c ， ) ；也可以是一个数字符号表，如自然数( 1 ，2 ，3 ，) 等。它便于在遗传算法中利 用所求解问题的专门知识，而且便于遗传算法与相关近似算法之间的混合使用。本 文在求解配送车辆线路优化问题中便使用了这种编码方法。 3 3 2 适应度函数 与生物学家使用适应度来度量某个物种对其生存环境的适应程度类似，遗传算法 中使用适应度来来度量群体中个体在优化计算中有可能达到、接近或有助于找到最 优解的优良程度。适应度高的个体遗传到下一代的概率较大，而适应度低的个体遗 传到下一代的概率就相对较小。度量个体适应度的函数称为适应度函数( f i t n e s s f u n c t i o n ) 。 评价个体的适应度的一般过程为： ( 1 ) 对个体的编码串进行解码后，得到个体的表现型； ( 2 )由个体的表现型可以得到对应个体的目标函数： ( 3 ) 根据最优化问题的类型，由目标函数按一定的转换规则求出个体的适应 度。 对于求解最大值和最小值的优化问题，基本遗传算法由解空间中的某一点的目 标函数f ( x ) 到搜索空间中对应个体的适应度函数值f ( x ) 的转换方法是： 对于求最大值的问题： 河海大学硕士学位论文 胁w “黑：篡! ：( 3 - - 2 ) 对于求最小值的问题： f c x ，= “一厂x ； ：；i ；：( 3 - - 3 ) 其中c 。i n jc 。是适当小或适当大的数。 遗传算法中，群体的进化过程就是以个体的适应度为依据，通过反复的迭代， 不断的寻求适应度较大的个体，最终就可得到最优解或近似最优解。仅靠上式完全 确定个体的适应度，有些算法会收敛的过快，有些算法会收敛的很慢，此外在同一 遗传算法的不同阶段对适应度的要求也有所不同。因此需要对个体的适应度进行适 当的扩大或缩小，称之为适应度尺度变换。常用的个体适应度尺度变换有线性尺度 变换、乘幂尺度变换、指数尺度变换。 3 3 3 遗传算子 3 3 3 1 选择算予 模仿自然界的“优胜劣汰”，选择操作用来确定如何从父代群体中按某种方法选 取哪些个体遗传到下一代群体的一种遗传运算。 选择操作建立在对个体的适应度进行评价的基础之上，其目的主要是为了避免基 因缺失、提高全局收敛性和计算效率。最常见的选择算子是基本遗传算法中的比例 选择算子，即轮盘赌选择，其基本思想是5 1 】：个体被选中的概率与其适