连锁便利店配送线路优化课程设计范本

1、 课 程 设 计 课程名称: 交通运输组织学 设计题目: 联华连锁便利店配送线路优化设计 学生姓名: 学 号: 班 级: 院系名称: 交通运输工程学院 指导老师: 周骞、叶鸿、王佳 2014 年 1 月交通运输组织学课 程 设 计 课程名称: 交通运输组织学 设计题目: 联华连锁便利店配送线路优化设计 学生姓名: 学 号: 班 级: 院系名称: 交通运输工程学院 指导老师: 周骞、叶鸿、王佳 长沙理工大学课程设计任务书 交通运输工程 学院 交通运输 专业 班课程名称 交通运输组织学 题目 联华连锁便利店配送线路优化设计 学生姓名 学号 同组设计者：无一、已知技术参数和设计要求1、已知技术参数与

2、参考资料交通运输部客货运组织与管理相关标准与规范董千里。交通运输组织学M 。人民交通出版社，2008年李维斌。公路运输组织学 M 。人民交通出版社，2008年崔书堂，朱艳茹。交通运输组织学M。东南大学出版社，2010年戴彤焱。运输组织学M。机械工业出版社，2008年2、设计要求本课程设计是针对学生学习和运用专业知识的综合考核和检查，是学生接受工程类基本训练的重要环节，是交通运输交通运输组织学专业课程学习的必修内容之一。本课程设计的特点是，内容所涉及的知识面广，有较强的系统性和综合性，对建模、算法设计、绘图、文本编写等方面有较高的要求。本课程应运用交通运输组织学课程涉及的相关理论与方法，结合具体

3、实践背景，解决实际问题。要求所涉及方法、模型与理论知识与本课程相关；有具体的实践背景；课程实际要求完整、系统，从提出问题、解决问题与结论三个方面开展，思路清晰，条理清楚。二、课程设计应完成的任务 1、详述研究（设计）背景、意义与设计流程；2、围绕课程中交通组织方面相关内容，完成对其方法、模型的阐述与构建；3、结合实际背景，采用以上理论，进行运输组织优化等针对性设计，提出方案；3、对方案结果进行分析。三、工作计划本次课程设计安排时间为3周，2013年12月16日至2014年1月4日，具体工作计划如下：1、2013年12月16日20日，项目背景资料的收集与整理；2、2013年12月21日23日，完

4、成课程设计大纲；3、2013年12月24日2013年12月29日，完成课程设计背景与基础资料的分析部分书写工作；4、2013年12月30日2014年1月1日，完成课程设计核心模型分析与问题解决部分的书写工作；5、2014年1月2日2014年1月4日，完成绘图与结论部分的书写以及修改工作。四、课程设计完成提交文档要求按照以下顺序装订成册：封面； 2、扉页； 3、任务书； （4）指导书；5、目录； 6、正文； 7、附录（表格或图纸）；8、成绩评定表指导老师：同意按照任务书要求开展设计教研室意见：同意按照任务书要求开展设计教研室主任：时间：注：1、此任务书由指导老师填写。如果不够，可以加页； 2、此

5、任务书最迟必须在课程设计开始前一周下达给学生；交通运输组织学课程设计指导书一、课程设计目的与要求1、课程设计目的交通运输组织学课程是交通运输本科专业的必修课， 是一门理论与实践结合紧密的核心课程。本课程设计是在该门课程的课堂教学完成之后，为巩固课程涉及到的交通运输组织学方面的方法、理论及应用而开展的。通过课程设计，使学生能够结合实际背景，应用已学理论，解决实际问题，从而培养学生资料查阅能力、绘图能力、理论联系实际的能力、系统解决问题的逻辑思维能力等，为毕业论文设计及今后从事相关工作打下基础。2、课程设计要求本课程设计要求学生根据课程涉及的相关内容与方法，结合实际背景，系统解决交通运输组织实际问

6、题。从背景分析、提出问题、解决问题、主要结论等几个方面开展。要求课程设计具有系统性、完整性、与课程相关性并具有一定的研究深度。二、课程设计的依据与资料来源课程设计的依据：交通运输部客货运组织与管理相关标准与规范董千里。交通运输组织学M 。人民交通出版社，2008年李维斌。公路运输组织学 M 。人民交通出版社，2008年崔书堂，朱艳茹。交通运输组织学M。东南大学出版社，2010年戴彤焱。运输组织学M。机械工业出版社，2008年资料来源：指导教师提供相关资料；实际调研收集资料；相关书籍；网络资料收集。三、课程设计学生应完成的内容（1）设计背景交代（实际现状分析与问题分析），进行现状分析，提出问题；

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

8、分计。运输与物流工程系2013年12月目录TOC o 1-3 h u HYPERLINK l _Toc23092 前言 PAGEREF _Toc23092 1 HYPERLINK l _Toc16495 第一章 联华连锁便利店背景和物流配送 PAGEREF _Toc16495 3 HYPERLINK l _Toc7547 1.1 背景 PAGEREF _Toc7547 3 HYPERLINK l _Toc3532 1.2 配送路线优化的必要性和可行性分析 PAGEREF _Toc3532 5 HYPERLINK l _Toc17000 1.2.1 配送路线优化设计的必要性 PAGEREF _T

9、oc17000 5 HYPERLINK l _Toc29 1.2.2 配送路线优化设计的可行性 PAGEREF _Toc29 5 HYPERLINK l _Toc12245 1.3 配送路线优化的意义 PAGEREF _Toc12245 6 HYPERLINK l _Toc13269 第二章 联华超市配送路线作业现状 PAGEREF _Toc13269 7 HYPERLINK l _Toc17738 第三章 配送线路优化模型及算法 PAGEREF _Toc17738 8 HYPERLINK l _Toc29627 3.1配送线路优化的模型 PAGEREF _Toc29627 8 HYPERLI

10、NK l _Toc20071 3.1.1多回路运输VRP模型 PAGEREF _Toc20071 8 HYPERLINK l _Toc8476 3.1.2 PDPTW问题模型 PAGEREF _Toc8476 8 HYPERLINK l _Toc709 3.2.3节约算法 PAGEREF _Toc709 11 HYPERLINK l _Toc2720 第五章 方案综合评价 PAGEREF _Toc2720 19 HYPERLINK l _Toc32252 5.1 算法的适用度评价 PAGEREF _Toc32252 19 HYPERLINK l _Toc3787 5.2加强线路管理水平 PAG

11、EREF _Toc3787 20 HYPERLINK l _Toc14504 5.3 公司采用该方案的整体评价 PAGEREF _Toc14504 20 HYPERLINK l _Toc3943 第六章 总结 PAGEREF _Toc3943 21 HYPERLINK l _Toc4758 参 考 文 献 PAGEREF _Toc4758 24 前言随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域”。配送是现代物流的一个重要环节，随着物流的全球化、信息化及一体化,配送在整个物流系统中的作用变得越来越重要。配

12、送是连接生产与消费之间的一种中介服务。它是指按客户(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。配送不是单纯的运输或送货，而是运输与其他活动（集货，分货，配货）的组合，是“配”与“送”的有机结合。因此对于配送问题的研究可分为对 “配”和“送”两方面的研究。“配”主要为配送中心选址问题，“送”包括旅行商问题(TSP)、车辆路线优化问题(VRP)。由于选址的外部因素（经济，基础设施，环境等）及内部因素（企业战略，劳动力成本和素质等）的影响，单纯考虑距离问题的选址是

13、不合理的，因此在本文中不对“配”进行研究，主要对“送”进行研究。配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速度、成本、效益影响很大。设计合理、高效的配送路线方案，不仅可以减少配送时间，降低作业成本，提高企业的效益，而且可以更好地为客户服务，提高客户的满意度，维护企业良好的形象。配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使用车辆尽可能少）。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变

14、等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要启发算法去求得近似最优解。本文将以桂林市联华超市当前的配送线路的优化问题作为研究对象，对全市各联华分店需求量及运距进行分析计算，建立VRP数学模型，运用节约算法 和扫描算法以及改进的最近插入法对建立的模型进行求解，对百源木业的配送路线进行优化。最后对三种方法求得的结果进行比较分析，从而为联华连锁超市提供较合理的配送方案，以期减少配送里程，降低物流运输成本，提高超市物流运作效率，客户服务质量和整体竞争力。第一章 联华连锁便利店背景和物流配送1.1 背景联华超市创建于1991年5月，是上海首家以发展连锁经

15、营为特色的超市公司，目前联华已成为现今中国最大的商业零售企业，形成了大型综合超市（大卖场）、超级市场、便利店等多元业态联动互补的竞争优势。在上海、北京、天津、江苏、浙江、安徽、江西、广东、山东、山西、河南、河北、辽宁、吉林、新疆、内蒙等20多个省市和自治区的100多个城市建立了强大的连锁经营网络，是消费者最信赖的商业品牌。发展壮大后的联华着力打造核心竞争力，在战略创新、经营创新、管理创新、技术创新等方面不断取得新突破。联华在全国建起了商品采购网络，建成了国内首家大型智能化配送中心，先进的计算机信息系统已经覆盖了联华的所有门店，实现了商业管理的自动化。2003年销售规模达 200多亿元，门店数近

16、 2600家。再次以雄厚的实力奠定了在中国零售业的龙头地位。 联华超市股份有限公司，有“零售连锁推土机” 之称，至2004年，联华公司以营业额计已连续6年位列中国零售业榜首，大型综合超市、超级市场及便利店是三大主要经营零售业态。2004年以联华为首的中国第一大零售集团百联集团销售规模达6762714万元、5493门店数个，其中联华超市公司销售额为3068494万元。广西联华超市股份有限公司（前身为广西佳用商贸股份有限公司），主要经营业态有大型会员制超市、综合超市、社区超市、便利店，公司共代理和分销国内外知名日用化妆品和食品品类3000多个。是目前广西连锁店数量最多、年销售总额最大、代理商品品牌

17、最多、企业发展最快的民营商业企业。据全国工商联统计，广西联华位列2002年中国民营企业500强第392位，中国连锁经营协会统计，广西联华位列连锁企业百强第 85位，全国连锁超市百强第51位，全国成长企业百强第48位。连续12年获得广西区工商管理局评为“重合同、守信用”单位。广西联华成立于1991年，也是在中国成立较早的连锁超市公司之一。目前拥有53家直营店，04年销售额8亿多元，涉及柳州、桂林、河池、来宾、贵港等五地市，经营面积近10万平方米。其中柳州有直营店39家，经营面积 5万多平方米。便利店，顾名思义是一种提供便利的商店。一般来说它的营业面积不大，约在60100平方米左右，有数名工作人员

18、，能提供 3000种左右人们日常生活必需的小商品，并能提供一些人们日常所需的服务。每天的营业时间一般长达16小时或24小肘通宵服务。由于营业面积不大，它可以深入到各个居民小区、车站、码头等，贴近人们的生活，给人们带来了极大的方便。现在人们不难在各居民小区，各条马路上发现便利店的身影。由于便利店规模较小，故在管理上更显重要，采用连锁经营的方式，所有下属便利门店采用统一的企业形象设计，统一的管理模式，能取得很好的品牌效应。统一的进货方式可保证所进商品的质量，同时降低采购成本。统一的销售价格，又可使顾客感到满意和放心。该公司经过几年来的努力，已取得了良好的经营业绩。该公司各便利店所供商品的进货渠道主

19、要有以下三个方面。少部分鲜活商品（如面包。牛奶、蔬菜等）每天由供货商直接送到各便利门店（以下简称门店）。公司自己建有一个冷冻仓库，负责各门店冷冻商品的供应，如冷冻肉食、禽类、速冻食品等。公司还有一个配货中心，负责其他常温商品的供应，如酒类、饮料、日用小商品等。门店根据各自的经营状况，在要货当日的上午10时前，将要货信息输入电脑，经通讯线路传送到有关配货中心和冷冻仓库，而配货中心等收到各门店的要货信息，经汇总后，组织好相应商品，及时送到各门店。公司规定各门店每两天可要货一次。按目前400多家门店的总规模，每天要货的门店达200多家，且分布在全市各个地方。冷冻仓库由于供应品种较少，根据经验，每辆送

20、货汽车一次满载可送20家门店，每天每车送货2次，现有车辆6辆。配货中心，由于供应品种较多，共有车辆11辆。如何合理地调度这些送货车辆，在保证各门店要货能及时得到满足的前提下，使送货车辆经过的路途最少，是一个十分有意义的工作。桂林市联华连锁便利店隶属于广西联华超市股份有限公司，本文探讨的就是桂林市的设立的十多家联华连锁便利店的配送路线情况。本文将对这十多家门店与运输车辆进行调度优化，阐述物流配送过程中配送线路设计与线路优化问题。1.2 配送路线优化的必要性和可行性分析1.2.1 配送路线优化设计的必要性物流是现代企业发展的动脉，特别是对于商业连锁企业来说，物流就是企业发展的咽喉，是制约很多企业发

21、展的瓶颈。而随着商业竞争的加剧，传统的低层次的竞争（如销售的竞争）在消费群体的消费心理日渐理性的今天，已转化成了产、供、销立体化的竞争，谁能在产供销链条上减少中间的环节、降低经营成本，谁就能够确立巨大的竞争优势。随着全球经济一体化、顾客需求的个性化和多样化发展，产品更新替换速度在不断加快、产品的生命周期也不断缩短，物流运输配送变得越来越复杂，物流成本也变得越来越高。为了降低风险，减少物流成本，处于物流供应链上各环节的部门或单位都纷纷采取各种措施以适应这种多品种、小批量。多频度的物流配送服务需求，如降低库存水平，减少订货量，增加订货频率，实行按订单生产等措施，这在某种程度上满足了发展的要求，但运

22、输和配送成本一直居高不下。造成物流运输成本居高不下的主要原因是出现了一些不合理的运输和方式，如对流运输、迂回运输、非最短路径运输和配送、非满载运输等。这些都会致使运输和配送服务水平难以提高，因此对运输和配送问题进行优化就变得非常有意义。联华超市配送中心的配送路线都是根据人的主观意识来制订的，缺乏科学依据，车辆装载率不高，路径也不是最短，造成了配送成本的居高不下，并且造成了资源的浪费。配送线路合理与否对配送速度、成本、效益影响很大，采用科学、合理的方法来确定配送线路，是配送活动中一项非常重要的工作。合理的选择配送线路，对企业和社会都具有重要的意义。1.2.2 配送路线优化设计的可行性联华超市配送

23、中心配送路线的优化设计属于车辆优化调度问题，而求解车辆优化调度问题的主要方法精确算法、启发算法和智能算法。而精确算法的计算量和计算时间随着车辆优化问题规模的增大呈指数增长，对于较大规模的车辆优化调度问题不适用。启发式算法当中的节约里程法，计算步骤简单，计算速度快，且易于考虑各种实际问题，并不追求问题的最优解，而强调问题解的满意性，可以高效地得到问题的近似最优解。本文针对零售业的实际情况，即各个门店对于某些常用商品的需求是稳定而不间断的，在研究这类问题的时候，不需要各个门店在不同时期对于不同货物的需求，只要每次配送固定的商品即可，对于这类问题，本文建立了问题一的模型，这种模型往往运用于配送中心的

24、某些常用的子系统，如某些常用的商品的配送，这类问题讲求简单高效，追求最快的满意解。因此，用节约里程法解决问题一这类模型是可行的。而对于更为复杂的配送模型，比如大量的非常规商品的配送，不同的门店需要不同的商品，针对这类错综复杂的模型，必须借助现代化的智能算法，使得配送方案更为科学合理，准确易行。因此，用智能算法当中的遗传算法来解决问题二这类模型是可行的。1.3 配送路线优化的意义配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合的理配送路线，对企业和社会都具有很重要的意义。 对企业来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用

25、率，降低配送成本;(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度;(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益。 对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用 。第二章 联华超市配送路线作业现状目前联华的物流体系是，所有货物由供货商直接送达店面，这种方式虽然灵活，但影响了供货速度，也加重了供货商的负担。由于联华各门店自行采购，供货商不一，大大影响了供货速度；并且，联华目前的供货方式也加重

26、了供货商负担。随着中国零售市场白热化竞争的日趋激烈，建设区域物流配送中心无疑可以帮助联华加快店面更新速度，巩固市场。而联华超市也应在各个市区确立商品配送中心，以后供应商只要将货物运送至物流中心，各分店商品的配送统一由物流中心来实现。作为便利店模式的首推者，“灵活”和“适应”一直被视为联华成功改变中国人购物习惯的法宝。店长的“钦点”让联华许多货架上充盈着本地的产品。加上所开门店位置多位于大中型城市，这让门店直送方式有了很强的操作性。联华不用多费心思经营物流，只需让供应商们接上它的订单生成系统，再顺手给个“deadline”（送货的最后期限），一切就告万事大吉。“小批量，多频次”的订货原则，保证联

27、华可以尽量减少门店库存。而使用时段限制，过期则不收货的“残酷”手段，来保证供应商的准时到货率，在中国也被认为是简明有效的。近乎于零的物流费用和基本合格的配送质量，曾让联华人颇感自豪。真正伤脑筋的是供应商们，本来利润就不高，面对联华在物流上的不作为，还得自己挖空心思节约成本。目前，联华的商品配送分几种情况，大部分情况是通过第三方物流实现的，费用由供应商承担。以北京地区为例，给联华做配送的主要有上海成协，朝百批发，大荣物流等几家公司。有一小部分品牌，包括可口可乐、宝洁和百事可乐等大公司以及一些生鲜食品等都具有直送的能力。有些联华的门店还习惯于将降价损失、损耗和营业额、毛利率指标的完不成数，转嫁给供

28、应商来承担，也就是说供应商与总部谈好的交易条件到了门店是要附加的，因为联华是最大的，供应商也无可奈何；另外据悉，联华近期采取的分区采购政策，也使得供货商从过去习惯于以一对一的模式变成了以一对多，这样无疑加大了供货商的运营成本，从而导致他们抱怨多多。第三章 配送线路优化模型及算法3.1配送线路优化的模型3.1.1多回路运输VRP模型多回路运输问题是现实中很普遍的一种调配问题，特别对于有大量服务对象的实体，例如拥有一个上千客户的企业。此类调配的核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型。该问题研

29、究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程最短，费用最小，时间尽量少等）。它涉及了多辆交通工具的服务对象的选择和路径确定两方面问题。一个典型的VRP模型可以如下表述：（1）基本条件 现有m辆相同的车辆停在一个共同的源点，它需给n个客户提供货物，顾客为。（2）模型目标 确定所需的车辆数N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用最小。（3）限制条件：N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点；车辆的容量限制不能超过；特殊问题

30、还需考虑时窗限制；运输规章限制。3.1.2 PDPTW问题模型PDPTW问题是VRP问题的一个很有用的扩展，近段时期引起越来越多的研究者的注意，许多新的优化思想和优化方法被引入到此问题中，并产生了一定的影响。PDPTW问题（Pickup and Delivery Problem with Time Windows，带时间窗口的装卸货问题）是为一个车队寻找最优的运输路径来满足所有客户的运输需求。车队的每一辆车从车库出发，沿优化的路径为客户服务并最终返回车库。每一辆车都给定最大容量和出发、返回车库。每个运输需求指定一个装货点、一个卸货点和运输货物量。装货点、卸货点以及车库都有时间窗口。车辆必须在规

31、定的时间窗内访问装、卸货点。也就是说，在运输网络中，已知待服务的装、卸货点和车库的位置和时间窗口、车辆的最大容量以及运输货物量的前提下，设计车辆运输路径，使运输成本最小化。PDPTW的解是路径的集合，每一辆车对应一条路径，包括以下方面： 1、需要用到的车辆数目；即，有多少条路径 2、 每辆车访问每一个点的顺序以及时刻PDPTW问题中，要求满足的约束条件主要有以下几种：1) 时间窗口约束：车辆必须在规定的时间窗内服务装货点或卸货点。如果车辆在 之前到达点 ，必须在点 等待到 才能开始装卸货。车辆在 时刻之后到达点 ，则无法按时完成该点的装卸货任务，因而是不允许的。 2） 访问约束：车辆到客户指定

32、的装货点装货，然后运输到相应的卸货点卸货。每一个点都必须被一辆车服务且只能服务一次。 3） 车库约束：车辆必须从车库出发到某一装货点，最后从某一卸货点返回车库。车辆返回车库后不允许再次出发。4） 成对约束：一个客户需求的装货点 和其对应的卸货点 必须被同一辆车访问。 5） 次序约束：客户需求的装货点 必须在对应的卸货点 之前被访问。 6） 容量约束：任何时刻车辆所装货物量之和不能超过车辆的最大容量。上述约束是PDPTW问题中常见的几种约束条件。另外还会根据实际情况的要求增加一些附加约束，如车辆类型与货物类型之间的类型匹配约束，司机的最大工作时间约束等。PDPTW问题的优化目标也是总运输成本最小

33、。一般来说，与总运输成本有关的费用包括：车辆的固定代价，是运输代价中最重要的部分，要最大可能的减少使用的车辆数；与车辆行驶距离有关的代价。3.2 配送问题的求解算法车辆配送问题的求解算法有很多种，但究其本质来讲，基本分为最优化算法和启发式算法两大类。3.2.1最优化算法最优化算法，也称之为精确算法，就是指能够通过有限的计算和推理得到优化问题的最优解的算法。在配送问题中，所谓最优化算法就是找到一组路径集合，使得其目标函数值比其它任何一组可行路径集合的目标函数值更好。常用的最优化算法主要有：分枝定界算法、动态规划算法和整数规划。通常情况下，NP-hard问题的精确解法的计算量较大，而且随着问题规模

34、的增大计算量会呈爆炸式的增长，因此在实际问题中最优化算法的应用范围有限。3.2.2启发式算法启发式算法是通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法。启发式方法要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而比较具体的模型及算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径。用启发式方法求解问题时强调“满意”。常常是得到满意解，决策者就认为可以了，而不去追求最优解。之所以这样是因为：(1) 很多问题不存在严格的最优解（如目标之间存在矛盾的多目标问题），此时对目标的满意性比最优性更能描述人们的选择行为。(2) 得到某些问题最优

35、解的成本太大。(3) 从实际出发，有时探求问题的最优解没有意义。对于NP-Hard问题，人们自然会想到启发式的算法。启发式的算法就是根据某种启发式的信息对已知的可行解进行改善，通过若干次的迭代获得相对满意的解。和精确算法相比，启发式的算法不能保证得到全局最优解，但是实现起来相对简单。由于车辆运输调度问题是NP-hard问题，而现实中该问题规模一般很大，因此想以能够接受的运算速度找到最优解是不可能的。而启发式算法可以在相对短时间内找到“满意”解，为此研究人员把精力主要放在构造高质量的启发式算法上。目前已提出的求解车辆运输调度问题的启发式算法很多，主要分为经典启发式算法和现代启发式算法两类。3.2

36、.3节约算法利用节约法确定配送线路的主要出发点是，根据配送中心的运输能力（包括车辆的多少和载重量）和配送中心到各个用户以及各个用户之间的距离来制订使总的车辆运输的t.km（吨数乘上公里数）数最小的配送方案。为了便于介绍节约法的基本思想，设：配送的是一种货物；各用户的坐标（x，y）及需求量均为已知；配送中心有足够的运输能力。利用节约法制订出的配送方案除了送总 t.km 数最小外，还满足以下条件：方案能满足所有用户的要求；不使任何一辆车超载；每辆车每天的总运行时间或行驶里程不超过规定的上限；能满足用户到货时间要求。（2）节约法的基本思想如图3-1所示，设A 点为配送中心，它分别向用户B 和C送货。

37、设A 到B 和C 的距离为a和b，两个用户B、C 之间的距离为c，送货方案只有两种，如图中（a）和（b）所示。BCCB(a)（b）节约法的送货方案AA图3-1 节约法配送方案图图中（a）方案是从配送中心A 向用户B、C分别单独送货，配送路线为：ABA，ACA；总的配送距离为：Da=2a + 2b图（b）方案是从配送中心向用户，A 依次送货，配送线路为：ABC；总的配送距离为：Db=a + b + c对比这两个方案，哪个更合理呢？这就要看 Da 和Db 哪个最小，配送距离月小则说明方案越合理，由总距离公式可得出：Da Db =2a + 2b a b c = a + b c如果把图中的A、B、C看

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

39、华便利店在市区内分布较为均匀，在环城路上零星分布着几家，结合桂林市实际城区分布特点以及费用考虑，联华便利店的配送中心定在桂林市七星路高新区附近，这里既有良好的仓库设备，交通情况也非常便利，同时又靠近桂林市区，配送方便，费用合理。以下是每个分店（一年365天）平均每天的需求量情况表：表4-1 联华便利店分店平均每天需求量表分店123456需求量(KG)302295292333289354分店789101112需求量(KG)337349361336306314现有路线是固定不变且为已知,每条线路行驶距离见下表所示：表4-2 联华便利店距联华配送中心最短距离（公里）PP11P1P21.62.4P2P

40、31.32.12.7P3P41.80.7532.7P4P54.23.255.22.5P5P63.52.64.94.11.91.8P6P73.42.753.42.33.41.6P7P82.81.94.23.41.32.20.731.4P8P92.31.63.92.61.231.51.20.82P9P104.23.35.64.62.62.20.731.61.32P10P113.22.84.62.22.94.93.21.82.71.93.4P11P124.63.96.24.53.53.92.21.22.32.31.72.6P12设每个车辆的运输能力是2吨，根据案例可知，联华平均每天所用车辆数为2辆。

41、现在用节约算法对该配送线路问题进行求解。根据配送中心与分店之间,分店与分店之间的距离距离表，计算出用户间的节约里程。表4-3 节约值矩阵表302P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P520.80.33.5P5354P61.90.20.73.45.9P6337P71.701.32.94.25.3P7349P81.90.20.73.34.85.574.8P8361P91.7012.93.54.34.54.28P9336P101.90.20.93.46.26.9765.74.5P10306P111.40.22.32.12.53.54.83.33.

42、64P11314P121.701.42.94.95.96.85.14.67.15.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连接点节约值表302P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P520.80.33.5P5354P61.90.20.73.45.9P6337P71.701.32.94.25.3P7349

43、P81.90.20.73.34.85.574.8P8361P91.7012.93.54.34.54.28P9336P101.90.20.93.46.26.9765.74.5P10306P111.40.22.32.12.53.54.83.33.64P11314P121.701.42.94.95.96.85.14.605.2从表3-3中选出节约值最大为6.97，如果连接P6和P10 ，则与上述线路合并，其总需求量为986kg，未超过一辆车的运输能力2t，因此，连接P6形成回路，即P-P6-P10-P12-P。再将顶点P6和P10的节约值赋为0。继续选出节约值最大为6.8，其对应两个顶点为P7、P1

44、2。如果连接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 剩余节约值表（一）302P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P520.80.33.5P5354P61.90.20.73.45.9P6337P71.701.32.94.2

45、5.3P7349P81.90.20.73.34.85.574.8P8361P91.7012.93.54.34.54.28P9336P10000000000P10306P111.40.22.32.12.53.54.83.33.60P11314P1200000000000继续选出节约值最大为5.9，其对应两个顶点为P5、P6。如果连接P5和P6 ，则与上述线路合并，其总需求量为1612kg，未超过一辆车的运输能力2t，因此，连接P5形成回路，即P-P5-P6-P10-P12-P7-P。此后，P6两端连接点也已确定，因此将P6点与其他连接点的节约值赋值为0。见表3-5：表4-6 剩余节约值表（二）3

46、02P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P520.80.33.5P5354P600000P6337P71.701.32.94.20P7349P81.90.20.73.34.804.8P8361P91.7012.93.504.54.28P9336P10000000000P10306P111.40.22.32.12.504.83.33.60P11314P1200000000000继续选出节约值最大为4.8，其对应的顶点为P5、P8和P7、P8以及P7、P11三对顶点。综合考虑，连入回路的应为P5、P8和P7、P11两对顶点。连接P5、P8和P7

47、、P11，则与上述线路合并，其总需求量为2207kg，超过一辆车的运输能力2t，因此，结合店铺分布情况考虑，将P11编入回路中，即形成P-P5-P6-P10-P12-P7-P11-P回路，此时该回路的运输总量为1918kg。因为只有两辆运输车，因此剩下的六点将形成另外一条回路，因为剩余点的总需求量为1932kg，小于运输车辆的额定载重，因此下面将不再考虑是否超过载重。将第一条回路所包含的点与其他点连接所节约的节约值赋为0，得到的剩余点的节约值表如下：表4-7 除回路1剩余点节约值表302P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P50000P53

48、54P600000P6337P7000000P7349P81.90.20.73.3000P8361P91.7012.90004.28P9336P10000000000P10306P110000000000P11314P1200000000000从上表可看出节约值最大值为4.28，其对应的两点为P8、P9，因此，连接P8、P9成回路，即P-P8-P9-P。再将顶点P8和P9的连接点节约值赋为0。重复回路1的操作，得到回路2的连接状况为：P-P1-P4-P8-P9-P3-P2-P，运输量为1932kg。两条回路节约的里程为：回路1（P-P5-P6-P10-P12-P7-P11-P）：5.9+6.9

49、7+7.1+6.8+4.8=31.57km回路2（P-P1-P4-P8-P9-P3-P2-P）：2.05+3.3+4.28+1+0.2=10.83km所以配送线路优化后，联华超市配送线路总节约里程为42.4公里。具体线路图如下：图4-2 联华超市优化后配送线路图第五章 方案综合评价5.1 算法的适用度评价配送运输通常是一种短距离、小批量、高频率的运输形式。如果单从运输的角度来看，它是对干线运输的一种补充和完善，属于末端运输、支线运输，以高质量的服务为目标，以尽可能满足客户要求。从配送中心把货物送到所需的各个分店，有很多种不同的路线选择方案。合理的选择配送线路，对企业和社会都具有很重要的意义。为

50、将货物送给分店，需要从一个或多个配送中心组织配送运输。一般地一个或多个配送中心目的地存在一个道路网，如何在这张道路网上综合考虑各线路车流量、道路状况、客户的分布状况、配送中心的选址、车辆额定载重量及其他车辆运行限制等因素，找出一条最佳的运输线路解决方案，达到节省运行距离、运输时间和运行费用的目的就是线路设计的意义所在。进行配送线路优化时，必须要有明确的目标，遵循基本的原则。配送路线方案目标的选择可以从以下几个方面来考虑。（1）配送效益最高或配送成本最低（2）配送里程最短（3）配送服务水准最优（4）配送劳动的消耗最小求解最短路径的配送路线的方法很多，结合具体的要求，在此设计中采用了节约里程法来求

51、解。启发式算法是从尚未安排的车辆、运输任务或行驶路径中按照构造算法进行选择，知道所有任务和车辆均被调度为止。构造的每一步，根据某个判别函数，把当前的线路构形和另外的构形进行比较并加以改进，以最小代价把一个不在当前构形上的需求对象插入进构形，最后得到一个较好的可行构形。我们根据启发式算法中的节约里程法得到优化后的线路。通过两种方法的比较我们可以发现在此设计中用节约里程法计算出来的配送路线算出来的配送路线有实用性。通过对物流配送线路的优化，可以派出更少的车辆来满足装货的要求，使车辆完成配送任务的同时行驶的距离最少。一方面可以缓解交通拥堵，另一方面可以减少汽车造成的污染。为广大人民造福。配送线路的优

52、化产生了一定的经济效益和社会效益。同时，我们虽然计算出了比较合理的配送路线，但模型也存在着一定的缺陷。在计算过程中也将一些因素理想化了，与实际情况不完全相符。所以在实际中，我们可以将更多的因素考虑进去，设计出更加合理的配送路线。5.2加强线路管理水平随着配送中要求成本费用要尽可能降低，特别是目前多批次、小批量配送的发展，要求配送中心采用效率化的配送方法。联华超市为实现效率化的配送，应越来越重视配车计划管理、提高装载率以及车辆运行管理。从总体上看，降低配送成本的措施就是追求车辆运行的效率化，提高车辆运行效率，这就需要建立有效的火车追踪系统，即在车辆上配置一个全球定位系统（GPS），通过这种终端一

53、方面对货物的在途情况进行控制。5.3 公司采用该方案的整体评价在此设计中，我们针对联华便利店以桂林市为例，对桂林市配送中心的配送区域进行配送路线的设计。通过节约里程法计算出的配送路线。在此配送线路中，避免了各个节点的重复配送，使车辆的运载率得到了一定的提高。同时我们也意识到在此模型中没有考虑配送时间，运价等问题，所以在以后的研究以及方法的改进中，我们可以将更多的影响因素考虑进去，为公司制定出更加合理的配送方案。第六章 总结通过对比可以看出，通过节约算法的优化之后，该配送中心的配送线路得到了改进，节约了里程42.4km，减少了运输车辆的数目，从而降低了运输成本，提高了利润。这只是节约里程算法的简

54、单运用，我们也应看到，在现实的企业配送过程中，要考虑的配送点会更多、分布更广，线路会更复杂，同时还要综合考虑配送时间的限制、车辆的保养维修、人力成本、交通路况等诸多因素。因此节约法简便易行,但也有一些弊端，一是过于强调节约里程，没有考虑时间。路况等因素，二是不能对客户需求作出灵活多变的处理。在配送路 线选择决策时,通常考虑较优的原则,而不是最优化原则. 我们还应做到深入了解客户,加强与客户的信息交流， 通过对客户需求的时间变化对其进行分类,以增加配送的灵活性，路线决策过程中实施多路线同步决策，节约法的实施过程,要综合考虑路程长短和时间因素，配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货

55、物组装的共同影响。物资管理工作的好坏直接影响到施工企业的生产、技术、财务等多方面的经营活动和经济效益；在现代社会，物流的概念被炒作的十分热门，但这不仅仅是一种炒作，现代物流管理思想确实是有相当的科学基础和成熟的技术，也不乏成功的例证。随着我国社会主义市场经济的建立和完善，建筑企业必须改变过去计划经济模式下的管理思想，采用先进的物流管理方式，建立高效的物流管理组织机构已成为必然的趋势。所以，施工企业引入现代物流管理思想，加强企业的物流管理，对于企业降低工程成本，实现工程项目效益最大化，提高企业竞争力具有重要的现实意义.随着社会生产分工细化，许多企业开始注重业务外包，将自身不擅长的业务外包给第三方

56、企业完成，自己把精力集中到核心业务上来，提高企业竞争力。建筑企业应该将物流业务外包给合适的第三方物流企业，减少自身服务，将精力集中在施工建设上来。第三方物流企业具有专业化的物流管理人员、技术人员、物流设备和信息系统等，充分发挥专业化的物流运作的管理经验，达到整体最优化的效果。物流业务的外包大大降低了企业物流成本，减少了物流人员，借助信息平台与第三方物流公司紧密沟通，同时利用其广泛的配送网络，不仅提高了物资的运送效率，降低运输成本，而且降低了建筑企业库存，削减了存储成本。企业还可以将企业信息系统建设转嫁给第三方物流公司，有利于提高信息系统的专业性、可靠性，且减少了建设投资和运营成本。物流外包可以更加明晰企业物流成本费用，降低了计算难度，提高了核算精确性，为运作的改进及决策的实施提供了有力保障。 建筑施工企业与供应商缺乏长期有