配送是物流活动中直接与消费者相连的环节。配送成本占物流的各项成本的比例相当高。配送线路合理与否影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。因此，物流车辆路线问题(VRP)成为国内研究的热点。
运筹学，用定量化方法了解和解释运行系统、为管理决策提供科学依据的学科。它把有关的运行系统首先归结成数学模型，然后用数学方法进行定量分析和比较，求得合理运用人力、物力和财力的系统运行最优方案。运筹学有广阔的应用领域，是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。
在运筹学中有解决物流配送问题的有效方法。本文主要介绍了节约法、遗传算法并用这些方法解决实际物流配送问题。
关键字：物流配送，节约法，遗传算法
Abstract
Distribution logistics activities directly connected with the consumer segment. The costs of logistics and distribution costs account for a very high proportion. Distribution line is reasonable or not affect the distribution of speed, cost and efficiency, especially multi-user distribution lines to determine is a complex system engineering. Therefore, the logistics vehicle routing problem (VRP) has become a hot domestic research.
Operations research, using quantitative methods to understand and explain the operating system, to provide a scientific basis for management decisions disciplines. It related to the operation of the system is due to a mathematical model first, and then use mathematical methods for quantitative analysis and comparison, and seek the rational use of human, material and financial resources of the system to run the optimal solution. Operations research has broad applications, the soft science of \"hardness\" of the larger one discipline, the nature of the logic of both mathematics and mathematical logic, is a basic theory of system engineering and modern management science and not lack of methods, means and tools.
There are effective ways to solve the logistics problems in operations research. This paper describes the conservation law, scanning method, tabu search, genetic algorithm and use these methods to solve practical problems of logistics and distribution.
Keywords: logistics, saving, scanning method, tabu search, genetic algorithm
现代运筹学算法在物流配送中的应用
1绪论
1.1发达国家和地区物流配送现状
理解物流配送概念离不开对物流概念的分析。物流概念最早是在美国形成的，被称为“physiealDistribution”(即Pn)，译成汉语是“实物分配”或“货物配送”。1963年被引入日本，物流被定义为“在连接生产和消费间对物资履行保管、运输、装卸、包装、加工等功能，以及作为控制这类功能后援的信息功能,，在物资销售中起了桥梁作用”。因此，现代物流是以满足消费者的需求为目标，把制造、运输、销售等市场情况统一起来思考的一个产业概念。配送是物流系统的核心环节之一，配送在英语中的原语是“delivery”，是交货送货的意思。在日本工业标准Jis中，将配送定义为“将货物从物流结点送交收货人”强调了送货的含义。可以说，物流配送是连接生产与消费之间的一种中介服务，是物资供应的种重要形式。配送是“配”和“送”有机结合的形式，它利用有效的分拣、配货等理货工作，使送货达到一定的规模，以利用规模优势取得较低的送货成本。 推行配送制有利于合理配置资源。由于实施配送可以做到以配送企业的库存取代社会上千家万户的零散库存，或者说，可以使库存相对集中，因此，有条件也有可能按照统一计划合理分配和使用资源，做到物尽其用。推行配送制可以降低物流成本，促进生产快速发展。这是因为各种流通要素相对集中，有益于开展规模经营活动；流通的物质要素相对集中，也便于合理安排各环节上的物流活动，使总体运动协调一致，最终会减少物流领域内的劳动消耗和费用支出。推行配送制能够充分发挥专业流通组织的综合优势。推行配送很容易使不同的流通组织联系在一起，从而构成多功能的、一体化的物流运动。这种以配送作为媒介而形成的一体化运作较之各个专业企业独立运作更能发挥流通组织的整体优势和综合优势。 从20世纪60年代起，商品配送的合理化在美国普遍得到重视。为了在流通领域产生效益，美国企业采取了以下措施：一是将老式的仓库改为配送中心；二是引进电脑管理网络，对装卸、搬运、保管实行标准化操作，提高作业效率；三是连锁店共同组建配送中心，促进连锁店效益的增长。美国连锁店的配送中心有多种，主要有批发型、零售型和仓储型三种类型。首先是批发型。该类型配送中心主要靠计算机管理。业务部通过计算机获取会员店的订货信息，及时向生产厂家和储运部发出订货指示单。其次是零售型。以美国沃尔玛商品公司的配送中心为典型。该类型配送中心一般为某零售商独资兴建，专为本公司的连锁店按时提供商品，确保各店稳定经营。第三是仓储型。美国福来明公司的食品配送中心是典型的仓储式配送中心。它的主要任务是接受独立杂货商联盟的委托业务，为该联盟在该地区的若干家加盟店负责商品配送。 在日本，零售业是首先建立先进物流系统的行业之一。便利店作为一种新的零售业态迅速成长，现己遍及日本，正影响着日本其他的零售商业形式。这种新的零售商业业态需要利用新的物流技术，以保证店内各种商品的供应顺畅。因此，日本的物流配送具有以下特点；第一，分销渠道发达。许多日本批发商过去常常把自己定位为某特定制造商的专门代理商，只允许经营一家制造商的产品。为了保证有效地供应商品,日本许多物流公司不得不对原有
的分销渠道进行合理化改造,更好地做到与上游或下游公司的分销一体化。第二，频繁、小批量进货。日本的物流配送企业的很大一部分服务需求来自便利店，便利店依靠的是小批量的频繁进货，只有利用先进的物流系统才有可能发展连锁便利店，因为它使小批量的频繁进货得以实现。第三，物流配送体现出共同化、混载化的趋势。共同化、混载化的商品配送使原来按照不同生产厂、不同商品种类划分开来的分散的商品物流转变为将不同厂家的产品和不同种类的商品混合起来运送的聚合的商品物流，从而得以发挥商品物流的批量效益，大大提高了运货车辆的装载率。第四,合作型物流配送。在日本,生产企业、零售企业与综合商社、综合物流公司之间基本上都存在一种长期的物流合作关系。并且，这种合作关系还随着日本工业生产的国际化延伸到国外。第五，政府规划在现代物流配送发展过程中具有重要作用。 台湾地区的配送中心多为中小规模、平房仓库,并采用适合本地区特点的设施设备。台湾地区创造了自己的“本土化物流”。他们认为“自动化”不一定适应所有国家和地区的物流产业发展，引进技术必须考虑企业的财力规模、土地成本、建筑成本、设备成本等条件。因此，台湾地区没有完全照搬美国和日本的发展经验,而是融合这些国家物流现代化的经验，根据自己的需求，尽量完善自己的物流薄弱环节。另外，物流人才的培养也是台湾物流企业形成 自己特色的重要原因之一，他们认为物流现代化不仅在于逐步实现物流设施的现代化更重要的是在于人才素质的提高。目前，台湾的物流配送发展趋势是从整合到聚集；在物流配送的发展初期，企业是凭借自身力量与外部竞争；在发展的阶段，则是通过若干企业间的互助合作与其他企业竞争。而在联合的阶段则是通过资源共享的结盟来与其他企业竞争，也就是使自己的竞争对手通过聚集成为自己的一部分。这样就达到了高层次竞争的阶段,即通过提供有差异的服务进行竞争，而并非仅通过硬件进行竞争。 1.2我国的物流配送发展现状
物流配送是现代流通的重要组成部分。近年来，我国物流配送发展出现了积极趋势，主要体现在以下几个方面：
各级政府部门采取措施积极推动物流配送的发展。不少省市己经把发展现代物流列入了日程，例如，上海、天津、深圳都把物流作为支柱产业。还有许多省市开始制定物流规划。国家有关部门对商品物流和配送采取了积极鼓励和支持的政策，在我国流通领域对外开放政策中，鼓励国外资本投资于物流和配送设施等。目前国内物流和配送服务己有较快的发展，物流配送己经成为许多企业降低成本，提高竞争力的重要手段。例如，相当多实行连锁经营的零售企业建立了自己的配送中心，为企业内部的连锁网点提供物流配送服务，一些连锁企业配送商品比例己经超过企业经营品种的50%。
在生活资料领域和生产资料领域出现了各具特色的不同类型的现代物流企业。一些传统的流通企业，包括运输和仓储业通过改造成为物流企业，如中远集团、中外运集团和中储集团等；一些国有商业批发企业和大型零售企业正在积极探索和尝试开展社会化物流配送服务；一些生产企业开始介入现代物流，如青岛海尔集团；一批专业化的物流企业得到较快发展，物流配送的社会化、专业化发展趋势日益明显，如深圳中海物流都是比较成功的第三方物流公司。外资在物流配送服务领域的发展也十分迅速，如中国储运总公司与日本岗谷钢机株式会社合资组建了天津岗谷物流公司，是集配送、加工、仓储、寄售、租赁、修理、展销和技术咨询为一体的新型流通组织。像这样的合资物流公司，在北京、天津、上海等地已有10家之多，它们主要是为在中国投资的跨国公司提供物流配送服务。这些企业根据各自特点，发挥特长优势，积极开拓物流服务领域，形成了服务模式多样、多种经济成份并存的现代物流企业群体。连锁企业内部的配送中心在硬件设施、管理水平、管理信息系统等方面的建设，获得较大发展，有些己经达到较先进的水平。 现代物流技术的开发研究取得一定进展。一些物流配送企业在研究开发物流信息技术和物流配送管理技术上取得了许多成果，对于推动我国现代物流发展发挥了积极作用。目前已
有相当多的物流和配送技术开始进入中国，并在企业中得到越来越广泛的应用，例如条形码技术、计算机支持的信息管理技术、EDI、MRP等。 尽管我国物流配送业近几年发展很快，但与发达国家相比还处在起步阶段，不可避免地会遇到这样或那样的问题。当前，主要存在以下几个方面的问题：
(l)物流配送市场化程度低，第三方物流配送发展滞后。目前我国大多数物流配送企业技术装备和管理手段比较落后，服务网络和信息系统不健全，物流配送市场化程度低，影响了物流服务的准确性与时效性。其主要表现是：小（物流配送企业数量小，经营规模小)、少(物流配送市场份额少、服务功能少，大多数企业还只是被动地按照用户的要求，从事单一功能的运输、仓储和配送，很少能提供物流策划、组织及深入到供应链的全过程管理，物流增值少)、散(网络分割、经营秩序不规范，不能为客户提供包括物流网络设计、预测、订货管理、存货管理等系统物流服务)、弱(竞争力弱和发展滞后，专业化、信息化、标准化还没跟上，还没有真正了解国际物流企业的运作方式和真正意义上的“第三方物流”)。 （2）物流基础设施落后，物流配送的整体功能低。一是交通运输设施建设与物流配送的需要不相适应，即交通运输能力仍不能满足运输需求，主要运输通道供需矛盾依然突出：二是技术装备水平落后；三是物流系统标准化程度低。
（3）物流配送管理体制和相关制度不完善。一方面，市场竞争机制和市场管理法规不健全，发展物流配送所需的产业政策和产业规划尚未出台，物流市场的进入与退出、竞争规则基本上无统一法律法规可循，对社会性的物流缺乏有效的外部约束，致使不正当竞争较为严重。另一方面，物流配送市场至今仍被人为地按照部门、地区和行业的行政壁垒分割，物流配送市场管理和行业管理还没有理顺，各地商委、经贸委、交通局、铁路局、外经贸委等都各自承担了一部分物流管理职能，各部门间分工又有交叉，造成了物流管理中条块分割、重复建设等问题，统一、竞争、有序的物流配送市场没有建立起来，严重影响了物流配送渠道的畅通和高效运转,使物流配送很难达到规模经济和预期回报。 （4）专业的物流配送管理和技术人才短缺。 1.3发展物流配送的意义
随着经济全球化和网络信息技术发展的加快，物流及配送业作为一个新的经济增长点引起了国人的注意。上海、天津、北京等城市纷纷将物流产业作为支柱产业，中储、中远、中外运等大型企业都把现代物流作为重点发展领域。我国证券市场己经形成了由几十家企业构成的“物流板块”，许多商贸流通部门纷纷介入现代物流配送业务中，物流及配送业的发展在全国方兴未艾。
2011年我国社会物流总费用为8.4万亿元，从构成情况看，运输费用4.4万亿元，占社会物流总费用的比重为52.4%，保管费用2.9万亿元，占社会物流总费用的比重是34.5%，管理费用1万亿元，占社会物流总费用的比重为11.9%。运输成本占物流成本的50%左右，是影响物流总费用的主要因素，调查显示，美国的运输成本仅占到其GDP的不到6%，日本也仅为6.5%。而我国运输成本占到GDP 的11%。中国仓储协会对146家生产企业的调查结果表明，运输费用占整个物流费用的比例分别为：生产企业原材料物流中运输费用占到58%，生产企业成品物流中运输费用占到73%，商业物流中运输费用占到 52%。 由以上数据可以看出运输费用在总物流费用中所占比重最大，因此节约运输费用可以极大的降低物流成本。在物流活动中，配送是很重要的一个环节，运输成本在配送成本中占有很大的一部分，因此在配送管理中，有效的使用车辆并确定配送车辆经济行驶路线，在最短的时间内把商品送到顾客手中，提高顾客的满意度，是配送作业的重点。显然，为了实现以上几点目标，必须对配送过程进行合理规划，这一点可以通过改进运输方式、进行线路规划等来实现。近年来，配送车辆路线的确定问题是物流配送领域的重点研究对象，它是指利用科学的、合理的手段来制定配送线路，对其进行研究可以提高配送效益、有利于实现配送科
学化。
为实现运输成本的降低，必须对运输的进行合理规划。运输的合理规划涉及到时间、财务、环境三方面的因素，首先从时间要考虑准时性、快速响应；财务上要考虑运输涉及的各种开支(车辆购置成本和消耗、司机薪酬、油耗等)；环境上要尽可能减少不必要的行驶,避免交通拥挤、空气以及噪音等污染。这些可以通过改进运输方式、线路规划等交通管理来加以改善。其中运输方式属于“硬”技术的问题。是可以通过设施的完善和提高运输的效率,降低相应成本。运输的线路规划主要是利用各种先进的信息技术对车辆及其路线进行规划，实现对车辆合理有效的利用，从而节省大量的时间和成本。而物流中心配送作业的重点就是如何将车辆有效的使用并决定其最经济的行驶路线图，使商品能在最短的时间内送到顾客的手中。该问题为；从配送中心(物流据点)用多辆车向多个需求点(顾客)送货，每个需求点的位置和需求量一定,每辆车的载重量一定，要求合理安排车辆路线，使总运距最短，并满足以下条件：(1)每条配送路径上各需求点的需求量之和不超过车辆载重量；(2)每条配送路径的长度不超过车辆一次配送的最大行驶距离；(3)每个需求点必须满足,且只能由一辆车送货。达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。此即为VRP问题。
通过科学合理的手段制定配送路线，在配送活动中是很重要的一个环节。合理的选择配送路线，对于社会和企业具有重要意义。对于企业，配送路线的优化，可以简化配送程序、提高配送效率，充分利用配送车辆运力、降低空载率、减少配送次数、尽量使配送成本降低；同时优化配送路线可以加快企业对客户需求的响应速度，准时、快速的把物品送达客户，提高客户满意程度。对于社会，配送路线优化可以节省作业车辆，进而缓解交通拥堵状况，减少噪声、尾气的排放，为保护生态环境做出贡献。所以研究配送车辆路线优化问题及算法具有重要的现实意义。
1.4物流配送路线优化研究现状
国内外相关领域对VRP问题的研究始于50年代，在理论研究和实际应用两方面都已取得了非常显著的成果。随着研究的深入发展,如何使研究的理论模型更贴近现实中的运输规划问题开始成为研究者们关注的焦点。车辆路线问题(VRP问题)是组合优化领域中著名的NP难题，近二十年来，无论在国内还是国外，VRP问题都是一个非常活跃的研究领域。目前国内外用于解决该问题的现代数学方法主要分为以下几类： （1）精确算法
精确算法是采用严密的数学手段进行计算的方法，在能够求得可行解的情况下，其求得的结果一般要好于启发算法。常见的精确算法有以下几种：分枝定界法、割平面法、动态规划法等。
分支定界法是一种应用范围很广的搜索算法，它的基本思想是把给定问题分解为若干个较小的子问题，每个子问题又可继续分解，直到子问题不能再分解或不能产生最优解。根据问题的特点和不同的策略，把问题分解为子问题的过程称之为分支。在分支过程，为每一子问题估算其对应的目标值的界限称之为定界。定界的目的是为了测定界的趋势，留下有价值的或尚不能判定的分支。删除肯定不存在的最优解的分支，称之为剪支，以达到加速收敛、简化运算的目的。对为题进行分解，确定子问题的解值界限，减去非优的子问题，在进行新的分支，这样一个分支到定界到剪支再到分支等反复的过程是分支定界法的基本算法步骤。不同的分支规则与定界方法，形成了同一问题的不同分支定界方法。
割平面法是由高莫瑞1958年提出的，故又称为Gomory的割平面法。它的基本思想是：不断增加线性约束条件（几何术语称为割平面）将原规划问题的可行域切割掉一部分，使其切割掉的部分只包含非整数解，没有切割掉任何整数可行解，直到切割后得到的可行域有一个整数坐标的极点恰好是问题的最优解为止。针对求解的决策变量是全部取整还是部分取整
问题，割平面算法中就分成了两种计算方法，前者称为分数算法，后者称为混合整数算法。 动态规划法是20世纪50年代由贝尔曼（R. Bellman）等人提出,用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程,就是把研究问题分成若干个相互联系的阶段,由每个阶段都作出决策,从而使整个过程达到最优化。许多实际问题利用动态规划法处理,常比线性规划法更为有效,特别是对于那些离散型问题。实际上,动态规划法就是分多阶段进行决策,其基本思路是：按时空特点将复杂问题划分为相互联系的若干个阶段,在选定系统行进方向之后,逆着这个行进方向,从终点向始点计算,逐次对每个阶段寻找某种决策,使整个过程达到最优,故又称为逆序决策过程。
精确式算法领域的研究主要是针对某一特定问题而设计，实际应用范围有限，基本是在传统物流配送模式下来考虑问题、改进模型和设计算法。该方法不能保证所得出的最终解是最优整数解，但其一定是非常接近最优解的。随着车辆运输调度系统的复杂化和调度目标的增加，问题的数据量会变得越来越大，利用精确算法求解问题就会变得十分困难，于是研究者们开始考虑利用启发算法来解决这类问题。启发方法是指人们根据经验规则来发现问题的满意解的方法。用启发式方法求解问题时往往注重求得满意解而非最优解。启发式算法分为传统启发式算法和现代启发式算法两种。 （2）传统启发式算法
传统的启发式算法主要有节约法、扫描法等。 节约里程法又称节约算法或节约法，是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。节约里程法基本规定，利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件；1）所有用户的要求；2）不使任何一辆车超载；3）每辆车每天的总运行时间或行驶里程不超过规定的上限；4）用户到货时间要求。基本思想是，为达到高效率的配送，使配送的时间最小距离最短成本最低，而寻找的最佳配送路线。近年来，由于小批量、多批次的及时配送方式的发展,运输费用正在逐年提升，许多企业的运费己经超越了库存费用。选择有效的配送路线，己成为控制物流成本的主要措施。那么如何选择有效的配送路线呢？现代企业已经普遍接受了一种观点，即有效的配送路线实际上是在保证商品准时到达客户指定点的前提下，尽可能地减少运输的车次和运输的总路程。在这种思想的指导下，节约法已成为选择配送路线的主要方法，并受到国内外物流界的青睐。
扫描法是Gillett和Miller于1974年所提出的求解车辆路线问题（Vehicle Routing Problem,VRP）的方法，此方法属于先分群再排路线的方式。该方法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，再借由Lin与Kernighan的交换法进行需求点的排序，建构车辆排程路线。一般情况下，制定从一个物流中心向多个用户运送货物的配送计划时，必须考虑每辆车的运载能力和行驶距离及时间等的限制。其中扫描法是一种能较好地解决配送路线问题的有效方法，它的基本思路是采用逐次逼近的方法来解决问题。 （3）现代启发式算法
现代启发式算法主要有禁忌搜索算法、遗传算法、蚁群算法、粒子群算法等。用现代启发算法对问题的求解是通过大规模的迭代来实现的，现代启发算法自身具有一套独特的搜索规则。为了求得满意解，算法在迭代中要不断采纳和分析新信息，必要情况下需要变更原来的策略，建立新的搜索规则，同时要注意从失败的搜索中取得经验教训，逐渐减小搜索的范围。随后从多个可行解中找出满意解。 1）禁忌搜索法
Gendreaut 等人（1991）最先将禁忌搜索法应用于车辆路径优化问题。先构造一系列的
解，然后对所得到的结果不断地改进。该算法所得到的解不一定是可行解，它们对可行性的偏离程度体现在目标函数里的惩罚函数值的大小。禁忌搜索法是针对车辆路线优化问题的较好的现代启发式算法，在许多经典的车辆路线优化问题的求解中都已经被成功地运用。 2）遗传算法
近年来，一类基于生物学,物理学和人工智能的具有全局优化能力、鲁棒性强、通用性强且适于并行处理的现代启发式算法得到了发展。因其高效的优化性能、无需问题特殊信息等优点，广泛用于计算机科学、优化调度、运输问题、组合优化、工程优化等领域。遗传算法是其中具有代表性的一种现代启发式方法。 3）蚁群算法
蚁群算法蚁群算法（ant colony optimization,，ACO）又称蚂蚁算法，是一种用来寻找最优解决方案的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。蚁群算法就是根据这一特点，通过模仿蚂蚁的行为，从而实现寻优。这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。
4）粒子群算法
Kennedy 和 Eberhart 在 1995 年首次提出了粒子群算法，该算法基于对鸟类飞行觅食行为的模拟，群体达到最优目标是通过鸟群个体之间的协作行为实现的。粒子群算法与遗传算法类似，它们的共同点是运算方式基于群体的迭代，但粒子群算法没有变异、交叉和算子的复制，群体在解可行域中追逐最优粒子不断搜索直到找到满意解。粒子群算法的优点为：个体数量少、计算简单、鲁棒性好、容易实现，并有着深刻的智能背景，适合于科学研究及工程应用。粒子群算法源于对鸟群捕食行为的研究。鸟群捕食场景为：鸟群在一片固定区域内寻找食物，但在这个区域内食物只有一块，群内的每一只鸟的搜索行为都具有随机性。鸟群中的所有个体都不清楚在哪里可以找到食物，但个体知道自身位置与食物间的距离。对于这个群体来说寻找食物的最简单有效的策略就是搜寻目前离食物最近的个体周围的区域，粒子群算法正是基于上述方式解决优化问题的。粒子群算法求解优化问题时，每一个潜在解可以被看做是空间中进行搜索的一只鸟，我们将之称为“粒子”。所有的粒子与相关优化函数之间都有适应值，这个适应值由优化函数决定，粒子自身具有速度，粒子的速度决定粒子本身的飞行距离和方向。所有的粒子追随目前的最优粒子在可行区域内搜寻最优解。粒子群算法随机初始化一定数量的粒子，它寻找最优解的方式是通过多次迭代。每次迭代粒子追逐个体极值（粒子自身在所经历的位置中找到的最优解）及全局极值（整个群体到目前为止找到的最优解）来更新自己。
2理论基础
2.1物流配送问题的基本理论 2.1.1配送路线问题模型
采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径。在满足客户配送需求的前提下，如何选择配送路线，是一项很重要的工作。配送作业的时效性和高效性主要受车辆路线的安排与调度方案优化情况的影响。配送路线优化问题由来已久，其可以描述如下，见图 2-1。
有一个（或者多个）配送中心，共有配送车辆 K 辆（一种或者多种车型），车辆载重量为Q1，Q2，„，Qk共有 I 位客户等待被服务，每位客户都有各自需求量G1，G2，„，Gi。从配送中心出发的配送车辆对等待服务的客户进行配送，以满足客户的要求（物品品种、数量、规格的要求，配送时间的要求），最后返回配送中心。要求所有客户都被服务到，同时配送车辆不能超载。最终求出车辆配送路线方案，并达到一定的优化目标（如路程最短、费用最少、时间尽量少等）。
车辆路线优化问题是 NP 难题。自从它被提出以来，由于其应用的广泛性和在经济上的价值，一直受到国内外学者的广泛关注。配送路线优化问题的主要构成要素为：配送车辆、货物、客户、配送中心、路网。各要素具体说明如下。
（1）车辆，其主要属性有：车辆类型、装载量、最大行驶距离、配送开始前与完成后所在的配送中心。
（2）货物，其主要属性有：重量、送达时间和送达地点等。货物能否装在同一配送车辆上取决于货物属性。
（3）客户，其主要属性有：需求(或供应)货物的种类、接受服务的时间等。
（4）配送中心，其主要是用来进行集货、分货、配货、送货等物流作业，在不同的路线优化问题中，配送中心的个数为一个或者多个。
（5）运输网络，其组成部分有配送中心、客户点和车辆行驶路线等。 2.1.2物流配送路线的优化目标
图2-1 配送路线优化问题原理图 客户点 配送中心 对车辆配送路线问题进行优化时，必须要有明确的目标和遵循的基本原则。配送路线优化问题的优化目标可以从以下几个方面考虑： （1）配送效益最高或配送成本最低。 物流企业是以追求效益为主要目标的，通常用企业利润来表示，即企业通常以利润的最大化作为自身经营的目的。配送成本对物流企业利润有直接的影响，以成本最低作为优化目标与物流企业利润的最大化有直接的联系。当与成本及利润相关的数据容易得到和计算时，就可以用利润最大或以成本最低作为优化目标。 （2）配送里程最短。
当配送成本与配送里程具有较强的相关特性，与除此之外的其它因素相关特性较弱时，配送里程最短就近似等同于配送成本最低。这时可以考虑用配送里程最短作为优化目标，这样就可以大大简化配送路线优化方法。当配送成本与配送里程的相关性不明显优于其它因素的时候，如考虑车辆载重情况、道路运行条件等因素，单以路线最短作为优化目标就变得不适宜。
（3）配送服务水平最优。 当准时性成为配送的第一要求，或当出现某些特殊情况需要确保服务水平而忽略配送成本时，则应尽量在成本不出现失控的情况下，以服务水平最优为优化目标。优质的服务可以采用较高的服务价格，从而保证企业的合理利润。 （4）配送劳动的消耗最小。
它是以物化劳动和活劳动消耗最小为优化目标，在许多情况下，如人员紧张、燃料紧张、车辆设备紧张等，限制了配送作业，这时就可以考虑以配送所需要的人员、车辆或其它相关资源消耗最小作为优化目标。实际上，配送路线优化问题的优化目标是多元的，但是考虑到优化目标的目标值应当符合实际情况，一般要尽可能取得实用性较强的目标值。因此，本文采用成本最低作为优化目标。
2.1.3配送车辆路线优化问题的约束条件 现实中，配送车辆路线优化问题存在着很多方面的约束条件，这些约束条件使得该问题在研究和应用上产生了许多不同的方向和型态，基于前文所述的分类标准，一些最重要的约束条件包括：
（1）容量约束。任意配送车辆所搭载的货物总量不能超过该车辆的载重能力。 （2）配送中心数目约束。配送中心有一个或者多个。 （3）优先约束。客户之间服务的次序存在着限制。
（4）车型约束。不同客户的配送要求需要由不同车型来满足。 （5）时间窗约束。包括硬时间窗约束和软时间窗约束。
（6）随机约束。客户数量、配送需求、行驶路线等随机出现。 （7）车速约束。车速是否稳定。
（8）相容性约束。客户是否可以被不同配送车辆（配送中心）服务。 通过以上分析，本文所要研究的配送车辆路线优化问题所采用的约束条件为：每个客户只能被一辆车服务，每个被服务客户没有优先次序，配送车辆的载重情况不超过自身的载重能力，每个客户对其被服务的时间窗的要求为软时间窗模式。 2.1.4配送路线优化问题的分类
对配送车辆路线问题类型分析是进一步对问题进行建模和求解的基础。现有的对 配送路线优化问题的分类大致有以下八种：
分类依据 按任务 特征分 分类 只送货问题 只取货问题 混合问题 具体分类说明 只送货问题的特征为：配送车辆仅考虑从配送中心向客户送货；只取货问题的特征为：配送车辆仅考虑从各客户处把供应的货物取到配送中心；取送货混合问题的特征为：既考虑将客户需求的货物从配送中心送到各个客户 单一车场问题的特征为：配送系统中只有一个车场、货场或 配送中心；多个车场问题的特征为：配送系统中有多个车场、货场或配送中心 单一车型问题的特征为：配送作业所用车辆都是同一类型，即车辆的参数如：载重能力、最长行驶时间和单次作业的最大行 驶距离等相同；反之多种车型问题的特征为配送作业所用的车辆类型不完全相同 按配送中心数目分 按配送车辆类型数目分 单一车场问题 多个车场问题 单一车型问题 多个车型问题 按配送车辆路线分 车辆开放问题 车辆封闭问题 车辆开放问题的特征为：车辆完成其配送任务后可以不返回 出发点；车辆封闭问题的特征为：车辆完成其配送任务后必须返回出发点 满载问题是指当客户的需求量或提供量大于或者等于配送车辆的载重能力时，需要用一辆或者多辆车来完成一项配送作业，其中大多数配送车辆要满载运行；非满载问题是指当客户的需求量或提供量小于配送车辆的载重能力时，多个客户的配送需求都可以由同一配送车辆来满足，整个配送过程中配送车辆处于非满载状态；满载和非满载混合问题是指当一部分客户的需求量或提供量大于或者等于配送车辆的载重能力，而一按配送车辆卸载状况分 满载问题 非满载问题 混合问题 按客户时间需求分 有时间床问题 无时间窗问题 部分客户的需求量或提供量小于配送车辆的载重能力时 无时间窗问题的特点是客户对服务时间无具体要求；有时间 窗问题的特点是客户要求配送车辆必须在规定的时间范围内将货物送达或取走。有时间窗问题又可以分为硬时窗问题和软间窗问题，其中硬时窗是指，客户要求必须在指定的时间范围内进行配送作业，不能提前也不能拖后否则需要等待或者不能为其服务，软时窗是指，客户要求配送车辆尽可能在规定的时间范围为其服务但也可以提前或拖后，只是要受到一定的惩罚，如交罚金 按优化目标数分 单目标问题 单目标问题是指选择某一最优或较优指标作为优化目标，如配送路线最短。多目标问题则是指同时选择多个最优或较优的指 标作为优化目标，如同时要求配送路线最短和成本最低。路线优化模型的指标一般包括：配送时间最短、配送路线最短、成本最低。一般情况下这三个目标是统一的：距离最短，也就意味着时间最短，成本也最低，但是很多情况下，也有出现多目标不统一、甚至互相矛盾的可能 多目标问题 按客户和路网特点分 静态问题 静态问题的特征为：客户的位置、数目、需求，以及天气、路况等因素是确定的和已知的；动态问题的特征为：客户的位置 数目、需求，以及天气、路况等因素是随机变化的。 表2-1
动态问题
2.2典型配送车辆路线优化问题的数学模型
本文此处以经典的带时间窗配送车辆路线优化问题为例，来说明配送车辆路线优化问题
的一般模型及表达方式。带时间窗配送车辆路线优化问题的一般描述为：有一个配送中心（含车场），拥有的配送车辆数为 K 辆，容量分别为 Qk（k=1，2，„，K）。有 I 个客户点需要被服务，客户点 i 的作业量为 Gi，配送车辆 k 到达客户点 i 的时刻为kis ，并且客户点 i 的配送作业需要在规定的时间窗[ETi，LTi]内完成，其中 ETi表示客户点 i 允许配送作业开始的最早时间，LTi表示客户点 i 允许配送作业开始的最迟时间。如果配送车辆到达客户点 i 的时间早于 ETi，则配送车辆需要在客户点 i 处等待，如果配送车辆到达客户点 i 的时间晚于 LTi，则客户点 i 的配送作业将被延迟进行，同时配送车辆需要接受处罚。
一般情况下带时间窗路线优化问题需要考虑以下几个约束条件：
（1）各客户点只可以由一辆车配送且只能被配送一次，不考虑多辆车同时为一个客户点服务的情况；
（2）配送中心（或车场）只有一个，所有车辆从配送中心出发，车辆在完成所有作业之后需要回到配送中心；
（3）各配送线路上客户点的作业总量不应大于该线路上作业车辆的载重量；
（4）每个客户点的配送作业量必须小于为其服务的车辆的最大载重量，即只需一台配送车辆即可满足该客户点的配送作业需求。 对模型参数定义如下：
车辆k由i到j 其他 客户i由k车来服务 其他 cij表示客户点 i 到客户点 j 的运输成本； PE表示配送车辆由于等待失去的机会成本； PL表示配送车辆由于迟到需要支付的罚金。
在仅考虑装载约束和时间窗约束的条件下，带时间窗的配送车辆路线优化模型可以表示为：
Gyii1KIikQk 任意的k
yk1Iik=1 i=1，2，„，I
xi0ijkyjk j=1，2，„，I，任意的k
xj0Iijkyik i=1，2，„，I，任意的k
i，j=1，2，„,I，任意的k
xijk=0或1
yik=0或1 i=1，2，„，I，任意的k
其中式中的目标函数，表示为各客户点配送的目标是使配送成本最小。目标函数由两部分组成，前半部分为车辆在线路上进行配送时所消耗的运输成本，后半部分为车辆在为各个客户点进行配送的过程中，由早到所损失的机会成本及迟到所支付的罚金之和。这一目标函数的具体意义为：要在满足配送路线最短的条件下，尽量考虑车辆配送的时间窗约束，以使得配送车辆运输成本及时间成本两者所代表的配送成本最低。该模型的不足是忽略了配送车辆载重情况及道路等级情况对车辆运输成本的影响。
3现代运筹学方法在物流配送路线优化中的实际应用
3.1传统启发式节约法及其应用 3.1.1节约法描述
利用里程节约法确定配送路线的主要出发点是，根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来制定使配送车辆总的周转量达到或接近最小的配送方案。 假设条件：
（1）配送的是同一种或相类似的货物； （2）各用户的位置及需求量已知； （3）配送方有足够的运输能力；
（4）设状态参数为tij, tij是这样定义的：
tij={1,表示客户I，J在同一送货路线上；0，表示客户I，J不在同一送货线路上。} t0j =2表示由送货点p0向客户J单独派车送货。
且所有状态参数应满足下式：
ti1j1ijij1tNij2(j1,2,...........N)
式中：N-----客户数
利用节约法制定出的配送方案除了使总的周转量最小外，还应满足： （1）方案能满足所有客户的到货时间要求； （2）不使车辆超载；
（3）每辆车每天的总运行时间及里程满足规定的要求。
如图3-1所示，设p0为配送中心，分别向用户pi和pj送货。p0到pi和pj的距离分别为
d0i和d0j，两个用户pi和pj之间的距离为dij，送货方案只有两种即配送中心p0向用户pi, pj分别送货和配送中心p0向用户pi, pj同时送货，如图11-7a)和b)。比较两种配送方案： 方案a）的配送路线为p0→pi→p0→pj→p0,配送距离为da=d0i+d0j 方案b)配送路线p0→pi→pj→p0,配送距离为db=. d0i+d0j+dij
显然，da不等于db，我们用sij表示里程节约量，即方案b)比方案a)节约的配送里程：
sijdoidojdij
根据节约法的基本思想，如果一个配送中心p0分别向N个客户pj(j=1.2………n)配送货物，在汽车载重能力允许的前提下，每辆汽车的配送线路上经过的客户个数越多，里程节约量越大，配送线路越合理。
图3-1 3.1.2节约法应用实例 例：某一配送中心p0向10个客户pj(j=1,2,„,10)配送货物，其配送网络如图3-2所示。图中括号内的数字表示客户的需求量（T），线路上的数字表示两节点之间的距离。配送中心有2t和4t两种车辆可供使用，试制定最优的配送方案。
图3-2
解：第一步：计算最短距离。根据配送网络中的已知条件，计算配送中心与客户及客户
之间的最短距离，结果见表3-3。
P0 10 9 7 8 8 8 3 4 10 7 P1 4 9 14 18 18 13 14 11 4 P2 5 10 14 17 12 13 15 8 P3 5 9 15 10 11 17 13 P4 6 13 11 12 18 15 P5 7 10 12 18 15 表3-3
P6 6 8 17 15 P7 2 11 10 P8 9 11 P9 8 P10
第二步：计算节约里程sij,结果见表3-4。
P1 15 8 4 0 0 0 0 9 13 P2 11 7 3 0 0 0 4 8 P3 10 6 0 0 0 0 1 P4 10 3 0 0 0 0 P5 9 1 0 0 0 表3-4
P6 5 4 1 0 P7 5 2 0 P8 5 0 P9 9 P10 第三步：将节约sij,进行分类，按从大到小的顺序排列，得表3-5。
节约里程项目分类表 序号 路线 节约里程 序号 路线 节约里程 1 2 3 4 4 6 6 6 9 9 11 12 p1p2 p1p10 p2p3 p3p4 p4p5 p1p9 p5p6 p9p10 p1p3 p2p10 p2p4 p3p6 15 13 11 10 10 9 9 9 8 8 7 6 表3-5
13 13 13 16 16 16 19 19 21 22 22 22 p6p7 p7p8 p8p9 p1p4 p2p9 p6p8 p2p5 p4p6 p7p9 p3p10 p5p7 p6p9 5 5 5 4 4 4 3 3 2 1 1 1 第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图。 （1）初始方案：对每一客户分别单独派车送货，结果如图3-6。
图3-6 初始方案
初始方案：配送线路10条 配送距离：S0：148km 配送车辆：2t×10
（2）对方案进行修正
1）按节约里程sij由达到小的顺序，连接p1和p2, p1和p10，p2和p3,得修正方案1。 配送线路：10条
配送距离：S1：109km 配送车辆：2t×6+4t×1
2）在剩余的Sij中，最大的是S3，4和S4，5，此时p4和p5都有可能并入线路A中，但考
虑到车辆的载重量及线路均衡问题，连接p4和p5形成一个新的线路B，得修正方案2。 配送线路：6条
配送距离：S2：99km 配送车辆：2t×5+4t×1
3）接下来最大的Sij是S1，9和S5，6，由于此时p1已属于线路A，若将p9并入线路A，车辆会超载，故只将p6点并入线路B，得修正方案3。 配送线路：5条
配送距离：S3：90km 配送车辆：2t×3+4t×2
4）再继续按Sij由大到小排出S9，10、S1，3、S2，10、S2，4、S3，6，由于与其相应的用户均已包含在已完成的线路里，故不予考虑。把S6，7对应p7点并入线路B中，得修正方案4。 配送线路：4条
配送距离：S4：85km 配送车辆：2t×2+4t×2
（3）最终方案：剩下的是S7，8，考虑到配送距离的平衡和载重量的限制，不将p8点并入到线路B中，而是连接p8 和 p9 ，组成新的线路C，得到最终方案，这样配送方案已确定：共存在3条配送线路，总的配送距离为80 km，需要的配送车辆为2t车一辆，4t车3辆。3条配送线路分别为：
第一条配送线路A：p0→p3→p2→ p1→p10→p0使用一辆4t车。 第二条配送线路B： p0→p4→p5→ p6→p7→p0，使用一辆4t车。 第三条配送线路C： p0→p8→p9→p0，使用一辆2t车。 最终方案： 配送线路：3条
配送距离：S4：80km 配送车辆：2t×1+4t×2
图3-7 最终方案
3.1.3节约法的优缺点分析 （1）节约法的优点
节约法一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，它也
体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单、清晰，便于执行。正是如此，它受到国内外物流配送业的青睐。 （2）节约法的缺点
第一，利用节约法选择配送路线过于强调节约路程,而没考虑行程中的时间因素，因为在许多情况下，时间更能决定物流配送的成本与服务质量。例如在城市间配送时对高速公路的选择，城市内部上下班时间的道路拥挤，一个巡回配送过程中的时间长短，直接影响配送人员的精神状态，而人员的精神状态又与交通事故和配送错误相连，所以时间对配送路线的选择有时更重要。 第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。由于现代消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量、多品种、多批次。而节约法更适合需求稳定或是需求时间不紧迫的情况，这显然不能满足现代多变得市场环境。
最后值得一提的是，节约法计算的配送路线并不是总路程最短。原因是节约法一方面要缩短总路程，另一方面又要充分利用车辆的运输空间(载重/容积)，减少配送车次，而且只要在前一条预设路线上运行的配送车辆的运输空间允许，就必须按着节约路程的大小顺序进行选择而不考虑其它的预设路线，在事实情况下选择的路线并不能“节约”路程和有效利用运输空间，而且运输的车次也不一定减少。 （3）节约法的改进建议
由以上的分析可知，节约法简便易行，同时也有一些弊端。是否可以通过改进使其成为一种最优的方法呢？撇开其他因素，只考虑运输路线是否最短，这就是不可能的。早在人们研究这一问题时就发现，即使不考虑运输工具的载运空间，而只考虑在多个节点之间寻求最短巡回路线(运筹学中的货郎担问题)，虽然人们可以利用动态规划的方法，可是计算量太大，当节点的个数足够多时，即使利用计算机仍是不可取的，而在配送路线中还要考虑运输工具载
运空间和配送时间的限制。但是,这并不意味着节约法是不可改进的，只是在配送路线选择决策时，通常考虑较优的原则，而不是最优化原则。
1）深入了解客户，加强与客户的信息交流。客户的需求是企业物流服务水平的准绳。只有深入了解客户群体，进行周密细致的研究，才能了解客户对商品的品种、规格、型号、供货期、服务收费及所需的物流增值服务等情况，并在此基础上建立客户管理档案，对未来需求进行预测，这样方能以适当向客户提供高质量的物流服务,，而使企业与客户之间建立稳定的关系，为企业迎来充裕的时间规划配送方案。 2）通过对客户按需求的时间变化进行分类,增加配送的灵活性。客户需求的时间变化决定了运送前的货物联合组装和对物流网络的有效利用。所以，企业应对客户进行分类，对不同的客户实施不同的配送策略与收费。按着客户需求的时间变化可把客户分两类：需求稳定或备货期较长的客户和需求变化无常或备货期较短的客户。对于前一种客户,应充分利用节约法，对其过程进行详细的规划，尽可能缩短配送的总过程与总的配送时间，提高设备的利用率，节约成本；对后一种客户要尽可能利用节约法原理来实施，但在必要时，为了支持企业的竞争战略，实现对客户的承诺，也可对特定客户进行单个配送。
3）节约法的实施过程，要综合考虑路程长短和时间因素。配送过程费用和服务质量取决于时间与路程的综合因素，所以应该在实施过程中综合考虑这两个因素。可以采用以下指标代替各节点间的距离的措施:第一，中间的过程指标用，（路长令正常速度X正常速度概率+路长干非常速度X非常速度概率)，或者用，(非常速度路长令非常速度+正常速度路长十正常速度)，第二，如果服务需求稳定,配送的起止时间是固定的，则中间的过程指标用，（路 程长度/平均车速)。
4）配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。如果在这些环节上出现不当，如设备落后而延长备货期，管理不善增加这些过程中的商品损坏和组装错误等，都会提高成本、降低服务质量。因此，在优化配送过程时，不但要优化配送路线和配送过程，还要提高配送过程其他环节的管理水平和设备的现代化水平。 3.2现代启发式遗传算法及其应用 3.2.1遗传算法概述
遗传算法 (Genetic Algorithm，GA)是借鉴生物界自然选择和群体进化机制形成的一种全局寻优算发。与传统的优化算法相比，遗传算法具有如下优点；1）不是从单个点，而是从多个点构成的群体开始搜索；2）在搜索最有解过程中，只需要由目标函数值转换得来的适应值，而不需要导数等其他辅助信息；3）搜索过程不易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题的有力工具。在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串结构数据；同时，将目标函数值转换成适应值，它用来评价个体的优劣，并作为遗传操作的依据。遗传操作包括三个算子：选择、交叉和变异。选择用来实施适者生存的原则，即把当前群体中的个体按与适应值成比例的概率复制到新的群体中，构成交配池(当前代与下一代之间的中间群体)。选择算子的作用效果是提高了群体的平均适应度值。由于选择算子没有产生新个体，所以群体中最好个体的适应度值不会因选择操作而有所改进。交叉算子可以产生新的个体，它首先使从交配池的个体随机配对，然后将两两配对的个体按某种方式交换部分基因。变异是对个体的某一个或某一些基因值按某一较小概率进行改变，从产生新个体的能力方面来说，交叉算子是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异算子只是产生新个体的辅助方法，但也必不可少，因为它决定了遗传算法的局部搜索能力。交叉和变异相配合，共同完成对搜索空间的全局和局部搜索。遗传算法是一种“生成+检测”的迭代搜索算法。它以种群中的所有个体为操作对象，每个个体对应问题的一个解。 选择、交叉和变异是其3个主要操作。标准遗传算法流程图如图3-8所示。
开始 Gen=0 编码 随机产生规模为NP的初始种群 满足终止条件 Y 输出结果 N 计算个体适应度 终止程序 从左至右依次执行遗传算子 P根据适应度选择复制个体 Pc 选择两个杂交个体 选择个体变异 执行复制操作 执行杂交操作 执行变异操作 复制后个体添加到种群中 杂交后个体添加到种群中 变异后个体添加到种群中 Gen=Gen+1
图3-8 标准遗传算法流程图
该算法包括以下6个基本要素:
1) 编码: 遗传算法不能直接处理解空间的数据，必须通过编码将它们表示成基因型串数据。
2) 初始化种群:初始种群的染色体是通过随机方法产生,一个染色体对应一个配送方案。
3) 评估适应度:遗传算法在搜索过程用适应度评估每个染色体的优劣,作为下一代种群更新的依据,
即把它作为遗传操作的依据,并确保适应度增大的方向与目标函数的优化方向一致。
4) 选择:从当前的种群中选择生命力强的染色体,产生新一代的种群。即适应度高的染色体被选中的机会就越大,但并不意味适应度高的染色体一定被选中。
5) 交叉:对种群的染色体,按一定的交叉概率,用随机不重复的方法,每次选择两个染色
体相互交叉,产生新一代染色体。从而,形成新的子代种群。
6) 变异:按一定的变异概率,在交叉的基础上,对种群的染色体进行变异,即改变自身染色体的基因位。
系统参数的选取一般遵循以下原则：
1）种群数目N。种群数目会影响GA的有效性。N太小，GA会很差或根本找不出问题的解，因为太小的种群数目不能提供足够的采样点；N太大，会增加计算量，使收敛时间延长。一般种群数目在20~160之间比较适合。
2）交叉概率Pc。此参数控制着交叉操作的频率。Pc太大，会使高适应值的结构很快破坏掉；Pc太小，搜索会停滞不前。一般Pc取0.25~0.75。
3）变异概率Pm。它是增大种群多样性的第二要素。Pm太小，不会产生新的基因块；Pm太大，会使GA变成随机搜索。一般Pm取0.01~0.20 基本步骤如下：
1）在一定的编码方案下，随机产生一个初始种群；
2）用相应的解码方法，将编码后的个体转换成问题空间的决策变量，并求得个体的适应值；
3）按照个体适应值的大小，从种群中选出适应度值较大的一些个体构成交配池； 4）由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种群； 反复执行步骤2~4，直至满足收敛判据为止。 3.2.2编码
将问题的解编码为染色体是用遗传算法解决各类问题的第一步，也是关键一步。编码方法决定了染色体的排列形式。它实际上确定了对问题的描述方式，直接影响到选择、交叉、变异这一系列基因操作，最终影响到整个遗传算法的性能。设计优良的编码方案是遗传算法的应用难点之一。下面介绍排列编码方法。
例如，旅行商问题（TSP）：选择一条商人遍历若干城市的最短路径。设共有n个城市，
d分别用1,2,3,,n来表示，每两个城市i和j之间的距离用ij表示，则商人的一次遍历路线
可以用一个1,2,3,,n的全排列
1,2,,n表示，该排列表示遍历路线
12n1。因此1,2,3,,n的全排列1,2,,n就可以作为TSP的
染色体。
3.2.3适应度函数
在遗传算法中，适应度是用来区分群体中个体（问题的解）的好坏，适应度越大的个体越好，反之，适应度越小的个体越差。遗传算法正是基于适应度对个体进行选择，以保证适应性好的个体有机会在下一代中产生更多的子个体。适应度函数是用来区分群体中个体好坏的工具，是算法演化过程的驱动力，是进行自然选择的唯一依据。改变群体内部结构的操作都是通过适应度加以控制。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。
遗传算法适应度函数值作为染色体的性能指标，以及利用繁殖概率的大小来评估各染色体的优劣程度，多半以最大化为目标(亦即越大越好)；但是许多优化问题(比如物流配送VRP问题)是求取费用函数的最小值，必须将目标函数转化为求最大值形式己得到适应度函数，而且保证适应度函数非负。一般可采用以下的方法进行转换：
fk转换后MAXfk转换前
其中MAX为一常数，最好与群体无关，一般可以由下列四种方式决定： 1）任意足够大的正数。
2）目前所出现最大的目标函数值。
3）目前操作的群体中，最大的目标函数值。
4）目前遗传世代中，最后n代出现的最大的目标函数值。 适应度函数一般要求非负，上述适应度函数的转换方法并不能保证后代的适应度函数值为正数，一旦在遗传过程中出现了比MAX更大的适应度函数值，就可能出现负的适应度，使复制算子失效。为了保证适应度函数为非负，可以采用如下的转化形式：
fk转换后fk/fk转换前
3.2.4遗传算子的基因操作 （1）选择算子
发展各种复制算子的目的是为了避免基因缺失，提高全局收敛性和效率。复制算子策略与编码方式无关，复制的主要思想是染色体的复制概率正比于其适应度。适应度比例方法是目前遗传算法中最基本也是最常用的复制方法，它也叫轮盘赌复制法或蒙特卡罗复制，其具体步骤如下：
Step l：对各个染色体
vk计算适应度fk；
Step 2：计算种群中n个染色体适应度的和； Step 3：对各染色体 Step 4：对各染色体
vk，计算选择概率； vk计算累计概率
由于染色体复制后，当前群体中最佳染色体可能丧失繁殖能力，为了提高遗传算法的性能，可在使用轮盘赌的基础上采用最佳保留策略。 （2）交叉算子
交叉算子的作用是组合出新的个体，在串空间进行有效搜索，同时需降低对有效模式的破坏概率。交叉算子是遗传算法区别于其他进化算法的重要特征。在交叉算子之前需首先配对，目前采用的是随机配对。采用二进制编码、实数编码和自然数编码时所采用的交叉策略不一样，下面介绍顺序交叉。 顺序交叉(ox )
Step l：从第一双亲中随机选择一个子串；
Step 2：将子串复制到一个空子串的相应位置，产生一个原始后代；
Step 3：删去第二双亲子串已有的城市，得到原始后代需要的其他城市的顺序； Step 4：按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。
双亲1： 5 7 4 9 1 3 6 2 8 原始后代： * * 4 9 1 3 * 7 * 8 * 双亲2： 1 2 3 4 5 6 9 后代： 2 5 4 9 1 3 6 2 8
图3-9 0x的运算说明
（3）变异算子
当交叉算子产生的后代的适应度不在比前辈好又未达到最优解，就会产生不成熟收敛，不成熟收敛的根源是发生了有效基因缺失，这时，为克服这种情况，只有依赖于变异。变异在遗传算法中的作用是第二位的[3,5]。目前较常用的高级遗传算子，来源于群体遗传学。 反转变异是在染色体上随机地选择两点，将两点间的子串反转。
随机选择子巡回
5 4 3 9 2 6 7 1 8 插入子巡回
5 4 3 7 6 2 9 1 8 图3-10 反转变异的说明
3.2.5遗传算法控制参数设定
为了选择合适的群体规模n、交叉率pc、变异率pm，许多学者进行了研究。通常认为：若种群过小，算法就有可能收敛于局部最优解，而不能收敛到最优结果或最优结果附近。这主要是种群规模过小，导致种群内个体多样性减小，从而可能丢失一些有意义的搜索点或最优点，然而种群过大，每次迭代所需要的计算量就会很大，这又可能导致一个无法接受的慢收敛率。一般，当种群规模增大时，将有利于改善种群的多样性，从而可能有利于使算法收。
p0.75~0.95,pm0.005~0.01。但在某些情建议的最优参数范围是n20~30, c况下，当种群达到一定规模时，再增大种群规模，对搜索结果的改善并无多大帮助，甚至有
p0.5~1.0，pm0~0.05。由于
可能变差。目前常用的参数范围是n20~200,c控制参数会相互影响，所以无法确定独立的最佳参数值，但当种群规模小时可选择较大的交叉及变异率以防止过早收敛；当群体规模大时可选择较小交叉及变异率以节省运算时间。目前许多学者认识到这些参数需要随着遗传进程而自适应变化，这种有自组织性能的遗传算法具有更强的鲁棒性、全局收敛性和计算效率。 3.2.6算法设计
（1）算法流程图
标准算法流程图如图3-8所示。 （2）染色体结构
为提高效率，对VRP采用自然数编码方式，即序数编码。
单车场车辆优化调度问题的一条可行线路可编成长度为n+m的染色体
0,i11,i12,i1s,0,i21,i22,,i2t,0,,im1,imw，其中ikj用自然数表示，代表编号为ikj的
需求点。这样的染色体结构可通俗地理解为第一辆车从配送中心0出发，经过需求点
i11,i12,,i1s后，回到配送中心0，形成子路径1；第二辆车也从配送中心0出发，经过以
前未访问的需求点
i21,i22,,i2t后，返回配送中心0，形成子路径2；依次类推，直到所有
的n个需求点全部被遍历，形成子路径m。如染色体021304605870表示的行车线路为： 子路径1: 配送中心0 →需求点2 →需求点1→需求点3→配送中心0 子路径2: 配送中心0 →需求点4 →需求点6→配送中心0
子路径3: 配送中心0 →需求点5→需求点8→需求点7→配送中心0
这种染色体结构子路径内部是有序的，若子路径1中点1， 3相互交换位置，会使目标函数值改变；而子路径之间是无序的，若子路径1和2相互交换位置，却不会改变目标函数的值；若子路径倒转，如0460倒转为0640，也不会改变目标函数的值。 （3）约束处理
对于VRP这类约束较复杂的优化问题，用遗传算法求解时，需要对约束进行处理。一般有下面几种方法：
问题的约束在染色体中表现出来，设计专门的遗传算子，使染色体所表示的解在遗传算法的求解过程中始终保持为可行解。
在编码的过程中不考虑约束，而在遗传算法的计算过程中检测得到的染色体相应的解是否可行，若可行，则放入下一代群体中，否则将其舍弃。
采用惩罚的方法来处理约束。如果一个染色体对应的解违反了某个约束，试其违反程度给予一定惩罚，使其具有较小的适应度。这样，一些不可行解也有可能进入群体，以保证群体中染色体的数目，使遗传算法得以继续运行。若干代后，不可行解在群体中所占的比例应越来越小，可行解逐渐占据主导地位，并逐渐趋于最优解。 1）载重量的约束处理
在此采用罚函数的方法处理约束。
对于一般VRP，使用如下变换将承载量约束式变为目标函数式的一部分：
minzdpki1pMckmaxpathk1i1kimnk1mk1
k1其中 表示若解违反载重量约束处以的惩罚值。k为第k辆车的超载
量；maxpath是所有两点间运距中最大的运距；M为超载时施以的惩罚系数，即目标函数所
Mckmaxpathmc加的最大的运距的倍数。 2）时间窗的约束处理
本文采用软时间窗约束处理，以d表示车辆在任务点处等待损失的单位时间机会成本，e表示车辆在要求时间之后到达单位时间所处以的罚值。 若车辆在之前罚款
aj到达需求点j则产生成本
dajsj；若车辆在
bj之后到达需求点j则处以
esjbjmnk1。用罚函数法处理时间窗约束，得到软时间窗VRP的目标函数：
mnnminzdpki1pkiMckmaxpathdmax(ajsj,0)emaxsjbj,0k1i1k1j1j1
3）适应度函数
在有时间窗的车辆优化调度问题中，目标函数值越小越好(即在满足载重量和时间约束的基础上，行车线路的总运距越小越好)，而在遗传算法中，个体适应度越大，表示个体的性能越好,因此需要将目标函数转化为适应度函数。本算法采用了如式4-10所示的变换将目标函数转化为适应度函数。
maxpathn2fkzk
式中
zk为群体中第k条染色体对应的目标函数值，反映了第k条染色体所对应解的运输费
fk为第k条染色体的适应度，其值决定了该染色体产生后代的
用；maxpath为最大运距；
概率。
4）初始种群
本算法采用随机生成的方法产生初试种群。 5)遗传算子
本算法采用了最佳保留的轮盘赌复制法进行染色体的复制。 本算法采用最优保留顺序交叉算子行染色体的交叉。 本算法采用改进的反转变异算子进行变异操作。按照概率
pm进行反转变异，第3章介
绍的反转变异算子是在染色体中随机选取两个不同位置，将两位置间的子串进行反转。如直接在本算法的染色体结构中采用会产生如下两种问题：
当随机选取的两点均为0点时，反转变异操作无效，因为此时只是将子路径倒转。 当随机选取的两点中有一点是0，而另一点的邻位是0时进行反转操作会产生非法的染色体，在染色体中出现两个0相邻的情况。
0 3 8 0 6 7 2 0 1 5 4 0 0 3 8 2 7 6 0 0 1 5 4 0
图3-11 传统变异操作产生的非法染色体
因此在变异操作前先进行判断，以杜绝以上两种情况的发生，改进的反转变异算子执行流程如3-17所示。
3)控制参数和终止条件 群体规模popsize、交叉率
pc和变异率pm
pc、变异率pm、)的选取对遗传算法的影响很大，
控制参数(包括群体规模popsize、交叉率
要想得到遗传算法执行的最优性能，必须确定最优参数的设置。一般控制参数的选取要根据问题的属性确定。 终止条件
由于遗传算法具有较大的随机性，这里根据几条启发式的终止条件，给定参数A、X、Y，只要有一条满足就认为算法收敛了。
开始 基于线性排序的轮盘赌策略选出中间代newpop i=0 N i 计算每代群体适应度均值，当均值与最佳染色体适应度的比值大于时，可认为算法 收敛； 记录每代最佳染色体，若染色体连续最佳保持到X代，可终止算法； 由于计算时间和机器容量都是有限的，代数不能无限长，故迭代达到规定Y时，可停止计算。 3.2.7算法实现及结果 在VC环境下采用c++语言依据算法编写了程序，并调试通过。 该实例是由1个配送中心、10个客户组成的VRP问题。货物的装载系数 (VehicleRate)= 0.89，车辆的载重量 (VehicleLoad)= 8(吨)，车辆的行使速度 (speed) =50(km/h)，种群执行遗传操作的代数(maxgen) =500，车辆早到的惩罚系数(earlity)=3，车辆晚到的惩罚系数(late)=6。其他数据见表3-13。 i xpoint ypoint time Etime Ltime 1 70 140 1.3 0.8 1.5 2 150 130 2.8 2.0 1.8 2.3 3 60 70 2.1 1.0 0.7 1.3 4 70 60 3.6 3.0 2.7 3.3 5 110 120 2.9 2.0 1.7 2.5 6 80 90 2.4 2.5 2.3 3.0 7 90 80 2.2 0.8 0.4 1.3 8 90 120 1.2 2.2 1.9 2.5 9 150 150 3.7 3.0 2.5 3.5 10 260 140 2.8 2.3 2.0 2.6 demand 2.0 表3-13 VRP实例的原始数据 执行程序得出结果如下： 路径为 ：0 7 10 0 8 5 4 0 2 9 0 3 6 1 0； 最小消耗为：4480.53； 4总结 因篇幅问题不能全部显示，请点此查看更多更全内容