超市物流配送路线优化范本

1、学年论文之家乐福超市物流配送路线优化 专业 物流工程 班级 姓名 学号 日期 摘要在物流配送业务中，合理确定配送路径是提商服务质量,降低配送成本,增加经济效益的重要手段。物流配送系统中最优路线的选择问题一直差不多上配送中心关注的焦点，针对当前家乐福物流配送体系不完善等方面的现状,本文从可持续进展的角度,用系统的观念,来研究家乐福物流配送体系，优化配送路线，使配送体系合理化。通过对家乐福超市现有物流配送路径的分析研究,发觉其中存在的一些问题,并由此提出解决方法,结合背景材料，建立了数学模型,运用遗传算法对家乐福物流配送路线进行优化选择,并得出结果。由此可见,家乐福超市原有的物流配送路线还能够进行

2、再优化,从而达到运输成本最小化的目标。关键词：物流配送;路径优化;节约里程算法目 录 TOC o 1-3 h z HYPERLINK N:整理后l1.绪论 PGEREF _oc360615011 1HYPERLIK l _Toc3606012.1 选题目的和意义PAGEREF Toc365012 h 1HERIN l _Tc36061503 12 国内外物流配送路线优化研究现状PAGERF _oc30613 h2HYPERLINK N:整理后2. 家乐福超市配送路线现状 PAEFTo36065014 3HYPERLINK N:整理后l2. 家乐福超市概况 PAGEREF _Toc3606515

3、 h 3HYPERLINK N:整理后 l _To3606506.2家乐福超市配送路线作业现状 PGE _Tc36061516 h4HYPERLINK N:整理后22.1 配送距离分析 PAGREF_36015017 h 4HYPERLINK N:整理后l2.22 车辆数分析 AGEE_oc36518h 5HYPERLINK N:整理后.3 需求量分析 PAGER Tc3606501 6 YPERI l _Toc361520 2.2. 商品品种分析PAGER_Toc3606100 h 6HYPERINK l _o36521 2.3 家乐福超市配送现有路线问题分析PGEREF Toc606102

4、 h 7HYPERLINK N:整理后3.配送路线优化建模与求解 GEEF Toc3606122 h 9HYPERLINK N:整理后3.研究对象目标设定PGERE Toc6061523h 9HYPERLINK N:整理后3.2 模型的构建PAGEREFToc36061502 11HYPERLINK N:整理后3.节约算法 PAGREF _oc360610 h 12HYPERLINK N:整理后 l _Toc3606150263.31节约算法的差不多原理 PAGEREF To36606h 12 HYELIK loc360615027 .2节约里程算法要紧步骤 GEREF _Toc3606152

5、 1HYPERLINK N:整理后.3基于节约算法的配送路线优化PAEEF oc30102 h 3HYPERLINK N:整理后33.4优化后的配送线 PAF _To3661502h HPERLI l Tc3601530 4.优化结果分析 PAEREF _Toc65030 h 25YPERLIN l_c60615031 4.1 优化前结果 AGEREF _oc3661503 h 25 HYPIN l_Toc3661502 42优化后结果 PAGEE _oc6061532 2HYPERLINK N:整理后43结论 PAGREF _Toc3606503 h26 HYPELINK l _Toc306

6、5034 .总结与建议 PGEREF_To36015034 h 27HYPERLINK N:整理后l参考文献: PAGEREF _T66150 h 281.绪论1.1 选题目的和意义配送是一项专门的、综合性的物流运动，其运行和进展有着深刻的社会根源和历史背景。在市场经济体系中，物流配送如同人体的血管，把国民经济各个部分紧密地联系在一起。配送是物流中一个重要的直接与消费者相连的环节,是将物资从物流结点送达收货人的过程，是在集货、配货基础上,完全按用户要求，包括种类、品种搭配、数量、时刻等方面的要求所进行的运送,是“配”和“送”的有机结合形式。其要紧包括集货作业、配货作业、车载物资的配装、配送线路

7、的确定。在生活中，基于电子商务的物流配送业务量逐渐增加,假如还沿用往常的物流方法来组织配送,会产生专门多问题。这些问题归纳起来，包括以下几点:1)服务质量的下降。电子商务的特征是交易量巨大和交易速度极快,而传统物流配送的特点是人工调度、反应时刻长。信息流与物流的矛盾会导致整个电子商务客户服务的低效。也许客户能够在几十秒内完成一次交易,却要等上一个星期才能收到物资，如此的服务只能逐渐失掉客户。2)物流成本操纵困难。传统的物流配送大多是由人工调度的，在交易量较小的情况下，能够合理地安排配送，降低成本。一旦交易量增加、交易速度加快，配送调度就会超出人工的能力范围，会导致大量的不合理调度的出现，物流成

8、本无法操纵。3)增加都市交通的负担。物流配送调度的不合理，会使物流配送的行车路线变长，导致在运车辆增加,从而给本已拥挤的都市交通加重负担。要解决以上的问题，使物流配送调度满足以下目标准时送货。确实是要客户选择物资送达他们指定地点的时刻,要按照每个客户的时刻要求安排物流配送。总成本最低。总行车路径最短。当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重要标志,也成为都市经济进展水平的体现,被喻为促进经济进展的“加速器”。物流配送是一种先进的现代物流形式,它不但给供应者和需求者带来降低物流成本、享受优质服务的直接效益，而且还能为社会节约运输车次、缓解交通压力、减少运输污染、爱护生态

9、环。而今，由于小批量、多批次的及时配送方式的进展,运输费用正在逐年提升，许多企业的运费差不多超越了库存费用,都市交通与改善物流的矛盾也愈演愈烈,都市交通混杂、堵塞、车辆噪音、尾气污染、车祸事故和能源白费等现象更加严峻,若物流路线选择的不合理，还会使物流配送的行车路线变长，导致在运车辆增加,从而给本己拥挤的都市交通加重负担,这就势必要选择合理有效的运输路线来减少重复运输、倒流运输、迁回运输、单程运输和空驶等,如此不仅提高配送效率,操纵了物流成本,而且可限制车辆在都市中的运行时刻，有效缓解都市交通负担。物流配送系统中最优路线的选择问题一直差不多上配送中心关注的焦点,关于都市配送而言，由于受交通堵塞

10、和各种交通管制的阻碍，导致配送路径寻优更具复杂性。因此本文通过对具有动态的交通堵塞和交通拥挤限制信息及静态禁止通行等限制信息的实际配送网络的描述,提出解决两种限制情况下配送网络寻优的方法,建立了配送网络图中权重确定模型，并基于此进一步建立了都市物流配送决策系统数学模型，运用二分领域搜索算法对其寻优。针对当前家乐福物流配送体系不完善等方面的现状,本文从可持续进展的角度，用系统的观念，来研究家乐福物流配送体系,优化配送路线，使配送体系合理化:一方面通过建立一种快速、高效、网络化的物流组织系统降低物流成本,增加利润;另一方面,增强家乐福的竞争力,使其配送系统相应得到优化，从而使家乐福物流取得时期性成

11、果,因此，对家乐福物流配送体系及其路线的优化问题进行研究将具有专门大的现实意义。1.2国内外物流配送路线优化研究现状物流配送路线优化，是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。对物流配送路线优化,能够提高物流经济效益,实现物流科学化。能够讲对物流配送路线优化理论与方法进行系统研究是物流集约化进展，构建综合物流系统,建立现代调度指挥系统,进展智能交通运输系统和开展电子商务的基础。配送路线合理与否对配送速度,成本,效益阻碍专门大，特不是多用户配送线路的确定更为复杂。采纳科学的,合理的方法来确定配送路线，是配送活动中特不重要的一项工作。路线优化问题最早是由DANTZIG和RER于1

12、59年提出的,由于这一问题的理论涉及专门多学科,专门多实际问题的理论抽象都可归结为这一类问题，应用前景宽敞，因此专门快便引起运筹学,应用数学，图论与网络分析，物流学科,交通运输工程，治理科学与工程,计算机应用等学科的专家,工程技术人员和治理者的极大重视，自此，一直成为运筹学与组合优化领域的前沿与研究热点问题。 在国外，物流配送路线优化问题已广泛应用于生产,生活的各个方面。如报纸投递及线路的优化,牛奶配送及送达线路的优化，电话预订物资的车辆线路设计，垃圾车的线路优化,连锁商店的送货的线路优化等等。目前,研究水平已有专门大进展,其理论成果除在汽车运输领域外，在水运,航空,通讯,电力，工业治理,计算

13、机应用等领域也有一定的应用，还用于航空乘务员轮班安排,轮船公司运送物资通过港口与物资安排的优化设计,交通车线路安排,生产系统中的打算与操纵等多种组合优化问题。在国内，该问题的系统研究还不多见。近年来有李军等人课题组承担的国家自然科学基金不确定信息条件下动态车辆路径等研究工作。纪寿文等人依照深圳市科技园的实际路网图,采纳神经网络的方法对运输车辆优化调度进行了试验研究。王正彬等人在分析V现有启发式算法的基础上,建立了考虑线路安排的物流配送方案模型，并提出了求解该问题的搜索算法。 2.家乐福超市配送路线现状2家乐福超市概况成立于1959年的家乐福集团是大卖场业态的首创者，是欧洲第一大零售商，世界第二

14、大国际化零售连锁集团。现拥有11,000多家营运零售单位，业务范围遍及世界30个国家和地区。集团以三种要紧经营业态引领市场：大型超市,超市以及折扣店。此外，家乐福还在一些国家进展了便利店和会员制量贩店。2004年集团税后销售额增至7268亿欧元,职员总数超过43万人。205年，家乐福在财宝杂志编排的全球500强企业中排名第22位。法国家乐福集团是大型超级市场（yperarket）概念的创始者,于163年在法国开设了世界上第一家大型超市。199年8月30日家乐福兼并普罗莫代斯组成世界第二大零售集团。现在家乐福已进展成为欧洲最大、全球第二大的零售商。20年，家乐福集团被财宝杂志评为全球5强企业的第

15、22位。家乐福于969年开始进入国际市场,目前在世界上31个国家和地区拥有一万多家销售网点,涉及的零售业态包括大卖场、超级市场、折扣店、便利店、仓储式商店与电子商务,集团的5万名职员正致力于为20亿消费者服务。家乐福集团建立了全球性的采购网络,向不同国家和地区的供应商采购具有市场竞争力的商品。家乐福的经营理念是以低廉的价格、卓越的顾客服务和舒适的购物环境为宽敞消费者提供日常生活所需的各类消费品。家乐福对顾客的承诺是在价格、商品种类、质量、服务及便利性等各方面满足消费者的需求。家乐福力争通过自己的努力成为当地社区最好的购物场所，为消费者带来更多的实惠和便利,并携手和各商业伙伴为当地经济的繁荣做出

16、贡献。家乐福于95年进入中国后,采纳国际先进的超市治理模式，致力于为社会各界提供价廉物美的商品和优质的服务,受到宽敞消费者的青睐和确信，其“快乐购物家乐福”、“一站式购物”等理念差不多深入人心。现在,家乐福已成功地进入了中国的2个都市，在北至哈尔滨、南至深圳、西至乌鲁木齐、东至上海的中国广袤土地上开设了09家大型超市,聘请万多名职员。在在华外资零售企业中处于领先地位。家乐福还向中国引进迪亚折扣店和冠军食品超市两种业态。2004年，家乐福(中国)被国内媒体评为“在华最有阻碍力的企业”之一。2004年约有2亿多人光顾了家乐福在中国的各门店，其中68为女性，32%乘公共汽车，%步行，1%骑自行车，9

17、%乘坐出租车或小轿车前往家乐福购物。家乐福成为了各地居民的好邻居。通过多年的经营，家乐福向中国的商业界输入了大型超市经营治理方面的技能和先进经验，并对商品采购、营销治理、资产治理以及人力资源开发等各方面实现现代化和本地化,为当地经济进展做了积极的贡献。2.2 家乐福超市配送路线作业现状2.2.配送距离分析(1)配送需求点坐标：现在以家乐福物流配送中心为原点(0,）,建立直角坐标系,各商店的坐标如下表所示：X(k）;Y(k） 表2-分店所在地坐标分店与配送中心间距离坐标XY1892453240253-30778869151019102-8-1134-514657-813417-508219-15

18、2083 i，20;(2) 现有路线是固定不变且为已知,每条线路行驶距离可由表2-3求得, 配送中心与商店之间,商店与商店之间的距离分析如下表: 表2-2 配送中心与分店之间,分店与分店之间的距离(0点表示配送中心)12467910112131451671812026.4.5239.2179.1131648.51511958.12017.8132.86173.61.42753.37.113626.130.1236106119161481103.151722123.7.86101834531311.222.151921961421118050145431813826153171814353039

19、36300374526414405324441391536922.8051470.319.26.4.224121204.2114.54.571766135.58.3069.613220.2212148.531289.211131268260272523.11821461712179171914.270586.13289.2813201329.2116.11843.6255.802.2187.26111585289.21113.4491040.2.12.12.2029165245147126115272038202437.1323290142420349.23136.41513.22625122

20、0111116141119.117418.98.53.10.553619.189.7.52110193.612522.1512315332402722826245.1190618916577.114.11413118.520.3.66010.119511711135.19.2184111410154217121107.168.267.2143.85718.57.4141917.1048.5191522119153228286.2102192401920.5626117517.2972393.6195.18.902.2.车辆数分析所需车辆数分析（家乐福配送中心一年(36天）的车辆调度):表23车

21、辆调度情况车辆运用数10291111100811运用天数25036424644884136表-4车辆运用数所占比率车辆运用数相对比率累计比率1070.720.080.15110100.2500.120.37120.130.5110.130.10130.7100.10.610.07.3150.0.97130.020.9110.0100则家乐福平均每天所用车辆数为1辆。2.3 需求量分析表25每个分店（一年365天)平均每天的需求量分店123456790需求量2412351分店11121341516181920需求量23132.2. 商品品种分析超市以满足消费者对差不多生活用品一次性购买需要为经营

22、宗旨,是一种经营品项较多的零售业态。下面对商品进行分类分析。一、大分类 大分类是超市最粗线条的分类。大分类的要紧标准是商品特征，如畜产、水产、果菜、日配加工食品、一般食品、日用杂货、日用百货、家用电器等。为了便于治理,超级市场的大分类一般以不超过1个为宜。二、中分类 中分类是大分类中细分出来的类不。其分类标准要紧有:（1)按商品功能与用途划分。如日配品那个大分类下，可分出牛奶、豆制品、冰品、冷冻食品等中分类。 (2）按商品制造方法划分。如畜产品那个大分类下，可细分出熟肉制品的中分类，包括咸肉、熏肉、火腿、香肠等。(3)按商品产地划分。如水果蔬菜那个大分类下,可细分出国产水果与进口水果的中分类。

23、 三、小分类 小分类是中分类中进一步细分出来的类不。要紧分类标准有： ()按功能用途划分。如“畜产”大分类中、“猪肉”中分类下,可进一步细分出“排骨”、“肉米”、“里肌肉”等小分类。 ()按规格包装划分。如“一般食品”大分类中、“饮料”中分类下，可进一步细分出“听装饮料”、“瓶装饮料”、“盒装饮料”等小分类。(3)按商品成份分类。如“日用百货”大分类中、“鞋”中分类下，可进一步细分出“皮鞋”、“人造革鞋”、“布鞋”、“塑料鞋”等小分类。 (4)按商品口味划分。如“糖果饼干”大分类中、“饼干”中分类下，可进一步细分出“甜味饼干”、“咸味饼干”、“奶油饼干”、“果味饼干”等小分类。 四、单品 单品

24、是商品分类中不能进一步细分的、完整独立的商品品项。如上海申美饮料有限公司生产的“355毫升听装可口可乐”、“1.25升瓶装可口可乐”、“2升瓶装可口可乐”、“2升瓶装雪碧”，就属于四个不同单品。 需要讲明的是，商品分类并没有统一固定的标准，各超市公司可依照市场和自身的实际情况对商品进行分类。但商品分类应该以方便顾客购物、方便商品组合、体现企业特点为目的。具体分类如下表所示：食品日用品1.粮油1.日化产品粮食米面淀粉食用油主食熟食豆制品其他粮油.日杂用品2.果蔬.家居用品新奇蔬菜新奇水果食用菌蔬菜制品干果|坚果果蔬深加工其他果蔬4 清洁用品及用具3.水产5.餐具鲜活水产品粗加工水产品精加工水产品

25、其他水产6.厨具畜产.日用小家电鲜活畜禽鲜肉类鲜蛋类鲜奶类肉制品蛋制品乳制品蜜制品.家用塑料制品 .糖酒饮料9.首饰糖类酒类茶叶软饮料冲饮品冷饮咖啡豆|可可其他糖酒饮料10.衣物5.加工食品11.箱包,袋，皮具保健食品休闲食品方便食品罐头食品特色食品调味品其他加工食品12. 文体用品6烟草13日用小五金烟叶香烟其他烟草14休闲家具7添加剂15个人护理用品食品添加剂 添加剂发酵制品16.卫浴用品8.包装机17.炊具加工设备食品包装其他机械包装制冷设备.灶具表2-6 商品品种3 家乐福超市配送现有路线问题分析家乐福的配送系统和信息系统是较落后的.家乐福至今没有在中国建立起统一的配送体系,且计算机系

26、统的开发和建立,要落后于竞争对手沃尔玛好几年.家乐福这种”滞后”的配送系统与信息系统是其战略规划的成果,因为商品的集中配送是连锁商业带来的,然而目前中国连锁商业基础特不薄弱,只有通过大的配送系统的完善和整合才能形成规模的,高效的,社会化的物流配送系统.家乐福配送路线的分配存在以下几方面的问题：物流公司与门店之间的分布太分散，难以形成固定的配送线路送货难以达到及时难以保证适量的库存而不压货路线里程未达最短费用消耗大劳力消耗大,运力难以适当分配，难以调度车辆配送车辆吨位公里数大配送未实现自动化配送未实现网络化配送服务未实现系列化3.配送路线优化建模与求解3.1 研究对象目标设定物流配送常考虑以最小

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

28、利，旅游和娱乐费用,房屋维修费，牌照费,职工培训费,宣传费及业务手续费。车辆运营成本:燃料(燃油,润滑油，过滤器）维修费(人工费+零部件）轮胎费,交通规费，养路费大修理基金提存道路服务：通行费,保险,许可证和登记费高速公路使用费,燃油司机费用占总营业成本的29.4%；维修费和折旧费占总营业成本的19.5%；其它的运营费用占总营业成本的.6%;燃料费占总营业成本的1.5；表上所述：公司车辆运营成本占据了总运输成本的78。随着道路服务政策的变化,车辆营业成本在公司总成本中所占比例日益增大。距离是阻碍运输成本的要紧因素,因为它直接对劳动、燃料和维修保养等变动成本发生作用。针对公司当前成本构成状况,能

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

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

31、;（3）不考虑每辆车为每个客户的服务时刻,即不考虑每个客户的卸货时刻；（4）一个配送中心依照配送条件能够负责多个客户,即一个配送中心服务多个客户；(5)车辆由配送中心动身，服务被指定的需求点后，再返回配送中心，区域内的需求点假设为固定数量且位置已知，不发生变动。(6）配送中心拥有一定数量的单一车型的配送车辆,且每辆车的容量已知。（）每条配送路径上各客户需求量之和不超过配送车辆的容量;(8）每个客户只能由一辆配送车辆送货；(9）每辆车配送总里程不超过其最大行驶距离;（10)各道路均顺畅，不考虑交通堵塞拥挤等专门情况。将配送中心编号为,车辆编号为，任务编号为i1,2,所有车型载重量单一，每辆汽车的

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

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

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

35、前的节约里程，分析下一个客户对。3.3.3基于节约算法的配送路线优化表32 每个分店（一年365天）平均每天的需求量分店234678910需求量(吨）2324121分店11213141516718920需求量(吨)23422132现有路线是固定不变且为已知,每条线路行驶距离可由表3-求得,配送中心与商店之间,商店与商店之间的距离分析如下表:表33 配送中心与分店之间，分店与分店之间的距离(0点表示配送中心)013456791011213511192000126.5230.17921716315648.51119.15.5112137.811.8217.1.42153623711365626.4

36、306.121611611961418131037.15.17.21234.7860184513114119.09.4515192196.1211118501454311103826153317146173635074564143402056243413913369.22.1051378.3.6.44.22412124.2114.5234.5717616135.4458.06.23.1220921248.5311289.2111332618202725237.11816171217719424192.2205.3219.813201328.10361618464.6255.80223117.2

37、261158.589.211131.4.210404.5.12.12.20915248.1.6.111518203820242.32312014245.103421341513922625122011818114011119117141.914.5610.5131.2189.7.252110193612523.61123131533242022282645.11191611911191657.1.1117344.211118.52913.616105.1195.11711135.19.24111141620154211218007.215187254394.8.51738.572445.171

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

39、5301882940.227.201.5.48.253189-0.83.926.80103.4-0.5-125027100-01.4-0.2.721.43.63465.4.4.4.4116.94.98.5.52516.716.3-0.3161716.5-0.53.954.50.2118.01020.6406-0.14.85101010290.50.39.97014.36.509.214.28121030.47.5401815.28.48.7170.23.17.413.6.15.10.21.1271.2.132192.40.5131.2112.43220114151500202014.52.96

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

41、.801203.4-0.5-12502017.100-13.4-0.1.7.143.634.5.443.411.4.98.5.2.516.7163-0.317.16.-.90154.4.2002118.20020.940.50161438.11010.2919.502.3.00714.36.31509.44282030.7.581528.48717.2021.917.1413.2167.1.2.21.71.29.11.21920.40.5301211224320.14.5100.202014.52.9613.55.51.23.50.716.315.31.40.561345.4.59.24.5

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

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

44、727.48.5 0.080.2.6.70.213.20.40.092.4751008000000000011265.4325824.-0.8001203.4-05-25.17.100-13.4-0.2.72.41143.645.40.7.40141694855.52.5167130.31606.5-0.53.9010.4.5020.211.200020.96.40.5016-0.1438.5100100.29.52.9.001701436.3159.14.280103.47.460185.2.8.71720.213.9.713.2510.2122.29.113201920.40.511.11

45、2.24020.811.41.515100.004.5.96.91.5.513.2150.716.301.401.40.58.44.9.2450 选出节约值最大为5,其对应的两个顶点为、11。假如连接4和11,则与上述两条线路合并，其总需求量为3,超过一辆车的运输能力8,因此,4和11不能连接 ,7和11也不能连接,则将4、11与7、1的节约值赋为。选出节约值最大为25，其对应的两个顶点为、12。假如连接5和2,则与上述线路合并，其总需求量为6,未超过一辆车的运输能力8,因此,连接0-12-5-19-0成回路,则将5、12与1、19的节约值赋为。同时,由于顶点5成回路的中间点,则与顶点相关的节

46、约值都赋为0，表示顶点5不可能再与其他点相连，其结果如下表所示。表371245689101112114116181920102.403874.80423.48.5050618.4.68.717.200237.48 00.98.24.7.20.0.209224.47.500170-.80000000000112365.4830180-0.00013.4-.00.217.00-101334-0.21.7.403.63.4.6.43.47.40416.94.855.016.716.-0161.0.53.9104.5000.2118.20009640.501-0.14.5100100299.50.39

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

48、617819200200.84074.50500005.687.2007485 7.9004700.40.20900000000000000001100000001203.40.5-10.201.10000130-0.212.4063446007.401404.98.55.016716.3-0.3000-.53.154.05000.2118.00020.9.405016.351000100.200002.30171436109.144.2000.47546018048.7170.917.1.00002.22.71.29.10004.510112200011.4.15100.20202.9133

49、213.50.700005613.5.45924.50从表3-8中选出节约值最大为09，其对应的两个顶点为1、15。假如连接2和15,则与上述线路合并,其总需求量为7，未超过一辆车的运输能力8,因此，连接012-5-19-成回路,则将、15;1、15与15、19的节约值赋为0。同时,由于顶点2成回路的中间点,则与顶点12相关的节约值都赋为0，表示顶点12不可能再与其他点相连，其结果如下表所示。表3-9123468910112131451617181921200304007.4.50000568.717.20707.48.5 0017.908060.0.40.090000000000000110

50、0000000000100000000000130-212.403.644.6000001404.98.55.5676.30.3003.90150.500.11.20006.40.0164.38.1000100.200002.3.90014.36.109.21.20000.474680.4.717.2013.917.400001.21.71.29.13.29.40.10.11.20.4150100.02002.96.13.53.21.50.000061.4.58.459.4.50从表3-9中选出节约值最大为18，其对应的两个顶点为、1。假如连接8和15，则与上述线路合并，其总需求量为1，超过一

51、辆车的运输能力8,因此, 8、19；8、5;8、2和8、15也不能连接，则将、19;8、5；、12和8、15的节约值赋为0.接着选出节约值最大为79,其对应的两个顶点为6、7。假如连接6和7，则与上述线路合并,其总需求量为9,超过一辆车的运输能力8,因此,6和7不能连接 ,和6也不能连接，则将6、7和4、6的节约值赋为0。选出节约值最大为17,其对应的两个顶点为7、。假如连接7和1,则与上述线路合并,其总需求量为10，超过一辆车的运输能力,因此，7和18不能连接 ，4和8也不能连接，则将7、18和4、8的节约值赋为。选出节约值最大值为16.7,其对应的两点为6、1。6、14两处的需求量之和为4

52、,未超过一辆车的运输能力8，因此，连接6、4成回路,即6-14-再将顶点6、14的节约值赋为.选出节约值最大为16.3,其对应的两个顶点为7、14。假如连接7和14，则与上述两条线路合并,其总需求量为11,超过一辆车的运输能力,因此，7和4不能连接 ,4和14也不能连接,则将、和、14的节约值赋为0选出节约值最大为5,其对应的两个顶点为、17。假如连接4和1,则与上述线路合并，其总需求量为,未超过一辆车的运输能力,因此,连接0-17-4-0成回路，则将与顶点4、7、7相关的节约值都赋为0，表示顶点4、7不可能再与其他点相连,其结果如下表所示。表3-10123456789111121341561

53、71192002003080050000605.68.700700 00004.0.700040900000000000000000100000000000000000001300.1.0.6060001404.98.5000-.30003.9004.40.500.2000040.0160438.5000200002.39.9700000000001808.48.01901.400001.2.71.2910019004050.0.20001.41.501002020029.0013.207003.058.0.24.50选出节约值最大为13.9，其对应的两个顶点为、18。假如连接6和8，则与上述

54、线路合并，其总需求量为7，未超过一辆车的运输能力，因此，连接-18-1-0成回路，则将6、18与14、18的节约值赋为。同时,由于顶点6成回路的中间点，则与顶点6相关的节约值都赋为，表示顶点6不可能再与其他点相连,其结果如下表所示。表3-1123467801123141516718920003480400050000060000007000 0008.600000000001000000001100000020000000030-0.21.700600001404.98.5000-03003.01504.40.50000004050164.50000200.39.900170000000000

55、0000018088.70001.400.201.29.10190.40.500012.2001.4.0100.20202.96.90000.7000613.40.58.409.5选出节约值最大为13.,其对应的两个顶点为1、2。假如连接4和0，则与上述线路合并，其总需求量为9,超过一辆车的运输能力，因此,4和0不能连接 ，和20;8和20也不能连接,则将6、2;4、20和18、20的节约值赋为0.选出节约值最大值为11.4,其对应的两点为13、1。假如连接13和19，则与上述线路合并，其总需求量为1，超过一辆车的运输能力8,因此,1和19不能连接，1、；1、5；1、1和1、5也不能连接，则将

56、13、1;13、5；3、1和13、1的节约值赋为0选出节约值最大为.9，其对应的两个顶点为、16。假如连接14和16,则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此,14和1不能连接 ，6和1；1和16也不能连接,则将6、16；1、6和18、16的节约值赋为0.选出节约值最大为8.7，其对应的两个顶点为3、1。假如连接3和8,则与上述线路合并,其总需求量为9,超过一辆车的运输能力,因此，3和18不能连接 ,3和8；3和6;3和1也不能连接,则将3、18;3、和3、1的节约值赋为0.选出节约值最大为8,其对应的两个顶点为3、1。假如连接3和16，其总需求量为,未超过一辆车的运输能

57、力8，因此，连接3、16成回路，即0-3-6-0.再将顶点3和16的节约值赋为.选出节约值最大为84,其对应的两个顶点为2、18。假如连接和8,则与上述线路合并，其总需求量为1，超过一辆车的运输能力8,因此，2和1；2和6;2和14也不能连接,则将2、1；2、6和2、14的节约值赋为0.选出节约值最大为84,其对应的两个顶点为1、20。假如连接1和20，其总需求量为6，未超过一辆车的运输能力8，因此,连接16、2成回路，即036-20-0再将顶点、2和3、20的节约值都赋为. 同时,由于顶点16成回路的中间点,则与顶点16相关的节约值都赋为0,表示顶点1不可能再与其他点相连,其结果如下表所示。

58、表3-213456789011111516178192010203.84000050000600070 00800.7000090000000010000000110000000001000000030-.1.700004.6000004000000-000.90504.40.50000000.010000000000000001000000000000018000.400012.00090040.50000001.5000.2200.00000.0000600005选出节约值最大为6，其对应的两个顶点为3、20。假如连接13和2,则与上述线路合并,其总需求量为0，超过一辆车的运输能力，因此,

59、3和0不能连接 ,3和3;1和16也不能连接，则将13、；13、1和13、20的节约值赋为0.选出节约值最大为.8,其对应的两个顶点为2、。假如连接2和3，则与上述线路合并,其总需求量为,超过一辆车的运输能力8，因此，2和3不能连接 ,2和1；2和20也不能连接，则将2、3;2、16和2、20的节约值赋为0.选出节约值最大为4.6，其对应的两个顶点为2、8。假如连接2和8,其总需求量为,未超过一辆车的运输能力,因此,连接，2、8成回路,即-80.再将与顶点和8相关的节约值都赋为0,表示顶点2和8不可能再与其他点相连。选出节约值最大为4.,其对应的两个顶点为19、0。假如连接19和,则与上述两条

60、线路合并，其总需求量为1，超过一辆车的运输能力8，因此，15、3;1、6；5、20;19、3;、16和9、20也不能连接，则将8、3；8、16；、20；1、;19、1和19、20的节约值赋为0.选出节约值最大为3.9，其对应的两个顶点为1、1。假如连接1和1,则与上述线路合并,其总需求量为1，超过一辆车的运输能力8,因此,3和14不能连接，13和1；13和6也不能连接，则将3、6；、14和13、18的节约值赋为0.选出节约值最大为1.5,其对应的两个顶点为4、19。假如连接1和19,则与上述两条线路合并,其总需求量为1，超过一辆车的运输能力8,因此，5、;15、14;9、8;19、和9、14也