家乐福超市物流配送路线优化论文

家乐福超市物流配送路线优化 . 学年论文之 家乐福超市物流配送路线优化 专业 物流工程 班级 姓名 学号 日期 . . 摘要 在物流配送业务中，合理确定配送路径是提商服务质量，降低配送成本，增加经济效益的重要手段。物流配送系统中最优路线的选择问一直都是配送中心关注的焦点，针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合理化。 通过对家乐福超市现有物流配送路径的分析研究，发现其中存在的一些问题，并由此提出解决办法，结合背景材料，建立了数学模型，运用遗传算法对家乐福物流配送路线进行优化选择，并得出结果。由此可见，家乐福超市原有的物流配送路线还可以进行再优化，从而达到运输成本最小化的目标。 关键词:物流配送;路径优化;节约里程算法 . . 目 录 1.绪论 .............................................................. 1 1.1 选题目的和意义 ................................................. 1 1.2 国内外物流配送路线优化研究现状 ................................. 2 2. 家乐福超市配送路线现状 ........................................... 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 家乐福超市配送现有路线问题分析 ................................. 7 3.配送路线优化建模与求解 ............................................ 93.1 研究对象目标设定 ............................................... 9 3.2 模型的构建 .................................................... 11 3.3 节约算法 ...................................................... 12 3.3.1节约算法的基本原理 ........................................ 12 3.3.2节约里程算法主要步骤 ...................................... 12 3.3.3基于节约算法的配送路线优化 ................................ 13 3.3.4优化后的配送线 ............................................ 24 4.优化结果分析 ..................................................... 25 4.1 优化前结果 .................................................... 25 4.2 优化后结果 .................................................... 25 4.3 结论 .......................................................... 26 5.总结与建议 ....................................................... 27 参考文献: .......................................................... 28 . . 1.绪论 1.1 选题目的和意义 配送是一项特殊的、综合性的物流运动，其运行和发展有着深刻的社会根源和历史背景。在市场经济体系中，物流配送如同人体的血管，把国民经济各个部分紧密地联系在一起。配送是物流中一个重要的直接与消费者相连的环节，是将货物从物流结点送达收货人的过程，是在集货、配货基础上，完全按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送”的有机结合形式。其主要包括集货作业、配货作业、车载货物的配装、配送线路的确定。 在生活中，基于电子商务的物流配送业务量逐渐增加，如果还沿用以前的物流方法来组织配送，会产生很多问题。这些问题归纳起来，包括以下几点: 1)服务质量的下降。电子商务的特征是交易量巨大和交易速度极快，而传统物流配送的特点是人工调度、反应时间长。信息流与物流的矛盾会导致整个电子商务客户服务的低效。也许客户可以在几十秒内完成一次交易，却要等上一个星期才能收到货物，这样的服务只能逐渐失掉客户。 2)物流成本控制困难。传统的物流配送大多是由人工调度的，在交易量较小的情况下，可以合理地安排配送，降低成本。一旦交易量增加、交易速度加快，配送调度就会超出人工的能力范围，会导致大量的不合理调度的出现，物流成本无法控制。 3)增加城市交通的负担。物流配送调度的不合理，会使物流配送的行车路线变长，导致在运车辆增加，从而给本已拥挤的城市交通加重负担。要解决以上的问题，使物流配送调度满足以下目标?准时送货。就是要客户选择货物送达他们指定地点的时间，要按照每个客户的时间要求安排物流配送。?总成本最低。?总行车路径最短。 当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重要标志，也成为城市经济发展水平的体现，被喻为促进经济发展的“加速器”。物流配送是一种先进的现代物流形式，它不但给供应者和需求者带来降低物流成本、享受优质服务的直接效益，而且还能为社会节省运输车次、缓解交通压力、减少运输污染、保护生态环。 而今，由于小批量、多批次的及时配送方式的发展，运输费用正在逐年提升，许多企业的运费已经超越了库存费用，城市交通与改善物流的矛盾也愈演愈烈，城市交通混杂、阻塞、车辆噪音、尾气污染、车祸事故和能源浪费等现象更加严重，若物流路线选择的不合理，还会使物流配送的行车路线变长，导致在运车辆增加，从而给本己拥挤的城市交通加重负担，这就势必要选择合理有效的运输路线来减少重复运输、倒流运输、迁回运输、单程运输和空驶等，这样不仅提高配送效率，控制了物流成本，而且可限制车辆在城市中的运行时间，有效缓解城市交通负担。 物流配送系统中最优路线的选择问题一直都是配送中心关注的焦点，对于城市配送而言，由于受交通堵塞和各种交通管制的影响，导致配送路径寻优更具复. . 杂性。所以本文通过对具有动态的交通堵塞和交通拥挤限制信息及静态禁止通行等限制信息的实际配送网络的描述，提出解决两种限制情况下配送网络寻优的方法，建立了配送网络图中权重确定模型，并基于此进一步建立了城市物流配送决策系统数学模型，运用二分领域搜索算法对其寻优。 针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合 一方面通过建立一种快速、高效、网络化的物流组织系统降低物流成本，增理化: 加利润;另一方面，增强家乐福的竞争力，使其配送系统相应得到优化，从而使家乐福物流取得阶段性成果，因此，对家乐福物流配送体系及其路线的优化问题进行研究将具有很大的现实意义。 1.2 国内外物流配送路线优化研究现状 物流配送路线优化，是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。对物流配送路线优化，可以提高物流经济效益，实现物流科学化。可以说对物流配送路线优化理论与方法进行系统研究是物流集约化发展，构建综合物流系统，建立现代调度指挥系统，发展智能交通运输系统和开展电子商务的基础。 配送路线合理与否对配送速度，成本，效益影响很大，特别是多用户配送线路的确定更为复杂。采用科学的，合理的方法来确定配送路线，是配送活动中非常重要的一项工作。 路线优化问题最早是由DANTZIG和RAMSER于1959年提出的，由于这一问题的理论涉及很多学科，很多实际问题的理论抽象都可归结为这一类问题，应用前景广阔，所以很快便引起运筹学，应用数学，图论与网络分析，物流学科，交通运输工程，管理科学与工程，计算机应用等学科的专家，工程技术人员和管理者的极大重视，自此，一直成为运筹学与组合优化领域的前沿与研究热点问题。 在国外，物流配送路线优化问题已广泛应用于生产，生活的各个方面。如报纸投递及线路的优化，牛奶配送及送达线路的优化，电话预订货物的车辆线路设计，垃圾车的线路优化，连锁商店的送货的线路优化等等。目前，研究水平已有很大发展，其理论成果除在汽车运输领域外，在水运，航空，通讯，电力，工业管理，计算机应用等领域也有一定的应用，还用于航空乘务员轮班安排，轮船公司运送货物经过港口与货物安排的优化设计，交通车线路安排，生产系统中的与控制等多种组合优化问题。 在国内，该问题的系统研究还不多见。近年来有李军等人课题组承担的国家自然科学基金《不确定信息条件下动态车辆路径》等研究工作。纪寿文等人根据深圳市科技园的实际路网图，采用神经网络的方法对运输车辆优化调度进行了试验研究。王正彬等人在分析VRP现有启发式算法的基础上，建立了考虑线路安排的物流配送方案模型，并提出了求解该问题的搜索算法。 . . 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分店所在地坐标 坐标 X Y 分店与配送中心间距离 1 8 9 2 -4 5 3 2 4 4 10 20 5 3 -30 6 6 7 7 8 15 8 -7 -6 9 15 9 10 10 12 11 9 10 12 -8 -13 13 4 -5 14 6 6 15 -7 -8 16 3 4 17 -5 10 18 2 9 19 1 -15 20 8 3 22 i=1，2.........20; D,(x,x)，(Y-Y)i0i0 (2) 现有路线是固定不变且为已知,每条线路行驶距离可由表2-3求得, 配送中心与商店之间，商店与商店之间的距离分析如下表: 表2-2 配送中心与分店之间,分店与分店之间的距离(0点表示配送中心) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 0 12 6.4 4.5 22 30 9.2 17 9.2 17 16 13 15 6.4 8.5 11 5 11 9.2 15 8.5 1 12 0 13 7.8 11 39 2.8 6 21 7 3.6 1.4 27 15 3.6 23 7.1 13 6 25 6 . . 2 6.4 13 0 6.1 21 36 10 16 11 19 16 14 18 13 10 13 7.1 5.1 7.2 21 12 3 4.5 7.8 6.1 0 18 34 5 13 13 14 11 9.2 20 9.2 4.5 15 1 9.2 5 19 6.1 4 22 11 21 18 0 50 14 5.4 31 12 8 10 38 26 15 33 17 18 14 36 17 5 30 39 36 34 50 0 37 45 26 41 43 40 20 25 36 24 34 41 39 15 33 6 9.2 2.8 10 5 14 37 0 8.3 18 9.2 6.4 4.2 24 12 1 20 4.2 11 4.5 23 4.5 7 17 6 16 13 5.4 45 8.3 0 26 9.2 3.6 5.1 32 20 9.2 27 12 14 8.5 31 12 8 9.2 21 11 13 31 26 18 26 0 27 25 23 7.1 11 18 2 14 16 17 12 17 9 17 7 19 14 12 41 9.2 9.2 27 0 5.8 6.1 32 18 9.5 28 13 20 13 28 9.2 10 16 3.6 16 11 8 43 6.4 3.6 25 5.8 0 2.2 31 18 7.2 26 11 15 8.5 28 9.2 11 13 1.4 14 9.2 10 40 4.2 5.1 23 6.1 2.2 0 29 16 5 24 8.5 14 7.1 26 7.1 12 15 27 18 20 38 20 24 32 7.1 32 31 29 0 14 24 5.1 20 23 24 9.2 23 13 6.4 15 13 9.2 26 25 12 20 11 18 18 16 14 0 11 11 9.1 17 14 10 8.9 14 8.5 3.6 10 4.5 15 36 1 9.2 18 9.5 7.2 5 24 11 0 19 3.6 12 5 22 3.6 15 11 23 13 15 33 24 20 27 2 28 26 24 5.1 11 19 0 16 18 19 11 19 16 5 7.1 7.1 1 17 34 4.2 12 14 13 11 8.5 20 9.1 3.6 16 0 10 5.1 19 5.1 17 11 13 5.1 9.2 18 41 11 14 16 20 15 14 23 17 12 18 10 0 7.1 26 15 18 9.2 6 7.2 5 14 39 4.5 8.5 17 13 8.5 7.1 24 14 5 19 5.1 7.1 0 24 8.5 19 15 25 21 19 36 15 23 31 12 28 28 26 9.2 10 22 11 19 26 24 0 19 20 8.5 6 12 6.1 17 33 4.5 12 17 9.2 9.2 7.1 23 8.9 3.6 19 5.1 15 8.5 19 0 2.2.2 车辆数分析 所需车辆数分析(家乐福配送中心一年(365天)的车辆调度): 表2-3车辆调度情况 车辆运用数 10 12 9 11 10 11 10 10 8 9 10 11 运用天数 25 30 36 42 46 49 48 38 24 13 8 6 表2-4车辆运用数所占比率 车辆运用数 相对比率 累计比率 12 0.07 0.07 12 0.08 0.15 11 0.10 0.25 10 0.12 0.37 12 0.13 0.50 11 0.13 0.63 13 0.13 0.76 10 0.10 0.86 14 0.07 0.93 15 0.04 0.97 13 0.02 0.99 11 0.01 1.00 则家乐福平均每天所用车辆数为12辆。 . . 2.2.3 需求量分析 表2-5 每个分店(一年365天)平均每天的需求量 分店 1 2 3 4 5 6 7 8 9 10 需求 2 3 2 4 1 2 3 5 1 3 量 分店 11 12 13 14 15 16 17 18 19 20 需求 2 3 4 2 1 2 1 3 2 2 量 2.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 家乐福超市配送现有路线问题分析 家乐福的配送系统和信息系统是较落后的.家乐福至今没有在中国建立起统一的配送体系,且计算机系统的开发和建立,要落后于竞争对手沃尔玛好几年.家乐福这种”滞后”的配送系统与信息系统是其战略规划的成果,因为商品的集中配送是连锁商业带来的,但是目前中国连锁商业基础非常薄弱,只有通过大的配送系统的完善和整合才能形成规模的,高效的,社会化的物流配送系统. 家乐福配送路线的分配存在以下几方面的问题: . . (1)物流公司与门店之间的分布太分散，难以形成固定的配送线路 (2)送货难以达到及时 (3)难以保证适量的库存而不压货 (4)路线里程未达最短 (5)费用消耗大 )劳力消耗大，运力难以适当分配，难以调度车辆 (6 (7)配送车辆吨位公里数大 (8)配送未实现自动化 (9)配送未实现网络化 (10)配送服务未实现系列化 . . 3.配送路线优化建模与求解 3.1 研究对象目标设定 物流配送常考虑以最小化总运输成本或距离最短为目标，总运输成本主要由由两部分组成:(1)运输固定成本:如服务所有客户所需要的车辆数、总行驶距离(或总行驶时间)和与所使用的车辆有关的固定费用;(2)运输营业成本:如司机的管理费,各种工作人员的工资等. 家乐福超市的业务运输成本是物流总成本的主要组成部分，占有56%。因此降低公司运输成本成为提高公司效益的直接有效途径。公司自有货运成本各项比例如下表: 表3-1公司货运成本比例表 固定费用(22%) 营业费用(78%) 折旧费(租赁费): 人力(司机): 装卸工具，车库，办公室， 工资,额外福利，装卸费 水电，通迅，差旅费，公务车费用 业务印刷费 投资利息: 车辆运营成本: 车辆，车库,办公室 燃料(燃油，润滑油，过滤器) 管理成本: 维修费(人工费+零部件) 职工月工资,额外福利,旅游和娱乐费用,轮胎费，交通规费，养路费 房屋维修费，牌照费，职工培训费，宣传大修理基金提存 费及业务手续费。 道路服务: 通行费,保险,许可证和登记费 高速公路使用费,燃油 司机费用占总营业成本的29.4%;维修费和折旧费占总营业成本的19.5%;其它的运营费用占总营业成本的32.6%;燃料费占总营业成本的18.5%; 表上所述:公司车辆运营成本占据了总运输成本的78%。随着道路服务政策的变化，车辆营业成本在公司总成本中所占比例日益增大。距离是影响运输成本的主要因素，因为它直接对劳动、燃料和维修保养等变动成本发生作用。针对公司当前成本构成状况，可以知道:通过优化公司配送路线，减少运输车辆行驶总里程，可以减少车辆燃油费和道路服务费支出，进而减少物流总成本。 因此，本文针对家乐福配送中心车辆路线优化问题，提出的目标是:总运输成本最小化。 . . 9 4 5 6 8 配送中心 3 1 2 7 配送中心 分店 车辆路线 图3-1 家乐福的配送模式 此问题可以描述为:这是一种分送式配送模型,是由一个供应点对多个客户的共同配送。对配送中心负责的需求网点(家乐福分店)，确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过各个分店各一次，最后返回配送中心，并在满足一定的约束条件下(如车辆容量限制、行驶里程限制、时间限制、顾客需求量、交发货时间等)，达到费用最少的目标。 本文研究的是不考虑时间窗的非满载车辆优化调度问题。表述如下:将货物 q从配送中心配送到各分配送中心,由分配送中心派出容量为的货车承运，现有m辆车，各分店对所需求的货物有一定的要求，第i个分店的货运量为g，(i=1，i2……l)已知g,q，在途中只有卸货任务,完成任务后返回配送中心,求满足配送i 需求的费用最少行车线路。 配送中心 分配送中心2 分配送中心1 .......................分配送中心3 ... 图3-2家乐福配送体系结构 分店1 分店3 分店4 ..........分店2 . ... . 3.2 模型的构建 为建模方便，需考虑以下几个前提假设条件: (1)配送中心不会出现缺货的可能并且对顾客的基本配送资料(需求量、地理位置)为已知，配送中心的位置也已知; (2)不考虑配送时间限制，即客户对货物的需求没有时间窗的规定; (3)不考虑每辆车为每个客户的服务时间，即不考虑每个客户的卸货时间; (4)一个配送中心根据配送条件可以负责多个客户，即一个配送中心服务多个客户; (5)车辆由配送中心出发，服务被指定的需求点后，再返回配送中心，区域内的需求点假设为固定数量且位置已知，不发生变动。 (6)配送中心拥有一定数量的单一车型的配送车辆，且每辆车的容量已知。 (7)每条配送路径上各客户需求量之和不超过配送车辆的容量; (8)每个客户只能由一辆配送车辆送货; (9)每辆车配送总里程不超过其最大行驶距离; (10)各道路均顺畅，不考虑交通堵塞拥挤等特殊情况。 将配送中心编号为0，车辆编号为k，任务编号为i=1,2........l, 所有车型载重 ，需要向L个需求点送货，每个需求点的需求量单一，每辆汽车的最大载重量为g qi(i,1,2,？,L)dij量为，并且满足，需求点i到j的运距为，配送中心到各q,gi dij(i,0,j,1,2,...,L)个需求点的距离为，再设为第k辆汽车配送的需求点数(=0nknk表示未使用第k辆汽车)，用集合Rk表示第k条路径，其中的元素表示需求点rkirki在路径k中的顺序为(不包括配送中心)，令=0表示配送中心，为每辆车单irk0m位里程的行驶费用，C为每辆车的派遣费用，考虑运输量约束,停车点车辆数目等约束,可以定义如下的基本模型: nKk minZ,m，[d，d,sign(n)]，K，C (3-1) ,,rrrrk(,1)0kikiknkk,,11ki nk q,g (3-2) ,rkii,1 0,n,Lk (3-3) K n,L,kk,1 (3-4) ,, (3-5) R,{r|r,1,2,...,L,i,1,2,...,n}kkikik 1,1n,k (), (3-6) signn,k0其他, 在上述模型中各个公式所代表的涵义如下: (3-1)式为目标，求总的配送费用最低; . . (3-2)式用于保证每条路径上各个需求点的需求量和不超过汽车的载重量; (3-3)式表明每条路径上的需求点数不超过总需求点数; (3-4)式表明每个需求点都得到配送服务; (3-5)式表示每条路径的需求点的组成; 3-6)式表示当第辆汽车服务的客户数大于或等于1时，说明该辆汽车参(k 加了配送，则取，当第k辆汽车服务的客户数小于1时，表示未使用sign(n),1k 该辆汽车，因此取; sign(n),0k 3.3 节约算法 3.3.1节约算法的基本原理 节约算法的核心思想是将运输问题中存在的两个回路(0，„ ，i，0)和(0，j，„ ，0)合并成一个回路(0，„ ，i，j，„，0)。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了 [6]运输距离。相应的变化值，叫做节约距离，如式(1)所示。 ,Cij (1) ,,，,Ccccijioojji 调整过程如图3所示。 j j 0 0 i i 调整前 调整后 图3-3节约算法的图像描述 3.3.2节约里程算法主要步骤 已知条件:需求点集={1,2,„, n},各点需求量,各点间最短距离。 NcRijRi Ij,第一步,形成一个初始解。确定各车辆配送点集令, III,,,,,,,,j12m. . j=1,2,„,n (先采取单点配送)。 第二步,进行节约度的计算。计算所有点对的节约度，然后对计算结果进 行升序排列。 第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始， 直到节约里程的队列空为止,重复下列步骤:按照节约里程队列从大到小 的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路 ,径内以及合并次数不超过2),将i, j连接起来,即可令。如果不IIII,,,,;iijj 是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对。 3.3.3基于节约算法的配送路线优化 表3-2 每个分店(一年365天)平均每天的需求量 分店 1 2 3 4 5 6 7 8 9 10 需求量2 3 2 4 1 2 3 5 1 3 (吨) 分店 11 12 13 14 15 16 17 18 19 20 需求量2 3 4 2 1 2 1 3 2 2 (吨) 现有路线是固定不变且为已知,每条线路行驶距离可由表3-2求得, 配送中心 与商店之间，商店与商店之间的距离分析如下表: 表3-3 配送中心与分店之间,分店与分店之间的距离(0点表示配送中心) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 0 12 6.4 4.5 22 30 9.2 17 9.2 17 16 13 15 6.4 8.5 11 5 11 9.2 15 8.5 1 12 0 13 7.8 11 39 2.8 6 21 7 3.6 1.4 27 15 3.6 23 7.1 13 6 25 6 2 6.4 13 0 6.1 21 36 16 11 19 16 14 18 13 10 13 7.1 5.1 7.2 21 12 10 3 4.5 7.8 6.1 0 18 34 5 13 13 14 11 9.2 20 9.2 4.5 15 1 9.2 5 19 6.1 4 22 11 21 18 0 50 14 5.4 31 12 8 10 38 26 15 33 17 18 14 36 17 5 30 39 36 34 50 0 37 45 26 41 43 40 20 25 36 24 34 41 39 15 33 6 9.2 2.8 10 5 14 37 0 8.3 18 9.2 6.4 4.2 24 12 1 20 4.2 11 4.5 23 4.5 7 17 6 16 13 5.4 45 8.3 0 26 9.2 3.6 5.1 32 20 9.2 27 12 14 8.5 31 12 8 9.2 21 11 13 31 26 18 26 0 27 25 23 7.1 11 18 2 14 16 17 12 17 9 17 7 19 14 12 41 9.2 9.2 27 0 5.8 6.1 32 18 9.5 28 13 20 13 28 9.2 10 16 3.6 16 11 8 43 6.4 3.6 25 5.8 0 2.2 31 18 7.2 26 11 15 8.5 28 9.2 11 13 1.4 14 9.2 10 40 4.2 5.1 23 6.1 2.2 0 29 16 5 24 8.5 14 7.1 26 7.1 12 15 27 18 20 38 20 24 32 7.1 32 31 29 0 14 24 5.1 20 23 24 9.2 23 13 6.4 15 13 9.2 26 25 12 20 11 18 18 16 14 0 11 11 9.1 17 14 10 8.9 14 8.5 3.6 10 4.5 15 36 1 9.2 18 9.5 7.2 5 24 11 0 19 3.6 12 5 22 3.6 . . 15 11 23 13 15 33 24 20 27 2 28 26 24 5.1 11 19 0 16 18 19 11 19 16 5 7.1 7.1 1 17 34 4.2 12 14 13 11 8.5 20 9.1 3.6 16 0 10 5.1 19 5.1 17 11 13 5.1 9.2 18 41 11 14 16 20 15 14 23 17 12 18 10 0 7.1 26 15 18 9.2 6 7.2 5 14 39 4.5 8.5 17 13 8.5 7.1 24 14 5 19 5.1 7.1 0 24 8.5 19 15 25 21 19 36 15 23 31 12 28 28 26 9.2 10 22 11 19 26 24 0 19 20 8.5 6 12 6.1 17 33 4.5 12 17 9.2 9.2 7.1 23 8.9 3.6 19 5.1 15 8.5 19 0 设每个车辆的运输能力是8吨，根据案例可知，家乐福平均每天所用车辆数为12辆。现在用节约算法对该配送线路问题进行求解。 根据配送中心与分店之间,分店与分店之间的距离距离表，计算出用户间的节约里程， 表3-4 节约值矩阵表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 0 5.4 2 0 8.7 4.8 3 0 23 7.4 8.5 4 0 3 0.4 0.5 2 5 0 18.4 5.6 8.7 17.2 2.2 6 0 23 7.4 8.5 33.6 2 17.9 0 7 0.2 4.6 0.7 0.2 13.2 0.4 0.2 0 8 22 4.4 7.5 27 6 17 24.8 -0.8 0 9 24.4 6.4 9.5 30 3 18.8 29.4 0.2 27.2 0 10 23.6 5.4 8.3 25 3 18 24.9 -0.8 23.9 26.8 0 11 0 3.4 -0.5 -1 25 0.2 0 17.1 0 0 -1 0 12 3.4 -0.2 1.7 2.4 11.4 3.6 3.4 4.6 5.4 4.4 3.4 7.4 0 13 16.9 4.9 8.5 5.5 2.5 16.7 16.3 -0.3 16 17.3 16.5 -0.5 3.9 0 14 0 4.4 0.5 0 20 0.2 1 18.2 0 1 0 20.9 6.4 0.5 0 15 -0.1 4.3 8.5 10 1 10 10 0.2 9 10 9.5 0 2.3 9.9 0 0 16 0 14.3 6.3 15 0 9.2 14 4.2 8 12 10 3 0.4 7.5 4 6 0 17 15.2 8.4 8.7 17.2 0.2 13.9 17.7 1.4 13.2 16.7 15.1 0.2 1.2 12.7 1.2 9.1 13.2 0 18 2 0.4 0.5 1 30 1.2 1 12.2 4 3 2 20.8 11.4 1.5 15 1 0 0.2 0 19 14.5 2.9 6.9 13.5 5.5 13.2 13.5 0.7 16.3 15.3 14.4 0.5 6 13.4 0.5 8.4 4.5 9.2 4.5 0 20 从表3-4中选出节约值最大值为33.6，其对应的两点为4、7。4、7两处的需. . 求量之和为7，未超过一辆车的运输能力8，因此，连接4、7成回路，即0-4-7-0.再将顶点4和7的节约值赋为0.结果如表3-5所示。 表3-5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 0 5.4 0 2 8.7 4.8 0 3 23 7.4 8.5 0 4 3 0.4 0.5 2 0 5 18.4 5.6 8.7 17.2 2.2 0 6 23 7.4 8.5 0 2 17.9 0 7 0.2 4.6 0.7 0.2 13.2 0.4 0.2 0 8 22 4.4 7.5 27 6 17 24.8 -0.8 0 9 24.4 6.4 9.5 30 3 18.8 29.4 0.2 27.2 0 10 23.6 5.4 8.3 25 3 18 24.9 -0.8 23.9 26.8 0 11 0 3.4 -0.5 -1 25 0.2 0 17.1 0 0 -1 0 12 3.4 -0.2 1.7 2.4 11.4 3.6 3.4 4.6 5.4 4.4 3.4 7.4 0 13 16.9 4.9 8.5 5.5 2.5 16.7 16.3 -0.3 16 17.3 16.5 -0.5 3.9 0 14 0 4.4 0.5 0 20 0.2 1 18.2 0 1 0 20.9 6.4 0.5 0 15 -0.1 4.3 8.5 10 1 10 10 0.2 9 10 9.5 0 2.3 9.9 0 0 16 0 14.3 6.3 15 0 9.2 14 4.2 8 12 10 3 0.4 7.5 4 6 0 17 15.2 8.4 8.7 17.2 0.2 13.9 17.7 1.4 13.2 16.7 15.1 0.2 1.2 12.7 1.2 9.1 13.2 0 18 2 0.4 0.5 1 30 1.2 1 12.2 4 3 2 20.8 11.4 1.5 15 1 0 0.2 0 19 14.5 2.9 6.9 13.5 5.5 13.2 13.5 0.7 16.3 15.3 14.4 0.5 6 13.4 0.5 8.4 4.5 9.2 4.5 0 20 从表3-5中选出节约值最大为30，其对应的两个顶点为4、10。如果连接4和10 ，则与上述线路合并，其总需求量为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，则与上述两条线路合并，其总需求量为11，超过一辆车的运输能力8，因此，4和9不能连接 ，7和9也不能连接，则将4、9与7、9的节约值赋为0。 选出节约值最大为26.8，其对应的两个顶点为10、11。如果连接10和11 ， ，因此，连接则与上述线路合并，其总需求量为6，未超过一辆车的运输能力80-9-10-11-0成回路 ，则将9、11与10、11的节约值赋为0。同时，由于顶点10成回路的中间点，则与顶点10相关的节约值都赋为0，表示顶点10不可能再与其他点相连，其结果如下表所示。 表3-6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 0 5.4 0 2 8.7 4.8 0 3 23 7.4 8.5 0 4 3 0.4 0.5 2 0 5 18.4 5.6 8.7 17.2 2.2 0 6 23 7.4 8.5 0 2 17.9 0 7 0.2 4.6 0.7 0.2 13.2 0.4 0.2 0 8 22 4.4 7.5 0 6 17 0 -0.8 0 9 0 0 0 0 0 0 0 0 0 0 10 23.6 5.4 8.3 25 3 18 24.9 -0.8 0 0 0 11 0 3.4 -0.5 -1 25 0.2 0 17.1 0 0 -1 0 12 3.4 -0.2 1.7 2.4 11.4 3.6 3.4 4.6 5.4 0 3.4 7.4 0 13 16.9 4.9 8.5 5.5 2.5 16.7 16.3 -0.3 16 0 16.5 -0.5 3.9 0 14 0 4.4 0.5 0 20 0.2 1 18.2 0 0 0 20.9 6.4 0.5 0 15 -0.1 4.3 8.5 10 1 10 10 0.2 9 0 9.5 0 2.3 9.9 0 0 16 0 14.3 6.3 15 0 9.2 14 4.2 8 0 10 3 0.4 7.5 4 6 0 17 15.2 8.4 8.7 17.2 0.2 13.9 17.7 1.4 13.2 0 15.1 0.2 1.2 12.7 1.2 9.1 13.2 0 18 2 0.4 0.5 1 0 1.2 1 12.2 4 0 2 20.8 11.4 1.5 15 1 0 0.2 0 19 14.5 2.9 6.9 13.5 5.5 13.2 13.5 0.7 16.3 0 14.4 0.5 6 13.4 0.5 8.4 4.5 9.2 4.5 0 20 选出节约值最大为25，其对应的两个顶点为4、11。如果连接4和11，则与. . 上述两条线路合并，其总需求量为13，超过一辆车的运输能力8，因此，4和11不能连接 ，7和11也不能连接，则将4、11与7、11的节约值赋为0。 选出节约值最大为25，其对应的两个顶点为5、12。如果连接5和12，则与上述线路合并，其总需求量为6，未超过一辆车的运输能力8，因此，连接-12-5-19-0成回路，则将5、12与12、19的节约值赋为0。同时，由于顶点50 成回路的中间点，则与顶点5相关的节约值都赋为0，表示顶点5不可能再与其他点相连，其结果如下表所示。 表3-7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 0 5.4 0 2 8.7 4.8 0 3 23 7.4 8.5 0 4 0 0 0 0 0 5 18.4 5.6 8.7 17.2 0 0 6 23 7.4 8.5 0 0 17.9 0 7 0.2 4.6 0.7 0.2 0 0.4 0.2 0 8 22 4.4 7.5 0 0 17 0 -0.8 0 9 0 0 0 0 0 0 0 0 0 0 10 23.6 5.4 8.3 0 0 18 0 -0.8 0 0 0 11 0 3.4 -0.5 -1 0 0.2 0 17.1 0 0 -1 0 12 3.4 -0.2 1.7 2.4 0 3.6 3.4 4.6 5.4 0 3.4 7.4 0 13 16.9 4.9 8.5 5.5 0 16.7 16.3 -0.3 16 0 16.5 -0.5 3.9 0 14 0 4.4 0.5 0 0 0.2 1 18.2 0 0 0 20.9 6.4 0.5 0 15 -0.1 4.3 8.5 10 0 10 10 0.2 9 0 9.5 0 2.3 9.9 0 0 16 0 14.3 6.3 15 0 9.2 14 4.2 8 0 10 3 0.4 7.5 4 6 0 17 15.2 8.4 8.7 17.2 0 13.9 17.7 1.4 13.2 0 15.1 0.2 1.2 12.7 1.2 9.1 13.2 0 18 2 0.4 0.5 1 0 1.2 1 12.2 4 0 2 0 11.4 1.5 15 1 0 0.2 0 19 14.5 2.9 6.9 13.5 0 13.2 13.5 0.7 16.3 0 14.4 0.5 6 13.4 0.5 8.4 4.5 9.2 4.5 0 20 从表3-7中选出节约值最大为23.6，其对应的两个顶点为1、11。如果连接1和11 ，则与上述线路合并，其总需求量为8，未超过一辆车的运输能力8，因此，连接0-9-10-11-1-0成回路，则将与顶点1、9、10、11相关的节约值都赋为0，表示顶点1、9、10、11不可能再与其他点相连，其结果如下表所示。 . . 表3-8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 0 0 0 2 0 4.8 0 3 0 7.4 8.5 0 4 0 0 0 0 0 5 0 5.6 8.7 17.2 0 0 6 0 7.4 8.5 0 0 17.9 0 7 0 4.6 0.7 0.2 0 0.4 0.2 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 0 3.4 -0.5 -1 0 0.2 0 17.1 0 0 0 0 12 0 -0.2 1.7 2.4 0 3.6 3.4 4.6 0 0 0 7.4 0 13 0 4.9 8.5 5.5 0 16.7 16.3 -0.3 0 0 0 -0.5 3.9 0 14 0 4.4 0.5 0 0 0.2 1 18.2 0 0 0 20.9 6.4 0.5 0 15 0 4.3 8.5 10 0 10 10 0.2 0 0 0 0 2.3 9.9 0 0 16 0 14.3 6.3 15 0 9.2 14 4.2 0 0 0 3 0.4 7.5 4 6 0 17 0 8.4 8.7 17.2 0 13.9 17.7 1.4 0 0 0 0.2 1.2 12.7 1.2 9.1 13.2 0 18 0 0.4 0.5 1 0 1.2 1 12.2 0 0 0 0 11.4 1.5 15 1 0 0.2 0 19 0 2.9 6.9 13.5 0 13.2 13.5 0.7 0 0 0 0.5 6 13.4 0.5 8.4 4.5 9.2 4.5 0 20 从表3-8中选出节约值最大为20.9，其对应的两个顶点为12、15。如果连接12和15，则与上述线路合并，其总需求量为7，未超过一辆车的运输能力8，因此，连接0-15-12-5-19-0成回路，则将5、15;12、15与15、19的节约值赋为0。同时，由于顶点12成回路的中间点，则与顶点12相关的节约值都赋为0，表示顶点12不可能再与其他点相连，其结果如下表所示。 表3-9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 0 0 2 . . 0 4.8 0 3 0 7.4 8.5 0 4 0 0 0 0 0 5 0 5.6 8.7 17.2 0 0 6 0 7.4 8.5 0 0 17.9 0 7 0 4.6 0.7 0.2 0 0.4 0.2 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 12 0 -0.2 1.7 2.4 0 3.6 3.4 4.6 0 0 0 0 0 13 0 4.9 8.5 5.5 0 16.7 16.3 -0.3 0 0 0 0 3.9 0 14 0 4.4 0.5 0 0 0.2 1 18.2 0 0 0 0 6.4 0.5 0 15 0 4.3 8.5 10 0 10 10 0.2 0 0 0 0 2.3 9.9 0 0 16 0 14.3 6.3 15 0 9.2 14 4.2 0 0 0 0 0.4 7.5 4 6 0 17 0 8.4 8.7 17.2 0 13.9 17.7 1.4 0 0 0 0 1.2 12.7 1.2 9.1 13.2 0 18 0 0.4 0.5 1 0 1.2 1 12.2 0 0 0 0 11.4 1.5 0 1 0 0.2 0 19 0 2.9 6.9 13.5 0 13.2 13.5 0.7 0 0 0 0 6 13.4 0.5 8.4 4.5 9.2 4.5 0 20 从表3-9中选出节约值最大为18.2，其对应的两个顶点为8、15。如果连接8和15，则与上述线路合并，其总需求量为12，超过一辆车的运输能力8，因此， 8、19;8、5;8、12和8、15也不能连接，则将8、19;8、5;8、12和8、15的节约值赋为0. 继续选出节约值最大为17.9，其对应的两个顶点为6、7。如果连接6和7，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，6和7不能连接 ，4和6也不能连接，则将6、7和4、6的节约值赋为0。 选出节约值最大为17.7，其对应的两个顶点为7、18。如果连接7和18，则与上述线路合并，其总需求量为10，超过一辆车的运输能力8，因此，7和18不能连接 ，4和18也不能连接，则将7、18和4、18的节约值赋为0。 选出节约值最大值为16.7，其对应的两点为6、14。6、14两处的需求量之和为4，未超过一辆车的运输能力8，因此，连接6、14成回路，即0-6-14-0.再将顶点6、14的节约值赋为0. 选出节约值最大为16.3，其对应的两个顶点为7、14。如果连接7和14，则与上述两条线路合并，其总需求量为11，超过一辆车的运输能力8，因此，7和14不能连接 ，4和14也不能连接，则将7、14和4、14的节约值赋为0. 选出节约值最大为15，其对应的两个顶点为4、17。如果连接4和17，则与. . 上述线路合并，其总需求量为8，未超过一辆车的运输能力8，因此，连接0-17-4-7-0成回路，则将与顶点4、7、17相关的节约值都赋为0，表示顶点4、7、17不可能再与其他点相连，其结果如下表所示。 表3-10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 0 0 2 0 4.8 0 3 0 0 0 0 4 0 0 0 0 0 5 0 5.6 8.7 0 0 0 6 0 0 0 0 0 0 0 7 0 4.6 0.7 0 0 0.4 0 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 12 0 -0.2 1.7 0 0 3.6 0 4.6 0 0 0 0 0 13 0 4.9 8.5 0 0 0 0 -0.3 0 0 0 0 3.9 0 14 0 4.4 0.5 0 0 0.2 0 0 0 0 0 0 6.4 0.5 0 15 0 4.3 8.5 0 0 10 0 0.2 0 0 0 0 2.3 9.9 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 8.4 8.7 0 0 13.9 0 1.4 0 0 0 0 1.2 12.7 1.2 9.1 0 0 18 0 0.4 0.5 0 0 1.2 0 12.2 0 0 0 0 11.4 1.5 0 1 0 0.2 0 19 0 2.9 6.9 0 0 13.2 0 0.7 0 0 0 0 6 13.4 0.5 8.4 0 9.2 4.5 0 20 选出节约值最大为13.9，其对应的两个顶点为6、18。如果连接6和18，则与上述线路合并，其总需求量为7，未超过一辆车的运输能力8，因此，连接0-18-6-14-0成回路，则将6、18与14、18的节约值赋为0。同时，由于顶点6成回路的中间点，则与顶点6相关的节约值都赋为0，表示顶点6不可能再与其他点相连，其结果如下表所示。 表3-11 . . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 0 0 2 0 4.8 0 3 0 0 0 0 4 0 0 0 0 0 5 0 0 0 0 0 0 6 0 0 0 0 0 0 0 7 0 4.6 0.7 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 12 0 -0.2 1.7 0 0 0 0 4.6 0 0 0 0 0 13 0 4.9 8.5 0 0 0 0 -0.3 0 0 0 0 3.9 0 14 0 4.4 0.5 0 0 0 0 0 0 0 0 0 6.4 0.5 0 15 0 4.3 8.5 0 0 0 0 0.2 0 0 0 0 2.3 9.9 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 8.4 8.7 0 0 0 0 1.4 0 0 0 0 1.2 0 1.2 9.1 0 0 18 0 0.4 0.5 0 0 0 0 12.2 0 0 0 0 11.4 1.5 0 1 0 0.2 0 19 0 2.9 6.9 0 0 0 0 0.7 0 0 0 0 6 13.4 0.5 8.4 0 9.2 4.5 0 20 选出节约值最大为13.4，其对应的两个顶点为14、20。如果连接14和20，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，14和20不能连接 ，6和20;18和20也不能连接，则将6、20;14、20和18、20的节约值赋为0. 选出节约值最大值为11.4，其对应的两点为13、19。如果连接13和19，则与上述线路合并，其总需求量为11，超过一辆车的运输能力8，因此，13和19不能连接，13、19;13、5;13、12和13、15也不能连接，则将13、19;13、5;13、12和13、15的节约值赋为0. 选出节约值最大为9.9，其对应的两个顶点为14、16。如果连接14和16，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，14和16不能连接 ，6和16;18和16也不能连接，则将6、16;14、16和18、16的节约值. . 赋为0. 选出节约值最大为8.7，其对应的两个顶点为3、18。如果连接3和18，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，3和18不能连接 ，3和18;3和6;3和14也不能连接，则将3、18;3、6和3、14的节约值 赋为0. 选出节约值最大为8.5，其对应的两个顶点为3、16。如果连接3和16，其总需求量为4，未超过一辆车的运输能力8，因此，连接3、16成回路，即0-3-16-0.再将顶点3和16的节约值赋为0. 选出节约值最大为8.4，其对应的两个顶点为2、18。如果连接2和18，则与上述线路合并，其总需求量为10，超过一辆车的运输能力8，因此，2和18;2和6;2和14也不能连接，则将2、18;2、6和2、14的节约值赋为0. 选出节约值最大为8.4，其对应的两个顶点为16、20。如果连接16和20，其总需求量为6，未超过一辆车的运输能力8，因此，连接16、20成回路，即0-3-16-20-0.再将顶点16、20和3、20的节约值都赋为0. 同时，由于顶点16成回路的中间点，则与顶点16相关的节约值都赋为0，表示顶点16不可能再与其他点相连，其结果如下表所示。 表3-12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 0 0 2 0 4.8 0 3 0 0 0 0 4 0 0 0 0 0 5 0 0 0 0 0 0 6 0 0 0 0 0 0 0 7 0 4.6 0.7 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 12 0 -0.2 1.7 0 0 0 0 4.6 0 0 0 0 0 13 0 0 0 0 0 0 0 -0.3 0 0 0 0 3.9 0 14 0 4.4 0.5 0 0 0 0 0 0 0 0 0 0 0.5 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 . . 0 0 0 0 0 0 0 1.4 0 0 0 0 1.2 0 1.2 0 0 0 18 0 0.4 0.5 0 0 0 0 0 0 0 0 0 0 1.5 0 0 0 0.2 0 19 0 2.9 0 0 0 0 0 0.7 0 0 0 0 6 0 0.5 0 0 0 4.5 0 20 选出节约值最大为6，其对应的两个顶点为13、20。如果连接13和20，则与上述线路合并，其总需求量为10，超过一辆车的运输能力8，因此，13和20不能连接 ，13和3;13和16也不能连接，则将13、3;13、16和13、20的节约值赋为0. 选出节约值最大为4.8，其对应的两个顶点为2、3。如果连接2和3，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，2和3不能连接 ，2和16;2和20也不能连接，则将2、3;2、16和2、20的节约值赋为0. 选出节约值最大为4.6，其对应的两个顶点为2、8。如果连接2和8，其总需求量为8，未超过一辆车的运输能力8，因此，连接,2、8成回路，即0-2-8-0.再将与顶点2和8相关的节约值都赋为0，表示顶点2和8不可能再与其他点相连。 选出节约值最大为4.5，其对应的两个顶点为19、20。如果连接19和20，则与上述两条线路合并，其总需求量为13，超过一辆车的运输能力8，因此，15、3;15、16;15、20;19、3;19、16和19、20也不能连接，则将8、3;8、16;8、20;19、3;19、16和19、20的节约值赋为0. 选出节约值最大为3.9，其对应的两个顶点为13、14。如果连接13和14，则与上述线路合并，其总需求量为11，超过一辆车的运输能力8，因此，13和14不能连接 ，13和18;13和6也不能连接，则将13、6;13、14和13、18的节约值赋为0. 选出节约值最大为1.5，其对应的两个顶点为14、19。如果连接14和19，则与上述两条线路合并，其总需求量为14，超过一辆车的运输能力8，因此，15、18;15、14;19、18;19、6和19、14也不能连接，则将15、18;15、14;19、18;19、6和19、14的节约值赋为0. 最后只剩下顶点13没成回路，即成回路0-13-0. 其总需求量为4，超过一辆车的运输能力8。 总有7条线路:1、0-9-10-11-1-0，线路长为38.4km,总运输量为8吨; 2、0-15-12-5-19-0，线路长为66.1km，总运输量为7吨; 3、0-18-6-14-0，线路长为23.2km，总运输量为7吨; 4、0-17-4-7-0，线路长为,51.4km，总运输量为8吨; 5、0-3-16-20-0，线路长为,19.1km，总运输量为6吨; 6、0-2-8-0，线路长为,16.6km，总运输量为8吨; 7、0-13-0，线路长为,12.8km，总运输量为4吨. . . 3.3.4优化后的配送线 16 8 20 3 2 13 4 7 1 17 10配送中心 18 00 00 9 6 15 12 19 14 5 图3-3优化后的家乐福配送线路 . . 4.优化结果分析 4.1 优化前结果 行驶距离 现有路线 实载量(吨) 准载量(吨) 实载率(%) (KM) 0-2-5-0 36 3.8 8 47.5% 0-9-12-0 32 3.9 8 48.75% 0-15-18-0 19 3.8 8 47.5% 0-4-0 22 3.6 8 45% 0-10-17-0 15 3.7 8 46.25% 0-1-19-0 25 3.9 8 48.75% 0-3-11-0 9.2 3.8 8 47.5% 0-8-0 9.2 4.8 8 60% 0-6-14-0 1 3.9 8 48.75% 0-16-20-0 5.1 3.8 8 47.5% 0-13-0 6.4 3.7 8 46.25% 0-7-12-0 32 5.7 8 70.125% 211.9 45.1 80 合计 (平均)50.3% 表4-1优化前路线分析 优化前成本经计算为10757元。 4.2 优化后结果 表4-2运行结果分析 所需车辆数 行驶距离(KM) 运输成本(元) 第1次 7 376.87 12706 第2次 7 372.63 12579 第3次 7 333.52 11406 第4次 7 381.59 12848 第5次 7 416.69 13901 . . 第6次 7 374.58 12637 第7次 7 383.36 12901 第8次 7 291.57 10147 平均值 7 366.35 12291 最小值 7 291.57 10147 表4-3优化后路线 准载量(吨) 实载率% 优化后路线 行驶距离(KM) 实载量(吨) 0-11-13-19-0 26 7.6 8 95% 0-10-5-7-0 88 6.5 8 81.25% 0-20-3-1-0 13.9 5.5 8 71.25% 0-12-16-18-0 25.1 7.8 8 97.5% 0-8-9-6-0 36.2 7.4 8 92.5% 0-4-17-2-0 23.1 7.9 8 98.75% 0-15-14-0 19 2.9 8 36.25% 合计 231.3 45.6 56 (平均)81.43% 优化后只需要7辆车，减少了5辆车;实载率增加到81.43%，提高了31.13%;总成本减少了610元。 ;minZ=10147元. D=291.57KM;K=7辆 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] 高晓亮,伊俊敏,甘卫华.仓储与配送管理[M].清华大学出版社,2006. [8] 孔少彻,梁彤铮.商品物流配送优化策略探讨[J].市场论坛,2009(7):94-95. [9] 蔡临宁.物流系统规划—建模实例分析[M].北京:机械工业出版社,2003.孔少彻, 梁彤铮.商品物流配送优化策略探讨[J].市场论坛,2009(7):94-95. [10] 孙焰.现代物流管理技术[M].上海:同济大学出版社,2004. [11] 王鑫.物流配送中车辆优化调度问题的研究与实践[D].沈阳:沈阳航空工业学院 计算机应用技术,2006. [12]马士华 林勇著.供应链管理.北京:高等教育出版社，2003. [13] 徐剑,牟燕妮等.物流配送车辆调度优化方法比较研究[J].物流科 技,2006(2):46-49. [14] 许星,物流配送路径优化问题的研究[D].浙江:浙江大学计算机科学与技术学院 计算机应用技术,2006. [15]邹旭东，郑四发，班学钢等,具有交通限制约束的道路网络最优路径算法，公交 通科技，2002,(8):82-84. [16]蔡淑兰,最短路径算法在铁路客运系统中应用的研究，燕山大学学报[ J]， 1998(4):157-159. [17] K.Altinkemer and B.Gavish(1991), “Parallel Savings Based heuristics For The Delivery Problem”, Operations Research39:456-469. [18]J.B.Atkinson(1994), “A Greedy Look-ahead Heuristic For Combinatorial Optimization:An Application to Vehicle Scheduling With Time Windows”, Journal of The Operational Research Society 45, 673-684. [19]J.B.Atkinson(1998), “A Greedy Randomised Search Heuristic For Time-constrained Vehicle Scheduling And The Incorporation of A Learning Strategy”, Journal of Operations Research Society 49: 700-708. [20]J.Antes and U.Derigs(1995), “A New Parallel Tour Construction Algorithm for the Vehicle Routing Problem with Time Windows”, Working Paper, Department of Economics and Computer Science, University of KEln, Germ .