联华连锁便利店配送线路优化设计.docx

课 程 设 计

课程名称: 交通运输组织学
设计题目: 联华连锁便利店配送线路优化设计
学生姓名:
学 号:
班 级:
院系名称: 交通运输工程学院
指导老师: 周骞、叶鸿、王佳

2014 年 1 月

《交通运输组织学》
课 程 设 计

课程名称: 交通运输组织学
设计题目: 联华连锁便利店配送线路优化设计
学生姓名:
学 号:
班 级:
院系名称: 交通运输工程学院
指导老师: 周骞、叶鸿、王佳

长沙理工大学课程设计任务书
交通运输工程 学院 交通运输 专业 班
课程名称 交通运输组织学
题目 联华连锁便利店配送线路优化设计
学生姓名 学号
同组设计者：无
一、已知技术参数和设计要求
1、已知技术参数与参考资料
①交通运输部客货运组织与管理相关标准与规范
②董千里。交通运输组织学[M] 。人民交通出版社，2008年
③李维斌。公路运输组织学 [M] 。人民交通出版社，2008年
④崔书堂，朱艳茹。交通运输组织学[M]。东南大学出版社，2010年
⑤戴彤焱。运输组织学[M]。机械工业出版社，2008年
2、设计要求
本课程设计是针对学生学习和运用专业知识的综合考核和检查，是学生接受工程类基本训练的重要环节，是交通运输《交通运输组织学》专业课程学习的必修内容之一。本课程设计的特点是，内容所涉及的知识面广，有较强的系统性和综合性，对建模、算法设计、绘图、文本编写等方面有较高的要求。
本课程应运用交通运输组织学课程涉及的相关理论与方法，结合具体实践背景，解决实际问题。要求
① 所涉及方法、模型与理论知识与本课程相关；
② 有具体的实践背景；
③ 课程实际要求完整、系统，从提出问题、解决问题与结论三个方面开展，思路清晰，条理清楚。

二、课程设计应完成的任务
1、详述研究（设计）背景、意义与设计流程；
2、围绕课程中交通组织方面相关内容，完成对其方法、模型的阐述与构建；
3、结合实际背景，采用以上理论，进行运输组织优化等针对性设计，提出方案；
3、对方案结果进行分析。
三、工作计划
本次课程设计安排时间为3周，2013年12月16日至2014年1月4日，具体工作计划如下：
1、2013年12月16日～20日，项目背景资料的收集与整理；
2、2013年12月21日～23日，完成课程设计大纲；
3、2013年12月24日～2013年12月29日，完成课程设计背景与基础资料的分析部分书写工作；
4、2013年12月30日～2014年1月1日，完成课程设计核心——模型分析与问题解决部分的书写工作；
5、2014年1月2日～2014年1月4日，完成绘图与结论部分的书写以及修改工作。
四、课程设计完成提交文档要求
按照以下顺序装订成册：
1、 封面； 2、扉页； 3、任务书； （4）指导书；
5、目录； 6、正文； 7、附录（表格或图纸）；8、成绩评定表
指导老师：
同意按照任务书要求开展设计

教研室意见：
同意按照任务书要求开展设计
教研室主任：

时间：
注：1、此任务书由指导老师填写。如果不够，可以加页；
2、此任务书最迟必须在课程设计开始前一周下达给学生；

交通运输组织学课程设计
指导书
一、课程设计目的与要求
1、课程设计目的
《交通运输组织学》课程是交通运输本科专业的必修课， 是一门理论与实践结合紧密的核心课程。本课程设计是在该门课程的课堂教学完成之后，为巩固课程涉及到的交通运输组织学方面的方法、理论及应用而开展的。通过课程设计，使学生能够结合实际背景，应用已学理论，解决实际问题，从而培养学生资料查阅能力、绘图能力、理论联系实际的能力、系统解决问题的逻辑思维能力等，为毕业论文设计及今后从事相关工作打下基础。
2、课程设计要求
本课程设计要求学生根据课程涉及的相关内容与方法，结合实际背景，系统解决交通运输组织实际问题。从背景分析、提出问题、解决问题、主要结论等几个方面开展。要求课程设计具有系统性、完整性、与课程相关性并具有一定的研究深度。
二、课程设计的依据与资料来源
课程设计的依据：
①交通运输部客货运组织与管理相关标准与规范
②董千里。交通运输组织学[M] 。人民交通出版社，2008年
④ 李维斌。公路运输组织学 [M] 。人民交通出版社，2008年
⑤ 崔书堂，朱艳茹。交通运输组织学[M]。东南大学出版社，2010年
⑤戴彤焱。运输组织学[M]。机械工业出版社，2008年
资料来源：
① 指导教师提供相关资料；
② 实际调研收集资料；
③ 相关书籍；
④ 网络资料收集。
三、课程设计学生应完成的内容
（1）设计背景交代（实际现状分析与问题分析），进行现状分析，提出问题；
（2）阐述解决问题的理论，构建相关模型与优化算法；
（3）提出优化设计方案；
（4）对优化方案进行评价，得出相关结论。

四、课程设计要求及其它
1、时间安排：3周设计时间（2013年12月16日～2014年1月4日），实际操作中，可提前进行相关资料的收集与大纲的完成；
2、要求独立完成，一人一题，每人提交1份打印的设计成果（A4）及电子文档；
3、格式要求：装订按照要求的顺序依次装订成册，文档具体格式参考格式模板；
4、纪律要求：集中在固定教室严格考勤，按时作息，一般不允许请假，如遇特殊情况，需要填写请假条报院领导批准，否则按照每天旷课8节处理。另请假或旷课时数累计达全部设计时间的1/3以上，该课程设计按照零分计。

运输与物流工程系
2013年12月

目录
前言 1
第一章 联华连锁便利店背景和物流配送 3
1.1 背景 3
1.2 配送路线优化的必要性和可行性分析 5
1.2.1 配送路线优化设计的必要性 5
1.2.2 配送路线优化设计的可行性 5
1.3 配送路线优化的意义 6
第二章 联华超市配送路线作业现状 7
第三章 配送线路优化模型及算法 8
3.1配送线路优化的模型 8
3.1.1多回路运输—VRP模型 8
3.1.2 PDPTW问题模型 8
3.2.3节约算法 11
第五章 方案综合评价 19
5.1 算法的适用度评价 19
5.2加强线路管理水平 20
5.3 公司采用该方案的整体评价 20
第六章 总结 21
参 考 文 献 24

前言
随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域”。配送是现代物流的一个重要环节，随着物流的全球化、信息化及一体化,配送在整个物流系统中的作用变得越来越重要。配送是连接生产与消费之间的一种中介服务。它是指按客户(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。
配送不是单纯的运输或送货，而是运输与其他活动（集货，分货，配货）的组合，是“配”与“送”的有机结合。因此对于配送问题的研究可分为对 “配”和“送”两方面的研究。“配”主要为配送中心选址问题，“送”包括旅行商问题(TSP)、车辆路线优化问题(VRP)。由于选址的外部因素（经济，基础设施，环境等）及内部因素（企业战略，劳动力成本和素质等）的影响，单纯考虑距离问题的选址是不合理的，因此在本文中不对“配”进行研究，主要对“送”进行研究。
配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速度、成本、效益影响很大。设计合理、高效的配送路线方案，不仅可以减少配送时间，降低作业成本，提高企业的效益，而且可以更好地为客户服务，提高客户的满意度，维护企业良好的形象。
配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使用车辆尽可能少）。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要启发算法去求得近似最优解。
本文将以桂林市联华超市当前的配送线路的优化问题作为研究对象，对全市各联华分店需求量及运距进行分析计算，建立VRP数学模型，运用节约算法
和扫描算法以及改进的最近插入法对建立的模型进行求解，对百源木业的配送路线进行优化。最后对三种方法求得的结果进行比较分析，从而为联华连锁超市提供较合理的配送方案，以期减少配送里程，降低物流运输成本，提高超市物流运作效率，客户服务质量和整体竞争力。

第一章 联华连锁便利店背景和物流配送
1.1 背景
联华超市创建于1991年5月，是上海首家以发展连锁经营为特色的超市公司，目前联华已成为现今中国最大的商业零售企业，形成了大型综合超市（大卖场）、超级市场、便利店等多元业态联动互补的竞争优势。在上海、北京、天津、江苏、浙江、安徽、江西、广东、山东、山西、河南、河北、辽宁、吉林、新疆、内蒙等20多个省市和自治区的100多个城市建立了强大的连锁经营网络，是消费者最信赖的商业品牌。
发展壮大后的联华着力打造核心竞争力，在战略创新、经营创新、管理创新、技术创新等方面不断取得新突破。联华在全国建起了商品采购网络，建成了国内首家大型智能化配送中心，先进的计算机信息系统已经覆盖了联华的所有门店，实现了商业管理的自动化。2003年销售规模达 200多亿元，门店数近 2600家。再次以雄厚的实力奠定了在中国零售业的龙头地位。
联华超市股份有限公司，有“零售连锁推土机” 之称，至2004年，联华公司以营业额计已连续6年位列中国零售业榜首，大型综合超市、超级市场及便利店是三大主要经营零售业态。2004年以联华为首的中国第一大零售集团百联集团销售规模达6762714万元、5493门店数个，其中联华超市公司销售额为3068494万元。
广西联华超市股份有限公司（前身为广西佳用商贸股份有限公司），主要经营业态有大型会员制超市、综合超市、社区超市、便利店，公司共代理和分销国内外知名日用化妆品和食品品类3000多个。是目前广西连锁店数量最多、年销售总额最大、代理商品品牌最多、企业发展最快的民营商业企业。据全国工商联统计，广西联华位列2002年中国民营企业500强第392位，中国连锁经营协会统计，广西联华位列连锁企业百强第 85位，全国连锁超市百强第51位，全国成长企业百强第48位。连续12年获得广西区工商管理局评为“重合同、守信用”单位。
广西联华成立于1991年，也是在中国成立较早的连锁超市公司之一。目前拥有53家直营店，04年销售额8亿多元，涉及柳州、桂林、河池、来宾、贵港等五地市，经营面积近10万平方米。其中柳州有直营店39家，经营面积 5万多平方米。
便利店，顾名思义是一种提供便利的商店。一般来说它的营业面积不大，约在60－100平方米左右，有数名工作人员，能提供 3000种左右人们日常生活必需的小商品，并能提供一些人们日常所需的服务。每天的营业时间一般长达16小时或24小肘通宵服务。由于营业面积不大，它可以深入到各个居民小区、车站、码头等，贴近人们的生活，给人们带来了极大的方便。现在人们不难在各居民小区，各条马路上发现便利店的身影。由于便利店规模较小，故在管理上更显重要，采用连锁经营的方式，所有下属便利门店采用统一的企业形象设计，统一的管理模式，能取得很好的品牌效应。统一的进货方式可保证所进商品的质量，同时降低采购成本。统一的销售价格，又可使顾客感到满意和放心。该公司经过几年来的努力，已取得了良好的经营业绩。
该公司各便利店所供商品的进货渠道主要有以下三个方面。少部分鲜活商品（如面包。牛奶、蔬菜等）每天由供货商直接送到各便利门店（以下简称门店）。公司自己建有一个冷冻仓库，负责各门店冷冻商品的供应，如冷冻肉食、禽类、速冻食品等。公司还有一个配货中心，负责其他常温商品的供应，如酒类、饮料、日用小商品等。门店根据各自的经营状况，在要货当日的上午10时前，将要货信息输入电脑，经通讯线路传送到有关配货中心和冷冻仓库，而配货中心等收到各门店的要货信息，经汇总后，组织好相应商品，及时送到各门店。
公司规定各门店每两天可要货一次。按目前400多家门店的总规模，每天要货的门店达200多家，且分布在全市各个地方。冷冻仓库由于供应品种较少，根据经验，每辆送货汽车一次满载可送20家门店，每天每车送货2次，现有车辆6辆。配货中心，由于供应品种较多，共有车辆11辆。如何合理地调度这些送货车辆，在保证各门店要货能及时得到满足的前提下，使送货车辆经过的路途最少，是一个十分有意义的工作。
桂林市联华连锁便利店隶属于广西联华超市股份有限公司，本文探讨的就是桂林市的设立的十多家联华连锁便利店的配送路线情况。本文将对这十多家门店与运输车辆进行调度优化，阐述物流配送过程中配送线路设计与线路优化问题。
1.2 配送路线优化的必要性和可行性分析
1.2.1 配送路线优化设计的必要性
物流是现代企业发展的动脉，特别是对于商业连锁企业来说，物流就是企业发展的咽喉，是制约很多企业发展的瓶颈。而随着商业竞争的加剧，传统的低层次的竞争（如销售的竞争）在消费群体的消费心理日渐理性的今天，已转化成了产、供、销立体化的竞争，谁能在产供销链条上减少中间的环节、降低经营成本，谁就能够确立巨大的竞争优势。
随着全球经济一体化、顾客需求的个性化和多样化发展，产品更新替换速度在不断加快、产品的生命周期也不断缩短，物流运输配送变得越来越复杂，物流成本也变得越来越高。为了降低风险，减少物流成本，处于物流供应链上各环节的部门或单位都纷纷采取各种措施以适应这种多品种、小批量。多频度的物流配送服务需求，如降低库存水平，减少订货量，增加订货频率，实行按订单生产等措施，这在某种程度上满足了发展的要求，但运输和配送成本一直居高不下。
造成物流运输成本居高不下的主要原因是出现了一些不合理的运输和方式，如对流运输、迂回运输、非最短路径运输和配送、非满载运输等。这些都会致使运输和配送服务水平难以提高，因此对运输和配送问题进行优化就变得非常有意义。联华超市配送中心的配送路线都是根据人的主观意识来制订的，缺乏科学依据，车辆装载率不高，路径也不是最短，造成了配送成本的居高不下，并且造成了资源的浪费。配送线路合理与否对配送速度、成本、效益影响很大，采用科学、合理的方法来确定配送线路，是配送活动中一项非常重要的工作。合理的选择配送线路，对企业和社会都具有重要的意义。
1.2.2 配送路线优化设计的可行性
联华超市配送中心配送路线的优化设计属于车辆优化调度问题，而求解车辆优化调度问题的主要方法精确算法、启发算法和智能算法。而精确算法的计算量和计算时间随着车辆优化问题规模的增大呈指数增长，对于较大规模的车辆优化调度问题不适用。
启发式算法当中的节约里程法，计算步骤简单，计算速度快，且易于考虑各种实际问题，并不追求问题的最优解，而强调问题解的满意性，可以高效地得到问题的近似最优解。本文针对零售业的实际情况，即各个门店对于某些常用商品的需求是稳定而不间断的，在研究这类问题的时候，不需要各个门店在不同时期对于不同货物的需求，只要每次配送固定的商品即可，对于这类问题，本文建立了问题一的模型，这种模型往往运用于配送中心的某些常用的子系统，如某些常用的商品的配送，这类问题讲求简单高效，追求最快的满意解。因此，用节约里程法解决问题一这类模型是可行的。
而对于更为复杂的配送模型，比如大量的非常规商品的配送，不同的门店需要不同的商品，针对这类错综复杂的模型，必须借助现代化的智能算法，使得配送方案更为科学合理，准确易行。因此，用智能算法当中的遗传算法来解决问题二这类模型是可行的。
1.3 配送路线优化的意义
配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合的理配送路线，对企业和社会都具有很重要的意义。
对企业来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本;(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度;(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益。
对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用 。

第二章 联华超市配送路线作业现状
目前联华的物流体系是，所有货物由供货商直接送达店面，这种方式虽然灵活，但影响了供货速度，也加重了供货商的负担。由于联华各门店自行采购，供货商不一，大大影响了供货速度；并且，联华目前的供货方式也加重了供货商负担。随着中国零售市场白热化竞争的日趋激烈，建设区域物流配送中心无疑可以帮助联华加快店面更新速度，巩固市场。而联华超市也应在各个市区确立商品配送中心，以后供应商只要将货物运送至物流中心，各分店商品的配送统一由物流中心来实现。
作为便利店模式的首推者，“灵活”和“适应”一直被视为联华成功改变中国人购物习惯的法宝。店长的“钦点”让联华许多货架上充盈着本地的产品。加上所开门店位置多位于大中型城市，这让门店直送方式有了很强的操作性。联华不用多费心思经营物流，只需让供应商们接上它的订单生成系统，再顺手给个“deadline”（送货的最后期限），一切就告万事大吉。
“小批量，多频次”的订货原则，保证联华可以尽量减少门店库存。而使用时段限制，过期则不收货的“残酷”手段，来保证供应商的准时到货率，在中国也被认为是简明有效的。近乎于零的物流费用和基本合格的配送质量，曾让联华人颇感自豪。
真正伤脑筋的是供应商们，本来利润就不高，面对联华在物流上的不作为，还得自己挖空心思节约成本。目前，联华的商品配送分几种情况，大部分情况是通过第三方物流实现的，费用由供应商承担。以北京地区为例，给联华做配送的主要有上海成协，朝百批发，大荣物流等几家公司。有一小部分品牌，包括可口可乐、宝洁和百事可乐等大公司以及一些生鲜食品等都具有直送的能力。
有些联华的门店还习惯于将降价损失、损耗和营业额、毛利率指标的完不成数，转嫁给供应商来承担，也就是说供应商与总部谈好的交易条件到了门店是要附加的，因为联华是最大的，供应商也无可奈何；另外据悉，联华近期采取的分区采购政策，也使得供货商从过去习惯于以一对一的模式变成了以一对多，这样无疑加大了供货商的运营成本，从而导致他们抱怨多多。

第三章 配送线路优化模型及算法
3.1配送线路优化的模型
3.1.1多回路运输—VRP模型
多回路运输问题是现实中很普遍的一种调配问题，特别对于有大量服务对象的实体，例如拥有一个上千客户的企业。此类调配的核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型。
该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程最短，费用最小，时间尽量少等）。它涉及了多辆交通工具的服务对象的选择和路径确定两方面问题。
一个典型的VRP模型可以如下表述：
（1）基本条件 现有m辆相同的车辆停在一个共同的源点，它需给n个客户提供货物，顾客为。
（2）模型目标 确定所需的车辆数N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用最小。
（3）限制条件：N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点；车辆的容量限制不能超过；特殊问题还需考虑时窗限制；运输规章限制。
3.1.2 PDPTW问题模型
PDPTW问题是VRP问题的一个很有用的扩展，近段时期引起越来越多的研究者的注意，许多新的优化思想和优化方法被引入到此问题中，并产生了一定的影响。PDPTW问题（Pickup and Delivery Problem with Time Windows，带时间窗口的装卸货问题）是为一个车队寻找最优的运输路径来满足所有客户的运输需求。车队的每一辆车从车库出发，沿优化的路径为客户服务并最终返回车库。每一辆车都给定最大容量和出发、返回车库。每个运输需求指定一个装货点、一个卸货点和运输货物量。装货点、卸货点以及车库都有时间窗口。车辆必须在规定的时间窗内访问装、卸货点。也就是说，在运输网络中，已知待服务的装、卸货点和车库的位置和时间窗口、车辆的最大容量以及运输货物量的前提下，设计车辆运输路径，使运输成本最小化。
PDPTW的解是路径的集合，每一辆车对应一条路径，包括以下方面：
l 1、需要用到的车辆数目；即，有多少条路径
l 2、 每辆车访问每一个点的顺序以及时刻
PDPTW问题中，要求满足的约束条件主要有以下几种：
1) 时间窗口约束：车辆必须在规定的时间窗内服务装货点或卸货点。如果车辆在 之前到达点 ，必须在点 等待到 才能开始装卸货。车辆在 时刻之后到达点 ，则无法按时完成该点的装卸货任务，因而是不允许的。
2） 访问约束：车辆到客户指定的装货点装货，然后运输到相应的卸货点卸货。每一个点都必须被一辆车服务且只能服务一次。
3） 车库约束：车辆必须从车库出发到某一装货点，最后从某一卸货点返回车库。车辆返回车库后不允许再次出发。
4） 成对约束：一个客户需求的装货点 和其对应的卸货点 必须被同一辆车访问。
5） 次序约束：客户需求的装货点 必须在对应的卸货点 之前被访问。
6） 容量约束：任何时刻车辆所装货物量之和不能超过车辆的最大容量。
上述约束是PDPTW问题中常见的几种约束条件。另外还会根据实际情况的要求增加一些附加约束，如车辆类型与货物类型之间的类型匹配约束，司机的最大工作时间约束等。
PDPTW问题的优化目标也是总运输成本最小。一般来说，与总运输成本有关的费用包括：车辆的固定代价，是运输代价中最重要的部分，要最大可能的减少使用的车辆数；与车辆行驶距离有关的代价。
3.2 配送问题的求解算法
车辆配送问题的求解算法有很多种，但究其本质来讲，基本分为最优化算法和启发式算法两大类。
3.2.1最优化算法
最优化算法，也称之为精确算法，就是指能够通过有限的计算和推理得到优化问题的最优解的算法。在配送问题中，所谓最优化算法就是找到一组路径集合，使得其目标函数值比其它任何一组可行路径集合的目标函数值更好。
常用的最优化算法主要有：分枝定界算法、动态规划算法和整数规划。通常情况下，NP-hard问题的精确解法的计算量较大，而且随着问题规模的增大计算量会呈爆炸式的增长，因此在实际问题中最优化算法的应用范围有限。
3.2.2启发式算法
启发式算法是通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法。启发式方法要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而比较具体的模型及算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径。
用启发式方法求解问题时强调“满意”。常常是得到满意解，决策者就认为可以了，而不去追求最优解。之所以这样是因为：
(1) 很多问题不存在严格的最优解（如目标之间存在矛盾的多目标问题），此时对目标的满意性比最优性更能描述人们的选择行为。
(2) 得到某些问题最优解的成本太大。
(3) 从实际出发，有时探求问题的最优解没有意义。
对于NP-Hard问题，人们自然会想到启发式的算法。启发式的算法就是根据某种启发式的信息对已知的可行解进行改善，通过若干次的迭代获得相对满意的解。和精确算法相比，启发式的算法不能保证得到全局最优解，但是实现起来相对简单。
由于车辆运输调度问题是NP-hard问题，而现实中该问题规模一般很大，因此想以能够接受的运算速度找到最优解是不可能的。而启发式算法可以在相对短时间内找到“满意”解，为此研究人员把精力主要放在构造高质量的启发式算法上。目前已提出的求解车辆运输调度问题的启发式算法很多，主要分为经典启发式算法和现代启发式算法两类。
3.2.3节约算法
利用节约法确定配送线路的主要出发点是，根据配送中心的运输能力（包括车辆的多少和载重量）和配送中心到各个用户以及各个用户之间的距离来制订使总的车辆运输的t.km（吨数乘上公里数）数最小的配送方案。
为了便于介绍节约法的基本思想，设：
①配送的是一种货物；
②各用户的坐标（x，y）及需求量均为已知；
③配送中心有足够的运输能力。
利用节约法制订出的配送方案除了送总 t.km 数最小外，还满足以下条件：
①方案能满足所有用户的要求；
②不使任何一辆车超载；
③每辆车每天的总运行时间或行驶里程不超过规定的上限；
④能满足用户到货时间要求。
（2）节约法的基本思想
如图3-1所示，设A 点为配送中心，它分别向用户B 和C送货。设A 到B 和C 的距离为a
和b，两个用户B、C 之间的距离为c，送货方案只有两种，如图中（a）和（b）所示。
B
C
C
B
(a)
（b）
节约法的送货方案
A
A

图3-1 节约法配送方案图
图中（a）方案是从配送中心A 向用户B、C分别单独送货，配送路线为：A→B→A，A→C→A；
总的配送距离为：
Da=2a + 2b
图（b）方案是从配送中心向用户，A 依次送货，配送线路为：A→B→C；
总的配送距离为：
Db=a + b + c
对比这两个方案，哪个更合理呢？这就要看 Da 和Db 哪个最小，配送距离月小则说明方案越合
理，由总距离公式可得出：
Da – Db =2a + 2b – a – b – c = a + b – c
如果把图中的A、B、C看成为一个三家性的三个顶点，那么a、b、 c 则是这个三角
形三条边的长度。由三角形的几何性质可知，任意两条边之和均大于第三边(即a + b > c)，有a + b – c > 0 。因此，可以认定Da – Db的结果是大于零的，即：
Da – Db
可以看出，（b）方案优于（a）方案，这种分析方案优劣的思想就是节约法的基本思想。根据节约法的基本思想，如果有一个配送中心分别向 N 个用户配送货物，在汽车载重能力允许的前提下，每辆汽车的配送线路上经过的用户个数越多，则配送线路越合理，总配送距离越小。第四章 基于节约算法的配送路线优化
联华连锁便利店在桂林市的分布具体如下图所示：

图4-1 桂林市联华便利超市分布图
从上图可看出联华便利店在市区内分布较为均匀，在环城路上零星分布着几家，结合桂林市实际城区分布特点以及费用考虑，联华便利店的配送中心定在桂林市七星路高新区附近，这里既有良好的仓库设备，交通情况也非常便利，同时又靠近桂林市区，配送方便，费用合理。
以下是每个分店（一年365天）平均每天的需求量情况表：
表4-1 联华便利店分店平均每天需求量表
分店
1
2
3
4
5
6
需求量(KG)
302
295
292
333
289
354
分店
7
8
9
10
11
12
需求量(KG)
337
349
361
336
306
314
现有路线是固定不变且为已知,每条线路行驶距离见下表所示：
表4-2 联华便利店距联华配送中心最短距离（公里）

P

P1
1
P1

P2
1.6
2.4
P2

P3
1.3
2.1
2.7
P3

P4
1.8
0.75
3
2.7
P4

P5
4.2
3.2
5
5.2
2.5
P5

P6
3.5
2.6
4.9
4.1
1.9
1.8
P6

P7
3.4
2.7
5
3.4
2.3
3.4
1.6
P7

P8
2.8
1.9
4.2
3.4
1.3
2.2
0.73
1.4
P8

P9
2.3
1.6
3.9
2.6
1.2
3
1.5
1.2
0.82
P9

P10
4.2
3.3
5.6
4.6
2.6
2.2
0.73
1.6
1.3
2
P10

P11
3.2
2.8
4.6
2.2
2.9
4.9
3.2
1.8
2.7
1.9
3.4
P11

P12
4.6
3.9
6.2
4.5
3.5
3.9
2.2
1.2
2.3
2.3
1.7
2.6
P12
设每个车辆的运输能力是2吨，根据案例可知，联华平均每天所用车辆数为2辆。现在用节约算法对该配送线路问题进行求解。
根据配送中心与分店之间,分店与分店之间的距离距离表，计算出用户间的节约里程。

表4-3 节约值矩阵表
302

P1

295
P2
0.2
P2

292
P3
0.2
0.2
P3

333
P4
2.05
0.4
0.4
P4

289
P5
2
0.8
0.3
3.5
P5

354
P6
1.9
0.2
0.7
3.4
5.9
P6

337
P7
1.7
0
1.3
2.9
4.2
5.3
P7

349
P8
1.9
0.2
0.7
3.3
4.8
5.57
4.8
P8

361
P9
1.7
0
1
2.9
3.5
4.3
4.5
4.28
P9

336
P10
1.9
0.2
0.9
3.4
6.2
6.97
6
5.7
4.5
P10

306
P11
1.4
0.2
2.3
2.1
2.5
3.5
4.8
3.3
3.6
4
P11
314
P12
1.7
0
1.4
2.9
4.9
5.9
6.8
5.1
4.6
7.1
5.2
从表3-2中选出节约值最大值为7.1，其对应的两点为P10、P12。P10、P12两处的需求量之和为650kg，未超过一辆车的运输能力2t，因此，连接P10、P12成回路，即P-P10-P12-P。再将顶点P10和P12的节约值赋为0。结果如表3-3所示。
表4-4 除P10与P12连接点节约值表
302

P1

295
P2
0.2
P2

292
P3
0.2
0.2
P3

333
P4
2.05
0.4
0.4
P4

289
P5
2
0.8
0.3
3.5
P5

354
P6
1.9
0.2
0.7
3.4
5.9
P6

337
P7
1.7
0
1.3
2.9
4.2
5.3
P7

349
P8
1.9
0.2
0.7
3.3
4.8
5.57
4.8
P8

361
P9
1.7
0
1
2.9
3.5
4.3
4.5
4.28
P9

336
P10
1.9
0.2
0.9
3.4
6.2
6.97
6
5.7
4.5
P10

306
P11
1.4
0.2
2.3
2.1
2.5
3.5
4.8
3.3
3.6
4
P11
314
P12
1.7
0
1.4
2.9
4.9
5.9
6.8
5.1
4.6
0
5.2
从表3-3中选出节约值最大为6.97，如果连接P6和P10 ，则与上述线路合并，其总需求量为986kg，未超过一辆车的运输能力2t，因此，连接P6形成回路，即P-P6-P10-P12-P。再将顶点P6和P10的节约值赋为0。
继续选出节约值最大为6.8，其对应两个顶点为P7、P12。如果连接P7和P12 ，则与上述线路合并，其总需求量为1323kg，未超过一辆车的运输能力2t，因此，连接P7形成回路，即P-P6-P10-P12-P7-P。再将顶点P7和P12的节约值赋为0。
由以上连接过程可看出P10点分别与P6、P12两点连接形成回路，P12点也分别与P7、P10两点连接形成回路，因此将所有与P10点、P12点的连接的节约值赋为0。见下表：
表4-5 剩余节约值表（一）
302

P1

295
P2
0.2
P2

292
P3
0.2
0.2
P3

333
P4
2.05
0.4
0.4
P4

289
P5
2
0.8
0.3
3.5
P5

354
P6
1.9
0.2
0.7
3.4
5.9
P6

337
P7
1.7
0
1.3
2.9
4.2
5.3
P7

349
P8
1.9
0.2
0.7
3.3
4.8
5.57
4.8
P8

361
P9
1.7
0
1
2.9
3.5
4.3
4.5
4.28
P9

336
P10
0
0
0
0
0
0
0
0
0
P10

306
P11
1.4
0.2
2.3
2.1
2.5
3.5
4.8
3.3
3.6
0
P11