并行工程在车身设计的应用(共37页)

1、学 号 M201470547课 程 论 文题 目现代运筹学算法在物流配送中的应用学 院机械学院专 业工业工程班 级机硕1407姓 名杨勇指导教师李新宇副教授2014年12月29日摘要(zhiyo) 配送是物流活动中直接与消费者相连的环节。配送成本占物流的各项成本的比例相当高。配送线路合理与否影响到配送速度、成本和效益，特别是多用户配送线路的确定(qudng)是一项复杂的系统工程。因此，物流车辆路线问题(VRP)成为国内研究的热点。 运筹学，用定量化方法了解和解释运行系统(xtng)、为管理决策提供科学依据的学科。它把有关的运行系统首先归结成数学模型，然后用数学方法进行定量分析和比较，求得合理运

2、用人力、物力和财力的系统运行最优方案。运筹学有广阔的应用领域，是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。在运筹学中有解决物流配送问题的有效方法。本文主要介绍了节约法、遗传算法并用这些方法解决实际物流配送问题。关键词：物流配送，节约法，遗传算法Abstract Distribution logistics activities directly connected with the consumer segment. The costs of logistics and distribution c

3、osts 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 domest

4、ic 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 quant

5、itative 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 math

6、ematical 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 a

7、nd use these methods to solve practical problems of logistics and distribution.Keywords: logistics, saving, scanning method, tabu search, genetic algorithm目录(ml)TOC o 1-3 h u HYPERLINK l _Toc1319 1绪论(xln) 现代运筹学算法(sun f)在物流配送中的应用1绪论(xln)1.1发达国家(f d u ji)和地区物流配送现状 理解物流配送概念离不开对物流概念的分析。物流概念最早是在美国形成的，被称为

8、“physiealDistribution”(即Pn)，译成汉语是“实物分配”或“货物配送”。1963年被引入日本，物流被定义为“在连接生产和消费间对物资履行保管、运输、装卸、包装、加工等功能，以及作为控制这类功能后援的信息功能,，在物资销售中起了桥梁作用”。因此，现代物流是以满足消费者的需求为目标，把制造、运输、销售等市场情况统一起来思考的一个产业概念。配送是物流系统的核心环节之一，配送在英语中的原语是“delivery”，是交货送货的意思。在日本工业标准Jis中，将配送定义为“将货物从物流结点送交收货人”强调了送货的含义。可以说，物流配送是连接生产与消费之间的一种中介服务，是物资供应的种重

9、要形式。配送是“配”和“送”有机结合的形式，它利用有效的分拣、配货等理货工作，使送货达到一定的规模，以利用规模优势取得较低的送货成本。 推行配送制有利于合理配置资源。由于实施配送可以做到以配送企业的库存取代社会上千家万户的零散库存，或者说，可以使库存相对集中，因此，有条件也有可能按照统一计划合理分配和使用资源，做到物尽其用。推行配送制可以降低物流成本，促进生产快速发展。这是因为各种流通要素相对集中，有益于开展规模经营活动；流通的物质要素相对集中，也便于合理安排各环节上的物流活动，使总体运动协调一致，最终会减少物流领域内的劳动消耗和费用支出。推行配送制能够充分发挥专业流通组织的综合优势。推行配送

10、很容易使不同的流通组织联系在一起，从而构成多功能的、一体化的物流运动。这种以配送作为媒介而形成的一体化运作较之各个专业企业独立运作更能发挥流通组织的整体优势和综合优势。 从20世纪60年代起，商品配送的合理化在美国普遍得到重视。为了在流通领域产生效益，美国企业采取了以下措施：一是将老式的仓库改为配送中心；二是引进电脑管理网络，对装卸、搬运、保管实行标准化操作，提高作业效率；三是连锁店共同组建配送中心，促进连锁店效益的增长。美国连锁店的配送中心有多种，主要有批发型、零售型和仓储型三种类型。首先是批发型。该类型配送中心主要靠计算机管理。业务部通过计算机获取会员店的订货信息，及时向生产厂家和储运部发

11、出订货指示单。其次是零售型。以美国沃尔玛商品公司的配送中心为典型。该类型配送中心一般为某零售商独资兴建，专为本公司的连锁店按时提供商品，确保各店稳定经营。第三是仓储型。美国福来明公司的食品配送中心是典型的仓储式配送中心。它的主要任务是接受独立杂货商联盟的委托业务，为该联盟在该地区的若干家加盟店负责商品配送。 在日本，零售业是首先建立先进物流系统的行业之一。便利店作为一种新的零售业态迅速成长，现己遍及日本，正影响着日本其他的零售商业形式。这种新的零售商业业态需要利用新的物流技术，以保证店内各种商品的供应顺畅。因此，日本的物流配送具有以下特点；第一，分销渠道发达。许多日本批发商过去常常把自己定位为

12、某特定制造商的专门代理商， 只允许经营一家制造商的产品。为了保证有效地供应商品,日本许多物流公司不得不对原有的分销渠道进行合理化改造,更好地做到与上游或下游公司的分销一体化。第二，频繁、小批量进货。日本的物流配送企业的很大一部分服务需求来自便利店，便利店依靠的是小批量的频繁进货，只有利用先进的物流系统才有可能发展连锁便利店，因为它使小批量的频繁进货得以实现。第三，物流配送体现出共同化、混载化的趋势。共同化、混载化的商品配送使原来按照不同生产厂、不同商品种类划分(hu fn)开来的分散的商品物流转变为将不同厂家的产品和不同种类的商品混合起来运送的聚合的商品物流，从而得以发挥商品物流的批量效益，大

13、大提高了运货车辆的装载率。第四,合作型物流配送。在日本,生产企业、零售企业与综合商社、综合物流公司之间基本上都存在一种长期的物流合作关系。并且，这种合作关系还随着日本工业生产的国际化延伸到国外。第五，政府规划在现代物流配送发展过程中具有重要作用。1.2我国的物流配送发展(fzhn)现状 物流配送是现代流通的重要组成部分。近年来，我国物流配送发展(fzhn)出现了积极趋势，主要体现在以下几个方面： 各级政府部门采取措施积极推动物流配送的发展。不少省市己经把发展现代物流列入了日程，例如，上海、天津、深圳都把物流作为支柱产业。还有许多省市开始制定物流规划。国家有关部门对商品物流和配送采取了积极鼓励和

14、支持的政策，在我国流通领域对外开放政策中，鼓励国外资本投资于物流和配送设施等。目前国内物流和配送服务己有较快的发展，物流配送己经成为许多企业降低成本，提高竞争力的重要手段。例如，相当多实行连锁经营的零售企业建立了自己的配送中心，为企业内部的连锁网点提供物流配送服务，一些连锁企业配送商品比例己经超过企业经营品种的50%。 在生活资料领域和生产资料领域出现了各具特色的不同类型的现代物流企业。一些传统的流通企业，包括运输和仓储业通过改造成为物流企业，如中远集团、中外运集团和中储集团等；一些国有商业批发企业和大型零售企业正在积极探索和尝试开展社会化物流配送服务；一些生产企业开始介入现代物流，如青岛海尔

15、集团；一批专业化的物流企业得到较快发展，物流配送的社会化、专业化发展趋势日益明显，如深圳中海物流都是比较成功的第三方物流公司。外资在物流配送服务领域的发展也十分迅速，如中国储运总公司与日本岗谷钢机株式会社合资组建了天津岗谷物流公司，是集配送、加工、仓储、寄售、租赁、修理、展销和技术咨询为一体的新型流通组织。像这样的合资物流公司，在北京、天津、上海等地已有10家之多，它们主要是为在中国投资的跨国公司提供物流配送服务。这些企业根据各自特点，发挥特长优势，积极开拓物流服务领域，形成了服务模式多样、多种经济成份并存的现代物流企业群体。连锁企业内部的配送中心在硬件设施、管理水平、管理信息系统等方面的建设

16、，获得较大发展，有些己经达到较先进的水平。 现代物流技术的开发研究取得一定进展。一些物流配送企业在研究开发物流信息技术和物流配送管理技术上取得了许多成果，对于推动我国现代物流发展发挥了积极作用。目前已有相当多的物流和配送技术开始进入中国，并在企业中得到越来越广泛的应用，例如条形码技术、计算机支持的信息管理技术、EDI、MRP等。 尽管我国物流配送业近几年发展很快，但与发达国家相比还处在起步阶段，不可避免地会遇到这样或那样的问题。当前，主要存在以下几个方面的问题： （1）物流配送市场化程度低，第三方物流配送发展滞后。目前我国大多数物流配送企业技术装备和管理手段比较落后，服务网络和信息系统不健全，

17、物流配送市场化程度低，影响了物流服务的准确性与时效性。其主要表现是：小（物流配送企业数量小，经营规模小)、少(物流配送市场份额少、服务功能少，大多数企业还只是被动地按照用户的要求，从事单一功能的运输、仓储和配送，很少能提供物流策划、组织及深入到供应链的全过程管理，物流增值少)、散(网络分割、经营秩序不规范，不能为客户提供包括(boku)物流网络设计、预测、订货管理、存货管理等系统物流服务)、弱(竞争力弱和发展滞后，专业化、信息化、标准化还没跟上，还没有真正了解国际物流企业的运作方式和真正意义上的“第三方物流”)。 （2）物流基础设施落后，物流配送的整体功能低。一是交通运输设施建设与物流配送的需

18、要(xyo)不相适应，即交通运输能力仍不能满足运输需求，主要运输通道供需矛盾依然突出：二是技术装备水平落后；三是物流系统标准化程度低。 （3）物流配送管理体制和相关制度不完善。一方面，市场竞争机制和市场管理法规不健全，发展物流配送所需的产业政策和产业规划尚未出台(ch ti)，物流市场的进入与退出、竞争规则基本上无统一法律法规可循，对社会性的物流缺乏有效的外部约束，致使不正当竞争较为严重。另一方面，物流配送市场至今仍被人为地按照部门、地区和行业的行政壁垒分割，物流配送市场管理和行业管理还没有理顺，各地商委、经贸委、交通局、铁路局、外经贸委等都各自承担了一部分物流管理职能，各部门间分工又有交叉，

19、造成了物流管理中条块分割、重复建设等问题，统一、竞争、有序的物流配送市场没有建立起来，严重影响了物流配送渠道的畅通和高效运转,使物流配送很难达到规模经济和预期回报。 （4）专业的物流配送管理和技术人才短缺。1.3发展物流配送的意义 随着经济全球化和网络信息技术发展的加快，物流及配送业作为一个新的经济增长点引起了国人的注意。上海、天津、北京等城市纷纷将物流产业作为支柱产业，中储、中远、中外运等大型企业都把现代物流作为重点发展领域。我国证券市场己经形成了由几十家企业构成的“物流板块”，许多商贸流通部门纷纷介入现代物流配送业务中，物流及配送业的发展在全国方兴未艾。 2011年我国社会物流总费用为8.

20、4万亿元，从构成情况看，运输费用4.4万亿元，占社会物流总费用的比重为52.4%，保管费用2.9万亿元，占社会物流总费用的比重是34.5%，管理费用1万亿元，占社会物流总费用的比重为11.9%。运输成本占物流成本的50%左右，是影响物流总费用的主要因素，调查显示，美国的运输成本仅占到其GDP的不到6%，日本也仅为6.5%。而我国运输成本占到GDP 的11%。中国仓储协会对146家生产企业的调查结果表明，运输费用占整个物流费用的比例分别为：生产企业原材料物流中运输费用占到58%，生产企业成品物流中运输费用占到73%，商业物流中运输费用占到 52%。 由以上数据可以看出运输费用在总物流费用中所占比

21、重最大，因此节约运输费用可以极大的降低物流成本。在物流活动中，配送是很重要的一个环节，运输成本在配送成本中占有很大的一部分，因此在配送管理中，有效的使用车辆并确定配送车辆经济行驶路线，在最短的时间内把商品送到顾客手中，提高顾客的满意度，是配送作业的重点。显然，为了实现以上几点目标，必须对配送过程进行合理规划，这一点可以通过改进运输方式、进行线路规划等来实现。近年来，配送车辆路线的确定问题是物流配送领域的重点研究对象，它是指利用科学的、合理的手段来制定配送线路，对其进行研究可以提高配送效益、有利于实现配送科学化。 为实现运输成本的降低，必须对运输的进行(jnxng)合理规划。运输的合理规划涉及到

22、时间、财务、环境三方面的因素，首先从时间要考虑准时性、快速响应；财务上要考虑运输涉及的各种开支(车辆购置成本和消耗、司机薪酬、油耗等)；环境上要尽可能减少不必要的行驶,避免交通拥挤、空气以及噪音等污染。这些可以通过改进运输方式、线路规划等交通管理来加以改善。其中运输方式属于“硬”技术的问题。是可以通过设施的完善和提高运输的效率,降低相应成本。运输的线路规划主要是利用各种先进的信息技术对车辆及其路线进行规划，实现对车辆合理有效的利用，从而节省大量的时间和成本。而物流中心配送作业的重点就是如何将车辆有效的使用并决定其最经济的行驶(xngsh)路线图，使商品能在最短的时间内送到顾客的手中。该问题为；

23、从配送中心(物流据点)用多辆车向多个需求点(顾客)送货，每个需求点的位置和需求量一定,每辆车的载重量一定，要求合理安排车辆路线，使总运距最短，并满足以下条件：(1)每条配送路径上各需求点的需求量之和不超过车辆载重量；(2)每条配送路径的长度不超过车辆一次配送的最大行驶距离；(3)每个需求点必须满足,且只能由一辆车送货。达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。此即为VRP问题。 通过科学合理的手段制定配送路线，在配送活动中是很重要的一个环节。合理的选择配送路线，对于社会和企业具有重要意义。对于企业，配送路线的优化，可以简化配送程序、提高配送效率，充分利用配送车辆运

24、力、降低空载率、减少配送次数、尽量使配送成本降低；同时优化配送路线可以加快企业对客户需求的响应速度，准时、快速的把物品送达客户，提高客户满意程度。对于社会，配送路线优化可以节省作业车辆，进而缓解交通拥堵状况，减少噪声、尾气的排放，为保护生态环境(shn ti hun jn)做出贡献。所以研究配送车辆路线优化问题及算法具有重要的现实意义。1.4物流配送路线优化现状 国内外相关领域对VRP问题的研究始于50年代，在理论研究和实际应用两方面都已取得了非常显著的成果。随着研究的深入发展,如何使研究的理论模型更贴近现实中的运输规划问题开始成为研究者们关注的焦点。车辆路线问题(VRP问题)是组合优化领域中

25、著名的NP难题，近二十年来，无论在国内还是国外，VRP问题都是一个非常活跃的研究领域。目前国内外用于解决该问题的现代数学方法主要分为以下几类： （1）精确算法 精确算法是采用严密的数学手段进行计算的方法，在能够求得可行解的情况下，其求得的结果一般要好于启发算法。常见的精确算法有以下几种：分枝定界法、割平面法、动态规划法等。 分支定界法是一种应用范围很广的搜索算法，它的基本思想是把给定问题分解为若干个较小的子问题，每个子问题又可继续分解，直到子问题不能再分解或不能产生最优解。根据问题的特点和不同的策略，把问题分解为子问题的过程称之为分支。在分支过程，为每一子问题估算其对应的目标值的界限称之为定界

26、。定界的目的是为了测定界的趋势，留下有价值的或尚不能判定的分支。删除肯定不存在的最优解的分支，称之为剪支，以达到加速收敛、简化运算的目的。对为题进行分解，确定子问题的解值界限，减去非优的子问题，在进行新的分支，这样一个分支到定界到剪支再到分支等反复的过程是分支定界法的基本算法步骤。不同的分支规则与定界方法，形成了同一问题的不同分支定界方法。 割平面法是由高莫瑞1958年提出的，故又称为Gomory的割平面法。它的基本思想是：不断增加线性约束条件（几何术语称为割平面）将原规划问题的可行域切割掉一部分，使其切割掉的部分只包含非整数(zhngsh)解，没有切割掉任何整数可行解，直到切割后得到的可行域

27、有一个整数坐标的极点恰好是问题的最优解为止。针对求解的决策变量是全部取整还是部分取整问题，割平面算法中就分成了两种计算方法，前者称为分数算法，后者称为混合整数算法。 动态(dngti)规划法是20世纪50年代由贝尔曼（R. Bellman）等人提出,用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程,就是把研究问题分成若干个相互联系的阶段,由每个阶段都作出决策,从而使整个过程达到最优化。许多实际问题利用动态规划法处理,常比线性规划法更为有效,特别是对于那些离散型问题。实际上,动态规划法就是分多阶段进行决策,其基本思路是：按时空特点将复杂问题划分为相互联系的若干个阶段,在选定系统行进

28、方向之后,逆着这个行进方向,从终点向始点计算,逐次对每个阶段寻找某种决策,使整个过程达到最优,故又称为逆序决策过程。 精确式算法领域的研究主要是针对某一特定问题而设计，实际应用范围有限，基本是在传统物流配送模式下来考虑问题、改进模型和设计算法。该方法不能保证所得出的最终解是最优整数解，但其一定是非常接近最优解的。随着车辆运输调度系统的复杂化和调度目标的增加，问题的数据量会变得越来越大，利用精确算法求解问题就会变得十分困难，于是研究者们开始考虑利用启发算法来解决这类问题。启发方法是指人们根据经验规则来发现问题的满意(mny)解的方法。用启发式方法求解问题时往往注重求得满意解而非最优解。启发式算法

29、分为传统启发式算法和现代启发式算法两种。 （2）传统启发式算法 传统的启发式算法主要有节约法、扫描法等。 节约里程法又称节约算法或 HYPERLINK /doc/5379092.html t /doc/_blank 节约法，是指用 HYPERLINK /doc/4332348.html t /doc/_blank 来解决运输车辆数目不确定的 HYPERLINK /doc/6783977.html t /doc/_blank VRP问题的最有名的 HYPERLINK /doc/6658906.html t /doc/_blank 启发式算法。节约里程法基本规定， HYPERLINK /doc/2

30、519078.html 利用节约法确定配送路线的主要出发点是，根据 HYPERLINK /doc/199749.html t /doc/_blank 配送中心的 HYPERLINK /doc/5687912.html t /doc/_blank 运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的 HYPERLINK /doc/199749.html t /doc/_blank 配送方案。另还需满足以下条件；1）所有用户的要求；2）不使任何一辆车超载；3）每辆车每天的总 HYPERLINK /doc/4101580.html t /doc/_blank 运行时

31、间或行驶里程不超过规定的上限；4）用户到货时间要求。基本思想 HYPERLINK /doc/2519078.html 是，为达到高效率的配送，使配送的时间最小距离最短成本最低，而寻找的最佳配送路线。近年来，由于小批量、多批次的及时配送方式的发展,运输费用正在逐年提升，许多企业的运费己经超越了库存费用。选择有效的配送路线，己成为控制物流成本的主要措施。那么如何选择有效的配送路线呢？现代企业已经普遍接受了一种观点，即有效的配送路线实际上是在保证商品准时到达客户指定点的前提下，尽可能地减少运输的车次和运输的总路程。在这种思想的指导下，节约法已成为选择配送路线的主要方法，并受到国内外物流界的青睐。 扫

32、描法是Gillett和Miller于1974年所提出的求解车辆路线问题（Vehicle Routing Problem,VRP）的方法，此方法属于先分群再排路线的方式。该方法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或 HYPERLINK /sowiki/%E9%80%86%E6%97%B6%E9%92%9F?prd=content_doc_search o 逆时钟 逆时钟方向，以车容量为限制条件进行服务区域之分割，再借由Lin与Kernighan的交换法进行需求点的排序，建构车辆排程路线。一般情况下，制定从一个物流中心向多个用户运送货物的配送计划时，必

33、须考虑每辆车的运载能力和行驶距离及时间等的限制。其中扫描法是一种能较好地解决配送路线问题的有效方法，它的基本思路是采用逐次逼近的方法来解决问题。 （3）现代(xindi)启发式算法 现代启发式算法主要有禁忌搜索算法、遗传算法、蚁群算法、粒子群算法等。用现代启发算法对问题的求解(qi ji)是通过大规模的迭代来实现的，现代启发算法自身具有一套独特的搜索规则。为了求得满意解，算法在迭代中要不断采纳和分析新信息，必要情况下需要变更原来的策略，建立新的搜索规则，同时要注意从失败的搜索中取得经验教训，逐渐减小搜索的范围。随后从多个可行解中找出满意解。 1）禁忌(jnj)搜索法 Gendreaut 等人（

34、1991）最先将禁忌搜索法应用于车辆路径优化问题。先构造一系列的解，然后对所得到的结果不断地改进。该算法所得到的解不一定是可行解，它们对可行性的偏离程度体现在目标函数里的惩罚函数值的大小。禁忌搜索法是针对车辆路线优化问题的较好的现代启发式算法，在许多经典的车辆路线优化问题的求解中都已经被成功地运用。 2）遗传算法 近年来，一类基于生物学,物理学和人工智能的具有全局优化能力、鲁棒性强、通用性强且适于并行处理的现代启发式算法得到了发展。因其高效的优化性能、无需问题特殊信息等优点，广泛用于计算机科学、优化调度、运输问题、组合优化、工程优化等领域。遗传算法是其中具有代表性的一种现代启发式方法。 3）蚁

35、群算法 蚁群算法蚁群算法（ant colony optimization,，ACO）又称蚂蚁算法，是一种用来寻找最优解决方案的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。蚁群算法就是根据这一特点，通过模仿蚂蚁的行为

36、，从而实现寻优。这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。 4）粒子群算法 Kennedy 和 Eberhart 在 1995 年首次提出了粒子群算法，该算法基

37、于对鸟类飞行觅食行为的模拟，群体达到最优目标是通过鸟群个体之间的协作行为实现的。粒子群算法与遗传算法类似，它们的共同点是运算方式基于群体的迭代，但粒子群算法没有变异、交叉和算子的复制，群体在解可行域中追逐最优粒子不断搜索直到找到满意解。粒子群算法的优点为：个体数量少、计算简单、鲁棒性好、容易实现，并有着深刻的智能背景，适合于科学研究及工程应用。粒子群算法源于对鸟群捕食行为的研究。鸟群捕食场景为：鸟群在一片固定区域内寻找食物，但在这个区域内食物只有一块，群内的每一只鸟的搜索行为都具有随机性。鸟群中的所有个体都不清楚在哪里可以找到食物，但个体知道自身位置与食物间的距离。对于这个群体来说寻找食物的最

38、简单有效的策略就是搜寻目前离食物最近的个体周围的区域，粒子群算法正是基于上述方式解决优化问题的。粒子群算法求解优化问题时，每一个潜在解可以被看做是空间中进行搜索的一只鸟，我们将之称为“粒子”。所有的粒子与相关优化函数之间都有适应值，这个适应值由优化函数决定，粒子自身具有速度，粒子的速度决定粒子本身的飞行距离和方向。所有的粒子追随目前的最优粒子在可行区域内搜寻最优解。粒子群算法随机初始化一定数量的粒子，它寻找最优解的方式是通过多次迭代。每次迭代粒子追逐个体极值及全局极值来更新自己。2理论(lln)基础2.1物流配送问题的基本(jbn)理论2.1.1配送(pi sn)路线问题模型采用科学的、合理的

39、方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径。在满足客户配送需求的前提下，如何选择配送路线，是一项很重要的工作。配送作业的时效性和高效性主要受车辆路线的安排与调度方案优化情况的影响。配送路线优化问题由来已久，其可以描述如下，见图 2-1。客户点配送中心图2-1 配送路线优化问题原理图 有一个(y )（或者多个）配送中心，共有配送车辆 K 辆（一种或者多种车型），车辆载重量为Q1，Q2，Qk共有(n yu) I 位客户等待被服务，每位客户都有各自需求量G1，G2，Gi。从配送中心出发的配送车辆对等待服务的客户进行配送，以满足客户的要求（物品品种、数量、规格的要求，配

40、送时间的要求），最后返回配送中心。要求所有客户都被服务到，同时配送车辆不能超载。最终(zu zhn)求出车辆配送路线方案，并达到一定的优化目标（如路程最短、费用最少、时间尽量少等）。车辆路线优化问题是 NP 难题。自从它被提出以来，由于其应用的广泛性和在经济上的价值，一直受到国内外学者的广泛关注。配送路线优化问题的主要构成要素为：配送车辆、货物、客户、配送中心、路网。各要素具体说明如下。 （1）车辆，其主要属性有：车辆类型、装载量、最大行驶距离、配送开始前与完成后所在的配送中心。 （2）货物，其主要属性有：重量、送达时间和送达地点等。货物能否装在同一配送车辆上取决于货物属性。 （3）客户，其主

41、要属性有：需求(或供应)货物的种类、接受服务的时间等。 （4）配送中心，其主要是用来进行集货、分货、配货、送货等物流作业，在不同的路线优化问题中，配送中心的个数为一个或者多个。 （5）运输网络，其组成部分有配送中心、客户点和车辆行驶路线等。2.1.2物流配送路线的优化目标 对车辆配送路线问题进行优化时，必须要有明确的目标和遵循的基本原则。配送路线优化问题的优化目标可以从以下几个方面考虑： （1）配送效益最高或配送成本最低。 物流企业是以追求效益为主要目标的，通常用企业利润来表示，即企业通常以利润的最大化作为自身经营的目的。配送成本对物流企业利润有直接的影响，以成本最低作为优化目标与物流企业利润

42、的最大化有直接的联系。当与成本及利润相关的数据容易得到和计算时，就可以用利润最大或以成本最低作为优化目标。 （2）配送里程最短。 当配送成本与配送里程具有较强的相关特性，与除此之外的其它因素相关特性较弱时，配送里程最短就近似等同于配送成本最低。这时可以考虑用配送里程最短作为优化目标，这样就可以大大简化配送路线优化方法。当配送成本与配送里程的相关性不明显优于其它因素的时候，如考虑车辆载重情况、道路运行条件等因素，单以路线最短作为优化目标就变得不适宜。 （3）配送服务水平最优。 当准时性成为配送的第一要求，或当出现某些特殊情况需要确保服务水平而忽略配送成本时，则应尽量在成本不出现失控的情况下，以服

43、务水平最优为优化目标。优质的服务可以采用较高的服务价格，从而保证企业的合理利润。 （4）配送(pi sn)劳动的消耗最小。 它是以物化劳动和活劳动消耗最小为优化目标，在许多情况下，如人员紧张、燃料紧张、车辆(chling)设备紧张等，限制了配送作业，这时就可以考虑以配送所需要的人员、车辆或其它相关资源消耗最小作为优化目标。实际上，配送路线优化问题的优化目标是多元的，但是考虑到优化目标的目标值应当符合实际情况，一般要尽可能取得实用性较强的目标值。因此，本文采用成本最低作为优化目标。2.1.3配送(pi sn)车辆路线优化问题的约束条件 现实中，配送车辆路线优化问题存在着很多方面的约束条件，这些约

44、束条件使得该问题在研究和应用上产生了许多不同的方向和型态，基于前文所述的分类标准，一些最重要的约束条件包括： （1）容量约束。任意配送车辆所搭载的货物总量不能超过该车辆的载重能力。 （2）配送中心数目约束。配送中心有一个或者多个。 （3）优先约束。客户之间服务的次序存在着限制。 （4）车型约束。不同客户的配送要求需要由不同车型来满足。 （5）时间窗约束。包括硬时间窗约束和软时间窗约束。 （6）随机约束。客户数量、配送需求、行驶路线等随机出现。 （7）车速约束。车速是否稳定。 （8）相容性约束。客户是否可以被不同配送车辆（配送中心）服务。 通过以上分析，本文所要研究的配送车辆路线优化问题所采用的

45、约束条件为：每个客户只能被一辆车服务，每个被服务客户没有优先次序，配送车辆的载重情况不超过自身的载重能力，每个客户对其被服务的时间窗的要求为软时间窗模式。2.1.4配送路线优化问题的分类 对配送车辆路线问题类型分析是进一步对问题进行建模和求解的基础。现有的对配送路线优化问题的分类大致有以下八种:分类依据分类具体分类说明按任务特征分只送货问题只送货问题的特征为：配送车辆仅考虑从配送中心向客户送货；只取货问题的特征为：配送车辆仅考虑从各客户处把供应的货物取到配送中心；取送货混合问题的特征为：既考虑将客户需求的货物从配送中心送到各个客户只取货问题混合问题按配送中心数目分单一车场问题单一车场问题的特征

46、为：配送系统中只有一个车场、货场或配送中心；多个车场问题的特征为：配送系统中有多个车场、货场或配送中心多个车场问题按配送车辆类型数目分单一车型问题单一车型问题的特征为：配送作业所用车辆都是同一类型，即车辆的参数如：载重能力、最长行驶时间和单次作业的最大行驶距离等相同；反之多种车型问题的特征为配送作业所用的车辆类型不完全相同多个车型问题按配送车辆路线分车辆开放问题车辆封闭问题车辆开放问题的特征为：车辆完成其配送任务后可以不返回出发点；车辆封闭问题的特征为：车辆完成其配送任务后必须返回出发点按配送车辆卸载状况分满载问题满载问题是指当客户的需求量或提供量大于或者等于配送车辆的载重能力时，需要用一辆或

47、者多辆车来完成一项配送作业，其中大多数配送车辆要满载运行；非满载问题是指当客户的需求量或提供量小于配送车辆的载重能力时，多个客户的配送需求都可以由同一配送车辆来满足，整个配送过程中配送车辆处于非满载状态；满载和非满载混合问题是指当一部分客户的需求量或提供量大于或者等于配送车辆的载重能力，而一部分客户的需求量或提供量小于配送车辆的载重能力时非满载问题混合问题按客户时间需求分无时间窗问题无时间窗问题的特点是客户对服务时间无具体要求；有时间窗问题的特点是客户要求配送车辆必须在规定的时间范围内将货物送达或取走。有时间窗问题又可以分为硬时窗问题和软间窗问题，其中硬时窗是指，客户要求必须在指定的时间范围内

48、进行配送作业，不能提前也不能拖后否则需要等待或者不能为其服务，软时窗是指，客户要求配送车辆尽可能在规定的时间范围为其服务但也可以提前或拖后，只是要受到一定的惩罚，如交罚金有时间床问题按优化目标数分单目标问题单目标问题是指选择某一最优或较优指标作为优化目标，如配送路线最短。多目标问题则是指同时选择多个最优或较优的指标作为优化目标，如同时要求配送路线最短和成本最低。路线优化模型的指标一般包括：配送时间最短、配送路线最短、成本最低。一般情况下这三个目标是统一的：距离最短，也就意味着时间最短，成本也最低，但是很多情况下，也有出现多目标不统一、甚至互相矛盾的可能多目标问题按客户和路网特点分静态问题静态问

49、题的特征为：客户的位置、数目、需求，以及天气、路况等因素是确定的和已知的；动态问题的特征为：客户的位置数目、需求，以及天气、路况等因素是随机变化的。动态问题表2-12.2典型配送(pi sn)车辆路线优化问题的数学模型 本文此处以经典的带时间窗配送车辆路线优化问题为例，来说明配送车辆路线优化问题的一般模型(mxng)及表达方式。带时间窗配送车辆路线优化问题的一般描述为：有一个配送中心（含车场），拥有的配送车辆数为 K 辆，容量分别为 Qk（k=1，2，K）。有 I 个客户点需要被服务，客户点 i 的作业量为 Gi，配送车辆 k 到达客户点 i 的时刻为kis ，并且客户点 i 的配送作业需要在

50、规定的时间窗ETi，LTi内完成，其中 ETi表示客户点 i 允许配送作业开始的最早时间，LTi表示客户点 i 允许配送作业开始的最迟时间。如果配送车辆到达客户点 i 的时间早于 ETi，则配送车辆需要在客户点 i 处等待(dngdi)，如果配送车辆到达客户点 i 的时间晚于 LTi，则客户点 i 的配送作业将被延迟进行，同时配送车辆需要接受处罚。 一般情况下带时间窗路线优化问题需要考虑以下几个约束条件： （1）各客户点只可以(ky)由一辆车配送且只能被配送一次，不考虑多辆车同时为一个客户点服务的情况； （2）配送(pi sn)中心（或车场）只有一个，所有车辆从配送中心出发，车辆在完成所有作业

51、之后需要回到配送中心； （3）各配送(pi sn)线路上客户点的作业总量不应大于该线路上作业车辆的载重量； （4）每个客户点的配送作业量必须小于为其服务的车辆的最大载重量，即只需一台配送车辆即可满足该客户点的配送作业需求。对模型参数定义如下：客户i由k车来服务其他车辆k由i到j其他表示客户点 i 到客户点 j 的运输成本；表示配送车辆由于等待失去的机会成本；表示配送车辆由于迟到需要支付的罚金。在仅考虑装载约束和时间窗约束的条件下，带时间窗的配送车辆路线优化模型可以表示为： 任意的k i=1，2，I j=1，2，I，任意的k i=1，2，I，任意(rny)的k=0或1i，j=1，2，,I，任意(

52、rny)的k=0或1 i=1，2，I，任意(rny)的k 其中式中的目标函数，表示为各客户点配送的目标是使配送成本最小。目标函数由两部分组成，前半部分为车辆在线路上进行配送时所消耗的运输成本，后半部分为车辆在为各个客户点进行配送的过程中，由早到所损失的机会成本及迟到所支付的罚金之和。这一目标函数的具体意义为：要在满足配送路线最短的条件下，尽量考虑车辆配送的时间窗约束，以使得配送车辆运输成本及时间成本两者所代表的配送成本最低。该模型的不足是忽略了配送车辆载重情况及道路等级情况对车辆运输成本的影响。3现代运筹学方法在物流配送路线优化中的实际应用3.1传统启发式节约法及其应用3.1.1节约法描述 利

53、用里程节约法确定配送路线的主要出发点是，根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来制定使配送车辆总的周转量达到或接近最小的配送方案。假设条件： （1）配送的是同一种或相类似的货物； （2）各用户的位置及需求量已知； （3）配送方有足够的运输能力； （4）设状态参数为tij, tij是这样定义的： tij=1,表示客户I，J在同一送货路线上；0，表示客户I，J不在同一送货线路上。 t0j =2表示由送货点p0向客户J单独派车送货。 且所有状态参数应满足下式： 式中：N客户数 利用节约法制定出的配送方案除了使总的周转量最小外，还应满足： （1）方案能满足所有客户的到货时间要求

54、； （2）不使车辆超载； （3）每辆车每天的总运行时间及里程满足规定的要求。 如图3-1所示，设p0为配送中心，分别(fnbi)向用户pi和pj送货。p0到pi和pj的距离(jl)分别为d0i和d0j，两个(lin )用户pi和pj之间的距离为dij，送货方案只有两种即配送中心p0向用户pi, pj分别送货和配送中心p0向用户pi, pj同时送货，如图11-7a)和b)。比较两种配送方案： 方案a）的配送路线为p0pip0pjp0,配送距离为da=d0i+d0j 方案b)配送路线p0pipjp0,配送距离为db=. d0i+d0j+dij 显然，da不等于db，我们用sij表示里程节约量，即方

55、案b)比方案a)节约的配送里程： 根据节约法的基本思想，如果一个配送中心p0分别向N个客户pj(j=1.2n)配送货物，在汽车载重能力允许的前提下，每辆汽车的配送线路上经过的客户个数越多，里程节约量越大，配送线路越合理。图3-13.1.2节约法应用 例：某一配送中心p0向10个客户pj(j=1,2,10)配送货物，其配送网络如图3-2所示。图中括号内的数字表示客户的需求量（T），线路上的数字表示两节点之间的距离。配送中心有2t和4t两种车辆可供使用，试制定最优的配送方案。 图3-2解：第一步：计算最短距离。根据配送网络中的已知条件，计算配送中心与客户(k h)及客户之间的最短距离，结果见表3-

56、3。 P010P194P2795P3814105P48181496P58181715137P6313121011106P74141311121282P810111517181817119P97481315151510118P10表3-3 第二步：计算节约(jiyu)里程sij,结果(ji gu)见表3-4。P115P2811P34710P403610P500039P6000015P70000045P894000125P91381000009P10表3-4 第三步：将节约(jiyu)sij,进行(jnxng)分类，按从大到小的顺序排列，得表3-5。节约里程(lchng)项目分类表序号路线节约里程

57、序号路线节约里程1p1p21513p6p752p1p101313p7p853p2p31113p8p954p3p41016p1p444p4p51016p2p946p1p9916p6p846p5p6919p2p536p9p10919p4p639p1p3821p7p929p2p10822p3p10111p2p4722p5p7112p3p6622p6p91表3-5 第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图。 （1）初始方案：对每一客户分别单独派车送货，结果如图3-6。图3-6 初始(ch sh)方案 初始方案(fng n)：配送线路10条 配送(pi sn)距离：S0：148k

58、m 配送车辆：2t10（2）对方案进行修正1）按节约里程sij由达到小的顺序，连接p1和p2, p1和p10，p2和p3,得修正方案1。配送线路：10条 配送距离：S1：109km 配送车辆：2t6+4t1 2）在剩余的Sij中，最大的是S3，4和S4，5，此时p4和p5都有可能并入线路A中，但考虑到车辆的载重量及线路均衡问题，连接p4和p5形成一个新的线路B，得修正方案2。 配送线路：6条 配送距离：S2：99km 配送车辆：2t5+4t1 3）接下来最大的Sij是S1，9和S5，6，由于此时p1已属于线路A，若将p9并入线路A，车辆会超载，故只将p6点并入线路B，得修正方案3。 配送线路：

59、5条 配送距离：S3：90km 配送车辆：2t3+4t2 4）再继续按Sij由大到小排出S9，10、S1，3、S2，10、S2，4、S3，6，由于与其相应的用户均已包含在已完成的线路里，故不予考虑。把S6，7对应p7点并入线路B中，得修正方案4。 配送线路：4条 配送距离：S4：85km 配送车辆：2t2+4t2 （3）最终(zu zhn)方案：剩下的是S7，8，考虑到配送距离的平衡(pnghng)和载重量的限制，不将p8点并入(bn r)到线路B中，而是连接p8 和 p9 ，组成新的线路C，得到最终方案，这样配送方案已确定：共存在3条配送线路，总的配送距离为80 km，需要的配送车辆为2t车

60、一辆，4t车3辆。3条配送线路分别为： 第一条配送线路A：p0p3p2 p1p10p0使用一辆4t车。 第二条配送线路B： p0p4p5 p6p7p0，使用一辆4t车。 第三条配送线路C： p0p8p9p0，使用一辆2t车。 最终方案： 配送线路：3条 配送距离：S4：80km 配送车辆：2t1+4t2 图3-7 最终方案3.1.3节约法的优缺点分析 （1）节约法的优点 节约法一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单、清晰，便于执行。正是如此，它受到国内外物流配送业的青睐。 （2）节约法的缺点 第一，