交通运输-太原市金虎便利店配送线路设计与优化 31页

太原市金虎便利店配送线路设计与优化[摘要]配送线路的设计与优化，是近几年来在物流业内比较关注的一个重点问题。配送线路的选择，不仅是连锁企业日常经营活动的一个重要组成部分，并且对连锁企业的营运成本有着重大的影响。一套合理的的配送方案可以为连锁企业节约成本，降低商品售价，从而提高企业的整体竞争力。因此，配送线路的选择与设计应该合理、有序并且符合实际需求。而连锁便利超市作为一种店面深入大街小巷连锁零售业的典型，配送中心对各店面配送路线的选择就显得尤为重要。本文以太原市金虎便利连锁超市配送线路的优化为例，详细介绍线路优化中经常使用到的节约算法，扫描算法及分支交换探索法，并且分别应用以上提及的计算方法对金虎便利店中一组较有代表性的需求数据进行配送线路的设计与优化。通过对公司配送问题的总结分析以及对优化过程中使用方法的总结，为金虎便利在配送方案的设计上提供一些参考。[关键词]车辆路径问题节约算法扫描算法分支交换探索法27 VehicleRoutingDesignForJinhuConvenienceStoreAbstract:Vehicleroutingdesignandoptimizationofthelogisticsindustryinrecentyearsakeyissueofconcern.Vehicleroutingchoice,notonlyisthechain"sdailyoperationsisanimportantpart,andtherightchainoftheoperatingcostshaveamajorimpact.Areasonabledistributionprogramforchaincostsavings,lowercommodityprices,therebyenhancingtheoverallcompetitivenessofenterprises.Therefore,thechoiceanddesignofVehicleRoutingshouldbereasonable,orderlyandinlinewithactualdemand.Theconveniencestorechainasachainofretailstoresin-depthtypicalstreets,thestoredeliverydistributioncentersonthechoiceofroutesisparticularlyimportant.Inthispaper,wegettheJinhuConvenienceStoreintaiyuanasanexample,Introductionthemethodlikethesavingsheuristicalgorithm,scanningalgorithmandtheBranchexchangeheuristics,andMentionedabovewereappliedthecalculationoftheJinhuconveniencestoreasetofmorerepresentativedatadistributionneedsofcircuitdesignandoptimization.Distributionthroughthecompanyanalyzedtheproblemandtheoptimizationprocessusingthemethodofintroduction,fortheJinhufacilitatedistributionprogramdesignedtoprovidesomereference.Keyword:vehiclerouting;savingalgorithm;sweepalgorithm;branchexchangeheuristics27 目录引言1第1章金虎便利线路优化的可行性与必要性分析21.1便利店概述21.1.1便利店概念21.1.2便利店的产品策略21.1.3便利店的分销渠道31.2金虎便利公司简介31.3金虎便利实行线路优化的可行性分析41.4金虎便利进行线路优化的必要性分析4第2章车辆路径优化的研究现状及方法介绍52.1车辆路径问题的分类52.2车辆路径问题的研究现状52.3线路优化的方法介绍72.2.1节约算法72.2.2扫描算法82.2.3分支交换探索法8第3章金虎便利线路优化的建模及计算103.1金虎便利的店面分布及需求量统计103.1.1金虎便利的店面布局103.1.2金虎便利店面的货物需求103.1.3金虎便利运输车辆车型及装卸货物的方法113.2金虎便利线路优化的VRP数学模型123.3节约算法配送线路设计133.4扫描算法的配送线路设计163.5分支交换探索法对扫描算法求解方案的局部优化193.6结论22结束语2527 致谢语26参考文献2727 引言随着经济的发展，我国人均消费水平和物质生活水平不断提高。人们对商品的需求数量逐渐增多，对商品种类的需求也日趋多元化。在市场需求的带动下，一批本土的大型超市迅速崛起。另外在世界经济一体化的大环境下，沃尔玛、家乐福等世界知名的大型零售商纷纷进入中国市场，使得在中国市场上，大型超市间的竞争日趋激烈。在大型超市在中国市场上激烈角逐的同时，另一种经营模式的超市也悄然兴起并且迅速在市场上占有了一席之地，这种新的经营模式就是便利商店的连锁化。这种连锁经营的便利超市利用了大型超市留下市场空白，深入居民区和公司企业集中的区域，为没有时间去大型超市的人群提供服务。每一个连锁经营的超市都拥有数量庞大的店面，这些店面广泛的分布于城市的大街小巷，一般面积不大，店内店员数量也有限，商品的补充均由连锁超市的配送中心提供。这样公司会在配送中心向店面进行配送的过程中投入大量的运输费用，在这一配送过程中，配送方案的选择直接影响到了运输费用的支出。而运输费用又被加入了商品成本之中，影响到了超市的商品价格，决定了超市的竞争能力。所以选定一个合理的配送方案对与连锁便利店具有巨大的价值，优化已有的配送线路也成为超市降低成本提高竞争力的一个重要手段。本文针对太原市金虎便利运输费用偏高，配送线路不够合理的问题，根据对实际数据的分析，并提供几种常用的线路优化方法，供金虎便利公司进行参考。希望能帮助公司降低该连锁超市在配送运输过程中的的产生消耗，降低运输成本，增加公司利润，加强公司竞争力。为了能给金虎便利公司一个较为全面并且有一定价值的参考价值的建议。本文一共介绍并且使用了三种方法对金虎便利公司的配送线路做了优化，并且将三种方法的优缺点做了总结与比较，以便公司在今后的配送活动中能够根据自己的实际情况选择一个合适的方法对配送线路做出优化。27 第1章金虎便利线路优化的可行性与必要性分析1.1便利店概述1.1.1便利店概念　　便利店，英文简称CVS（ConvenienceStore）是一种用以满足顾客应急性、便利性需求的零售业态。该业态最早起源于美国，继而衍生出两个分支，即传统型便利店与加油站型便利店，前者在日本、中国台湾等亚洲诸国得以发展成熟，后者则在欧美地区较为盛行[1]。　　便利店的兴起缘于超市的大型化与郊外化，超市的变化体现在距离、时间、商品、服务等诸多方面：如远离购物者的居住区，需驾车前往；卖场面积巨大，品种繁多的商品消耗了购物者大量的时间和精力；结账时还要忍受“大排长龙”等候之苦，以上种种使得那些想购买少量商品或满足即刻所需的购物者深感不便。于是人们需要一种能够满足便利店购买需求的小超市来填补空白。　　　　1.1.2便利店的产品策略　　1.提高门店的商品陈列利用率商品的选择和陈列是一门学问,如果做得好会给消费者带来便利,并有极佳的促销作用。在产品策略方面,便利店的经营者应避免某些货物成列面积过大而另一些物品因为缺乏空间无法上架。(2)正确进行商品类型的选择便利店的主打商品应在速冻食品、饮料及日常用品上,这些商品不求多、全,而应求精,即选择畅销的、质量高的、价格又适中的产品上架。在便利店中应避免出现整扎销售或者大包装的产品,既然便利店的定位是为应急的需求,量贩包装的商品是不属于便利店的销售范围。(3)避免货架存在大面积空位27 货架大面积空位是门店的暂时性缺货或者其他问题,但是这种现象反映出的结果无非是:配送中心配送货物不及时,采购部商品采购的品种不足,理货人员补货不及时。这三种问题造成的这一后果必然影响门店销售和形象。一个货架空空的门店会给顾客留下较差的印象，不仅仅是顾客此次购物无功而返,还可能使企业损失一批固定客户。1.1.3便利店的分销渠道　　(1)建立网络配送系统,统一配送　　鉴于目前国内便利店多数已有配送中心这一事实,现在重要的问题就是怎样提高配送中心的工作效率,尽量采取在特定区域高密度集中开店的策略。要充分发挥自设配送中心的优势,建立电脑网络配送系统,统一集货、统一配送,特别要发挥配送中心分别与供应商及各家店铺相连的电脑网络作用。为了保证不断货,配送中心一般应根据以往的经验保留3天左右的库存。同时,中心的电脑系统每天都会定期收到各个店铺发来的库存报告和要货报告,配送中心把这些报告集中分析,最后形成一张张向不同供应商发出的定单,由电脑网络传给供应商,而供应商则会在预定时间之内向中心派送货物。配送中心在收到所有货物后,对各个店铺所需要的货物分别打包,等待发送。　　(2)提高商品周转率,减少库存由于门店面积小,又因地理位置多处于繁华地段,高额的房租不允许门店有大量的库存。货架商品的库存量应严格控制在最大库存量以内,这就要求配送中心将配送商品配准、配全,从而保证便利店的商品常进、常新,以减少库存,提高商品的周转率。为了完成门店商品的快速周转,对于配送商品的时效,包装应当仔细检查,以减少不必要的库存。通常将商品的库存定为3天左右,而对于像冰激凌、速冻食品类商品,供应商每天早晨直接送货到各个门店。1.2金虎便利公司简介27 太原市金虎超市配送有限公司（金虎便利）成立于2001年5月18日，在职员工近1000人。公司总部位于太原市五龙口街549号，其中包括总部面积约2000平方米，各便利店营业面积约20000平方米。公司充分发挥"人本主义"的优势，总结并借鉴国内外的先进管理技术与管理经验，形成了金虎独特的管理模式。目前，公司正以每年递增6-8家加盟连锁店的速度发展壮大，已成为太原市连锁超市的龙头企业[2]。1.3金虎便利实行线路优化的可行性分析金虎便利的全称为太原市金虎超市配送有限公司，在公司创建伊始就组建了自主经营管理的运输车队，在2003年又通过购买工厂旧厂房进行改建的方式在太原市郝庄建立了自有的配送中心。经过近十年的发展，金虎便利已经拥有了一套自主运营的物流配送团队和的配送管理系统。这使得公司可以及时方便的收集到配送线路优化所需的数据。另外，公司已经拥有了一个较为成熟的物流管理团队和一套自主经营的物流系统，使得在物流管理上做出调整和优化的决策可以有效的施行。1.4金虎便利进行线路优化的必要性分析金虎便利作为太原市最大的连锁便利店之一，拥有庞大的销售网点，其网点深入大街小巷，是一家传统模式的便利连锁店。其销售策略和分销渠道基本采用了前文介绍过的便利店模式，即销售品种少，但多为畅销产品。配送网络自有并且统一配送，同时为减少库存提高店面的空间利用率，采取两天配送一次的配送频率。在这样一种销售策略和分销渠道下，配送中心因配送而产生的费用很自然的就被加入到商品的成本当中，然而目前金虎便利的配送环节仍存在一些问题，使得配送成本偏高，这些成本被算入商品成本后使得商品成本较高，为了保证销售利润金虎便利每件商品定价比大型超市贵出0.5元，比一般的非连锁型店便利店也贵出0.2元左右。这样的价格劣势直接限制了金虎便利竞争能力。如何降低物流成本便成为了金虎便利必须解决的一个问题，配送线路的优化是降低运输费用的一个主要手段。本文就从线路优化这一方面给金虎便利提供一些建议。27 第2章车辆路径优化的研究现状及方法介绍2.1车辆路径问题的分类VRP问题可根据不同的性质具体分为以下几类：1.按照运输任务分为纯装问题，纯卸问题，装卸混合问题。2.按车辆装载货物状况分为满载和非满载问题。3.按车型分可分为单车型问题和多车型问题。4.按车辆是否返回配送中心车场分为车辆开放问题和车辆闭合问题。5.按优化目标分可分为单目标优化问题和多目标优化问题。6.按有无时间要求可分为有时间窗VRP问题和无时间窗VRP问题。本文所要解决的问题是一个纯卸问题，同时是一个不带时间窗、单车型、车辆封闭的VRP问题。2.2车辆路径问题的研究现状车辆路径问题（VehicleRoutingProblem，VRP）是运筹学与物流管理决策的一个重要问题，国内外相关领域对VRP问题的研究始于20世纪50年代，在理论研究和实际应用两个方面都已经取得了非常显著的成果。随着研究的加深研究的重点也逐渐转移到了如何开发更加贴近现实情况的理论和计算模型。车辆路径问题简单可以定义为：从配送中心用多辆车向多个需求点供货，每个需求点的需求量和位置一定，每辆车的的载重辆一定，通过合理安排车辆路径，达到一定目的(如路程最短、费用最小、时间最少、使用的车辆尽量少等)[3]。大多数的物流配送运输调度问题可以归结为配送车辆的分配、行车路线的组织问题，即根据一定的要求——目标函数(例如运距最短、配送时间最短、运输费用最少等)，将配送运输过程归结为表述问题的数学模型，然后用计算机求得合理可行的优化方案，在生产中付诸实施。车辆路径问题是组合优化领域中著名的难题。近二十年来，无论在国内外，VRP问27 题都是一个非常活跃的研究领域。日前用于解决该问题的现代数学方法主要分为以下几类:1.精确优化方法。包括制定下界及相关分枝定界算法、K度中心树及相关算法、动态规划、集合划分和列产生法、二索引车辆流方式、止索引车辆流方式等。但精确算法的计算复杂度很高，随着运输系统的复杂化和对调度的多目标要求，获得整个系统的精确优化解越来越困难，花费的时间和费用太大，因此精确解法不能应用于规模较大的物流配送车路径问题的求解，仅用于运输调度的局部优化问题。2.启发式方法(Heuristics)。指通过经验法则来求取运输过程满意解的数学方法。启发式方法能同时满足详细描绘问题和求解的需要，较精确优化方法更为简单实用，缺点是难于知道什么时候好的启发式解己经被求得。启发式方法中最具代表性的就是由Clarck和wrigllt提出的节约法。许多成功的车辆调度软件就是根据该方法或其改进方法开发的。针对有时间窗的车辆路线安排问题提出了一种利用节约法的启发式算法。典型启发式算法中还包括由Lin和Kemighan提出的分支交换探索法，该算法始终保持解的可行性而力图向最优目标前进。在每一步，都改变一个可行解而减少总费用，直到这个过程继续到不再可能使费用减少为止。Gillet和Miller提出的扫描算法先把点或弧的需求进行分组或划群，然后对每一组按旅行商问题(TSP)求解，设计出一条经济的路线。此外，常用的启发式方法还有一阶段法、不完全树搜索算法等。各种启发式方法的主要区别在于收敛的速度和程度不同[4]。随着现代计算机技术的发展，启发式算法也得到进一步发展，例如现在应用比较广泛的遗传算法、蚁群算法及禁忌搜索法等。因为这些算法由启发式算法发展而来，所以被称为亚启发式算法，有这样的说法吗？是因为这些算法模拟生物进化过程，因此也被称为智能进化算法。至于也被称为亚启发式算法的原因得好好追究一番了，这里可以不提。也被称为智能进化算法。3.模拟方法(Simulation)。利用数学公式、逻辑表达式、图表、坐标图形等抽象概念表示实际运输系统内部状态和输入输出的关系，以便通过计算机对模型进行实验，通过实验取得改善运输系统或设计新运输系统所需信息。虽然模拟方法在模型构造、程序序调试、数据整理方面工作量大，但由于运输系统结构复杂，不确定情形多，模拟方法仍以其描述和求解问题的能力优势，成为复杂运输调度系统建模的主要方法。27 4.交互式优化法。这是一种通用方法，它把人的知识和经验结合到问题的求解过程中去。其思想是:有经验的决策者应具有确定和修改参数的能力，井且根据知识直感，把主观的估计加到优化模型中去。精确优化方法是以经广泛采用的方法，另外三种方法则代表了最近研究的方向。尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到有较高精度的解，而且也易于考虑各种实际问题。因此，它成为解决配送问题的重要方法。与传统的启发式方法相比，近年来一些新的启发式方法，通过对启发式规则和搜索方式的改进，在求解多节点、多约束的VRP问题上可以获得较快的收敛速度和较高质量的全局解，从而进一步拓宽了启发式方法的应用领域。2.3线路优化的方法介绍2.2.1节约算法节约算法（SavingAlgorithm）是Clarke和Wright在1964年提出的它是目前解决VRP模型最有名也是应用最普遍的启发式算法。节约算法是用来解决运输车辆数目不确定（运输车辆数目在VRP问题中是一个决策变量）的VRP问题，这个算法对有向和无向问题同样有效。他的核心思想就是将运输问题中存在的两个回路（0，…,i,…,0）和（0，j，…，0）合并成为一个回路（0，…，i,j,…，0）。在整个合并的过程中，整个运输问题的总距离将会发生变化，如果变化后的总运距下降，则称节省了运输距离。相应的变化值，叫做节约距离[5]。节约算法的一般步骤：第一步，形成一个初始解。形成初始解时，需要使每个顾客的要求都得到满足，而且使所有的约束条件得到满足。初始解可以由具有运载限制的最近邻点法得到。第二步，进行节约度的计算。计算所有点对的节约度：，i,j=1,2,…，n且27 然后对结果进行升序排列。第三步，进行回路的合并。从升序排列的节约度序列的最上面的值开始对已有的回路进行合并，将回路中的部分路径（0，j）和（i，0）删除，然后得到新的回路（0，…，i,j,…，0）在解决实际问题的过程中，合并时要考虑整个回路在体积或重量上的运载限制，当合并会导致回路上各个点的需求总量在体积或重量上超出限制时，要停止合并，并开始设计新的回路。2.2.2扫描算法扫描算法（SweepAlgorithm）是Gillett和Miller在1974年首先提出的，他也是求解车辆数目不确定的CVRP问题的常用方法。扫描算法一般分为四个步骤完成：第一步，以起始点作为极坐标系的原点，并以连通图中的任意一顾客点和原点的连线定义角度为零，建立极坐标系。然后对所有顾客所在的位置，进行坐标系的变换，全部都转化为极坐标系。第二步，分组。从最小角度的顾客开始，建立一个组，按逆时针方向，将顾客逐渐加入到组中，直到顾客的需求总量超出了运载车辆体积或重量的负载限制。然后建立了一个新的组，继续按逆时针方向旋转，将顾客继续加入到组中。第三步，重复步骤二的过程，直到所有顾客都被分类为止。第四步，路径优化。对各个分组内的顾客点，就是一个TSP模型的线路优化问题，可以用TSP模型的方法对结果进行优化，选择一个合理的线路[6]。2.2.3分支交换探索法分支交换探索的概念是由Lin和Kemighan在1973年提出的，这种算法是一种局部搜索优化法。该算法的核心思想是始终保持解的可行性而力图向最优目标前进。在每一步，都改变一个可行解而减少总费用，直到这个过程继续到满足停止搜索条件为止。由于搜索的随机性，这种算法很难得到最优解，但可以得到一个接近最优解的方案。27 分支交换探索法主要是在满足运载限制或其他一些限制的条件下，通过交换或移动路径之间的边或客户来改进当前解。在分支交换探索法中最主要的两个部分是搜索准则和停止条件：分支交换搜索法的搜索准则是在满足约束条件的邻域解中随机的进行搜索，搜索到优于当前解的邻域解即更新该解为当前解，同时完成向最优解的一步移动。然后以新的当前解为标准继续搜索。分支交换探索法的停止准则，一般分为两种形式：第一种是指定一个固定的移动步数，当移动次数达到移动步数限制时即停止搜索，另一种是以一个指定的条件目标（例如运输总距离小于一个定值），只有当通过搜索得到的解满足目标条件时才能够停止搜索。交换分支探索法与其它局部搜索优化法一样，需要在求出一个初始解的情况才能进行优化，得到的解为局部最优解。27 第3章金虎便利线路优化的建模及计算3.1金虎便利的店面分布及需求量统计3.1.1金虎便利的店面布局金虎便利的店面分布及配送中心的位置如图所示：图3-1配送中心及店面分布图注：0.金虎便利店配送中心1.解放路店2.旱西关店3.新建南路店4.三道巷店5.上马街店6.康乐街店7.侯家巷店8.长风街店9.大王路店10.并州西街店11.山西大学店12.坞城路店13阳光小区店27 3.1.2金虎便利店面的货物需求金虎便利店的货物主要由三大类构成；第一类货物是以方便面、饼干、薯片和肉罐头为主的速食产品。第二类货物由各类饮料及酒类组成，这一部分货物体积小重量大，并且每日销售额在总销售额中占很大比重。第三类货物由一些日用品如洗发液、牙膏、洗衣粉等组成，这类货物的日销售额要明显小于前两种商品，但依然是每日销售额中的一个重要组成部分。通过对金虎配送中心仓库管理员进行咨询及对仓库出仓统计的查阅，得到了一组较为准确的配送需求数据。具体配送频率为2天一次，各店面每次配送的需求详细数据见下表。表3-1金虎便利各店面需求表需求货物体积（）需求货物重量（t）1.解放路店5.50.852.旱西关店4.00.533.新建南路店4.50.694.三道巷店3.50.575.上马街店4.00.626.康乐街店5.50.837侯家巷店3.50.568长风街店4.50.679.大王路店3.00.4310.并州西街店6.00.9711.山西大学店7.51.1012.坞城路店4.00.5813阳光小区店4.00.60注：该数据来自金虎便利仓管记录3.1.3金虎便利运输车辆车型及装卸货物的方法金虎便利选择的车辆统一为解放牌轻卡，总载重量为27 2.8吨，其货箱容积约为22，满载时一公里油耗约为0.18升，是一款较为实用的轻型卡车。在配送的过程中，仓库在货物装车前先将个门店的货物进行拼盘，尽量将每一个门店的货物放置于一个托盘之上，然后在已经拼装成整托盘的货物贴上纸质标签，并用粗水笔标明货物目的地缩写，对与无法拼成整盘的货物要与其他门店货物进行拼盘，但要在每一箱货物的外包装上注明卸货地点。不同门店货物拼盘时要注意将不同门店的货物清楚的区分，即使不能合理利用托盘的全部空间，也要避免将两个门店的货物混在一起，以减少货物的卸车时间，同时避免因卸错货物而在门面店的重复装卸，更要避免因为没有及时发现错卸漏卸而导致的另外加派车辆。另外要注意不能将没有直接线路连接的店面的货物拼在一个托盘内，以免在积载安排时造成困难，也避免在装卸时造成困难和混乱。最后要在拼好的托盘上贴另一种颜色的纸质标签，同时注明卸货地点。装货的过程中要注意“先到后装”的原则，保证先到达的门店的货物被放在最靠近车尾的地方[8]。这样做可以方便卸车，防止店面在卸载自己的货物时因货物被遮挡而对其他店面的货物进行重复装卸。另外要注意的是两家直接相连门店拼盘装车的货物被放置在先到门店货物与后到门店货物的衔接处并归入先到门店一组，以防漏卸货物。最后所有托盘应将贴有标签的一面面向车尾，以方便卸车时候辨认。在卸货过程中以贴在整盘货物的标签为辨识标准，逐个卸下自己门店的货物，同时注意拼盘货物货物包装上的目的地编号，防止错卸货物。3.2金虎便利线路优化的VRP数学模型将金虎便利的配送中心编号为0，车辆编号为k，任务编号为1，2，…，1考虑运输量约束问题可以定意义如下模型：27 i=0,1,…,1;j=0,1,…,1;式中表示从点i到点j的运输成本。和为变量，定义为：时，车辆从点i行驶到点j，时，车辆没有从i点行驶到j点；=1时，点i的任务由车辆k完成，=0时，点i的任务不由车辆k完成。在式中为第i点的需求量，q为运输车辆的定额载重量。n为在设计方案中所用到的车辆数，D为添加一辆车所需要的固定成本。D主要由车辆的保养费用及司机的工资构成。在本次的计算之中，车辆每公里的固定油耗为0.18升每公共里。柴油价格为每升6元。车辆最大载重辆为2.8吨，最大容积为22。每次配送每派出一辆车的固定费用为100元。3.3节约算法配送线路设计第一步，假设每个点都是由一辆货车进行单独的配送，这样每一个门店的需求都可以得到满足，并且也不会超出车辆的载重与体积限制。我们将这个方案作为节约算法的初始解。27 图3-2金虎便利线路设计初始解第二步：计算各点间距离(由于统计条件有限，各门店之间的距离以地图上所测量出的直线距离进行计算，而并非实际的车辆行驶距离)。各点间距离见表3-2。表3-2各点间距离表(单位km)012345678910111213004.15.84.54.92.85.02.55.17.32.96.35.42.4101.61.71.51.42.71.76.24.12.58.26.94.1202.41.73.03.13.37.33.53.89.38.15.5303.12.30.92.24.92.81.86.95.73.4402.34.02.87.75.13.89.68.35.3503.20.55.65.11.94.76.33.2602.94.42.32.16.45.23.5705.15.01.46.95.82.6806.13.82.00.82.8904.48.17.05.81005.74.51.71101.24.41203.3130对所有点对的节约度进行计算并经过统计排序后，按降序排列，见表3-3。表3-3各点对节约度降序列表点对节约度点对节约度点对节约度11-1210.52-752-83.66-910.03-5510-133.627 8-129.75-953-133.52-99.61-74.910-113.53-992-104.92-123.12-496-114.91-833-68.63-74.82-112.81-28.35-74.82-132.72-37.97-94.81-122.62-67.73-84.77-82.51-47.58-134.71-132.41-97.34-74.64-82.34-97.15-64.65-82.31-36.96-74.67-132.33-46.31-104.51-112.28-96.312-134.57-122.14-65.95-114.44-1226-105.811-134.34-1329-105.83-124.25-1326-85.78-104.25-121.99-125.74-1047-111.92-55.67-1044-111.63-105.63-113.91-55.56-133.99-115.59-133.94-55.45-103.86-125.210-123.8第三步，按排列好的节约度降序表，将节约度最大的点对合并，在考虑车辆最大承载能力的情况下得到一个优化方案，其线路图如3-3所示。27 图3-3节约算法法得到的线路图经检验每条回路的载货量均没有超出货车载重限制和体积限制。第四步，计算使用该配送线路所需要的费用：回路0-6-9-2-4-0所经历的里程数：5.0+2.3+3.8+4.9=16km回路0-10-3-1-0所经历的里程数：2.9+1.8+1.7+4.1=10.5km回路0-13-7-5-0所经历的里程数：2.4+2.6+0.5+2.8=8.3km回路0-11-12-8-0所经历的里程数：6.3+1.2+0.8+5.1=13.4km总里程为16+10.5+8.3+13.4=48.2km每次运输成本为：0.18×48.2×6＋4×100=452元。3.4扫描算法的配送线路设计第一步，将配送中心所在的点0点视为极坐标原点，并建立极坐标系。如图3-4所示。27 图3-4扫描法求解的扫描过程图第二步，扫描算法的分组过程：从角度为零向逆时针方向进行扫描，第一个被分组的是店面4,0.57；下一个被分组的是店面5，0.57＋0.62=1.19，没有超过2.8限制。继续转动，下一个被分组的是门店1，0.57＋0.62＋0.85=2.04,没有超出限制，然后继续转动，门店2被分到第一组。0.57＋0.62＋0.85＋0.53=2.75，仍然没有超出限制。接下来的扫描中遇到门店7，0.57+0.62+0.85+0.53+0.56=3.13，超出了2.8的限制，按规则，需要一个新的分组，这样第一组由店面4、5、1、2组成，在第二组中有店面7，0.56，继续转动，重复上面的步骤，直到所有店面分组完毕，可以得到一个店面的分组如图3-5所示。27 图3-5扫描算法求得的各店面分组图第三步，通过在每一组店面内使用最近邻点法可以得到一个线路优化方案，如图3-6所示。图3-6扫描算法求得的线路优化方案27 第四步，对该方案进行成本的计算：回路0-5-1-2-4-0的总距离：2.8＋1.4＋1.6＋1.7＋4.9=12.4km回路0-7-3-6-9-0的总距离：2.5＋2.2＋0.9＋2.3＋7.3=15.2km回路0-13-10-8-0的总距离：2.4＋1.7＋3.8＋5.1=13回路0-12-11-0的总距离：5.4＋1.2＋6.3=12.9km该线路设计方案的总运距为：12.4＋15.2＋13＋12.9=53.5km每次配送的成本约为：0.18×53.5×6＋4×100=458元。通过计算，可以明显看出扫描法在第二阶段使用最近邻点法进行局部回路的设计后，得出的配送方案不太理想，所以要采用其他的优化设计方法对已有方案进行局部回路的优化。3.5分支交换探索法对扫描算法求解方案的局部优化由于通过扫描算法得到的初始解并不理想，所以要用其他方法对已经求出的最初解进行局部优化。而优化的种类根据范围可以分为路径间优化和路径内部优化。现在用来优化的主要方法有遗传算法、蚁群算法、退火算法等，但这些方法较为复杂，需要利用计算机程序进行辅助计算。在这里将采用一种较为简单的优化算法：分支交换探索法。由于计算能力的限制，我们在进行分支交换探索法时只做五步移动。我们对上节得出的结论进行路径间的局部优化，将扫描算法设计出的配送线路作为一个初始解，然后在保持解的可行性的前提下交换不同回路中的一个或几个需求点，以试图找到一个优于当前解的新解。邻域解是一个满足配送过程中的条件限制但又不同于当前解的一个可行解，例如回路0-11-12-0吸收点3构成新回路0-3-11-12-0，然后失去点3的回路吸收点1再构成新的回路，得到一个拥有四条回路的新解，为（0-5-4-2-7-0，0-1-9-6-10，0-3-12-11-0，0-10-13-8-0）如图3-6所示，通过检验，该解在体积和重量上都没有超出回路的运载限制，则该解为最初解的一个邻域解。但这个解并不优于当前解，所以当前解不能向这个解移动。27 图3-7初始解的邻域解分支交换探索法的优化过程实际上就是一个不断对领域解进行探索并向更优的邻域解移动的过程。当搜索到解（0-4-2-1-0，0-3-9-6-0，0-13-10-7-5-0，0-8-12-11-0）时，该解的总运距为49.1km，小于初始解的53.5km，所以将该解作为新的当前解，为了避免重复搜索，以及方便比较。我们对已经找到的解记录到下表。此时完成第一次移动。表3-4记录表之一1（0-4-2-1-0，0-3-9-6-0，0-13-10-7-5-0，0-8-12-11-0）23当搜索到解（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）时该解总运距为48.6km，小于原有的49.1km，将该解更新为当前解。完成第二步，进行记录后继续搜索。表3-5记录表之二1（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）2（0-4-2-1-0，0-3-9-6-0，0-13-10-7-5-0，0-8-12-11-0）27 3搜索到解（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）时该解总运距为48.4km，小于原有的48.6km，将该解更新为当前解并记录。第三步移动结束。表3-6记录表之三1（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）2（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）3（0-4-2-1-0，0-3-9-6-0，0-13-10-7-5-0，0-8-12-11-0）搜索到解（0-5-1-2-4-0，0-10-6-9-3-0，0-13-7-0，0-8-12-11-0）时该解总运距为47.9km，小于原有的48.4km，将该解更新为当前解，将该解进行进行记录。因为记录表已满，按照“先进先出”的原则将最先进入记录表中的解退出记录表，第四步结束，然后继续搜索。表3-7记录表之四1（0-5-1-2-4-0，0-10-6-9-3-0，0-13-7-0，0-8-12-11-0）2（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）3（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）搜索到解（0-4-2-1-5-0,0-7-3-9-6-0,0-13-10-0,0-8-12-11-0）时该解总运距为47.6km，小于原有的47.9km，将该解更新为当前解，将该解加入到记录表。将最先进入记录表中的解删除，此时已经完成全部五步的移动。表3-8记录表之五1（0-4-2-1-5-0,0-7-3-9-6-0,0-13-10-0,0-8-12-11-0）2（0-5-1-2-4-0，0-10-6-9-3-0，0-13-7-0，0-8-12-11-0）3（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）27 因为此时的最优解为（0-4-2-1-5-0,0-7-3-9-6-0,0-13-10-0,0-8-12-11-0）所以将该方案定为分支交换探索法得到的局部优化方案。如图3-8所示。图3-8分支交换探索法得到的配送方案按此路线配送的成本约为：回路0-4-2-1-5-0的总运距为：2.8＋1.4＋1.6＋1.7＋4.9=12.4km回路0-7-3-9-6-0的总运距为：2.5＋2.2＋2.8＋2.3＋5.0=14.8km回路0-13-10-0的总运距为：2.4＋1.7＋2.9=7.0km回路0-8-12-11-0的总运距为：5.1＋0.8＋1.2＋6.3=13.4km该设计方案的总运距为：12.4＋14.8＋7.0＋13.4=47.6km该设计方案的配送成本为：0.18×47.6×6＋4×100=451元。3.6结论通过对配送总成本的比较，不难发现通过分支交换探索法得到的27 线路优化方案是最节省费用的，但这并不能说明分支交换探索法就是最好的。本文中涉及到的三种方法可以说是各有特色。节约算法虽然步骤较为繁琐，但是它却可以较为直接的得出一个接近最优解的配送方案。缺点是计算步骤过于复杂，每增加一个点都会使得计算数据大幅增加。所以此种方法在面对大量的需求点的时候就会出现因为数据庞大，难于计算的问题。扫描算法最大的优点是即使面对大量的需求点时可以进行快速的分组，并且可以很快的得到一个初始解[9]。但是缺点也尤为明显，扫描法的缺点是在分组后的第二阶段需要另一种优化方法对局部进行优化，而第二阶段所选取的方法会对优化的结果产生很大的影响。所以当最后的优化结果不理想时。，需要引入其他的方法用对做出的配送方案进行进一步优化。分支交换探索法提出的时间较早，该解的使用需要有一个初始解，并且在移动的过程中有很大的随机性，比较容易跳过最优解，所以使用该方法一般只能得到一个近似最优解。但是近几年来随着计算机技术的发展，在计算机强大的计算能力的支持下，分支交换探索法的价值得到了进一步的发掘，例如现在经常使用的禁忌搜索算法和遗传算法都在一定程度上受到了分支交换法的影响，另外分支交换法也发展出了更加精确的链式L-K算法和循环L-K算法。本次计算是以一组静态的数据作为研究对象，以扫描算法与分支交换探索法搭配使用得到了一个合适的解决方案，但这不能说明以上两种方法的混合使用在任何情况下都能够得到最合适的解决方案。当数据发生变化时我们需要用本文所提供的几种方法重新进行计算与优化，通过比较得出一个合适新数据的最优解配送方案。例如，山西大学店与并州西街店的服务对象主体分别是山西大学和太原医科大学的的学生，当寒暑假到来的时候，其货物的需求量会急降致0.35吨与0.3吨左右，此时，配送方案会发生巨大的变化。通过扫描算法发现只需调用3辆车即可满足配送要求，在这种情况下，扫描算法的在提高车辆利用率方面的优势得到了极大的体现，而配送线路也需要重新设置。另外值得一提的是本文所设计的金虎便利的配送方案是一个小范围内的配送方案，这使得车辆的固定成本在整个配送成本中占了很大的比重。27 公司采取了每两天进行一次配送的配送策略，那么公司可以采用将4条配送回路分为两组，采取不同组别隔天配送的配送策略，即第一天由两辆车配送组1的两条回路，第二天仍由这两辆车对组2中的两条回路进行配送，这样就可以将车辆的购买数量减少两台，节约在车辆购买和雇佣司机方面支出的成本，提高车辆的利用率，大幅降低配送成本。27 结束语近年来连锁零售业的发展突飞猛进，从沃尔玛，家乐福，麦德龙这三家来自不同国家的零售巨头跻身世间500强企业的前50强开始，标志着连锁零售模式的普及化和零售业的迅速崛起，而随着连锁分店的增多配送成本的合理控制就显得尤为重要。然而很多国内的零售业既没有采用较为先进的越库配送模式，也没有对自己的配送线路做出很好的规划，造成了商品售价偏高，市场的竞争力低下的现状。本文利用节约算法，扫描算法，分支交换法对金虎便利比较具有代表性的一组数据进行配送线路的设计与优化，期望能为金虎便利今后每次解决具体配送问题提供方法上的参考。最后，需要指出的是，该文章在计算方面仍存在着许多不足之处，例如本文采用的需求量数据是静态的，而现实中的实际需求量却是围绕该组静态数据上下波动的一组动态数据，但由于时间原因和商业保密原因，所能获得的数据精确程度也只能局限于此。另外在本文中各点间的距离一律采用了直线距离，这与实际的行车距离产生了较大的出入。车辆的耗油量也统一按照满载时的耗油量进行计算。因为存在以上原因，使得计算得到的结果的精确程度受到很大影响。27 致谢语经过长期的积累和反复修改，我的毕业论文终于得以完成，在论文即将定稿之际，又临近毕业之时，对曾经悉心指导并多次给我改进建议的各位老师及对我进行无私帮助的同学，报以由衷的感谢。特别要感谢的是我的论文指导老师，刘旺盛老师，她严谨的治学精神和广博的学术知识以及负责的指导态度，给了我巨大的学术帮助和精神动力。在毕业在即之时，再次向对我进行悉心教导和提供无私帮助的老师、同学、朋友致意真诚的敬意和由衷的感谢！27 参考文献[1]牛鱼龙.美国物流经典案例[M].重庆：重庆大学出版社，2006:21-22.[2]王烨.太原零售业近况.山西商报[J].2007.506:28.[3]吴璟莉.配送中心车辆调度问题的研究[J].广西大学学报，2002：5.[4]J.Homberger.ManagementScience[M].Amsterdam:North-holland,1998:543-544.[5]蔡临宁.物流系统规划--建模及实例分析[M].北京：机械工业出版社，2003.[6]袁际军.现代物流配送线路优化研究[D].上海海运学院博士学位论文，2002.[7]彭扬，伍蓓.物流系统优化与仿真[M].北京：中国物资出版社，2007.[8]冯媛媛.运输务实[M].北京；对外经济贸易大学出版社，2004.[9]BetlndBullnhelmer.ApplyingtheantsystemtotheVRP[J].LogisticsandTransportationReview,2001.[10]K.C.Tan.AVehicleroutingwithbackhauls:modelsalgorithmsandcasestudies[J]JournalofBusinessLogistics,2003.27