车辆调度与优化.doc

.中 文 摘 要物流配送车辆调度问题是指：在给定运输任务的条件下，如何派车、组织循环运输，使空驶里程最少，运输成本最低。目前我国大多数的物流企业运输资源分配不均、配送路线安排不合理、运力资源浪费严重，而缺乏完善的物流配送车辆调度优化方案是造成此现象的重要因素之一。因此对物流配送车辆调度问题的研究具有重要的现实意义。目前对单车场、封闭式物流配送车辆调度问题研究较多，而对多车场开放式物流配送车辆调度问题研究较少，但是多车场开放式物流配送车辆调度问题有很强的应用背景。本文针对此问题，建立了一种灵活的多目标组合优化模型，设计了适合多车场开放式车辆路径问题的通用染色体编码方案，并对遗传算法中的交叉变异操作做了详细说明。此模型可以方便的增减优化目标值，并通过测试用例验证了本文设计的优化模型和遗传算法在解决多车场多目标开放式物流配送车辆调度问题中的可行性。自动化立体仓库出库端车辆调度策略的设计是物流配送车辆调度中的一个关键问题，好的调度策略可以大大缩短出库端的配货时间。为此本文引入动态优先级理论，并利用该理论对大型 AS/RS 出库口车辆调度问题进行了深入研究与分析，提出了基于动态优先级的 AS/RS 出库端车辆调度策略，并开发了相应的 AS/RS 出库口发货资源监控系统，即 AS/RS 出库口车辆调度系统，优化了 AS/RS 出库端车辆调度策略，大大提高了物流配送当中的配货效率。本文建立的多目标组合优化模型以及设计的遗传算法求解方案，可以有效的缩减物流配送中的送货时间；设计的 AS/RS 出库端车辆调度优化策略及开发的 AS/RS出库端车辆调度系统，可以有效缩减车辆在出库端的配货时间。本文对以上两种物流配送中的车辆调度问题进行研究，大大提高了物流配送效率、减少了物流配送成本。关键词：物流配送；车辆调度；多目标组合优化；遗传算法第一章 绪论1.1 课题背景物流(Logistics)：指在合适时间，将合适的物品以适当的数量准确地送到顾客手中，它是供应链中最重要的组成部分。一般意义上是指在生产和生活中所涉及的各种物质实体由供给方向需求方的物理性转移过程。这一概念将物流定义在有用的物、供方、需方等几个基本因素之上。也就是说，我们通常所指的物流是指人们在生产和生活中发生的有意义的物流行为。整个物流过程是一个物理过程，只改变时间和空间的状态，不改变其使用价值。其中，时间状态的改变称之为仓储、流通加工等活动，空间状态的改变称之为运输、搬倒等活动。物流配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流中心进行分货、配工作，并将配好的货物及时送交收货人的物流活动。配送成本直接关系到物流企业和部门的效益，目前我国的大多数的物流企业运输资源分配不均、配送路线安排不合理、运力资源浪费严重, 根据中国仓储协会对146个企业的调查显示，用于运输的费用占整个物流费用的比例分别为：在生产企业原料物流中占58%，在生产企业成品物流中占73%，在商业物流中占52%。所以物流配送车辆调度方案的合理优化，对于整个物流运输速度、成本、效益的影响至关重要。运输是指“物”的长距离的移动，任何跨越空间的物质实体的流动，都可称为运输。运输是物流的中心环节之一，被称为国民经济的动脉和现代产业的支柱，从社会经济的角度讲，运输功能的发挥，缩小了物质交流的空间，扩大了社会经济活动的范围并实现在此范围内价值的平均化、合理化。在社会经济的发展中，运输的重要性己经被人们所确认，成为国民经济的命脉。从物流系统的观点来看，运输作业的关键因素包括运输成本和运输速度两个方面。运输成本：是指为两个地理位置的运输所支付的款项，以及管理和维持转移中存货的有关费用，应采用能把系统总成本降低到最低限度的运输方式。运输速度：是指为完成特定的运输作业所需花费的时间。运输速度和成本的关系，主要表现在以下两个方面：首先，运输商提供的服务越快速，实际需要收取的费用也就越高。其次，运输服务越快，转移中的存货就越少，可利用的运输间隔时间越短。因此在选择最合理的运输方式时，至关重要的问题就是如何平衡其服务的速度和成本。运输主要目的就是要以最低的时间、财务和环境资源成本，将产品从原产地转移到规定地点。同时，产品转移所采用的方式必须能满足顾客有关交付履行和装运信息的可得性等方面的要求。所以在物流系统中，必须精确地维持运输成本和服务质量之间的平衡。低成本运输和高质量服务是令人满意的。物流配送车辆调度就是研究怎样合理运输的问题，所谓合理运输就是在实现物资产品实体从物流中心至消费地转移的过程中，充分有效地运用各种运输工具的运输能力，以最少的人、财、物消耗，及时、迅速、按质、按量和安全的完成运输任务。其标志是：运输距离最短、运输环节最少、运输时间最短和运输费用最省。据统计运输费约占整个物流费用的40%，占销售收入的2.88%。物流配送车辆调度问题就是指在给定运输任务的条件下，如何派车、组织循环运输，使空驶里程最少，运输成本最低。车辆调度是物流管理最重要的部分，正确合理的调度可以有效减少车辆的空驶率，实现合理路径运输，从而有效减少运输成本，节约运输时间，提高经济效益。1.2 课题研究的意义物流产业的发展，将从整体上改变经济运行的方式，提高经济运行效率，对增强国际竞争力将起到巨大的推动作用。我国国民经济的发展呼唤物流的进一步发展，对物流的发展要求如下：(1) 降低流通成本在 GDP 中的比重：在我国目前工业企业生产中，直接劳动成本占总成本的比重不到 10，而物流费用占商品总成本的比重，从账面反映约为40，全社会物流费用支出约占 GDP 的 20，而其他发达国家一般在 10%左右。这反映了我国物流系统落后，流通成本太高，反映了我国国民经济运行质量不高。通过发展现代物流业来促进物流合理化，降低流通成本在 GDP 中的比重，无疑将成为我国新的经济增长点。“十五”期间，如果我国物流费用降低到占 GDP 的 15，每年将为社会直接节约 2400 亿元的物流成本。(2) 减少企业流动资金占用：我国工业企业和流通企业由于物流基础设施、技术和管理的落后，原材料、半成品、成品积压严重，大量流动资金被占用，周转速度很慢，物流成本过高。据统，1992 年，国有独资、控股工业企业流动资金占用1 万多亿元，周转速度为 1.62 次/年；1999 年，国有独资、控股工业企业流动资金达 31000 亿元，周转速度仅 1.2 次/每年，与发达国家相比非常落后。如果工业企业把物流职能分离出来交给第三方物流企业，通过其先进、科学的专业化服务，就可以减少流动资金占用，提高核心竞争能力，实现从粗放式经营向集约式经营转变。(3) 电子商务的发展需要物流做基础：电子商务是流通领域的一场革命，它把3商品买卖虚拟成一个大的市场，使客户在任何地点、任何时间都可以购买商品。但是，电子商务需要将网上订的货物及时送到可能在任何地方的客户手里，这就给物流系统带来很大的挑战。实际上，物流已经成为电子商务发展的瓶颈，需要建立具有响应性、灵活性和可视化的现代物流系统，需要第三方物流企业的服务。世界 500强中相当多的企业都是通过第三方物流来解决它的供应链与销售问题的，很多跨国公司在欧洲、亚洲、美洲等地分别有不同的第三方物流企业为他服务。(4) 现代物流产业的发展，将减少由于低水平、条块分割的物流方式造成的巨大物耗：在传统的物流框架下，一件商品从生产出来到最终的消费环节，至少要被搬倒、装运十几次。实行社会化的多式联运、一单到底，物流过程中的物耗至少可以减少几倍。我国汽车空驶率达 37左右，意味着全国每年有 150 多万辆载重汽车无活可干，这种潜在浪费至少也在数千亿元。按现代物流要求，合理的流程设计可使空驶率降低到 5以下。在现代物流集约化、一体化的发展中，配送是直接与消费者相连的重要环节，其核心部分为配送车辆的集约、货物配装及送货过程，而配送车辆优化调度是物流系统优化、物流科学化的关键一环，是货物从配送中心送达收货人的过程。配送首要解决的是车辆的调度问题，几十年来这一直是一个研究的热点，在满足和完成各任务的前提下，正确合理的安排行车路线、提高配送车辆的利用率就可以有效的节省时间从而减少运输成本。另外对出库口车辆调度问题的研究，将有效减少货物装配的时间。所以本文对物流配送车辆调度的研究具有重要意义。1.3 国内外研究现状车辆调度问题最早是由Dantzig和Ramsert在上个世纪50年代末期提出，该问题一般称之为VehicleRouting Problem(VRP)或者Vehicle Scheduling Problem(VSP)，现在我们将车辆调度问题一律简称为VRP。 VRP提出后就很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科的专家对该问题进行了大量的理论研究及实验分析，取得了很大进展。国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1962年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP模型；1964年，Clarke和Wright提出了一种启发式节约法来建立车队配送路线；1968年，Rao等人在VRP 集分割的基础上引入了列生成方法进行求解，这种算法本质上是最短路径算法，同时结合了分枝定界算法；1971年，Eilon 等人提出将动态规划法用于固定车辆数的VRP，通过递归方法求解；1981年，针对带能力约束、时间窗以及无停留时间的VRP，Fisher提出了三下标车辆流方程；Thangiah于1991和Joe于l993分别用遗传算法求解VRP，但是都存在“早熟收敛”的问题；2001年，Tan，Lee，Du结合遗传算法、tabu树搜索算法的优点，形成知识库，用人工智能的方法来求解；2002年，Taranrilis,Kiranondis使用空间决策支持系统来解决车辆路径问题。在国内,有关车辆调度问题的研究是在20世纪90年代以后才逐渐兴起的，比国外相对落后。国内研究对象主要是旅行商问题(Traveling Salesman Problem，简称TSP)、中国邮递员问题(Chinese Postman Problem，简称CPP)、有向中国邮递员问题(DirectedChinese Postman Problem，简称DCPP)等，系统性研究还很少见到。西南交通大学的李军教授和郭耀煌教授对车辆优化调度的基础理论及各类问题进行了系统的研究；李大为等以TSP的最近距离启发式为基础，通过设置评价函数来处理时间窗约束，求解了简单的VRP。另外在利用现代优化算法(如:遗传算法、神经网络方法、模拟退火等)对简单TSP的求解取得了一定成果。蔡延光等应用模拟退火法针对满载问题进行了求解。总体来说，目前我国对车辆调度问题的理论研究仍相对薄弱，需要进一步研究。1.4 本文内容的安排本课题的研究以内蒙古蒙牛乳业股份(集团)有限公司的物流配送业务为背景，主要研究两方面内容：首先，对多车场多目标开放式物流配送车辆调度问题做了研究，以此可以优化对客户的派车问题及最佳车辆路径的选择问题。其次，对AS/RS出库端车辆调度策略做了研究，以本文建立的策略对出库口的车辆分配车位，可以减少车辆的配货时间。本文的研究将在最大程度上减少蒙牛集团的运输成本，给蒙牛集团带来可观的经济效益。本文研究的具体内容如下：第一章绪论：介绍了本文研究的背景以及研究的目的与意义，并对国内外对车辆调度问题的研究现状作了简单介绍。第二章车辆调度问题概述：首先对物流配送车辆调度问题进行了描述，其次介绍了车辆调度问题的构成要素和车辆调度问题的分类，最后列举了车辆调度的相关求解算法。第三章遗传算法概述：首先对GA的背景作了简单的介绍，接着对GA算法的基本概念、工作流程和算法的组成做了详细描述。第四章用遗传算法解决多车场多目标开放式车辆调度问题：首先介绍了两种求解多车场车辆调度的方法，然后对多车场多目标开放式车辆调度问题的研究背景进行了描述，在此基础上确定了多车场多目标开放式车辆调度问题的数学模型，并详细描述了用遗传算法对多车场多目标开放式车辆调度问题的求解过程，最后用实例证明了用遗传算法求解此问题的可行性。第五章对AS/RS出库端车辆调度策略做了研究，提出了基于动态优先级的AS/RS出库端车辆调度策略，并开发了相应的AS/RS出库端发货资源监控系统，即AS/RS出库口车辆调度系统，以此策略对出库口的车辆分配车位,可以减少车辆的配货时间。第六章总结与展望：归纳与总结了本文的创新之处，并提出进一步研究车辆调度问题的方向。第二章 车辆调度问题概述2.1 车辆调度问题的描述“配送”一词是日本引进美国物流学时，对英文单词delivery一词的意译，我国转学于日本，也直接用了“配送”这个词。配送是物流系统中由运输派生出的功能，是短距离的运输。具有： 配送距离较短，位于物流系统的最末端，处于支线运输、二次运输和末端运输的位置。 在配送中，也包含着其他的物流功能，是多种功能的组合。 配送是物流系统的缩影，也可以说是一个小范围的物流系统。从物流来讲，配送几乎包括了所有物流的要素，车辆调度就是其中一个最重要且有意义的要素，所以本文研究的是物流配送车辆调度问题。物流配送车辆调度优化问题最早是由Dentzing和Ramser在1959年第一次提出的。从此，车辆调度优化问题很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者的极大重视，同时也逐渐成为运筹学与组合优化领域的热点研究问题。由于它应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。国外将物流配送车辆优化调度问题归结为或称之为Vehicle Routing Problem和Vehicle Scheduling Problem。本课题采用的是后者，也就是将车辆调度问题归结为VSP问题：Vehicle Scheduling Problem。物流配送车辆调度问题的一般性定义是：物流配送车辆调度问题是把一系列的装货点和（或）卸货点，有机的组织起来，形成一系列行车线路，使待调度车辆能够高效、节能且有序地通过这些点。当然，这种组织方式是应该在满足一定的约束条件（例如：用户对货物的需求量、一次性发货量、应交发货时间、单个车场的车辆容量限制、路程约束、时间限制等），最终达到缩短里程、减少开支费用、缩短运输时间、使用车辆数尽量少等优化目标。物流配送车辆调度问题一般研究的是在配送中心及用户位置均已知、资源及运输能力充分、各用户需求量己知的前提下，如何合理、高效、低成本的解决分配与运送的问题，也就是说如何将货物从配送中心按照一定的要求发送到若干个用户点。配送方案应该包括两个相关的环节： 有哪些用户要被分配到一条回路上，即有哪些用户的货物应该安排在同一辆车上； 每条配送路线上用户的连接顺序。物流配送车辆调度的最优解实际上是一个效率最高的运输方案，它应明确的规定应派出的车辆型号、车辆数以及每辆车的具体行车路线。实施这一配送方案，即可以满足用户的需求，又可以使总的运输行程最短。2.2 车辆调度问题的构成要素物流配送车辆调度问题主要包括货物、车辆、配送中心、客户、运输网络、约束条件、和目标函数等要素。(1) 货物货物是我国交通运输领域中的一个特有专用概念，交通运输领域将其经营的对象分为两大类：一类是人，一类是物。“物”这一类的运输目标统称为货物。我们这里所说的货物是指物流配送的对象，每批货物都包括品名、包装、重量、体积、要求送到(或取走)的时间和地点，能否分批配送等属性。(2) 车辆车辆是“车”与车的单位“辆”的总称。所谓车，是指陆地上用轮子转动的交通工具；所谓辆，来源于古代对车的计量方法。本文所说的车辆是指运载货物的工具，车辆的主要属性包括：类型、工作时间、配送前的停放位置、载重量以及配送任务完成后的停放位置等。(3) 配送中心配送中心是指接受供应者所提供的多品种、小批量的货物，通过存储、保管、分拣、配货以及流通加工、信息处理等作业后，将按需要者订货要求配齐的货物送交顾客的组织机构和物流设施。本文所说的配送中心是指从事配送业务的物流场所或组织，如可以进行货物集中、分拣、配货、送货等的仓库、车站、港口等固定场所。在物流配送系统中，配送中心可以只有一个，也可以同时具有多个。配送中心专业性强，和客户有固定的配送关系，一般实行计划配送，需配送的商品有一定的库存量，一般情况很少超越自己的经营范围。配送中心的设施及工艺流程是根据配送需要专门设计的，所以配送能力很强，配送距离较远，配送的品种较多，配送数量比较大。使用配送中心配送覆盖面宽，规模大，因此，必须有一套配套的大规模实施配送的设施。本文的研究背景就是基于配送中心的物流配送中车辆调度问题的研究。(4) 客户客户指的是物流配送的服务对象，可以是各种零售店，也可以是分仓库，还可以是别的仓库的外调。也就是说客户是有配送任务的对象的统称。客户的属性包括需求数量、需求时间、需求次数及目前需求的满足动态等。8(5) 运输网络本文的运输网络采用了离散数学中对网的介绍，配送中心、客户、停车场等构成网络的顶点、它们之间的交互运输构成了无向边，具体的运输任务被称为由有向弧组成的运输的网络。边、弧的属性包括方向、权值和交通流量限制等。在运输网络中，边或弧具有一定的权值，该值可以表示为距离、时间或费用。边或弧的权值变化具有以下几种情况：固定不变，不随着时间和车辆的不同而变化；随时间段或者车辆不同而变化；既随着时间的不同而变化，又随着车辆的不同而变化。对运输网络中的定点、边或弧的交通流量要求分为以下几种情况：无流量限制；边、弧限制，即每条边、弧上同时行驶的车辆数有限；顶点限制，即每个顶点上同时装、卸货的车辆数有限；边、弧、顶点都有限制。(6) 约束条件物流配送车辆调度问题应满足以下约束条件：能够满足所有客户对货物品种、规格、数量的要求；能够在客户要求或者承受的时间内将货物送到；运输车辆每天的运行时间、运行历程都要有一定的限制，不能超过预定的时间或者里程；在物流配送过程中实际装载的货物不能超过车辆的最大载重要求，也就是不能超载；当然，客户的需求也必须在物流中心现有的运力范围内，也就是目前有这个能力去完成待完成的任务。(7) 目标函数目标函数是指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。简单的说，就是你求解后所得出的那个函数。在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。本课题研究的物流配送车辆调度问题，可以只选用一个目标，也可以同时选用多个目标。使用概率比较多的目标函数主要有： 配送的距离最短，也就是在配送过程中车辆所走的路程最短。在实际的物流配送中，配送里程直接关系到配送车辆的耗油量、磨损程度以及司机疲劳程度等因素。因此，在众多的目标函数中选择配送里程最短的目标，在某种程度上可以直接减少运输成本。 配送车辆的载重量与公里数最少，这种方式的目标是将配送距离与车辆的载重量进行了有机结合，综合来考虑载重量与配送距离之间的关系，以达到最优化的配置，是比较常用的目标之一。9 综合费用最低，完成最多的任务，花最少的成本，这是物流配送中的一个根本原则。降低各项开支的综合费用是实现物流配送业务中取得良好经济效益的根本要求。在物流配送中，与配送相关的费用包括：车辆维护费用、车辆耗油费用、车队管理费用、装卸工所需费用、各部门人员工资费用等。 准时完成任务，无论是分仓库还是分销点，各种用户都对需求的交货时间有着严格的要求。配送任务完成的准时性，很大程度上决定了配送公司在客户心中的地位，决定了公司的信誉度。各种成本虽然是必须考虑的因素，也是最实际的因素，但是为提高配送服务质量，按时完成用户的需求，有时需要将准时性最高作为配送路线的目标。 使用的车辆数最少，该目标考虑的是使用尽量少的车辆去完成指定的配送任务。前面的目标叙述了各项指标的要求，但是如果车辆跑的距离最短、也是按时到达的，但是使用的车辆都没有满载，这无疑也是对资源的一种浪费，也不能是整体配送效益达到最优，所以必须要求车辆的满载率最高，以充分利用车辆的装载能力。 劳动消耗最低，充分考虑人的因素。也就是使用最少的司机数，这当然和前面使用最少的车辆数是一致的，只有车辆少了，司机才会少，只有车辆都装满了，才会使用最少的车辆。只有选择的距离最短了，司机才能工作最短的时间，这些都是重要的目标值。2.3 车辆调度问题的分类车辆调度问题(Visual-Schedule Problem，VSP)被提出后，国内外各学科的学者从不同角度对它进行了各种研究，并各自按不同的标准对其进行了分类。综合起来可分为以下几种：(1) 按车场数目分：有单车场车辆调度问题和多车场车辆调度问题。单车场问题指配送系统中仅有一个配送中心，多车场车辆调度问题指配送系统中存在多个配送中心。(2) 按配送任务特征分：分为纯送货问题、纯取货问题以及取送混合问题。其中纯送货问题指仅仅考虑从物流中心向客户送货，而不考虑从用户向配送中心送货；纯取货问题指单纯考虑把各客户供应的货物取到配送中心不考虑配送中心给客户供货问题；取送混合问题是上面两者的有机组合，既要考虑将客户需求的货物从物流中心送到各个客户，同时还考虑将客户提供的货物从客户取到物流中心。(3) 按车辆载货状况分：分为满载问题、非满载问题以及满载和非满载混合问题。10满载问题指的是货运量不小于车辆容量，完成一项任务需要不少于一辆车；非满载问题指的是货运量小于车辆容量，多项货物合用一辆车，在实际的车辆配送过程中经常会出现这种处于非满载的状态；满载和非满载混合问题是上述两者的有机组合，既存在一部分客户需求和供应的货物数量大于或等于车辆的载重量，同时又存在另一部分客户需求量或供应的货物数量小于车辆的载重量，上述情况就造成一部分配送车辆满载运行，而另一部分运行在非满载的状态。(4) 按客户对货物处理时间的要求分：分为无时间约束问题和有时间约束问题。其中无时间约束问题指的是客户对货物的取走和送到的时间没有严格的要求；有时间约束问题指的是客户要求将其需求的货物在一定的时间范围内送到，并且将供应的货物在一定的时间范围内取走。有时间约束问题又分为硬时间窗问题和软时间窗问题，硬时间窗问题指的是对任务的完成有硬性的时间限制，或者说时间要求。软时间窗问题指的是有一定的时间约束，但是相对比较宽松，尽量在用户规定的时间范围内将货物送到或者取走，但是如果超越了规定的时间限制可能要有一定的处罚机制。(5) 按车辆类型分：分为单车型问题和多车型问题。单车型问题指所有配送车辆类型和容量相同，这种情况方便统一管理和装卸。多车型问题指在执行任务过程中的配送车辆类型和容量不完全相同，这种情况处理起来比较复杂。(6) 按车辆对车场所属关系分：分为开放式车辆调度问题和封闭式车辆调度问题。开放式车辆调度问题指的是车辆完成配送任务后可以不返回其原来发出车场；封闭式车辆调度问题指的是车辆完成配送任务后必须返回其原来发出车场。本课题是针对开放式车辆调度问题进行的研究。(7) 按优化目标数分：分为单目标问题和多目标问题。单目标问题指的是仅考虑一个配送目标；而多目标问题指的是同时考虑多个配送目标。2.4 车辆调度的相关求解算法用于解决物流配送车辆调度问题的算法分为：精确算法和启发式算法两大类，精确算法一般用于解决小规模的VRP问题，车辆调度问题应用最为广泛的算法是启发式算法，启发式算法并不追求问题的最优解，而是强调问题解的满意性。所以，启发式算法对于大规模的车辆调度问题能在较短的时间内获得较满意的次优解，并且这些算法的通用性也很强。常见的启发式算法有如下几种：(1) C-W Savings算法C-W Savings算法采用了几何中三角形的边定理，即三角形的两边之和大于第三边。当路径中有这样的两个边时用第三边来代替，以达到节约配送距离的目的。我们可以设节点i和节点j之间的节约量为Sij，这两点和节点o之间的距离为Doi和Doj，则Sij=Doi+Doj-Dij（ij, i,j=1,2,n,），算法首先求出所有Sij，并按非增顺序排列。然后从最大的Sij开始，确定是否存在两条路径，其中一条从弧(0,j)开始，而另一条以(i,o)结束。如果存在，则去掉弧(0,j) 、(i,o)，引入弧(j,i)合并这两条路径。重复上述过程直到没有路径可以合并。(2) Sweep算法Sweep算法是一种“先分组后路线”的算法。所谓的分组就是：首先计算出要访问的顾客的位置的极坐标，并把这些极坐标按角度大小排序，然后在未分配到任何路径中的顾客中从角度最小的顾客开始，依次将顾客归并到相应的路径中，直到车辆的能力约束满足为止，再重新选择新的车辆，重复上述过程，直到所有的顾客都分配完毕。最后利用TSP的优化算法对各子路经进行优化。(3) Cluster and Route算法一般有两种方法：先聚类后排序方法(CFRS)和先排序后聚类方法(RFCS)。CFRS最早由G.Gillett等提出，它是先用启发式方法将节点分成若干路径，然后对路径中的点进行排序。RFCS由Besley提出，它先对所有节点进行TSP排序，然后将大的路径分成若干个小路径。(4) 遗传算法GA遗传算法使用群体搜索技术，借用适者生存规律进行局部搜索改进，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，每一次进化则对应解的一次迭代，并逐步使群体进化到包含或接近最优解的状体。当迭代次数达到最大次数限制或群体中的个体无显著差异时，迭代终止。J.Lawrence最先将GA应用于求解车辆调度问题。(5) 禁忌搜索算法TSTS的思想由Glover最早提出，它通过对避开一些局部最优解，达到接纳一部分较差解，从而跳出局部搜索的目的。TS是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类思维过程的一种模拟。禁忌搜索算法通过利用一个禁忌表记录已经到达过的局部最优点，并在后面的搜索中，根据某种限制循环的规则和禁忌表中记录的信息在当前搜索邻域中取一个合适的解。(6) 模拟退火算法SA其思想最早有Metropolis 1953年提出，Osman于1993年用之解决VRP。模拟退火算法用固体退火模拟组合优化问题，将内能模拟为目标函数值，温度演化成控制参数。由初始解和控制参数初值开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减控制参数值，算法终止时的当前解即为所得近似最优解。(7) 蚁群优化算法ACO蚁群算法模拟了蚁群搜索食物的行为。蚂蚁在寻找食物时，会在它所经过的路径排放一种外激素(pheromone, 在算法中称为信息素) 作为标记，排放的量则根据路径长度和食物的等级决定。这些外激素可以指导蚂蚁的运动方向，并使蚁群朝着外激素强度高的方向移动。在用蚁群算法解决车辆调度问题时，可根据优化的目标函数个数，构造多组相互协作的人工蚁群，使各组分别优化其中的一个目标函数，并以共用解的方式建立协作关系。在以上求解VRP的算法中，有的算法利用全局信息进行整体搜索适合构解，如GA等；还有的利用局部信息，适合改进解，如SA、TS等。每种方法都各有所长与不足，一般来说，根据具体的求解问题，采用两种或两种以上的混合方法，能够得到更好的解。2.5 小结本章从车辆调度基本理论的角度，首先介绍了车辆调度涉及到的基本概念，包括了问题的描述和构成要素。其次对车辆调度问题的分类进行的描述，列举了一些相关解决车辆调度问题的算法。第三章 遗传算法概述3.1 背景介绍遗传算法 (GeneticA lgorithm.G A)是由美国Michigan大学J.Holland教授和他的学生发展建立的一类借鉴生物界的进化规律 适者生存、优胜劣汰遗传机制演化而来的概率搜索算法。GA算法是近几年发展起来的一种崭新的全局优化算法，遗传算法作为一种非数值并行算法，其思想起源于生物遗传学适者生存的自然规律，通过自然选择、遗传、变异等作用机制，实现各个体适应性的提高。它是多学科结合与渗透的产物，已经发展成一种自组织、自适应的综合技术，广泛应用在计算机科学、工程技术和社会科学等领域。GA算法是通过对自然进化现象的模拟，利用简单的编码技术和进化机制来解决复杂的优化问题。特别是由于它不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存在等假设，以及其固有的并行性。它是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法，其通过给解向量编码，形成初始种群，然后用变异、交叉、重组、自然选择等算子，进行并行迭代求得优化解。由于遗传算法具有不依赖于问题模型采用随机运算，对搜索空间无特殊要求、无需求导，具有全局最优性求解能力、隐含并行性、收敛速度快以及能高效率地解决不同非线性问题的鲁棒性的特点。因此近年来有很快的发展，在组合优化、自适应控制、机器学习等许多领域获得应用，并在电气自动化、计算机和通信以及人工智能的许多领域取得了非凡的成就，尤其适合求解NP-hard问题。3.2 遗传算法的基本概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，因而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：(1) 串(String)它是个体(Indlvidual)的形式，对应于遗传学中的染色体(Chromosome)。(2) 群体(Population)个体的集合称为群体，个体是群体的元素。(3) 群体大小(Populationsize)在群体中个体的数量称为群体的大小。(4) 基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S=1010，则其中的1，0，1，0这4个元素分别称为基因。(5) 基因位置(GenePosition)一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左边向右计算，如在串S=1011中，0基因位置是2。基因位置对应于遗传学中的地点(Locus)。(6) 基因特征值(GeneFeature)在用串表示整数时，基因的特征值与二进制数的权一致，如在串S=1011中，第三基因位值上的1，它的基因特征值为2；第一基因位值上的1，它的基因特征值为8。(7) 串结构空间S在串中，基因任意组合构成的串的集合称为串结构空间。基因操作是在结构空间中进行的。(8) 适应度(Fitness)表示某一个体对于环境的适应程度。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数适应度函数，用于计算个体在群体中被使用的概率。(9) 选择(Selection)就是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代，故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度来决定其繁殖量的，故有时也称为非均匀再生(Differentia1Reproduction)。(10) 交叉(Crossover)就是在选中用于繁殖下一代的个体中，对两个不同的个体随机选取一个子串进行交换，从而产生新的个体。(11) 变异(Mutation)就是在选中的个体中，随机选择两点，将两点间的子串按一定的规则进行变异。3.3 遗传算法的工作流程遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉及的五大要素为：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。其流程框图如图3.1所示。图3.1遗传算法流程图从图3.1可以看出，遗传算法的运行为一个典型的迭代过程，其必须完成的工作内容和基本步骤如下：(1) 选择编码策略，将解空间中的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的编码。(2) 定义适应度函数f(x )。(3) 确定遗传策略，包括选择群体大小n，选择、交叉、变异方法，以及确定交叉概率pc、变异概率pm等遗传参数。(4) 随机初始化生成群体P。(5) 计算群体中个体位串解码后的适应度f(x)。(6) 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体。(7) 判断群体性能是否满足某一指标，或者己完成预定迭代次数，不满足则返回步骤(6)，或者修改遗传策略再返回步骤(6)。在遗传算法的应用过程中，人们往往结合问题的特征和领域知识对基本遗传算法进行各种改变，形成了各种各样具体的遗传算法，从而使得遗传算法具备求解不同类型优化问题的能力。3.4 遗传算法的组成遗传算法主要由六个部分组成：编码方式、初始群体产生的方法、评价函数、遗传操作、算法终止条件、算法参数的设置。要利用遗传算法成功的解决物流配送车辆调度问题，就需要对这六个步骤进行设计。3.4.1 编码方式在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达到优化的目的，这是遗传算法的特点之一。遗传算法通过这种对个体编码的操作，不断搜索出适应度较高的个体，并在群体中逐渐增加其数量，最终寻求出问题的最优解或近似最优解。在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就成为编码。编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。编码方法除了决定了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。一个好的编码方法，有可能会使得交叉运算、变异运算等遗传操作可以简单的实现和执行。而一个差的编码方法，却有可能会使得交叉运算、变异运算等遗传操作难以实现，也有可能会产生很多在可行解集合内无对应可行解的个体，这些个体经解码处理后所表示的解称为无效解。虽然有时产生一些无效解并不完全都是有害的，但大部分情况下它却是影响遗传算法运行效率的主要因素之一。针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，De Jong曾提出了两条操作性较强的使用编码原则：编码原则一：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。编码原则二：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。第一个编码原则中，模式是指具有某些基因相似性的个体的集合，而具有短定义长度、低阶且适应度较高的模式称为构造优良个体的积木块或基因块，这里可以把该编码原则理解成应使用易于生成适应度较高的个体的编码方案。第二个编码原则说明了我们为何偏爱于使用二进制编码方法的原因，因为它满足这条编码原则的思想要求。事实上，理论分析表明，与其他编码字符集相比，二进制编码方案能包含最大的模式数，从而使得遗传算法的确定规模的群体中能够处理最多的模式。由于遗产算法应用的广泛性，迄今为止人们己经提出了许多种不同的编码方法。总的来说，常用的编码方法可分为三大类：二进制编码方法、实数编码方法、有序串编码方法。二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集0，1，它所构成的个体基因型是一个二进制编码符号串。在二进制编码方式的遗传算法中，遗传操作是作用在编码空间上的，操作后的二进制串通过解码转换到解空间，在这里进行评估选择(如图3-2所示)。图3.2 编码解码操作使用二进制编码方法，在求解高维优化问题时，二进制串会很长，因而算法的搜索效率很低。为了克服二进制编码方法的缺点，对于变量是实向量的情况，可以直接采用实数编码方法。实数编码表示比较自然，较易引入相关领域知识，因此，实数编码还可以使遗传算法更接近问题空间，避免了编码和解码的过程 ，其使用将越来越广泛。对很多组合优化问题，目标函数的值不仅与表示解的字符串中各字符的值有关，而且与其所在字符串的位置有关，这样的问题称为有序问题，用有序串编码方法表示。这类编码方法较多地用在组合优化问题中，如二次分配问(QuadraticAssignment problem)，旅行商问题(Traveling Salesman Problem)我们常用的是有序串的编码方式。基于遗传算法的以上特点，在本文用遗产算法求解物流配送车辆调度问题时，我们采用有序串编码方式的染色体设计。初始化过程有很多种，在研究遗传算法时，常常随机产生初始群体，这样做的好处是产生方式不依赖于问题，也就是对于任何问题，我们都可以采用这种方式来生成初始群体，由于本文是对某个特定的非线性规划问题求解，所以我们采用人机交互方式来初始化群体，这样结合人类智慧使算法优化收敛速度更快。3.4.2 适应度函数在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应度程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少。与此相似，在遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大，而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数就称为适应度函数（Fitness Function）。遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的一般过程是：(1) 对个体编码串进行解码处理后，可达到个体的表现型。(2) 由个体的表现型可计算出对应个体的目标函数值。(3) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。遗传算法中，群体的进化过程就是以群体中各个个体的适应度为依据，通过一个反复迭代过程，不断地寻求出适应度较大的个体，最终就可以得到问题的最优解或者近似最优解。对于本课题的多车场多目标开放式车辆调度模型优化问题，采用函数值来评价解的好坏，这种方法是最直接，也是最方便的方法，取函数值最小的解为最优解。3.4.3 选择策略遗传算法中的选择策略就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算，选择提供了遗传算法的驱动力。如果驱动力过大，遗传搜索将过早地终止，而如果驱动力太小，进化过程将变得难以接受。相对而言，较小的驱动力一般能使群体保持足够的多样性，从而增大了算法收敛到全局最优的概率。选择操作是建立在对个体的适应度进行评价的基础之上的，选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。下面是遗传算法中较常用到的几种选择策略。(1) 繁殖池(Breeding Pool)选择繁殖池选择首先根据当前群体中个体的适应值，按下式计算其相对适应值：其fi 是群体中第 i 个成员的适应值，N是群体规模。则每个个体的繁殖量为：此处Round(x)表示与x距离最小的整数。计算出群体中每个个体的繁殖量，即可将它们分别复制N个以生成一个临时群体，即繁殖池(Breeding pool)再通过在繁殖池中随机地抽取成对个体进行交配，所产生的后代将取代当前群体形成下一个群体。显然，个体复制到繁殖池的数目越大，则它被选到进行交配的机会也就越多，而对于 Ni =0 的个体，它们将被淘汰出整个演化过程。在实现算法时需要注意的是，繁殖池中个体的数目不一定正好等于N。(2) 轮盘赌选择(Roulette Wheel Selection)轮盘赌选择是由Holland提出的，是最知名的选择方式之一，其基本原理是根据每个染色体适应值的比例来确定该个体的选择概率或生存概率。选择的过程就是旋转轮盘若干次（次数等于种群规模），每次为新种群选出一个个体。轮盘赌选择策略在遗传算法中使用的最多，它的具体选择过程为：先计算个体的适应值Pi ，然后根据选择概率把轮盘分成N份，其中第 i 扇形的中心角为 2Pi。在进行选择时，先转动轮盘，若某参照点落入到第i个扇形内，则选择个体i。可见，这种选择方式非常类似轮盘赌中的转盘，小扇区的面积越大，骰子落入其中的概率也越大，即个体的适应值越大，它被选择到的机会也越大。从而，其基因结构被遗传到下一代的可能性也越大。(3) 锦标赛（Toumament）选择锦标赛选择也是一种基于个体适应度之间大小关系的选择方法。在选择时，每次进行适应度大小比较的个体数目称为竞赛规模，一般情况下，竞赛规模K的取值为2。具体操作过程如下：首先，从群体中随机选取K个个体进行适应度大小的比较，将其中适应度最高的个体作为生成下一代的父体。其次，将上述过程重复M次，就可得到下一代群体中的M个个体。显然，这种选择方式也使得适应度好的个体具有较大的“生存”机会。同时，由于它只使用适应度的相对值作为选择的标准，而无个体适应度的算术运算。从而它能避免超级个体的影响，在一定程度上，避免发生过早收敛现象和停滞现象。3.4.4 杂交策略交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。它在遗传算法中起着关键作用，是产生新个体的主要方法。一方面它使原来群体中优良个体的特性能够在一定程度上被遗传和继承，另一方面它使算法能够搜索新的基因空间，从而使新群体中的个体具有多样性。交叉或基因重组是遗传算法获取新的优良个体的最重要的手段。经常采用的交叉算子有以下几种：(1) 部分映射交叉(Partially Mapped Crossover，简称PMX)这种算子在构造后代时通过从一个父体中选取一段路径，并尽可能多的保留另一个父体中城市的次序和位置。选择一个路径时，首先随机选取两切割点作为交换操作的边界。例如两父体(两切割点用“|”标记)P1= (1 2 3 | 4 5 6 7 | 8 9) P2= (2 5 4 | 1 8 7 6 | 3 9)产生后代的过程如下：首先交换两切割点之间的相应段(符号“x” 表示目前未知值)，得到Q1=( x x x | 1 8 7 6 | x x ) Q2= ( x x x | 4 5 6 7 | x x)这一交换同时定义了一系列的映射：然后从各自的父体中填入无冲突的城市，得