家乐福超市物流配送路的线优化-大学毕业论文

家乐福超市物流配送路线优化家乐福超市物流配送路的线优化摘要在物流配送业务中，合理确定配送路径是提商服务质量，降低配送成本，增加经济效益的重要手段。物流配送系统中最优路线的选择问题一直都是配送中心关注的焦点，针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合理化。通过对家乐福超市现有物流配送路径的分析研究，发现其中存在的一些问题，并由此提出解决办法，结合背景材料，建立了数学模型，运用遗传算法对家乐福物流配送路线进行优化选择，并得出结果。由此可见，家乐福超市原有的物流配送路线还可以进行再优化，从而达到运输成本最小化的目标。关键词：物流配送；路径优化；遗传算法THELOGISTICSOFSUPERMARKETOFCARREFOURPROVIDESANDDELIVERSTHEROUTETOOPTIMIZEAbstractInlogisticsanddistributionbusiness,areasonablepathistodeterminethedistributiontoservicequality,reducedistributioncosts,animportantmeanstoenhanceeconomicefficiency.Logisticsanddistributionsystemintheselectionoftheoptimalroutedistributioncenterhasbeenthefocusofattention,inviewofthecurrentsystemCarrefourlogisticsaspectsofthecurrentsituationleavesmuchtobedesired,thisarticlefromtheperspectiveofsustainabledevelopment,theconceptofusingthesystem,tostudyathomeLokFulogisticssystemandoptimizethedistributionline,sothattherationalizationofdistributionsystems.

Carrefoursupermarketontheexistinglogisticsanddistributionanalysisofthepathandfoundsomeproblemsandproposesolutionswhich,combinedwithbackgroundmaterials,theestablishmentofamathematicalmodel,Carrefouruseofgeneticalgorithmstooptimizelogisticsanddistributionrouteschoicesandtheoutcome.ThisshowsthatCarrefoursupermarketlogisticsoriginalroutecanalsobeusedforfurtheroptimization,inordertominimizetransportationcoststoreachthegoal.

Keywords：logisticsanddistribution;pathoptimization;geneticalgorithm目录1.绪论 11.1选题目的和意义 11.2国内外物流配送路线优化研究现状 21.3研究内容与技术路线 32.家乐福超市配送路线现状 52.1家乐福超市概况 52.2家乐福超市配送路线作业现状 62.2.1配送距离分析 62.2.2车辆数分析 72.2.3需求量分析 82.2.4商品品种分析 82.3家乐福超市配送现有路线问题分析 113.配送路线优化建模与求解 123.1研究对象目标设定 123.2模型的构建 143.2遗传算法 163.2.1遗传算法介绍 163.2.2算法思想与算法流程 184.优化结果分析 214.2优化后结果 214.3结论 225.总结与建议 23参考文献 24致谢 25附录一：MATLAB编程 26家乐福超市物流配送路线优化作者：漆华兰第30页共34页1.绪论1.1选题目的和意义配送是一项特殊的、综合性的物流运动，其运行和发展有着深刻的社会根源和历史背景。在市场经济体系中，物流配送如同人体的血管，把国民经济各个部分紧密地联系在一起。配送是物流中一个重要的直接与消费者相连的环节，是将货物从物流结点送达收货人的过程，是在集货、配货基础上，完全按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送”的有机结合形式。其主要包括集货作业、配货作业、车载货物的配装、配送线路的确定。在生活中，基于电子商务的物流配送业务量逐渐增加，如果还沿用以前的物流方法来组织配送，会产生很多问题。这些问题归纳起来，包括以下几点:1)服务质量的下降。电子商务的特征是交易量巨大和交易速度极快，而传统物流配送的特点是人工调度、反应时间长。信息流与物流的矛盾会导致整个电子商务客户服务的低效。也许客户可以在几十秒内完成一次交易，却要等上一个星期才能收到货物，这样的服务只能逐渐失掉客户。2)物流成本控制困难。传统的物流配送大多是由人工调度的，在交易量较小的情况下，可以合理地安排配送，降低成本。一旦交易量增加、交易速度加快，配送调度就会超出人工的能力范围，会导致大量的不合理调度的出现，物流成本无法控制。3)增加城市交通的负担。物流配送调度的不合理，会使物流配送的行车路线变长，导致在运车辆增加，从而给本已拥挤的城市交通加重负担。要解决以上的问题，使物流配送调度满足以下目标①准时送货。就是要客户选择货物送达他们指定地点的时间，要按照每个客户的时间要求安排物流配送。②总成本最低。③总行车路径最短。当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重要标志，也成为城市经济发展水平的体现，被喻为促进经济发展的“加速器”。物流配送是一种先进的现代物流形式，它不但给供应者和需求者带来降低物流成本、享受优质服务的直接效益，而且还能为社会节省运输车次、缓解交通压力、减少运输污染、保护生态环。而今，由于小批量、多批次的及时配送方式的发展，运输费用正在逐年提升，许多企业的运费已经超越了库存费用，城市交通与改善物流的矛盾也愈演愈烈，城市交通混杂、阻塞、车辆噪音、尾气污染、车祸事故和能源浪费等现象更加严重，若物流路线选择的不合理，还会使物流配送的行车路线变长，导致在运车辆增加，从而给本己拥挤的城市交通加重负担，这就势必要选择合理有效的运输路线来减少重复运输、倒流运输、迁回运输、单程运输和空驶等，这样不仅提高配送效率，控制了物流成本，而且可限制车辆在城市中的运行时间，有效缓解城市交通负担。物流配送系统中最优路线的选择问题一直都是配送中心关注的焦点，对于城市配送而言，由于受交通堵塞和各种交通管制的影响，导致配送路径寻优更具复杂性。所以本文通过对具有动态的交通堵塞和交通拥挤限制信息及静态禁止通行等限制信息的实际配送网络的描述，提出解决两种限制情况下配送网络寻优的方法，建立了配送网络图中权重确定模型，并基于此进一步建立了城市物流配送决策系统数学模型，运用二分领域搜索算法对其寻优。针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合理化:一方面通过建立一种快速、高效、网络化的物流组织系统降低物流成本，增加利润;另一方面，增强家乐福的竞争力，使其配送系统相应得到优化，从而使家乐福物流取得阶段性成果，因此，对家乐福物流配送体系及其路线的优化问题进行研究将具有很大的现实意义。1.2国内外物流配送路线优化研究现状物流配送路线优化，是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。对物流配送路线优化，可以提高物流经济效益，实现物流科学化。可以说对物流配送路线优化理论与方法进行系统研究是物流集约化发展，构建综合物流系统，建立现代调度指挥系统，发展智能交通运输系统和开展电子商务的基础。配送路线合理与否对配送速度，成本，效益影响很大，特别是多用户配送线路的确定更为复杂。采用科学的，合理的方法来确定配送路线，是配送活动中非常重要的一项工作。路线优化问题最早是由DANTZIG和RAMSER于1959年提出的，由于这一问题的理论涉及很多学科，很多实际问题的理论抽象都可归结为这一类问题，应用前景广阔，所以很快便引起运筹学，应用数学，图论与网络分析，物流学科，交通运输工程，管理科学与工程，计算机应用等学科的专家，工程技术人员和管理者的极大重视，自此，一直成为运筹学与组合优化领域的前沿与研究热点问题。在国外，物流配送路线优化问题已广泛应用于生产，生活的各个方面。如报纸投递及线路的优化，牛奶配送及送达线路的优化，电话预订货物的车辆线路设计，垃圾车的线路优化，连锁商店的送货的线路优化等等。目前，研究水平已有很大发展，其理论成果除在汽车运输领域外，在水运，航空，通讯，电力，工业管理，计算机应用等领域也有一定的应用，还用于航空乘务员轮班安排，轮船公司运送货物经过港口与货物安排的优化设计，交通车线路安排，生产系统中的计划与控制等多种组合优化问题。在国内，该问题的系统研究还不多见。近年来有李军等人课题组承担的国家自然科学基金《不确定信息条件下动态车辆路径》等研究工作。纪寿文等人根据深圳市科技园的实际路网图，采用神经网络的方法对运输车辆优化调度进行了试验研究。王正彬等人在分析VRP现有启发式算法的基础上，建立了考虑线路安排的物流配送方案模型，并提出了求解该问题的搜索算法。1.3研究内容与技术路线本文结构：绪论（研究背景，目的，意义及现状）绪论（研究背景，目的，意义及现状）路线优化现状（公司概况，需求货物品种，货物需求量，分店分布，车辆数，现有路线分配方法）构建模型（目标设定，函数构建）模型求解（遗传算法介绍，算法流程，编程实现）优化结果分析结论，总结与建议图1-1：论文结构图本文章节安排：第一章：研究背景，目的及意议，研究发展现状，论文结构与技术路线；第二章：家乐福超市物流配送路线现状分析，及存在的问题分析；第三章：针对问题设定目标，构建数学模型，引入遗传算法，编程实现；第四章：优化结果分析；第五章：结论，总结与建议；本文技术路线：（1）分析家乐福超市物流配送路线状况，并针对路线优化提出问题；（2）在考虑成本最小化的目标及其各种约束条件的基础上建立数学模型；（3）根据具体物流配送的特点和要求，提出车辆路线优化方案；（4）引入遗传算法进行求解，采用MATLAB计算机编程进行算法实现；2.家乐福超市配送路线现状2.1家乐福超市概况成立于1959年的家乐福集团是大卖场业态的首创者，是欧洲第一大零售商，世界第二大国际化零售连锁集团。现拥有11,000多家营运零售单位，业务范围遍及世界30个国家和地区。集团以三种主要经营业态引领市场：大型超市，超市以及折扣店。此外，家乐福还在一些国家发展了便利店和会员制量贩店。2004年集团税后销售额增至726.68亿欧元，员工总数超过43万人。2005年，家乐福在《财富》杂志编排的全球500强企业中排名第22位。法国家乐福集团是大型超级市场（Hypermarket）概念的创始者，于1963年在法国开设了世界上第一家大型超市。1999年8月30日家乐福兼并普罗莫代斯组成世界第二大零售集团。如今家乐福已发展成为欧洲最大、全球第二大的零售商。2004年，家乐福集团被《财富》杂志评为全球500强企业的第22位。家乐福于1969年开始进入国际市场，目前在世界上31个国家和地区拥有一万多家销售网点，涉及的零售业态包括大卖场、超级市场、折扣店、便利店、仓储式商店与电子商务，集团的50万名员工正致力于为20亿消费者服务。家乐福集团建立了全球性的采购网络，向不同国家和地区的供应商采购具有市场竞争力的商品。家乐福的经营理念是以低廉的价格、卓越的顾客服务和舒适的购物环境为广大消费者提供日常生活所需的各类消费品。家乐福对顾客的承诺是在价格、商品种类、质量、服务及便利性等各方面满足消费者的需求。家乐福力争通过自己的努力成为当地社区最好的购物场所，为消费者带来更多的实惠和便利，并携手和各商业伙伴为当地经济的繁荣做出贡献。家乐福于1995年进入中国后，采用国际先进的超市管理模式，致力于为社会各界提供价廉物美的商品和优质的服务，受到广大消费者的青睐和肯定，其“开心购物家乐福”、“一站式购物”等理念已经深入人心。如今，家乐福已成功地进入了中国的25个城市，在北至哈尔滨、南至深圳、西至乌鲁木齐、东至上海的中国广袤土地上开设了109家大型超市，聘请3万多名员工。在在华外资零售企业中处于领先地位。家乐福还向中国引进迪亚折扣店和冠军食品超市两种业态。2004年，家乐福(中国)被国内媒体评为“在华最有影响力的企业”之一。2004年约有2亿多人光顾了家乐福在中国的各门店，其中68%为女性，32%乘公共汽车，37%步行，15%骑自行车，9%乘坐出租车或小轿车前往家乐福购物。家乐福成为了各地居民的好邻居。通过多年的经营，家乐福向中国的商业界输入了大型超市经营管理方面的技能和先进经验，并对商品采购、营销管理、资产管理以及人力资源开发等各方面实现现代化和本地化，为当地经济发展做了积极的贡献。2.2家乐福超市配送路线作业现状2.2.1配送距离分析(1)配送需求点坐标：现在以家乐福物流配送中心为原点(0,0),建立直角坐标系,各商店的坐标如下表所示:X(km);Y(km)表2-1分店所在地坐标分店与配送中心间距离坐标分店与配送中心间距离坐标XY1892-453244102053-3066778158-7-691591010121191012-8-13134-5146615-7-8163417-5101829191-152083i=1，220；(2)现有路线是固定不变且为已知,每条线路行驶距离可由表2-3求得,配送中心与商店之间，商店与商店之间的距离分析如下表：表2-2配送中心与分店之间,分店与分店之间的距离(0点表示配送中心)0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.862173.61.427153.6237.113625626.41306.12136101611191614181310211018345131314119.2209.24.51519.25196.1422112118050145.4311281038261533171814361753039363450037452641434020253624344139153369.22.8105143708.324121204.2114.5234.5717616135.4458.30232209.22712148.5311289.22111133126182602725237.11118214161712179177191412419.29.22705.86.132189.528132013289.210163.616118436.43.6255.802.231187.22611158.5289.211131.4149.210404.25.1236.12.2029165248.5147.1267.11215271820382024327.1323129014245.12023249.223136.415139.2262512201118181614011119.11714108.9148.53.6104.5153619.2189.57.2524110193.6125223.615112313153324202722826245.11119016181911191657.17.1117344.2121413118.5209.13.6160105.1195.11711135.19.21841111416201514231712181007.12615189.267.2514394.58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512238.93.6195.1158.51902.2.2车辆数分析所需车辆数分析(家乐福配送中心一年(365天)的车辆调度):表2-3车辆调度情况车辆运用数101291110111010891011运用天数2530364246494838241386表2-4车辆运用数所占比率车辆运用数相对比率累计比率120.070.07120.080.15110.100.25100.120.37120.130.50110.130.63130.130.76100.100.86140.070.93150.040.97130.020.99110.011.00则家乐福平均每天所用车辆数为12辆。2.2.3需求量分析表2-5每个分店（一年365天）平均每天的需求量分店12345678910需求量2324123513分店11121314151617181920需求量23421213222.2.4商品品种分析超市以满足消费者对基本生活用品一次性购买需要为经营宗旨，是一种经营品项较多的零售业态。下面对商品进行分类分析。

一、大分类

大分类是超市最粗线条的分类。大分类的主要标准是商品特征，如畜产、水产、果菜、日配加工食品、一般食品、日用杂货、日用百货、家用电器等。为了便于管理，超级市场的大分类一般以不超过10个为宜。

二、中分类

中分类是大分类中细分出来的类别。其分类标准主要有：

(1)按商品功能与用途划分。如日配品这个大分类下，可分出牛奶、豆制品、冰品、冷冻食品等中分类。

(2)按商品制造方法划分。如畜产品这个大分类下，可细分出熟肉制品的中分类，包括咸肉、熏肉、火腿、香肠等。

(3)按商品产地划分。如水果蔬菜这个大分类下，可细分出国产水果与进口水果的中分类。

三、小分类

小分类是中分类中进一步细分出来的类别。主要分类标准有：

(1)按功能用途划分。如“畜产”大分类中、“猪肉”中分类下，可进一步细分出“排骨”、“肉米”、“里肌肉”等小分类。

(2)按规格包装划分。如“一般食品”大分类中、“饮料”中分类下，可进一步细分出“听装饮料”、“瓶装饮料”、“盒装饮料”等小分类。

(3)按商品成份分类。如“日用百货”大分类中、“鞋”中分类下，可进一步细分出“皮鞋”、“人造革鞋”、“布鞋”、“塑料鞋”等小分类。

(4)按商品口味划分。如“糖果饼干”大分类中、“饼干”中分类下，可进一步细分出“甜味饼干”、“咸味饼干”、“奶油饼干”、“果味饼干”等小分类。

四、单品

单品是商品分类中不能进一步细分的、完整独立的商品品项。如上海申美饮料有限公司生产的“355毫升听装可口可乐”、“1．25升瓶装可口可乐”、“2升瓶装可口可乐”、“2升瓶装雪碧”，就属于四个不同单品。

需要说明的是，商品分类并没有统一固定的标准，各超市公司可根据市场和自身的实际情况对商品进行分类。但商品分类应该以方便顾客购物、方便商品组合、体现企业特点为目的。具体分类如下表所示：表2-6商品品种食品日用品1.粮油1.日化产品粮食

米面

淀粉

食用油

主食熟食

豆制品

其他粮油2.日杂用品2.果蔬3.家居用品新鲜蔬菜

新鲜水果

食用菌

蔬菜制品

干果|坚果

果蔬深加工

其他果蔬4.清洁用品及用具3.水产5.餐具鲜活水产品

粗加工水产品

精加工水产品

其他水产6.厨具畜产7.日用小家电鲜活畜禽

鲜肉类

鲜蛋类

鲜奶类

肉制品

蛋制品

乳制品

蜜制品

8.家用塑料制品4.糖酒饮料9.首饰糖类

酒类

茶叶

软饮料

冲饮品

冷饮

咖啡豆|可可

其他糖酒饮料10.衣物5.加工食品11.箱包,袋,皮具保健食品

休闲食品

方便食品

罐头食品

特色食品

调味品

其他加工食品12.文体用品6.烟草13.日用小五金烟叶

香烟

其他烟草14.休闲家具7.添加剂15.个人护理用品食品添加剂

其他添加剂

发酵制品16.卫浴用品8.包装机17.炊具加工设备

食品包装

其他机械包装

制冷设备18.灶具2.3家乐福超市配送现有路线问题分析家乐福的配送系统和信息系统是较落后的.家乐福至今没有在中国建立起统一的配送体系,且计算机系统的开发和建立,要落后于竞争对手沃尔玛好几年.家乐福这种”滞后”的配送系统与信息系统是其战略规划的成果,因为商品的集中配送是连锁商业带来的,但是目前中国连锁商业基础非常薄弱,只有通过大的配送系统的完善和整合才能形成规模的,高效的,社会化的物流配送系统.家乐福配送路线的分配存在以下几方面的问题：物流公司与门店之间的分布太分散，难以形成固定的配送线路送货难以达到及时难以保证适量的库存而不压货路线里程未达最短费用消耗大劳力消耗大，运力难以适当分配，难以调度车辆配送车辆吨位公里数大配送未实现自动化配送未实现网络化配送服务未实现系列化3.配送路线优化建模与求解3.1研究对象目标设定物流配送常考虑以最小化总运输成本或距离最短为目标，总运输成本主要由由两部分组成:(1)运输固定成本：如服务所有客户所需要的车辆数、总行驶距离(或总行驶时间)和与所使用的车辆有关的固定费用；(2)运输营业成本：如司机的管理费,各种工作人员的工资等.家乐福超市的业务运输成本是物流总成本的主要组成部分，占有56%。因此降低公司运输成本成为提高公司效益的直接有效途径。公司自有货运成本各项比例如下表：表3-1公司货运成本比例表固定费用（22%）营业费用（78%）折旧费（租赁费）：装卸工具，车库，办公室，水电，通迅，差旅费，公务车费用业务印刷费人力（司机）：工资,额外福利，装卸费投资利息：车辆，车库,办公室管理成本：职工月工资,额外福利,旅游和娱乐费用,房屋维修费，牌照费，职工培训费，宣传费及业务手续费。车辆运营成本：燃料（燃油，润滑油，过滤器）维修费（人工费+零部件）轮胎费，交通规费，养路费大修理基金提存道路服务：通行费,保险,许可证和登记费高速公路使用费,燃油司机费用占总营业成本的29.4%；维修费和折旧费占总营业成本的19.5%；其它的运营费用占总营业成本的32.6%；燃料费占总营业成本的18.5%；表上所述：公司车辆运营成本占据了总运输成本的78%。随着道路服务政策的变化，车辆营业成本在公司总成本中所占比例日益增大。距离是影响运输成本的主要因素，因为它直接对劳动、燃料和维修保养等变动成本发生作用。针对公司当前成本构成状况，可以知道：通过优化公司配送路线，减少运输车辆行驶总里程，可以减少车辆燃油费和道路服务费支出，进而减少物流总成本。因此，本文针对家乐福配送中心车辆路线优化问题，提出的目标是：总运输成本最小化。5594配送中心632781配送中心分店车辆路线图3-1家乐福的配送模式此问题可以描述为：这是一种分送式配送模型,是由一个供应点对多个客户的共同配送。对配送中心负责的需求网点（家乐福分店），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过各个分店各一次，最后返回配送中心，并在满足一定的约束条件下(如车辆容量限制、行驶里程限制、时间限制、顾客需求量、交发货时间等)，达到费用最少的目标。本文研究的是不考虑时间窗的非满载车辆优化调度问题。表述如下：将货物从配送中心配送到各分配送中心,由分配送中心派出容量为的货车承运，现有m辆车，各分店对所需求的货物有一定的要求，第i个分店的货运量为gi，（i=1，2……l）已知，在途中只有卸货任务,完成任务后返回配送中心,求满足配送需求的费用最少行车线路。分配送中心1分配送中心1分配送中心2分配送中心3分店1分店2分店3分店4配送中心图3-2家乐福配送体系结构3.2模型的构建为建模方便，需考虑以下几个前提假设条件：（1）配送中心不会出现缺货的可能并且对顾客的基本配送资料（需求量、地理位置）为已知，配送中心的位置也已知；（2）不考虑配送时间限制，即客户对货物的需求没有时间窗的规定；（3）不考虑每辆车为每个客户的服务时间，即不考虑每个客户的卸货时间；（4）一个配送中心根据配送条件可以负责多个客户，即一个配送中心服务多个客户；（5）车辆由配送中心出发，服务被指定的需求点后，再返回配送中心，区域内的需求点假设为固定数量且位置已知，不发生变动。（6）配送中心拥有一定数量的单一车型的配送车辆，且每辆车的容量已知。（7）每条配送路径上各客户需求量之和不超过配送车辆的容量；（8）每个客户只能由一辆配送车辆送货；（9）每辆车配送总里程不超过其最大行驶距离；（10）各道路均顺畅，不考虑交通堵塞拥挤等特殊情况。将配送中心编号为0，车辆编号为k，任务编号为i=1,2,所有车型载重量单一，每辆汽车的最大载重量为g，需要向L个需求点送货，每个需求点的需求量为，并且满足，需求点i到j的运距为，配送中心到各个需求点的距离为，再设为第辆汽车配送的需求点数（=0表示未使用第辆汽车），用集合表示第k条路径，其中的元素表示需求点在路径中的顺序为（不包括配送中心），令=0表示配送中心，为每辆车单位里程的行驶费用，为每辆车的派遣费用，考虑运输量约束,停车点车辆数目等约束,可以定义如下的基本模型:(3-1)(3-2)(3-3)(3-4)(3-5)(3-6)在上述模型中各个公式所代表的涵义如下：（3-1）式为目标函数，求总的配送费用最低；（3-2）式用于保证每条路径上各个需求点的需求量和不超过汽车的载重量；（3-3）式表明每条路径上的需求点数不超过总需求点数；（3-4）式表明每个需求点都得到配送服务；（3-5）式表示每条路径的需求点的组成；（3-6）式表示当第辆汽车服务的客户数大于或等于1时，说明该辆汽车参加了配送，则取，当第k辆汽车服务的客户数小于1时，表示未使用该辆汽车，因此取；3.2遗传算法3.2.1遗传算法介绍遗传算法与其它传统方法相比,具有如下优点:（1）适用范围广，具有很强的搜索能力；（2）能以很大的概率找到问题的全局最优解；（3）能有效处理较大规模优化问题；（4）搜寻空间并行性；（5）鲁棒性强；（6）智能性；（7）只通过目标函数计算适应度，不受约束条件束缚。基于以上几点,本文将采用遗传算法对家乐福超市物流配送路线进行寻优。遗传算法是由美国Michigan大学的Holland教授于1969年提出,后经DeJong、Goldberg等人归纳总结所形成的一类模拟进化算法。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。本文所设计的遗传算法的基本流程如下：STEP1：初始化，产生初始种群。STEP2：个体评价，即计算种群中每个个体的适应度。STEP3：按选择概率PS，执行选择算子，从当前种群中选择部分个体进入下一代种群。STEP4：按交叉概率PC，执行交叉算子。STEP5：按变异概率Pm，执行变异算子。STEP6：若满足设定的终止条件，则执行STEP7，否则执行STEP2。STEP7：输出种群中适应度最优的个体作为问题的最优解或满意解。解空间最优化问题描述解空间最优化问题描述第二步第一步建立优化模型确定决策变量,约束条件第二步第一步建立优化模型确定决策变量,约束条件第五步确定适应度转换规则第三四步编码,解码第五步确定适应度转换规则第三四步编码,解码个体基因型x适应度F(X)个体基因型x适应度F(X)第六步设计遗传算子第六步设计遗传算子第七步确定运行参数第七步确定运行参数遗传算法空间遗传算法遗传算法空间遗传算法图3-3应用遗传算法求解问题示意图第一步和第二步可以归结为建立优化问题的模型，可以是解析性的数学模型，也可以是非解析性模型。这是应用任何优化算法求解优化问题都需要的步骤。第三步“编码”实际上包含了设计或选择个体基因型的表示方法、设计解的表现型到个体基因型的转换算法。第四步“解码”是因为遗传算子只作用于编码后的染色体，而染色体的优劣要到解空间计算其对应的值由个体表现型计算目标函数值后才能进行判断。第五步“确定适应度转换规则”是因为染色体所对应的解空间的值可能相差很大，不适合直接用来定量评估个体的优劣。第六步“设计遗传算子”即为设计交叉、变异、选择等遗传操作，遗传算子与待优化问题、染色体的编码方案有很大的关系，也是遗传算法应用领域的一个重要创新点。第七步“确定运行参数”即确定遗传算法中的交叉概率、变异概率、最大进化代数等参数。3.2.2算法思想与算法流程首先根据每项任务的需求量qi，总任务量以及每辆车的最大载重量q，每辆车的任务不超过其最大载重量g，确定至少需要m辆车来完成任务,最后计算每辆车的总里程，其中总里程最小的即为所求任务安排。（1）构造染色体设车辆的可行线路可以编成自然数编码的长度为m+的染色体（i11，i12，i13，i1s；i21，i22i2t；；im1，im2im.），ikj为有需求的分店,即第ikj项任务,为分店的总数目，m为车辆从配送中心出发,经过各分店后,又回到配送中心的各条回路，即m辆车；车辆行驶线路为：第一辆车从配送中心出发，每个分店访问一次，经过i11，i12，i13，i1s的路线，又回到配送中心，形成子路径1；第二辆车从配送中心出发，每个分店访问一次，经过以前未经过的i21，i22i2t路线，又回到配送中心，形成子路径2；这样重复，直到每个分店都被访问到且每个分店只访问一次，项任务全部完成为止；其中i1s与i2t交换位置,表示行驶路径的改变,也使函数目标改变；算出每条路径的总行程，其中总行程最小的即为所求的最优化路径，其总运输费用最小。如染色体12345678表示行车路线：子路径π1：配送中心—任务1—任务2—配送中心子路径π2：配送中心—任务3—任务4—任务5—配送中心子路径π3：配送中心—任务6—任务7—任务8—配送中心这种染色体结构子路径内部是有序的，若子路径π1中点1，2交换位置，会使函数目标值改变；而子路径之间是无序的，若子路径π1和子路径π2交换位置，却不会改变目标函数的值。（2）初始种群满足编码方案的前提下,随机产生L个需求点的全排列,构成初始种群,如：i1，i2，…….i。若qij≤g且qij≥g将S至的基因依次向后移动一位,使S位空出,将0插入S位。接着若qij≤g且qij＞g如上面的操作,使t空出,将配送中心插入第t位。如此继续，直到将m个配送中心全部插入染色体为止。这样就构成了一条初始染色体，如此反复，构造满足群体数的染色体个数。（3）适应度函数对种群中的每个染色体Vi(i=1,2,…..l)根据目标函数的式子计算其值为Ui,若染色体对应的是不可行解，则赋予其目标函数值一个很大的整数，适应度函数可以设为：fi=1/Zi+M*1000,则fi>0，Zi为染色体Vi对应的运输成本；fi为染色体Vi的适应度，fi越大，其性能越好，其对应的解越接近最优解。（4）遗传算子1)选择算子个体选择的分配方法:按比例的适应度分配。利用比例于各个体适应度的概率决定其子孙的遗留可能性，选择概率公式为:pi=fi/fi即适应度越大，其选择概率越大。根据计算父代和子代的适应度，并将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用轮盘赌选择法产生。2)交叉算子对通过选择操作的新群体，除排在第一位的最优个体外，另N-1个个体要按交叉概率pc进行配对交叉重组。本文采用顺序法实施交叉操作：a)随机在你代个体中选取一个交配区域,如两父代个体及交配区域定为：A=47|8563|921，B=83|4691|257；b)将B的交配区域加到A的前面，A的交配区域加到B的前面，得：A‘=4691|478563921，B’=8563|834691257；c)在A‘，B’中自交配区域后依次删除与交配区相同的自然数，得到最终的两个个体分别为：A‘‘=496178532，B‘’=856349127。3)变异算子以一定的变概率Pm随机选取发生变异的个体染色体，然后在该染色体上随机选取2个非零基因位，把这2个位置上的基因互换形成新的基因串。（5）控制参数和算法的终止条件1)参数设置交叉概率Pc=0.6；变异概率Pm=0.01；终止代数T=100；初始种群N=100；δ=0.65；车辆数m=[qi/δ]+1（gi为需求点i的货运量）；g=8吨；2)终止条件由于计算时间的机器容量都是有限的，代数不能无限长，故当迭代次数达到规定值T时，停止计算。4.优化结果分析现有路线行驶距离（KM）实载量（吨）准载量（吨）实载率（%）0-2-5-0363.8847.5%0-9-12-0323.9848.75%0-15-18-0193.8847.5%0-4-0223.6845%0-10-17-0153.7846.25%0-1-19-0253.9848.75%0-3-11-09.23.8847.5%0-8-09.24.8860%0-6-14-013.9848.75%0-16-20-05.13.8847.5%0-13-06.43.7846.25%0-7-12-0325.7870.125%合计211.945.180(平均)50.3%4.1优化前结果表4-1优化前路线分析优化前成本经计算为10757元。4.2优化后结果表4-2运行结果分析所需车辆数行驶距离（KM）运输成本（元）第1次7376.8712706第2次7372.6312579第3次7333.5211406第4次7381.5912848第5次7416.6913901第6次7374.5812637第7次7383.3612901第8次7291.5710147平均值7366.3512291最小值7291.5710147表4-3优化后路线优化后路线行驶距离（KM）实载量（吨）准载量（吨）实载率%0-11-13-19-0267.6895%0-10-5-7-0886.5881.25%0-20-3-1-013.95.5871.25%0-12-16-18-025.17.8897.5%0-8-9-6-036.27.4892.5%0-4-17-2-023.17.9898.75%0-15-14-0192.9836.25%合计231.345.656（平均）81.43%优化后只需要7辆车，减少了5辆车；实载率增加到81.43%，提高了31.13%;总成本减少了610元。D=291.57KM;K=7辆;minZ=10147元.4.3结论在物流配送业务中，合理确定配送路径是提商服务质量，降低配送成本，增加经济效益的重要手段。本文以家乐福物流配送路径为研究背景，探讨物流配送路径优化问题，针对家乐福物流配送路径的现状，分析其不足之处，找出了车辆路径优化存在的问题；分析了相关的配送数据，并对优化计算方法进行了分析，结合实际情况，选择遗传算法作为论文的主要方法；结合背景材料，建立了数学模型，并设计了遗传算法；通过本文的分析可知，家乐福的现有配送路线还可以再优化，而达到节约运输成本的目的；还证明了遗传算法在路径优化问题中是一种很实用的计算方法，具备很多优点。5.总结与建议总配送中心统筹规划车辆数量，调整各个分配送中心的车辆数，预留一定的备用车辆，分配送中心编排好车辆的出车顺序，兼顾车辆保养保修等；此外，公司的发展必然使其业务范围扩大，出现新的货物类别，所以需要适时地增加其他的车型。针对配送车辆，特提出以下几点意见：（1）对重要客户指定某几辆车专门负责，以保证服务质量；（2）划分配送区域时区，针对较远的客户群，使用较大配送量的车辆负责配送，而较近的客户群则使用一般性的车辆负责配送；（3）指定某几辆车专门负责临时需求，即随要随送；（4）在路线安排上，一般方法是将客户按地理位置分成几个区域，再按照客户要求的送达时间从小到大进行排序，优先满足要求送达时间早的客户，如遇到问题则再进行调整。参考文献[1]李军，郭耀煌，物流车辆优化调度理论与方法[M].中国物资出版社.[2]谢胜利,唐敏,董金祥.求解TSP问题的一种改进的遗传算法[J].计算桢工程与应用,2002,38(8):58-60.[3]李向阳.遗传算法求解VRP问题[J].计算机工程与设计,2004,25(2):271-276.[4]胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学,2002,10(5):51-56.[5]李敏.基于复杂系统理论的配送网络优化研究[D].西安:西北工业大学,2006.[6]王述英.现代商贸物流配送组织体系的理论依据和基本框架[J]，中国流通经济，2002(6):7-10.[7]邹旭东，郑四发，班学钢等,具有交通限制约束的道路网络最优路径算法，公路交通科技，2002,(8):82-84.[8]蔡淑兰,最短路径算法在铁路客运系统中应用的研究，燕山大学学报[J]，1998(4):157-159.[9]K.AltinkemerandB.Gavish(1991),“ParallelSavingsBasedheuristicsForTheDeliveryProblem”,OperationsResearch39:456-469.[10]J.B.Atkinson(1994),“AGreedyLook-aheadHeuristicForCombinatorialOptimization:AnApplicationtoVehicleSchedulingWithTimeWindows”,JournalofTheOperationalResearchSociety45,673-684.[11]J.B.Atkinson(1998),“AGreedyRandomisedSearchHeuristicForTime-constrainedVehicleSchedulingAndTheIncorporationofALearningStrategy”,JournalofOperationsResearchSociety49:700-708.[12]J.AntesandU.Derigs(1995),“ANewParallelTourConstructionAlgorithmfortheVehicleRoutingProblemwithTimeWindows”,WorkingPaper,DepartmentofEconomicsandComputerScience,UniversityofKEln,Germ附录一：MATLAB编程程序代码functiondistA;%计算配送中心与商店之间,商店与商店之间的距离zb=[0001892-453244102053-3066778158-7-691591010121191012-8-13134-5146615-7-8163417-5101829191-152083];[n,nn]=size(zb);distA=zeros(n,n);fori=1:nforj=1:nx=sqrt((zb(i,2)-zb(j,2))^2+(zb(i,3)-zb(j,3))^2);formatshortgy=roundn(x,-2);distA(i,j)=y;endenddistAfunctionvrp[distA]=zbzl;[h,hh]=size(distA);lchrom=h-1;%染色体长度popsize=100;%种群规模pc=0.6;%交叉概率pm=0.01;%变异概率maxgen=100;%最大进化代数[pop]=initialize(popsize,lchrom);%调用初始化种群函数%q为按各网点序号排列的需求量q=[23241235132342121322];forii=1:maxgenp=pop;kmun=zeros(popsize,1);fori=1:popsizesumd2=0;forj=1:(lchrom-1)