物流企业配送路线优化模型与方法研究综述.docx

《物流企业配送路线优化模型与方法研究综述.docx》由会员分享，可在线阅读，更多相关《物流企业配送路线优化模型与方法研究综述.docx（17页珍藏版）》请在优知文库上搜索。

1、物流企业配送路线优化模型与方法研究综述物流业已经成为国民经济的重要产业，在社会经济发展中起着越来越重要的作用，配送是物流中的重要环节，配送路线的选择直接影响配送成本，进而影响了物流成本。物流配送路线优化研究，是配送系统优化中的重要一环。通过配送路线优化，可以提高企业的运作效率，降低配送成本，实现物流科学化。自从配送路径优化问题被提出以来，国内外的专家学者对其开展了广泛的研究。目前己经产生出多种成熟的模型和算法，为后人继续研究提供了基础。关键词:配送，路线优化Areviewofresearchonoptimizationmodelsandmethodsfordistributionroutesi

2、nlogisticsenterprises1.ongFangLeiSchlofBusiness,BeiFangUniversityofNationalitiesyYinchiian75002l,ChinaABSTRACTThelogisticsindustryhasbecomeanimportantindustryinthenationaleconomy,playinganincreasinglyimportantroleinsocialandeconomicdevelopment.Distributionisanimportantlinkinlogistics,andtheselection

3、ofdistributionroutesdirectlyaffectsdistributioncosts,whichinturnaffectslogisticscosts.Thestudyoflogisticsdistributionrouteoptimizationisanimportantpartofdistributionsystemoptimization.Byoptimizingdeliveryroutes,enterprisescanimprovetheiroperationalefficiency,reducedeliverycosts,andachievescientificl

4、ogistics.Sincetheoptimizationproblemofdistributionrouteswasproposed,expertsandscholarsathomeandabroadhaveconductedextensiveresearchonit.Atpresent,variousmaturemodelsandalgorithmshavebeendeveloped,providingafoundationforfutureresearch.Keywords:Delivery,Routeoptimization绪论1.1 研究背景及意义2011年我国社会物流总费用为8.4

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

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

7、和企业具有重要意义。对于企业，配送路线的优化，可以简化配送程序、提高配送效率，充分利用配送车辆运力、降低空载率、减少配送次数、尽量使配送成本降低；同时优化配送路线可以加快企业对客户需求的响应速度，准时、快速的把物品送达客户，提高客户满意程度。对于社会，配送路线优化可以节省作业车辆，进而缓解交通拥堵状况，减少噪声、尾气的排放，为保护生态环境做出贡献。所以研究物流企业配送路线优化模型及方法具有重要的现实意义。1.2 国内外研究现状关于配送路线优化问题的研究经过了50多年的发展，衍生出了许多模型，根据模型被研究次数的多少以及模型中包含约束条件的多少，大致可分为：基本类型和衍生类型。1.2.1 基本类

8、型影响配送车辆路线选择的因素有很多，由此产生了很多种问题模型。根据以往文献资料，将被研究次数较多的问题模型提取出来，参照问题中考虑的约束条件的不同，问题的模型分为以下几种基本类型。（1）带能力约束的车辆路线优化模型该模型是车辆路线优化问题的基本模型，它考虑的约束条件少，一般只考虑了车辆的载重和行驶时间（或距离）方面的约束。该模型被研究的时间最长，取得的研究成果最多。（2）带时间窗约束的车辆路线优化模型该模型是在带能力约束模型的基础上添加了时间窗约束，时间窗约束的添加使得该模型更贴近现实情况，同时也增加了求解的难度。此模型是当前被研究次数最多的模型，针对该模型大量的优化算法被提出。时间窗分为：软

9、时间窗（当不满足时间窗约束时，接受惩罚），硬时间窗（当不满足时间窗约束时，解不可行）。（3）带取送货的车辆路线优化模型带取送货的车辆路线问题，一般有以下两种情况：第一种是客户点既收取货物，又返还货物，返还的货物要运回配送中心，这种情况典型的配送案例为：啤酒、饮料企业送货的同时回收空瓶。第二种是车辆将货物从客户点取走，送到相应的收货客户点，这种情况典型的案例为：邮包快递的收送口3。(4)周期性的车辆路线优化模型周期性车辆路线问题是在扩展车辆路线问题的基础上形成的，一般配送路线问题研究的是车辆单次配送任务的路线选取策略，而周期性的车辆路线问题研究的是车辆一个周期内多次配送任务路线的选择策略。这类问

10、题中，客户点在一个周期内可以被多次服务。典型的案例为：牛奶收购，成品油配送等45。(5)分散车辆配送路线优化模型分散车辆配送路线问题相对一般车辆配送路线问题的不同点在于客户点可以被两台或两台以上车辆服务，此问题是Dror和Trudeau在1989年提出的671。(6)带回程取货的车辆路线优化模型该模型是带取送货的车辆路线问题模型的一种特例。该模型中，车辆在配送时，首先为客户点送货，然后从有货物需要返还的客户点取货。该问题需要充分考虑车辆容积限制。1.2.2 衍生类型在上述基本模型的基础上，针对不同的实际情况，添加不同的约束条件，从而形成了许多车辆路线优化问题的衍生模型。这里只对当前研究次数较多

11、的一些模型做简要介绍，具体如下。(1)多车场的车辆路线优化问题模型实际配送作业中，采用多车场配送能有效提高配送作业调度的效率，求解多车场配送路线问题比求解单车场配送路线问题更为复杂，一般情况下，在其求解过程中大多先要按照某种规则，将客户点分配给某个车场，然后按照单车场配送路线问题进行求解89o(2)多车型车辆路线优化问题模型实际配送作业中，采用多车型配送能更好地提高配送车辆利用率，对于这种情况，Golden(1982)对多车型车辆路线问题进行了的研究。模型中各车型的车辆数确定或者不确定，每种车型的使用费用不同，模型的优化目标是使运输总成本最小、车辆最少10.(3)随机车辆路线问题目前随机车辆路

12、线问题主要研究内容集中在随机需求、随机客户及随机时间三方面。随机需求的车辆路线问题，虽然知道确定的客户，但无法知道客户确切需求量。随机顾客和需求的车辆路径问题是将随机需求车辆路线问题和随机客户车辆路线问题结合起来形成的问题。它是一个难度非常大的问题，其目标函数值的计算是十分困难的。目前.，对于随机时间的车辆路线问题的研究并不是很多，当前的研究手段正趋向于引入随机网络的最短路径问题研究成果来求解随机时间的车辆路线问题1512。(4)模糊车辆路线优化问题模型在现实的配送车辆调度过程中，某些等待服务的客户点的信息不确定，这就需要在问题的模型中引入模糊概念来解决这类问题。模糊概念的引入方式有两种，一种

13、是路线优化问题中模糊信息的处理，如客户点的需求模糊、距离模糊1314o另一种是将模糊概念引入时间窗约束，即客户点要求服务的时间窗在一定范围内是一个模糊量，车辆在时间窗内到达是可行的，但由于到达时间的不同，客户的满意度也会不同。这类问题模型是多目标寻优模型。(5)动态车辆路线问题动态车辆路线优化问题是指：在车辆调度指令执行前，调度者对所有与路线优化有关信息并不一定完全掌握，这些信息随时有可能发生改变，在路线优化过程中，需要根据新出现的信息或者现有信息的变动及时调整调度结果。动态车辆调度概念是PSarafliS在20世纪80年代首先提出的15,随着定位导航技术、计算机网络、数据通信技术与信息处理技

14、术的发展，动态车辆路线问题越来越受到研究者们的关注。广义上讲，各种随机的、模糊的车辆路线优化问题都属于动态车辆路线优化问题。(6)开放式车辆路线优化问题现实生活中，很多配送企业为节约成本,所用配送车辆并不完全是自有车辆，其中一部分是租用车辆，它们与个体司机签订合同，通过合作的方式来完成本企业的配送任务，该方式不要求车辆返回配送中心，可以很好的整合社会资源，这类问题被称为开放式车辆路线优化问题。它与基本的车辆路线优化问题模型的主要区别在于，不要求完成配送作业的车辆返回配送中心，因此车辆路线是开放式的，不是闭合的16o二、配送路线优化问题的基本理论2.1配送路线优化问题的描述采用科学的、合理的方法

15、来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径。在满足客户配送需求的前提下,如何选择配送路线,是一项很重要的工作。配送作业的时效性和高效性主要受车辆路线的安排与调度方案优化情况的影响。配送路线优化问题由来已久，其可以描述如下，见图2.Io有一个（或者多个）配送中心，共有配送车辆K辆（一种或者多种车型）车辆载重量为2，0，“，Qk。共有/位客户等待被服务，每位客户都有各自需求量Gi,G2,G/。从配送中心出发的配送车辆对等待服务的客户进行配送，以满足客户的要求（物品品种、数量、规格的要求，配送时间的要求）最后返回配送中心。要求所有客户都被服务到，同时配送车辆不能超载。最终

16、求出车辆配送路线方案，并达到一定的优化目标（如路程最短、费用最少、时间尽量少等）客户点Q酉电中心图2.1酉叫路线优化问题原理图车辆路线优化问题是NP难题。自从它被提出以来，由于其应用的广泛性和在经济上的价值，一直受到国内外学者的广泛关注。酉选路线优化问题的主要构成要素为：配送车辆、货物、客户、配送中心、路网。各要素具体说明如下。（1）车辆，其主要属性有：车辆类型、装载量、最大行驶距离、配送开始前与完成后所在的配送中心。（2）货物，其主要属性有：重量、送达时间和送达地点等。货物能否装在同一配送车辆上取决于货物属性。（3）客户，其主要属性有：需求（或供应）货物的种类、接受服务的时间等。（4）配送中心，其主要是用来进行集货、分货、配货、送货等物流作业，在不同的路线优化问题中，配送中心的个数为