基于优化的粒子群算法的物流配送路径问题研究(共42页)

1、 43/43基于优化的粒子(lz)群算法的物流配送路径问题研究 摘 要随着市场经济的突飞猛进与现代物流技术的发展,物流配送环节(hunji)正受到日益广泛的关注,而配送中的物流配送路径问题成为了物流配送中的核心问题。本文正是在这一背景下产生,文章重点研究了物流配送路径优化模型的建立(jinl)和粒子群算法的改进问题。本文对物流配送路径问题进行了深入研宄,通过对多种不同目标的物流配送模型研究,分析总结模型建立的一般步骤,并建立了基于最短路径的多个车场多个车辆的物流配送模型,同时从控制车辆行驶里程角度考虑,对车辆服务客户数量加以限制,加入了新的约束条件。同时为了对模型进行计算,分析对比多种算法,最

2、后选择粒子群算法做为研宄对象。通过对传统粒子群算法缺点的研宄,设计了一种自适应变异的粒子群优化算法。文章通过对现有一些改进方法的分析研究,对传统算法进行了优化,引入模糊分类、自适应变异机制、加入新的变异概率和可调节适应度方差,以达到对当前粒子进行自适应调整的目的,从而避免早熟收敛,形成新的自适应变异的粒子群优化算法。同时本文给出一种编码模式,降低了出现不可行解的概率。最后通过MatLab 2011a平台对所做内容进行仿真实验,验证相应结论,仿真内容分别为用文章建立的多车场多车辆模型验证优化算法的可行性和优越性,用前文给出的基于最短路径最少车辆和基于顾客满意度的两个模型验证基于不同目标前提下的配

3、送模型所得物流配送方案不同。仿真获得两个结论,分别为本算法在求解此类问题时具有优于传统粒子群算法的特征,既保持了较好的全局搜索能力,又可有效避免算法早熟收敛;基于不同最优配送目标的物流配送模型,所得物流配送方案具有差异性。关键词:物流配送问题;数学建模;粒子群算法;自适应目 录摘要 IAbstract II目录 Ill1绪论 11.1研宄的背景与意义11.2研宄现状综述11.2.1国内外研究现状21.2.2算法研宄现状31.3研究内容与研宄方法41.4本文的组织结构52物流配送模型建立与常见模型分析82.1物流配送路径问题相关研究82.1.1 物流配送路径问题定义82.1.2物流配送路径问题分

4、类82.2物流配送路径问题数学建模种类92.3模型举例102.3.1 基于行驶距离最短和使用车辆最少的物流配送问题102.3.2基于开放式车辆路径的物流配送问题112.3.3基于顾客满意度的物流配送问题122.4模型建立思路总结142.5基于最短路径的多车场多车辆配送模型建立153物流配送路径问题(wnt)相关算法研究193.1物流配送路径问题相关(xinggun)算法研究193.2常见(chn jin)现代优化算法分析与对比203.2.1算法举例203.2.2算法比较243.3传统粒子群算法局限性分析253.3.1经典PSO算法253.3.2传统算法的流程263.3.3算法具体描述273.3

5、.4粒子群算法特点分析313.4已有粒子群算法的改进方法314一种改进的粒子群算法设计354.1改进后的自适应变异粒子群算法354.2粒子编码374.3算法实现的具体步骤384.3.1算法实现步骤文字表述384.3.2 算法实现步骤的流程图表述394.4优化的粒子群算法与其他算法比较414.4.1优化的粒子群算法与遗传算法的比较414.4.2优化的粒子群算法与传统粒子群算法比较425 MatLab仿真与实验445.1算法仿真环境445.2算法可行性与对比分析445.2.1仿真实验数据445.2.2算法可行性研究455.2.3优化算法与传统算法的对比分析465.3基于不同目标模型的对比研究495

6、.3.1仿真实验数据495.3.2 仿真结果495.4 仿真结果总结516 结论与展望536.1本文工作总结536.2研宄展望54参考文献56作者简历59独创性声明60学位论文数据集611绪论1.1研究的背景与意义迅速发展的现代科学技术,加强了全球经济一体化的脚步,国家正面临着前所未有的机遇和挑战,而物流对于经济活动的影响,越来越受到人们的重视。存储的需求在现代物流配送过程中的重要性减弱,取而代之,配送成为最重要的环节。车辆的集货、货物配备和交货流程、车辆配送路线的优化是整个物流配送最核心的部分,它们对整个物流的成本、运输速度和效益的影响都是非常重要的。根据中国仓储协会对146企业协会调查显示

7、,在整个物流费用中,用于运输的费用比例分别为:在成品物流在生产企业占73%,原料生产企业物流占58%,因此,对于分配环节的优化方面,最重要的就是研宄配送路径车辆调度问题,而对于集货路线优化、物品配送路线和装备方式是对于配送车辆调度优化的重要环节,也是进行对配送环节进行优化的重中之重。物流系统中物流配送是一个非常重要的环节,它是整个对客户服务过程中最后一个环节。因此,需要知道在物流过程中,物流配送的地位非常突出,所以企业经营中必须实现快速、准确的物流配送,这是十分重要问题。物流配送路径问题提出之后,很快便引起计算机学科(xuk)、运筹学、组合数学、应用数学、物流科学等学科专家的极大重视,并且一直

8、是人工智能、应用数学领域的前沿与热点问题。在现实生产和生活中,网络路由问题、邮政投递问题、公共汽车调度问题、管道铺设问题等都可以抽象化为物流配送路径问题。在物流配送业务中,物流配送问题需要考虑的因素比较多,涉及的面比较广,同时对配送企业降低成本、提高服务质量、增加(zngji)经济效益的影响也比较大。然而目前研究发现,我国在研究物流配送车辆调度方面成果较少,所获得的进展缓慢,并且对于仿生算法研究还有一定的欠缺性,对于算法自身的缺陷弥补不足,针对以上原因,本文将重点研究物流配送中车辆调度和路径问题,并将物流配送中的算法进行详细研究,针对算法缺陷进行改进,形成新的优化算法,并根据最优配送目标和实际

9、要求建立数学模型,进行计算与仿真。1.2研究现状(xinzhung)综述在现代物流体系中物流配送车辆路径问题是一个重要组成部分,它是指在物流中心的货物,通过交货,将货物送到收货人的一系列活动都需要按照用户需求进行设置。例如,你有一个中央货场货物需要交付给多个用户,每个用户都有不同的需求,货物车辆在装满后运输货物,它配送完每一个用户后再回到货场,完成任务,在这个过程中,如何满足用户的需求,以最小的成本费用和车辆的路线进行配送,那就是物流配送路径问题。又如另一个例子,需要被运送到中央仓库的一些厂家生产的产品,车辆从仓库开始向厂家装车后,全额返还到仓库,并满足一些生产产品的制造商的要求,按照一定的路

10、线,可以降低总费用,这就是物流配送路径问题。这两个问题具有相同的实质,只是交付的任务或者集货的任务存在差异。在物流和运输业务中,有很多的优化决策问题。合理选择运输路径,在提高服务质量,加快交货过程,提高经济效益,降低运营成本上都有较大的影响。1.2.1国内外硏究现状对于物流配送路径优化问题一度被提出后,国内外学者都十分关注,分别从不同的方向、不同的角度对这一问题进行了深入的研究,分别按照不同的标准对其进行优化和分类。本文为了方便描述,根据业务类型的不同简要将其分类描述。物流配送问题是预先设计好的一种路径走向,可以将物流配送路径问题简要的分成五个类别。分别是:(1)最简单的物流配送路径优化问题1

11、。最简单的物流配送路径优化问题被抽象为有一个配送中心,有一辆配送车辆,且满足相应的约束条件进行货物配送。是最简单的一种路径优化向题2。(2)基本的物流配送路径优化问题3。将前一种分类进行推广研究,就可以描述为一个中心,有多辆车,每辆车有固定载重,按照要求进行配货。其实这是一个标准的车辆路径问题4,也可以说是车辆调度问题,一直是优化学科和运筹学的前沿热点5。(3)根据实际设定约束的物流配送路径优化问题。目前条件下一共需要考虑的因素有以下几种。1)客户对时间有限制6。即可以描述为客户对整个物流配送过程有时间窗的要求,包括硬时间和软时间7;2)车辆对于运输(ynsh)的距离有相应的限制8。即可以描述

12、(mio sh)为车辆的最大行驶距离的有限性9;3)对于客户由不确定的需求限制(xinzh)ieiu即客户有随机或模糊的需求11。(4)多样性限制的物流配送路径优化问题。1)有多种车型的配送方式12。即整个配送中心具有多种类的车型车辆进行配送服务13;2)有多个车场的配送方式14。即多个车场同时服务,进行物流配送15;3)物流配送有多个目标16,即配送中心所具有的优化目标含有几个相互排斥的分目标17。(5)其他种类配送路径优化问题。例如开放式的物流配送路径优化服务等18。1.2.2算法硏究现状粒子群优化算法是求解组合优化问题的一种群体智能算法,其具有参数少、模型简单、收敛速度快等优点,常被运用

13、到神经网络问题中,用来解决实际问题。目前对于粒子群算法的优化改进主要集中在以下的几个方面:(1)对粒子群算法结构进行改变;(2)对粒子群算法机理进行分析;(3)研宄粒子群算法中参数的设置;(4)研究粒子群算法的拓扑结构;(5)研宄对粒子群算法进行离散化的方法;(6)研究粒子群算法的并行版本;(7)对用于多目标求解的粒子群算法进行研究;(8)研究粒子群算法在实际问题中的应用。Shi第一次在粒子群算法中引入了惯性权重系数19,通过调解原有速度和更新速度的关系,平衡粒子的局部搜索能力和全局搜索能力。Kennedy在粒子群算法中提出了带邻域拓扑20,通过拓扑来延缓信息在种群中的交流速度,降低粒子群内部

14、粒子之间的相互影响,从而降低得到局部最优值发生早熟的可能性,同时通过对各种邻域拓扑结构对算法性能影响的分析,总结出指出冯诺依曼结构具有最好的综合性。Kennedy分析了速度更新公式在粒子群算法中的作用,同时分析了无速度更新公式的粒子群算法21。Kennedy提出了动态概率粒子群算法22。 Clerc在粒子群算法中引入了约束因子,用来确保粒子群算法局部的收敛性。曾建潮等提出了一种保证粒子群算法全局收敛的新方法。Bratton和Kennedy对粒子群算法的各种改进提出了一个标准框架23,为各种PSO算法改进研究提供了参照标准。Bergh等提出协作粒子群算法24。 Chen等将结合极值优化引入到粒子

15、群算法中,通过结合E0的开拓能力和PSO的探索能力来提高其性能。对粒子群算法参数的设置问题,本文研究主要包括,对于惯性权重W、社会因子C1、个人因子C2和速度上限Vniax的取值策略以及研宄粒子群的规模。Chatterje和Shi分别提出了惯性权重的非线性变化和线性变化的粒子群算法王俊伟等通过实验研究,给出了设置惯性权重的指导性原则。彭宇等对于C1， C2和惯性权重W的设置通过方差分析手段对算法性能的影响分析,总结了针对参数设置的有哪些指导原则25。 Liu提出了一种中央粒子粒子群算法,实验证明该算法性能比传统粒子群算法好26。除此之外,目前的研究热点还包括将其他进化计算方法融合到粒子群算法中

16、将其改进27。针对物流配送路径问题和粒子(lz)群算法的现状,文章对粒子群算法进行深入研究,对其缺陷进行分析,引入新的优化手段,优化现有粒子群算法,并根据需求加入相应的约束条件建立物流配送模型进行求解,对于实际应用起到相应作用,也为下一步研究工作的展开奠定基础。1.3 研究(ynji)内容与研究方法本文首先介绍物流配送路径的基本理论与相关算法,然后对物流配送路径的问题进行描述型定义、分类与建立数学模型。通过对传统的解决物流配送问题的算法进行分析与对比,了解其流程、特点与不足,针对问题和这些不足设计了一种改进的可以自适应的粒子群算法。最后(zuhu)进行了仿真实验与结果分析。本文主要采用以下研究

17、方法:(1)文献调研文献调研方法将当前物流配送路径问题和粒子群算法以及相关算法的现状和问题进行描述与分析,了解当前最新研宄动态,获取到相关的方法信息。(2)定性与定量分析所谓定性分析,是指不采用数学方法,仅采用研究者的直觉、感观、经验对研究对象进行判断,并结合以前的事实或者其他资料,对研究对象的性质、趋势、规律等作出感性判断的一种方法,最后采用文字等方式进行描述表达。所谓定量分析,是指根据研究对象的各项指标特点与数值,采用概率模型、统计模型等进行适当的数据建模,并用规范的数学语言进行描述的一种方法。通过科学的定量分析,可以从本质上了解事物的发展规律。定性分析和定量分析两种方法是相互依存的,缺一

18、不可,定量分析以定性分析作为基础,而定性分析要通过定量分析来具体化、精确化,只有将这两种研究方法结合起来使用,才能达到较好的硏究效果。本文首先将所需解决的物流配送路径问题定性化,选择相应模型和算法,并对算法进行改进和优化,同时建立所需模型,然后定量的仿真与计算。将定性与定量方法相结合,并运用其完成文章所需。(3)理论分析与实证研宄相结合理论分析是指运用粒子群理论、运筹学与计算机仿真理论对系统需求及实现进行了深入剖析。实证分析是指借助本文最后采用的对经验事实的描述通过诉诸事实来解决人们经验事实中所遇到的问题。它注重人的现实功利要求追求结果的时效性。(4)仿真实验通过在MatLab 2011a上的

19、仿真实验,验证本文设计算法的科学性与有效性。1.4本文的组织结构本文包括以下六章:第一章绪论:介绍了本文的研究背景与意义,阐述了研究物流配送路径问题的重大需求。然后论述了国内外对于物流配送问题的研究现状、算法的研究现状及其发展情况,最后给出本文的主要研宄内容和章节安排。第二章物流配送相关问题介绍和模型建立:对于物流配送问题进行了详细介绍,并且介绍了多种物流配送问题可建立的模型,并进行模型总结,同时介绍物流配送路径的基本算法和分类,以及配送区域划分算法的基本分类,同时建立多车场多车辆的物流配送模型,并加入新的约束条件。第三章物流配送问题相关算法研究:对传统的粒子群算法进行介绍,并对其特点进行分析

20、,同时列举出现有的几种针对粒子群算法的改进方法。第四章应用(yngyng)于物流配送路径(ljng)问题中的一种改进的自适应的粒子群算法设计:在前三章理论(lln)基础上,通过对问题研究所需的粒子群算法的分析以及与其他算法的对比,论证其算法的不足,并结合己有的几种优化方法和改进方式设计了一种新的改进的自适应粒子群算法。第五章MatLab仿真实验:在本文前几章的理论分析和模型建立、算法优化的基础上,根据实验数据设计了仿真实验,通过对结果进行分析比较,验证了本文算法的科学性和有效性,同时验证不同最优配送目标下物流配送的方案不同。第六章总结与展望:对本文的研究进行总结,并对未来的工作做展望和建议。具

21、体研宄思路如图1-1所示。1-1文章(wnzhng)思路图Fig. 1-1 Articles ideas roadmap2物流配送模型建立与常见(chn jin)模型分析本章(bn zhn)着重研究物流配送路径问题的模型分类,并总结建立模型的一般步骤。并根据自身对物流配送模型的理解,建立基于最短路径的多车场多车辆的物流配送模型,并加入新的约束条件。在后续工作中需要对具有不同最优配送目标的模型进行仿真,了解不同最优配送目标下物流配送路径之间的关系。2.1物流配送路径(ljng)问题相关硏究2.1.1物流配送路径问题(wnt)定义物流配送路径问题最早是由学者Dantzig和Ramser于1959年

22、首次提出的,一般可定义为:对于一系列装货点和(或)卸货点,组织合适的行车线路,使载货车辆有序地通过它们,在满足一定的约束条件(如货物的发送量、货物的需求量、运送(yn sn)货物车辆容量限制、交发货时间和运输时间限制等)下,达到一定的目标(如运输所用费用最少、运输路程最短、使用车辆数量少、运输时间少等)。2.1.2物流配送路径问题分类由于实际情况不同可以根据不同的分类标准划分成不同类型的物流配送路径问题,其分类情况如表2-1所示:表2-1物流配送路径优化问题分类Tab.3-1 Logistics and distribution routing problem classification形态

23、范围车辆种类单一车种、多种车种车辆容量限制不同车有不同的限制、所有车辆统一的限制、不限制时间限制不同路线时间限制不同、所有路线时间限制相同、无时间限制路网方向性混合性路网、有方向性路网、没有方向性路网里程限制不同车辆里程限制不同、所有车辆里程限制相同、无限制装卸作业形态混合型、卸货、装货配送中心单一的配送中心、多配送中心货物类别货物多种、货物同种需求形态需求量随机、需求量固定最优化目标服务效用最大、路线成本小、车辆数量少、变动及固定成本小2.2 物流配送路径问题数学建模种类对于物流分配模型建立有很多种模型可以使用,在物流分配中有针对时间最短确立,有根据费用最短确立,有根据路径最短确立,各自模型

24、有所差异,下面介绍几种物流分配的数学模型。在前文国内外现状部分对物流配送路径问题进行了分类,下面对分类进行描述,并选取其中有代表性的几种分类进行举例介绍。(1)最简单的物流配送路径优化问题。在一个配送中心内部由一台容量为Q的车进行配送,配送点有n个,并满足一定的条件:1)每个客户都必须被访问,且只能访问一次;2)车辆从中心车场出发,完成配送任务后必须回到中心车场;3)要用最短的物流配送路径;4)每个客户的需求必须满足。(2)基本的物流配送路径优化问题。在一个(y )配送中心内部有K辆容量为Q的车,配送点有n个,并满足一定条件:1)每个客户都必须被访问,且只能访问一次;2)车辆从中心(zhngx

25、n)车场出发,完成配送任务后必须回到中心车场;3)要用最短的物流配送路径;4)每个客户的需求必须满足。(3)根据实际设定(sh dn)约束的物流配送路径优化问题。以上都是基于数学方法理想化的物流配送问题,而实际工作中,物流配送限制因素有很多,物流问题所面临的情况也是十分复杂的,研究人员在物流配送中必须要考虑很多的约束条件,例如车辆油量限制、车辆故障,道路故障等一些突发事故都会对车辆造成影响,因此在物流配送路线设计时,考虑很多因素。1)客户对时间有限制2)车辆对于运输的距离有相应的限制3)对于客户由不确定的需求限制(4)多样性限制的物流配送路径优化问题。以上所考虑的问题都是有相同的前提条件,即车

26、辆是同种类型,有确定的优化目标,然而在实际情况下有很多因素是变化的。如车辆种类有很多,可装载的货物不同,车的容量限制也不同;配送中心有多个,即车辆从不同地方出发;还有就是整个配送有很多优化目标,这些优化目标并不是相互独立的,如距离最小、时间最短或者车辆等。目前研究中一般考虑的多样性限制的物流配送路径问题主要有:1)有多种车型的配送方式2)有多个车场的配送方式3)物流配送有多个目标(5)其他种类配送路径优化问题在实际生活中,物流需求是多种多样的,也有很多种不同的变异方式,目前的物流配送问题,日趋贴近现实生活,例如多配送中心联合的配送任务,即在同一个信息平台内,多种车辆,多个中心为同一家客户服务;

27、或者开放式的物流配送路径优化服务,即配送完成后车辆无需返回原有车场。随着科技的进步和物流技术的发展,信息共享的加剧,物流配送向更加多样化更加现代化不断的进步。2.3模型举例2.3.1基于行驶距离最短和使用车辆最少的物流配送问题基于行驶距离最短和使用车辆最少,物流配送问题可以表示成的数学模型如下:假定配送中心最多可以用K辆车对N个客户进行物流配送,其中k=1,2K,用户i=1,2N。其中i=0表示仓库,每个车辆载重为q, g为每个客户的需求,客户i到客户j的运输成本为CV优化的目标是行驶距离最短和使用车辆最少。定义变量:其数学模型如下表示: (式2-1) (式2-2) (式2-3) (式2-4)

28、 (式2-5) (式2-6)其中(2-2)控制每辆车的能力约束(yush)。(2-3)确保每个客户都被服务到。(2-4)(2-5)确保每个客户被一辆车服务。(2-6)消除子回路。2.3.2基于开放式车辆(chling)路径的物流配送问题对于开放式车辆路径的物流配送问题,可以表示为,第一阶段:先把客户分群,考虑(kol)一定的限制,将客户群个数最小化,然后根据一些规则重新分配客户,目的是最小化距离,用模型表述为,当车辆将所有客户配送完成后,并不需要返回配送中心,这样可以建立开放式车辆路径数学模型,文章给出如下模型:假定配送中心最多可以用K辆车对N个客户进行物流配送,其中k=l、2.K,用户i=l

29、、2.N。其中i=0表示仓库,每个车辆载重为q, g为每个客户的需求,客户i到客户j的运输成本为Cij,假设每辆车最后会回到虚拟的配送中心,配送中心于客户间的距离为0,即Cio。定义变量: 其数学模型如下表示: (式2-7) (式2-8) (式2-9) (式2-10) (式2-11) (式2-12)其中(2-8)控制每辆车的能力(nngl)约束。(2-9)确保每个客户都被服务到。(2-10)(2-11)确保每个客户被一辆车服务。(2-12)消除子回路。第二阶段:每个群被转化成开放式线路(xinl),用最小生成树算法来最小化线路2.3.3基于顾客(gk)满意度的物流配送问题基于客户的满意程度,物

30、流的配送问题可以表示成的数学模型如下:假定配送中心最多可以用K辆车对N个客户进行物流配送,其中k=l、2?K,用户i=1,2N。其中i=0表示仓库,每个车辆载重为q, g为每个客户的需求,客户i到客户j的运输成本为Cij。假设每辆车最后会回到虚拟的配送中心,配送中心于客户间的距离为0,客户i的时间窗是Ei, Li,到达客户i并且开始服务的时间是ti,行驶时间是, wi为所需的等待时间,Si为服务时间, 表示客户满意度,I是很大的整数。定义变量:基于顾客的满意程度可得求解目标有:第一步是最大化的平均客户满意度: (式2-13)其可以等价转化为最小化的平均客户不满意度 （式2-14)第二步是最小化

31、的车辆(chling)数: (式2-15)第三步是最小化的车辆(chling)行驶距离和等待时间: (式2-16) (式2-17)其有如下(rxi)的约束条件: i = l,2N (式2-18) (式2-19) (式2-20) (式2-21) (式2-22) (式2-23) (式2-24) (式2-25) (式2-26)以上(yshng)公式中,公式(2-18)可以保障每个客户满意程度不低于其中(qzhng)是决策者根据自身的实际经验给出相应的值,其中给每个客户的值可以相同也可以不同,其是根据客户的重要(zhngyo)程度进行划分的。公式(2-19)用来保证每辆车的承载能力。公式(2-20)用

32、来确保每个客户都被服务到。公式(2-21)(2-22)确保每个客户只被一辆车服务.公式(2-23)用来消除子回路。公式(2-24)、 (2-25)、 (2-26)用来确保客户在确定时间窗内接受服务。2.4 模型建立思路总结根据前文介绍的几种模型,总结出对于物流配送路径问题建模的大致思路首先,自定义变量。大多是&和7,对所求变量进行初始条件设置,即变量为1时则为服务到,变量为0则为未服务到。如:第二步,设定最小化目标。如最小化的费用、最小化的时间或者最小化的路径。如: 第三步,自定义满足条件。如顾客满意度、车辆分配总数或运输时间等。如: 第四步,保证每个客户都被服务到。如:第五步,保证每个客户都

33、被服务一次。有时候第四步和第五步可以合并。如: 第六步,保证消除子回路。如: 第七步,保证车辆的承载能力。如: 对于模型思路和每一种约束条件的分析与总结十分必要,利于根据实际要求建立对应的所需模型,并根据自身的要求加入相应的约束条件,改进模型,使模型更加贴合实际要求。2.5 基于最短路径的多车场多车辆配送模型建立根据前文对于(duy)模型建立的分析与总结,运用前文的方法,建立一种基于最短路径的多车场多车辆(chling)的配送(pi sn)模型,并加入新的约束条件。配送路径中多个车场多个车辆的优化问题可以描述为:某物流中心一共有M个车场,各自有Ki(K1, K2Km)台配送车辆,每辆车容量都为

34、q,向N个客户送货,用户i的货物需求为gi, (i=l,2,.N)。要求合理安排车辆配送方案,使车辆总运输成本最低,并满足以下条件:(1)每辆车运送完后必须返回原车场;(2)每个客户的需求必须满足;(3)可以由任意一个车场的车辆服务,但只能由一台配送车辆送货;(4)对车辆的服务数量进行限制。根据以上条件,设全部用户的编号分别为1,2, N;车场具有编号为N+l,N+2, N+M;定义变量 (式2-27)N:表示客户的总数目;M:表示车场的总数目;dij:表示节点i与节点j之间的距离;km:表示车场m所拥有的车辆总数;gi:表示客户i的要求;q:车场m中车辆k载重负荷。以上可以建立数学模型如下:

35、 (式2-28)公式2-28用来保证最小化的车辆行驶路径。也是整个问题的核心需求,是下步工作运用算法所需要完成的内容,即适应值。接下来就要根据实际要求对运算加以限制,列出限制公式,以便于计算,获得与实际相符的可行解。 (式2-29)条件2-29限制了从一个车场出发的车辆总数目,必须小于!。此条件用于限制计算时车辆的数量,因为一个车场所含有的车辆数是固定的,因此必须加以限制。 (式2-30)公式2-30保证了消除子回路。即不能出现路径反复,出现误差。 (式2-31) (式2-32)条件2-31和2-32保证了每个客户仅被一辆车服务一次。该公式的目的(md)是控制每个客户都被服务到,并且仅被一辆车

36、服务。 (式2-33)公式2-33表示每辆车的载重(zizhng)量不超过它的载重能力。由于每辆车的承载能力是固定的,因此必须对车辆总承载数加以(jiy)控制。同时在前文研究的基础上发现,大部分的约束条件都是从客户的角度出发,要求每个客户都被服务到,每个客户都被一辆车服务,但是如果车辆所经过的客户过多,就会对车辆的行驶里程产生一定要求,车辆行驶的距离与车辆状态、储油量和车辆使用年限等都有一系列的关系,对车辆要求很高,而车辆本身具有一定的局限性,基于以上原因,本文从车辆行驶里程考虑,对车辆服务客户数量加以限制,加入了新的约束条件,如公式2-34所示: (式2-34)对于第mk车辆,它所经历的客户

37、总数量控制在R以下,即最多为R客户服务,这样可以保证车辆的客户服务数,同时也能在一定的范围内对车辆行驶里程加以限制,确保车辆正常行驶并能将货物送达每一个客户。根据本章对物流配送路径模型定义、分类的研究,了解物流配送问题建模的内容与意义。本章中选择三种常见的模型进行分析,分别是基于行驶距离最短和使用车辆最少的物流配送模型、基于开放式车辆路径的物流配送模型和基于顾客满意度的物流配送模型,对模型进行深入研究,并总结建立模型的相关思路。根据实际情况建立了一种基于最短路径的多车场多车辆的物流配送模型,并从车辆行驶里程角度分析加入了新的约束条件,保证车辆的正常行驶,同时也保证车辆能将货物送达每一位客户。3

38、物流配送路径问题相关算法研究物流配送算法主要的解决方案分为两大类:人工智能算法和精确算法。人工智能算法包括有:扫描法、旅行商方法、分区配送算法、节约法以及一些现代优化计算方法(禁忌搜索算法、遗传算法、模拟退火算法等)。人工智能算法虽然比精确算法精度低,但在求解大规模VRP时,总可以求解,找到满意的可行解或次优解,这是精确算法无法做到的。因此,人工智能算法更广泛的运用在实际生活中。精确算法可以这样划分:直接树搜索算法、割平面法、分枝定界法、网络流算法、整数线性规划和动态规划法。总的来说,精确算需要十分严格的数学手段,所以在可以求解的情况下,其解要比人工智能算法更加优良。但由于需要严格的数学方法,

39、因而无法避开指数过多问题,所以该类算法有限制性,对于小规模的确定性VRP才能有效求解。3.1物流配送路径问题相关算法研究(1)精确算法精确算法指可求出最优解的算法,主要有分枝定界法、割平面法、网络流算法、动态规划法等。精确算法的计算量一般随着问题规模的增大而呈指数增长,所以,多用于规模较小的问题。(2)启发式算法通常情况下,通过自身发展的性质和生物系统,可以使许多复杂的问题得到令人满意的解决方案,计算机科学家从生物系统的研究(ynji)中得到的灵感,、以模仿自然的世界,获取新的方法来解决复杂的计算问题。在算法的设计过程中,设计灵感起源于或者是物理现象,或者是生物群体现象。如模拟退火算法模拟的固

40、体物质从高温度的不稳定状态的过程中向低温度稳定状态过度;遗传算法从大自然的优胜劣汰的生存现象中获得;蚁群算法模仿蚁群觅食的费洛蒙应用(yngyng),以便找到最短的觅食路径。这些智能的优化算法的出现,一方面极大地丰富了优化技术,为那些传统的优化技术无法处理的组合优化问题提供了一个实用的解决方案,另一方面,他们也从另一个角度来探讨生物世界的机制为实际运用提供新的工具和技术。虽然这些新的方法进行了优化,并且每个机制是不一样的,但它们有类似的特征。他们都是迭代算法,通过在不断的迭代计算,一步一步从质量差的解决方案,以更优质的解决方案逼近。因此,这些算法在多篇论文或其他著作被列为一类,概括起来,即启发

41、式算法一一Heuristic Algorithm。启发式算法,是一种定义在可以接受的花费(占用空间、计算时间等)下解决组合(zh)优化问题的一个可行的解决方案,这种解决方案与最佳方案水平偏差不可预知。另一种定义指定启发式算法是一种技术,使寻找最佳的解决方案在一个可接受的计算成本内,但不一定保证得到的解决方案是可行的和最优的,或者甚至在大多数情况下,得到的解决方案不能逼近最优解。在某些情况下,尤其是在实际问题,求解最优算法的过程长,计算时间的难以承受,或因为问题的难度使计算时间的增加,如TSP问题,这个问题只能通过启发式算法获得一种可行的解决方案。(3)现代优化算法现代优化算法一般从初始解开始,

42、通过对当前解不断进行局部扰动以达到较好的解。常见的算法除了本文研究的粒子群算法外,还有模拟退火算法、禁忌搜索算法、遗传算法等。3.2常见现代优化算法分析与对比下面详细介绍几种现代优化算法,包括蚁群算法、遗传算法、粒子群算法和局部搜索算法,分析几种算法的优点和缺点,并针对所需求解问题,选择优势较明显的算法解决问题,同时针对所用算法的缺陷与不足,展幵后续工作。3.2.1算法举例(1)蚁群算法蚁群算法于20世纪90年代由意大利学者Dorigo.M等首先提出的,是一种用于解决复杂优化,基于种群的模拟进化的全新启发式算法。蚁群算法由许多蚂蚁共同完成,每只蚂蚁在候选解的空间中独立地搜索,然后在所得的解上做

43、好标记,蚂蚁倾向于朝着标记多的方向移动。本质上仍是一种随机搜索算法,它寻求最优解是通过对候选解组成的群体的进化。因此,由大量蚂蚁组成的蚁群的集体行为便表现出来一种信息正反馈现象:一条路上蚂蚁经过的多了,其他蚂蚁就会逐渐向这条路靠拢,最后形成收敛。1)蚁群算法的优点蚁群算法在搜索过程中不需要人工干预,并具有正反馈、并行性、健壮性等特点,显著用于解决小规模(n30)的旅行商问题。2)蚁群算法的缺点但在初期的道路上,由于各种激素水平基本相等,蚂蚁的搜索呈现出较大的盲目性,使解决较大规模旅行商问题性能迅速恶化,激素水平会呈现明显的指导需要长时间的时间要求。此外,由于蚁群算法是一种正反馈算法,算法虽然收

44、敛快,但是容易陷入局部最优。此外,蚁群算法中许多参数的设定都是基于经验的,没有充足的证据,蚂蚁数量往往依靠实验设置调整。因此,在运用算法时,需要先实验,然后根据实验结果调整参数,进行搜索才能应用蚁群算法求解旅行商问题。3)蚁群算法(sun f)在TSP中的应用算法(sun f)如下:步骤:初始化各个(gg)点)之间的长度,即随机赋予所有边一个外激素水平初始值;步骤:将蚂蚁放入其中;步骤:各个蚂蚁根据外激素水平和相应距离选择下一个走向;步骤:所有蚂蚁完成搜索后更新外激素水平:蚂蚁经过次数多的边,增加其外激素水平(分泌外激素);蚂蚁经过少的边减少外激素水平(挥发性);然后判断是否产生新的最优路线,

45、如产生，则记录到全局变量中;步骤:循环步骤,直至满足条件退出。(2)遗传算法遗传算法是建立在孟德尔的遗传学说和达尔文的生物进化论基础上的算法,是一种模拟遗传机制和自然选择的寻优方法,它是在60年代中期由美国密执安大学HollandJ.H首先提出,随后的工作由他和他的一批学生共同研究发展起来的。进化论中描述,每一个物种都是在不断的开发过程中越来越适应环境,物种的个体的后代将继承物种的基本特征,但未来的世代,并且不完全等同于父代,这些新变化如果适应环境,就会保留下来;否则,淘汰。在遗传学中,遗传基因作为基因代码指令蕴藏在每个细胞中,并以染色体的形态存在,生物的特征由基因所控制。产生出来的个体对环境

46、有一定的适应能力,基因突变和基因杂交可能产生对环境适应性强的后代。最后通过自然选择,优胜劣汰保存适应值高的基因结构。遗传算法就是引用了随机统计原理而形成的,并模拟了进化原理和生物的遗传。在求解过程中,遗传算法在最初给粒子赋予一个初始变量,然后逐代地寻找问题的最优解,直到预先假定的迭代次数或满足收敛判据为止,它是一种迭代式算法。1)遗传算法的优点算法重点搜索性能较高的部分,同时进行全空间并行搜索,目的是够提高效率。算法具有全局寻优能力强的特点,搜索不是从一个单一的个体开始,而是从一组解开始,且将并行搜索功能蕴藏其中,从而将陷入局部极小的可能性降低。算法具有内在平行性,可以通过遗传处理大量的模式,

47、并易于并行实现。2)遗传算法缺点遗传算法在搜索过程不断进化,每一代保持一定的群体规模。如果规模小,包含信息也会比较少,不能充分发挥遗传算法的功能;如果规模大,它包含的信息量大,会急剧的增加计算次数,对遗传算法的使用有一定的限制。该算法能够存在的早熟现象,有多种原因造成这一现象,其原因如下:交叉算子使群体中的染色体局部相似,遗传时染色体交换的信息量变小,使搜索停滞不前;此外,如果基因突变率太小,会导致搜索不能转向其他的解空间进行。3)遗传算法应用编码目前多采用以遍历于城市的次序排列进行编码,在求解TSP问题的各种遗传算法中,如串25413是指从城市2开始,逐次经过城市5, 4, 1, 3,最后返

48、回城市2的过程路径,这是一种自然的编码方法,但是其有自身的缺陷,缺陷是引入交叉操作困难。选择对当前群体中成员进行选择,选择优良的个体,他们有机会(j hu)繁殖下一代,被选择机会的大小由个体适应度的大小决定。变异(biny)策略在TSP运用中,交叉功能是遗传算法主要强调的功能,从进化的角度遗传算法,它是一种解决问题的进化方法,主要以交叉策略和选择机制来完成,变异的选择和交叉只是(zhsh)一些维修和补充。遗传算法有几种不同的变异操作,如移位变化、插入变异、交换变异、目标导向的变异。交叉策略它是遗传算法中最主要的操作,由两步进行,首先随机的对群体中的个体进行配对;然后随机设定交叉处在配对个体中,

49、使配对个体彼此交换部分信息。交叉的方法有多种,如单点交叉映射法、PMX法、类0X法、单点顺序交叉法等。适应度函数取路径长度Td的倒数为适应度函数常,即戶1 I Td。(3)粒子群算法概述粒子群算法,也被称为粒子群优化算法,简称为粒子群优化算法,与遗传算法相同,都是从随机模型的最优解的迭代开始,它是通过适应度来评价的解决方案,但它更简单的规则比遗传算法更加有利于实际应用,它没有遗传算法的交叉、变异操作,它通过遵循当前搜索到的最优值来寻找全局最优。粒子群优化算法属于一个的进化的算法,是近年来发展起来的一种新的算法。该算法具有精度高、易于实现和收敛快的优点,在学术界显示出解决实际问题的优越性1)粒子

50、群算法优点算法原理简单,容易实现;粒子间协同搜索,搜索策略是由群体全局信息和个体局部信息进行指导;算法不依赖于问题信息,通用性比较强;粒子群算法具有群体搜索和记忆的能力,能使种群和个体的最优信息得到保留。2)粒子群算法缺点算法容易陷入局部最优,局部搜索能力比较差,且其搜索精度也不够高;算法搜索性能对参数的依赖性较强;算法理论还不完善,特别是在算法具体应用时算法的设计缺少实用性指导原则。算法并不能保证一定得到全局最优解,容易陷入局部极小解;(4)局部搜索算法局部搜索又称邻域搜索,它是一种迭代搜索技术在复杂函数优化的过程中经常采用,其基本原则是在当前的解决方案所形成的邻域解中不断迭代和优化设计的目

51、标函数,使之逐渐成为更好解,直到在邻近的领域内找不到比当前更好地解决方案为止。从最初的解决方案起,基于群体功能在当前解前提下,继续搜索比它好解,如果能找到一个这样的解决方案,则使它成为新解决方案,然后重复这个过程,如果没有更好的终止搜索过程,当前的解决方案为最终解决方案。邻域搜索算法主要包括确定局部搜索方式和设计邻域函数。函数优化中有比较直观的邻域函数概念,最常用的方式是利用距离的概念通过附加扰动来确定邻域函数。邻域函数的设计往往依赖于解的表达方式和问题的特性。对于邻域函数的具体表现方式,组合优化和函数优化存在着明显的差异。该算法的主要优点是速度比较快、容易改进、相应的算法程序简单、容易实现、

52、算法直观。该算法的缺点:算法的搜索性能完全依赖于初始解和邻域函数,如果初始值选取不合适或者是设计不当,则算法将会有非常差的最终性能;在搜索过程中可能出现早熟,即可能会出现陷入局部极小的情况。3.2.2算法比较对于前文介绍(jisho)的各种算法的优缺点,下面进行汇总,如表3-1所示。Tab 3-1 Algorithm contrast table操作难易搜索速度搜索性能搜索规模局部极小算法特点搜索特点存在早熟备注遗传算法中等慢好较小低交叉,变异内在平行性是算法基于遗传和变异产生粒子群算法简单快好中等 高适应度协同搜索算法有记忆性否算法理论不完善局部搜索算法简单快低小中初始解和临域函数现搜索性能

53、依赖初始解和邻域函数是算法容易操作程序间单,容易改进蚁群算法中等 快好小高外激素水平行正反馈并行性健壮性是算法不需要人工干预,用于解决小性规模旅行商问题如上表所示,粒子群算法具有操作简单、搜索速度快、搜索规模适中的优点,可以用于解决物流配送路径问题,但是粒子群算法有自身的缺点,算法容易早熟,且理论缺少完善性,所以针对这一特点,文章选择粒子群算法进行(jnxng)物流配送路径问题研究,并将算法进行改进,以避免早熟收敛的情况(qngkung)发生。3.3 传统粒子群算法局限性分析3.3.1 经典PSO算法粒子群算法(PSO)是一种基于群体理论的智能优化算法(J.Kennedy andR.C.Ebe

54、rhart, 1995),它将每个粒子都当成无体积的,在一定的搜索空间内以不确定速度飞行,并且其速度是根据自身的历史经验和同伴的经验进行实时调整的。基本原理为:设Xi= (Xii,Xi2, , Xin)为粒子i的当前位置,Vi=(Vi,Vi2,Vin)为粒子i的当前飞行速度,Pi=(Pi1,Pi2,Pin),为粒子i所经历的最佳位置,也就是粒子i所经历过的具有最好适应值的位置,称为个体在时间k获得的最好位置。对于最小化问题,目标函数值越小,对应的适应值越好。整个粒子群搜索到的最佳位置表示为Pg= (Pgl,Pg2,Pg3,Pgn),意义为整个粒子群到时间k位置搜索到的最佳位置。其中每个粒子新的

55、速度按式3-1进行更新： (式3-1)C1和C2:加速度系数,( 是惯性权重系数,一般取2,可以控制当前粒子速度受之前速度影响的大小。R1和r2为随机数值,一般取值0到1之间。根据公式3-2,可计算出每个粒子更新位置。 (式3-2)通常为了避免在进化过程中粒子飞出搜索空间,公式3-2中的取范围内的数,粒子以公式3-1飞向新位置,并循环此过程直至用户定义的迭代条件不满足。3.3.2传统算法的流程在解决物流路径问题时,传统的算法的流程如下:Step 1:随机初始化每个粒子的速度和位置,如果运用d维的搜索空间,那么每个粒子包含d个变量。Step 2:对评价种群中所有粒子,并将各粒子的目标和位置存于各

56、粒子的中, =所有中的个体具有最优目标值的位置和目标。Step 3:按算法(sun f)原理中的公式将粒子的位置及速度进行更新。Step 4:对种群(zhn qn)中的所有粒子进行评价。Step5:将各个(gg)粒子的与当前目标值比较,从而更新粒子的。.Step 6:比较当前所有和更新。Step 7:若满足终止准则(通常为达到一个预设最大迭代次数或足够好的适应值),则输出gbest及其目标值并停止算法,否则转向Step 3。 28算法流程图如图3-1所示:Fig.3-1 The traditional particle swarm optimization algorithm flowchar

57、t to solve the problemsof logistics and distribution path3.3.3算法具体描述粒子群算法就是模拟一群鸟类寻食的过程,每个粒子都可以看做是一只鸟,也是求解问题的一种可行解,它们在寻找食物过程中不断的更新自己的位置,用图可以这样表示。根据自身理解,将这个过程转化为一个数学问题。令函数为,在0,4最大值。此函数图形如图3-2所示。图3-2曲线图Fig. 3-2 Diagram of curves当x=0.9350-0.9450,函数达到最大值y=1.3706。为了得到该函数的最大值,随机在0, 4之间分布点,算法(sun f)的具体实现过程,

58、如图3-3至图3-7所示(1)初始化图3-3初始(ch sh)图Fig.3-3 The initial diagram(2)第一次位置(wi zhi)更新 图3-4第一次更新(gngxn)图Fig.3-4 The first updated map(3)第二次位置(wi zhi)更新图3-5第二次更新(gngxn)图Fig. 3-5 The second updated map(4)第21次更新(gngxn)图3-6第二十一次更新图Fig.3-6 The twenty-first updated map(4) 30次迭代(di di)结果图3-7第三十次迭代(di di)结果Fig.3-7 T

59、he thirtieth iteration result整个算法的最后(zuhu)在最大值的地方,粒子集中。以上就是算法的过程描述。3.3.4粒子群算法特点分析在解决物流配送路径问题时,传统算法的局部改良能力和全局探索能力的平衡很大程度上决定了算法的搜索性能,这种平衡在控制参数上有很大程度上依赖性(包括最大代数、种群规模、惯性权因子、最大速度和加速常数等)。传统算法与其他进化算法相比,他们需要调整的参数相对较少。总而言之,粒子群算法是一种随机,平行的优化算法,它不需要被优化的函数连续、可微可导。它还具有算法简单、快速收敛和易于编程实现的优势。短短几年,粒子群算法己经有了很大的发展,并己在某些

60、领域的应用。但粒子群算法有其自身的缺点:容易下降到局部极值点,无法获得最佳解决方案,当粒子在参数选择的多样性不当,会导致优化过程迅速消失,导致算法早熟收敛。因此,研宄人员已经提出的各项改善措施。从基本的粒子群算法己开发许多不同的改进算法。下面对改进的粒子群优化的简要介绍。3.4已有粒子群算法的改进方法(1)标准算法将惯性权重引入算法,目的是为了更好的控制算法的开发能力和搜索改善基本粒子群算法的收敛性等方面,引入惯性权重在速度进化方程中,可得出以下公式:通常标准粒子群算法是将上面的式子与传统的粒子群算法进行结合(jih)组成。在正常情况下,本文谈论的粒子群优化算法是指标准的粒子群算法。显然,惯性