店铺管理家乐福超物流配送路线优化

1、【瞿新卓據如方塞惭可自宙编損】（店铺管理）家乐福超市物流配送路线优化20XX年XX月_务年的企业咨询颐问经验.经过实战验证可比藩地执行的卓越置理方案.值得您下茕拥有学年论文之家乐福超市物流配送路线优化专业 物流工程班级姓名学号日期摘要在物流配送业务中，合理确定配送路径是提商服务质量，降低配送成本，增 加经济效益的重要手段。物流配送系统中最优路线的选择问题一直都是配送中心 关注的焦点，针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续 发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配 送体系合理化。通过对家乐福超市现有物流配送路径的分析研究，发现其中存在的一些问题,

2、 并由此提出解决办法，结合背景材料，建立了数学模型，运用遗传算法对家乐福 物流配送路线进行优化选择，并得出结果。由此可见，家乐福超市原有的物流配 送路线还可以进行再优化，从而达到运输成本最小化的目标。关键词：物流配送；路径优化；节约里程算法目录1. 绪论1.1.1选题目的和意义1.1.2国内外物流配送路线优化研究现状 22. 家乐福超市配送路线现状 3.2.1家乐福超市概况3.2.2家乐福超市配送路线作业现状 4.2.2.1配送距离分析4.2.2.2车辆数分析5.2.2.3需求量分析 6.2.2.4商品品种分析6.2.3家乐福超市配送现有路线问题分析 Z.3. 配送路线优化建模与求解 .9.3

3、.1 研究对象目标设定 9.3.2模型的构建 1.1.3.3节约算法12.331节约算法的基本原理 12.332节约里程算法主要步骤 13.333基于节约算法的配送路线优化 1.3.3.3.4优化后的配送线24.4. 优化结果分析 25.4.1优化前结果25.4.2优化后结果25.4.3 结论26.5. 总结与建议27.参考文献：28.1. 绪论1.1选题目的和意义配送是一项特殊的、综合性的物流运动，其运行和发展有着深刻的社会根源和历史背景。在市场经济体系中，物流配送如同人体的血管，把国民经济各个部 分紧密地联系在一起。配送是物流中一个重要的直接与消费者相连的环节，是将 货物从物流结点送达收货

4、人的过程，是在集货、配货基础上，完全按用户要求， 包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送” 的有机结合形式。其主要包括集货作业、配货作业、车载货物的配装、配送线路 的确定。在生活中，基于电子商务的物流配送业务量逐渐增加，如果还沿用以前的物流方法来组织配送，会产生很多问题。这些问题归纳起来，包括以下几点：1）服务质量的下降。电子商务的特征是交易量巨大和交易速度极快，而传统物 流配送的特点是人工调度、反应时间长。信息流与物流的矛盾会导致整个电子商 务客户服务的低效。也许客户可以在几十秒内完成一次交易，却要等上一个星期 才能收到货物，这样的服务只能逐渐失掉客户。2）物

5、流成本控制困难。传统的物流配送大多是由人工调度的，在交易量较小的 情况下，可以合理地安排配送，降低成本。一旦交易量增加、交易速度加快，配 送调度就会超出人工的能力范围，会导致大量的不合理调度的出现，物流成本无法控制。3）增加城市交通的负担。物流配送调度的不合理，会使物流配送的行车路线变 长，导致在运车辆增加，从而给本已拥挤的城市交通加重负担。要解决以上的问题，使物流配送调度满足以下目标准时送货。就是要客户选择货物送达他们指 定地点的时间，要按照每个客户的时间要求安排物流配送。总成本最低。总 行车路径最短。当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重 要标志，也成为城市经济

6、发展水平的体现，被喻为促进经济发展的“加速器”。物流配送是一种先进的现代物流形式，它不但给供应者和需求者带来降低物流成本、 享受优质服务的直接效益，而且还能为社会节省运输车次、缓解交通压力、减少 运输污染、保护生态环。而今，由于小批量、多批次的及时配送方式的发展，运输费用正在逐年提升，许多企业的运费已经超越了库存费用，城市交通与改善物流的矛盾也愈演愈烈， 城市交通混杂、阻塞、车辆噪音、尾气污染、车祸事故和能源浪费等现象更加严 重，若物流路线选择的不合理，还会使物流配送的行车路线变长，导致在运车辆 增加，从而给本己拥挤的城市交通加重负担，这就势必要选择合理有效的运输路 线来减少重复运输、倒流运输

7、、迁回运输、单程运输和空驶等，这样不仅提高配 送效率，控制了物流成本，而且可限制车辆在城市中的运行时间，有效缓解城市 交通负担。物流配送系统中最优路线的选择问题一直都是配送中心关注的焦点，对于城 市配送而言，由于受交通堵塞和各种交通管制的影响，导致配送路径寻优更具复 杂性。所以本文通过对具有动态的交通堵塞和交通拥挤限制信息及静态禁止通行 等限制信息的实际配送网络的描述，提出解决两种限制情况下配送网络寻优的方 法，建立了配送网络图中权重确定模型，并基于此进一步建立了城市物流配送决 策系统数学模型，运用二分领域搜索算法对其寻优。针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角 度

8、，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合 理化:一方面通过建立一种快速、高效、网络化的物流组织系统降低物流成本，增 加利润;另一方面，增强家乐福的竞争力，使其配送系统相应得到优化，从而使家 乐福物流取得阶段性成果，因此，对家乐福物流配送体系及其路线的优化问题进 行研究将具有很大的现实意义。1.2国内外物流配送路线优化研究现状物流配送路线优化，是物流系统优化中关键的一环，也是电子商务活动不可 缺少的内容。对物流配送路线优化，可以提高物流经济效益，实现物流科学化。 可以说对物流配送路线优化理论与方法进行系统研究是物流集约化发展，构建综 合物流系统，建立现代调度指挥系统，

9、发展智能交通运输系统和开展电子商务的 基础。配送路线合理与否对配送速度，成本，效益影响很大，特别是多用户配送线 路的确定更为复杂。采用科学的，合理的方法来确定配送路线，是配送活动中非 常重要的一项工作。路线优化问题最早是由 DANTZIG和RAMSER于1959年提出的，由于这一 问题的理论涉及很多学科，很多实际问题的理论抽象都可归结为这一类问题，应 用前景广阔，所以很快便引起运筹学，应用数学，图论与网络分析，物流学科， 交通运输工程，管理科学与工程，计算机应用等学科的专家，工程技术人员和管 理者的极大重视，自此，一直成为运筹学与组合优化领域的前沿与研究热点问题在国外，物流配送路线优化问题已广

10、泛应用于生产，生活的各个方面。如 报纸投递及线路的优化，牛奶配送及送达线路的优化，电话预订货物的车辆 线路设计，垃圾车的线路优化，连锁商店的送货的线路优化等等。目前，研 究水平已有很大发展，其理论成果除在汽车运输领域外，在水运，航空，通 讯，电力，工业管理，计算机应用等领域也有一定的应用，还用于航空乘务 员轮班安排，轮船公司运送货物经过港口与货物安排的优化设计，交通车线 路安排，生产系统中的计划与控制等多种组合优化问题。在国内，该问题的系统研究还不多见。近年来有李军等人课题组承担的国 家自然科学基金不确定信息条件下动态车辆路径等研究工作。纪寿文等人 根据深圳市科技园的实际路网图，采用神经网络的

11、方法对运输车辆优化调度进行 了试验研究。王正彬等人在分析 VRP现有启发式算法的基础上，建立了考虑线路 安排的物流配送方案模型，并提出了求解该问题的搜索算法。2. 家乐福超市配送路线现状2.1家乐福超市概况成立于1959年的家乐福集团是大卖场业态的首创者，是欧洲第一大零售商，世界第二大国际化零售连锁集团。现拥有 11,000多家营运零售单位，业务范围遍及世界30个国家和地区集团以三种主要经营业态引领市场：大型超市，超市以及折扣店。此外，家 乐福还在一些国家发展了便利店和会员制量贩店。2004年集团税后销售额增至726.68亿欧元，员工总数超过 43万人。2005年，家乐福在财富杂志编排的全球

12、500强企业中排名第22位。法国家乐福集团是大型超级市场(Hypermarket )概念的创始者，于 1963 年在法国开设了世界上第一家大型超市。1999年8月30日家乐福兼并普罗莫代 斯组成世界第二大零售集团。如今家乐福已发展成为欧洲最大、全球第二大的零 售商。2004年，家乐福集团被财富杂志评为全球 500强企业的第22位。家乐福于1969年开始进入国际市场，目前在世界上 31个国家和地区拥有一 万多家销售网点，涉及的零售业态包括大卖场、超级市场、折扣店、便利店、仓 储式商店与电子商务，集团的50万名员工正致力于为20亿消费者服务。家乐福 集团建立了全球性的采购网络，向不同国家和地区的供

13、应商采购具有市场竞争力 的商品。家乐福的经营理念是以低廉的价格、卓越的顾客服务和舒适的购物环境为广 大消费者提供日常生活所需的各类消费品。家乐福对顾客的承诺是在价格、商品 种类、质量、服务及便利性等各方面满足消费者的需求。家乐福力争通过自己的 努力成为当地社区最好的购物场所，为消费者带来更多的实惠和便利，并携手和 各商业伙伴为当地经济的繁荣做出贡献。家乐福于1995年进入中国后，采用国际先进的超市管理模式，致力于为社会 各界提供价廉物美的商品和优质的服务，受到广大消费者的青睐和肯定，其“开 心购物家乐福”、“一站式购物”等理念已经深入人心。如今，家乐福已成功地 进入了中国的25个城市，在北至哈

14、尔滨、南至深圳、西至乌鲁木齐、东至上海的中国广袤土地上开设了 109家大型超市，聘请3万多名员工。在在华外资零售企业中处于领先地位。家乐福还向中国引进迪亚折扣店和冠军食品超市两种业态。2004年，家乐福(中国)被国内媒体评为“在华最有影响力的企业”之一。2004年约有2亿多人光顾了家乐福在中国的各门店，其中68%为女性，32% 乘公共汽车，37%步行，15%骑自行车，9%乘坐出租车或小轿车前往家乐福购物。 家乐福成为了各地居民的好邻居。通过多年的经营，家乐福向中国的商业界输入了大型超市经营管理方面的技 能和先进经验，并对商品采购、营销管理、资产管理以及人力资源开发等各方面 实现现代化和本地化，

15、为当地经济发展做了积极的贡献。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配送中心与分店之间，分店

16、与分店之间的距离(0点表示配送中心)0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.862173.61.427153.6237.113625626.41306.12136101611191614181310137.15.17.2211234.57.86.1018345131314119.2209.24.51519.25196.1422112118050145.43112810382615331718143617530393634500374526414

17、34020253624344139153369.22.8105143708.3189.26.44.224121204.2114.5234.5717616135.4458.30269.23.65.132209.22712148.5311289.22111133126182602725237.11118214161712179177191412419.29.22705.86.132189.528132013289.210163.616118436.43.6255.802.231187.22611158.5289.211131.4149.210404.25.1236.12.2029165248.51

18、47.1267.11215271820382024327.1323129014245.12023249.22316.415139.226212201118181614011119.11714108.93518.53.6104.515319.2189.57.2524110193.6125223.646111231315332202722826245.111190161819111954157.17.111734.2121413118.5209.13.6160105.1195.164111135.19.2184111416201514231712181007.126157119.267.25143

19、4.58.517138.57.124145195.17.10248.5891152521193612331122828269.21022111926240199528.56126.11734.512179.29.27.1238.93.6195.1158.519003222车辆数分析所需车辆数分析（家乐福配送中心一年（365天）的车辆调度）:表2-3车辆调度情况车辆运用数101291110111010891011运用天数2530364246494838241386表2-4车辆运用数所占比率车辆运用数相对比率累计比率120.070.07120.080.15110.100.25100.120.371

20、20.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商品品种分析超市以满足消费者对基本生活用品一次性购买需要为经营宗旨，是一种经营品项较多的零售业态。下面对商品进行分类分析。、大分类大分类是超市最粗线条的分类。大分类的主要标准是商品特征，如畜产、水产、果菜、日

21、配加工食品、一般食品、日用杂货、日用百货、家用电器等。为了便于管理，超级市场的大分类一般以不超过 10个为宜。二、中分类中分类是大分类中细分出来的类别。其分类标准主要有：按商品功能与用途划分。如日配品这个大分类下，可分出牛奶、豆制品、冰品、 冷冻食品等中分类。(2) 按商品制造方法划分。如畜产品这个大分类下，可细分出熟肉制品的中分类，包括咸肉、熏肉、火腿、香肠等。(3) 按商品产地划分。如水果蔬菜这个大分类下，可细分出国产水果与进口水果的 中分类。三、小分类小分类是中分类中进一步细分出来的类别。主要分类标准有：(1) 按功能用途划分。如“畜产”大分类中、“猪肉”中分类下，可进一步细分出“排骨”

22、、“肉米”、“里肌肉”等小分类。(2) 按规格包装划分。如“一般食品”大分类中、“饮料”中分类下，可进一步细分出“听装饮料”、“瓶装饮料”、“盒装饮料”等小分类。(3) 按商品成份分类。如“日用百货”大分类中、“鞋”中分类下，可进一步细分出“皮鞋”、“人造革鞋”、“布鞋”、“塑料鞋”等小分类。(4) 按商品口味划分。如“糖果饼干”大分类中、“饼干”中分类下，可进一步细分出“甜味饼干”、“咸味饼干”、“奶油饼干”、“果味饼干”等小分类。四、单品单品是商品分类中不能进一步细分的、完整独立的商品品项。如上海申美饮料有限公司生产的“ 355毫升听装可口可乐”、“ 1 . 25升瓶装可口可乐”、“2升瓶

23、 装可口可乐”、“2升瓶装雪碧”，就属于四个不同单品。需要说明的是，商品分类并没有统一固定的标准，各超市公司可根据市场和自身的实际情况对商品进行分类。但商品分类应该以方便顾客购物、方便商品组合、体现企业特点为目的。具体分类如下表所示：食品日用品1.粮油1.日化产品粮食米面 淀粉食用油 主食熟食 豆制品其他粮油2.日杂用品2保蔬3.家居用品新鲜蔬菜新鲜水果食用菌蔬菜制品 干果|坚果 果蔬深加工 其他果蔬4.清洁用品及用具3.水产5餐具鲜活水产品 粗加工水产品 精加工水产品其他水产6.厨具畜产7.日用小家电鲜活畜禽鲜肉类鲜蛋类鲜奶类肉制品蛋制品 乳制品蜜制品8.家用塑料制品4.糖酒饮料9.首饰糖类

24、酒类茶叶软饮料冲饮品冷10.衣物饮 咖啡豆1可可 其他糖酒饮料5.加工食品11.箱包，袋，皮具保健食品 休闲食品 方便食品 罐头食 品 特色食品 调味品 其他加工食品12.文体用品6.烟草13.日用小五金烟叶香烟其他烟草14.休闲家具7.添加剂15.个人护理用品食品添加剂添加剂 发酵制品16.卫浴用品8.包装机17.炊具加工设备食品包装其他机械包装制冷设备18.灶具表2-6 商品品种2.3家乐福超市配送现有路线问题分析家乐福的配送系统和信息系统是较落后的家乐福至今没有在中国建立起统一 的配送体系,且计算机系统的开发和建立，要落后于竞争对手沃尔玛好几年家乐福 这种”滞后”的配送系统与信息系统是其

25、战略规划的成果，因为商品的集中配送是 连锁商业带来的，但是目前中国连锁商业基础非常薄弱，只有通过大的配送系统的 完善和整合才能形成规模的，高效的，社会化的物流配送系统.家乐福配送路线的分配存在以下几方面的问题：(1) 物流公司与门店之间的分布太分散，难以形成固定的配送线路(2) 送货难以达到及时(3 )难以保证适量的库存而不压货(4) 路线里程未达最短(5) 费用消耗大(6) 劳力消耗大，运力难以适当分配，难以调度车辆(7 )配送车辆吨位公里数大(8) 配送未实现自动化(9) 配送未实现网络化(10 )配送服务未实现系列化3. 配送路线优化建模与求解3.1研究对象目标设定物流配送常考虑以最小化

26、总运输成本或距离最短为目标，总运输成本主要由 由两部分组成：(1)运输固定成本：如服务所有客户所需要的车辆数、总行驶距离(或 总行驶时间)和与所使用的车辆有关的固定费用；(2)运输营业成本：如司机的管理 费，各种工作人员的工资等家乐福超市的业务运输成本是物流总成本的主要组成部分，占有56%。因此降低公司运输成本成为提高公司效益的直接有效途径。公司自有货运成本各项比例如下表:表3-1公司货运成本比例表固定费用（22%）营业费用（78%）折旧费（租赁费）：人力（司机）：装卸工具，车库，办公室，工资，额外福利，装卸费水电，通迅，差旅费，公务车费用业务印刷费投资利息：车辆运营成本：车辆，车库，办公室燃

27、料（燃油，润滑油，过滤器）管理成本：维修费（人工费+零部件）职工月工资，额外福利，旅游和娱乐费用，轮胎费，交通规费，养路费房屋维修费，牌照费，职工培训费，宣传大修理基金提存费及业务手续费。道路服务：通行费，保险，许可证和登记费高速公路使用费，燃油司机费用占总营业成本的29.4% ;维修费和折旧费占总营业成本的 19.5% ;其它的运营费用占总营业成本的 32.6% ;燃料费占总营业成本的18.5% ；表上所述：公司车辆运营成本占据了总运输成本的78%。随着道路服务政策的变化，车辆营业成本在公司总成本中所占比例日益增大。距离是影响运输成本 的主要因素，因为它直接对劳动、燃料和维修保养等变动成本发

28、生作用。针对公 司当前成本构成状况，可以知道：通过优化公司配送路线，减少运输车辆行驶总里程，可以减少车辆燃油费和道路服务费支出，进而减少物流总成本因此，本文针对家乐福配送中心车辆路线优化问题，提出的目标是：总运输成本最小化。车辆路线图3-1家乐福的配送模式此问题可以描述为：这是一种分送式配送模型，是由一个供应点对多个客户的共同配送。对配送中心负责的需求网点（家乐福分店），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过各个分店各一次，最后返回配送中心,并在满足一定的约束条件下(如车辆容量限制、行驶里程限制、时间限制、顾客需 求量、交发货时间等)，达到费用最少的目标。本文研究的是不考虑

29、时间窗的非满载车辆优化调度问题。表述如下：将货物从配送中心配送到各分配送中心，由分配送中心派出容量为的货车承运， 现有m辆 车，各分店对所需求的货物有一定的要求，第i个分店的货运量为gi(i=1 ,2I) 已知，在途中只有卸货任务，完成任务后返回配送中心，求满足配送需求的费用最少 行车线路。图3-2家乐福配送体系结构3.2模型的构建为建模方便，需考虑以下几个前提假设条件：(1 )配送中心不会出现缺货的可能并且对顾客的基本配送资料(需求量、地理位 置)为已知，配送中心的位置也已知；(2)不考虑配送时间限制，即客户对货物的需求没有时间窗的规定；(3 )不考虑每辆车为每个客户的服务时间，即不考虑每个

30、客户的卸货时间；(4) 一个配送中心根据配送条件可以负责多个客户，即一个配送中心服务多个客户;(5) 车辆由配送中心出发，服务被指定的需求点后，再返回配送中心，区域内的需求点假设为固定数量且位置已知，不发生变动。(6) 配送中心拥有一定数量的单一车型的配送车辆，且每辆车的容量已知。(7) 每条配送路径上各客户需求量之和不超过配送车辆的容量；(8 )每个客户只能由一辆配送车辆送货；(9 )每辆车配送总里程不超过其最大行驶距离；(10) 各道路均顺畅，不考虑交通堵塞拥挤等特殊情况。将配送中心编号为0，车辆编号为k，任务编号为i=1,2.,所有车型载重 量单一，每辆汽车的最大载重量为g，需要向L个需

31、求点送货，每个需求点的需求 量为，并且满足，需求点i到j的运距为，配送中心到各个需求点的距离为，再设 为第辆汽车配送的需求点数(=0表示未使用第辆汽车)，用集合表示第k条路径， 其中的元素表示需求点在路径中的顺序为(不包括配送中心)，令=0表示配送中心，为每辆车单位里程的行驶费用，为每辆车的派遣费用，考虑运输量约束，停车点车辆数目等约束，可以定义如下的基本模型：(3-1)(3-2)(3-3)(3-4)(3-5)(3-6)在上述模型中各个公式所代表的涵义如下：(3-1 )式为目标函数，求总的配送费用最低;（3-2 ）式用于保证每条路径上各个需求点的需求量和不超过汽车的载重量;（3-3 ）式表明每

32、条路径上的需求点数不超过总需求点数；（3-4 ）式表明每个需求点都得到配送服务；（3-5 ）式表示每条路径的需求点的组成；（3-6）式表示当第辆汽车服务的客户数大于或等于 1时，说明该辆汽车参加 了配送，则取，当第k辆汽车服务的客户数小于1时，表示未使用该辆汽车，因 此取；3.3节约算法3.3.1节约算法的基本原理节约算法的核心思想是将运输问题中存在的两个回路（0，i，0）和（0， j，0）合并成一个回路（0，0）。在上面的合并操作中，整个 运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运 输距离。相应的变化值，叫做节约距离，如式（1）所示。(1)调整过程如图3所示调整前

33、调整后图3-3节约算法的图像描述3.3.2节约里程算法主要步骤已知条件:需求点集=1,2,n,各点需求量，各点间最短距离。第一步,形成一个初始解。确定各车辆配送点集令,=1,2,n （先采取单点配送）。第二步，进行节约度的计算。计算所有点对的节约度，然后对计算结果进行升序排列。第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始，直到节约里程的队列空为止，重复下列步骤：按照节约里程队列从大到小的顺序，分 析客户i和j之间合并的可能性（是否满足装载限制条件、不在同一路径内以及合并 次数不超过2）,将i, j连接起来，即可令。如果不是这样，则从节约里程队列中去除当 前的节约里程，分析下

34、一个客户对。3.3.3基于节约算法的配送路线优化表3-2每个分店（一年365天）平均每天的需求量分店12345678910需求量（吨）2324123513分店11121314151617181920需求量（吨）2342121322现有路线是固定不变且为已知，每条线路行驶距离可由表3-2求得，配送中心与商店之间，商店与商店之间的距离分析如下表：表3-3配送中心与分店之间，分店与分店之间的距离（0点表示配送中心）0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.81139

35、2.862173.61.427153.6237.113625626.41306.12136101611191614181310137.15.17.2211234.57.86.1018345131314119.2209.24.51519.25196.1422112118050145.4311281038261533171814361753039363450037452641434020253624344139153369.22.8105143708.3189.26.44.224121204.2114.5234.5717616135.4458.30269.23.65.132209.22712148

36、.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.610

37、4.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.512179.29.27.1

38、238.93.6195.1158.5190设每个车辆的运输能力是8吨，根据案例可知，家乐福平均每天所用车辆数为12辆。现在用节约算法对该配送线路问题进行求解 根据配送中心与分店之间，分店与分店之间的距离距离表，计算出用户间的节约里程，表3-4节约值矩阵表12345678910111213141516171819201025.4038.74.804237.48.50530.40.520618.45.68.717.22.207237.48.533.6217.9080.24.60.70.213.20.40.209224.47.52761724.8-0.801024.46.49.530318.829.

39、40.227.201123.65.48.32531824.9-0.823.926.801203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.44.43.47.401416.94.98.55.52.516.716.3-0.31617.316.5-0.53.901504.40.50200.2118.201020.96.40.5016-0.14.38.510110100.29109.502.39.90017014.36.31509.2144.28121030.47.54601815.28.48.717.20.213.917.71.413.2

40、16.715.10.21.212.71.29.113.201920.40.51301.2112.243220.811.41.515100.202014.52.96.913.55.513.213.50.716.315.314.40.5613.40.58.44.59.24.50从表3-4中选出节约值最大值为33.6，其对应的两点为4、7。4、7两处的需求量之和为7,未超过一辆车的运输能力8，因此，连接4、7成回路，即047-0.再将顶点4和7的节约值赋为0.结果如表3-5所示表3-512345678910111213141516171819201025.4038.74.804237.48.5053

41、0.40.520618.45.68.717.22.207237.48.50217.9080.24.60.70.213.20.40.209224.47.52761724.8-0.801024.46.49.530318.829.40.227.201123.65.48.32531824.9-0.823.926.801203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.44.43.47.401416.94.98.55.52.516.716.3-0.31617.316.5-0.53.901504.40.50200.2118.201020.96.

42、40.5016-0.14.38.510110100.29109.502.39.90017014.36.31509.2144.28121030.47.54601815.28.48.717.20.213.917.71.413.216.715.10.21.212.71.29.113.201920.40.51301.2112.243220.811.41.515100.202014.52.96.913.55.513.213.50.716.315.314.40.5613.40.58.44.59.24.50从表3-5中选出节约值最大为30 ,其对应的两个顶点为4、10。如果连接4和10，则与上述线路合并，其

43、总需求量为10，超过一辆车的运输能力8，因此，4和10不能连接，7和10也不能连接，则将4、10与7、10的节约值赋为0。继续选出节约值最大为30,其对应两个顶点为5、19。5和19两处的需求 量之和为3，未超过一辆车的运输能力8，因此，连接,5、19成回路，即0-5-19-0. 再将顶点5和19的节约值赋为0。继续选出节约值最大为27.2，其对应两个顶点为9、10。9和10两处的需求 量之和为4,未超过一辆车的运输能力8，因此，连接9、10成回路，即0-9-10-0. 再将顶点9和10的节约值赋为0。选出节约值最大为27,其对应的两个顶点为4、9。如果连接4和9，则与上 述两条线路合并，其总

44、需求量为 11，超过一辆车的运输能力8，因此，4和9不 能连接，7和9也不能连接，则将4、9与7、9的节约值赋为0。选出节约值最大为26.8，其对应的两个顶点为10、11。如果连接10和11 ，则与上述线路合并，其总需求量为 6，未超过一辆车的运输能力 8,因此，连接0-9-10-11-0 成回路，则将9、11与10、11的节约值赋为0。同时，由于顶点10成回路的中间点，则与顶点10相关的节约值都赋为0，表示顶点10不可能再 与其他点相连，其结果如下表所示。表3-612345678910111213141516171819201025.4038.74.804237.48.50530.40.52

45、0618.45.68.717.22.207237.48.50217.9080.24.60.70.213.20.40.209224.47.506170-0.801000000000001123.65.48.32531824.9-0.80001203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.403.47.401416.94.98.55.52.516.716.3-0.316016.5-0.53.901504.40.50200.2118.200020.96.40.5016-0.14.38.510110100.2909.502.39.90017014.36.31509.2144.2801030.47.54601815.28.48.717.20.213.917.71.413.2015.10.21.212.71.29.113.201920.40.5101.2112.240220.811.41.515100.202014.52.96.913.55.513.213.50.716.3014.40.5613.40.58.44.59.24.50选出节约值最大为25，其对应的两个顶点为4、11。如果连接4和