[优秀毕业设计精品] 南城平安货运公司车辆线路优化设计

1、 课课 程程 设设 计计 课程名称课程名称: 交通运输组织学交通运输组织学 设计题目设计题目: 学生姓名学生姓名: 学学 号号: 班班 级级: 院系名称院系名称: 交通运输工程学院交通运输工程学院 指导老师指导老师: 2011 年年 12 月月 交通运输组织学交通运输组织学 课课 程程 设设 计计 课程名称课程名称: 交通运输组织学交通运输组织学 设计题目设计题目: 学生姓名学生姓名: 学学 号号: 班班 级级: 院系名称院系名称: 交通运输工程学院交通运输工程学院 指导老师指导老师: xxx 课程设计任务书 交通运输工程 学院 交通运输 专业 2008 级 班 课程名称 交通运输组织学 题目

2、 南城平安货运公司车辆线路优化设计 学生姓名 学号 同组设计者：无 一、已知技术参数和设计要求一、已知技术参数和设计要求 1、已知技术参数与参考资料、已知技术参数与参考资料 客货运管理相关标准与规范 交通运输组织学 ，人民交通出版社，2008 年 公路运输组织学 ，人民交通出版社，1998 年 交通运输组织学 ，东南大学出版社，2008 年 运输组织学 ，机械工业出版社，2008 年 2、设计要求、设计要求 本课程设计是针对学生学习和运用专业知识的综合考核和检查，使学生接 受工程类基本训练的重要环节，是交通运输交通运输组织学专业课程学习 的必修内容之一。本课程设计的特点是，内容所涉及的知识面较

3、一般习题广， 有较强的系统性和综合性，在运算、绘图、编写设计文本方面有较高的要求。 本课程实际应针对交通运算组织学课程涉及的相关理论与方法，结合具体 实践背景，解决实际问题。要求 所涉及方法、模型与理论知识与本课程相关； 有具体的实践背景； 课程实际要求完整、系统，从提出问题、解决问题与结论三个方面开展， 思路清晰，条理清楚。 二、课程设计应完成的任务二、课程设计应完成的任务 课程设计应结合课程内容，独立解决课程设计实际问题，本课题应完成以 下几个方面的任务： 第一，论述设计背景和内容以及本设计的思路，完成本设计的实际背景和 相关实际数据说明等。即说明南城平安（深圳）货运公司配送线路现状及其存

4、 在的问题。 第二，完成设计所需要的方法及理论的阐述；即节约法理论原理及改进节 约法的优点以及其应该中的约束条件与局限性等。 第三，结合上述理论与方法，应用于实际背景，解决实际存在的问题；即 结合改进的节约法，结合南城平安（深圳）货运公司配送的相关数据，完成其 配送路线的优化设计方案。 第四，对设计结论的总结分析。 三、工作计划三、工作计划 本次课程设计安排时间为二周，2010 年 12 月 19 日至 2011 年 1 月 2 日， 具体工作计划如下： 1、2009 年 12 月 27 日28 日，项目背景资料的收集与整理； 2、2009 年 12 月 29 日30 日，完成课程设计大纲；

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

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

7、要求、课程设计要求 本课程设计要求学生根据课程涉及的相关内容与方法，结合实际背景，系 统解决实际问题。从背景分析、提出问题、解决问题、主要结论等几个方面开 展。要求课程设计具有系统性、完整性、与课程相关性并具有一定的研究深度。 二、课程设计的依据与资料来源 课程设计的依据： 客货运管理相关标准与规范 交通运输组织学 ，人民交通出版社，2008 年 公路运输组织学 ，人民交通出版社，1998 年 交通运输组织学 ，东南大学出版社，2008 年 运输组织学 ，机械工业出版社，2008 年 资料来源： 指导教师提供相关资料； 实际调研收集资料； 相关书籍； 网络资料收集。 三、课程设计学生应完成的内

8、容 根据交通运输组织学课程设计要求及线路优化设计内容，学生应按 照以下几个方面内容开展设计： 第一章 概述 1.1 设计背景和内容 1.2 概括问题的提出 1.3 本设计所做的工作及基本结构 第二章 货运中心配送路线优化的研究现状 2.1 配送路线优化的意义 2.2 货运中心路线优化的方法 2.3 货运中心路线优化原则 第三章 南城平安（深圳）货运公司配送线路现状 3.1 公司业务状况 3.2 公司的配送路线 3.3 存在的主要问题及分析 第四章 货运中心配送路线的优化设计 4.1 优化思路 4.2 市内配送优化 第五章南城平安（深圳）货运公司线路优化模型的求解 5.1 节约法的基本思想与步骤

9、 5.2 简单节约法的求解 5.3 用改进的节约法制定配送计划 5.4 配送计划软件的实际运用 5.4.1 计划软件的运用 5.4.2 配送和流通中心的关系 四、课程设计要求及其它 1、时间安排：二周设计时间（2010 年 12 月 27 日2011 年 1 月 7 日） ，实 际操作中，可提前进行相关资料的收集与大纲的完成； 2、要求独立完成，一人一题，每人提交 1 份打印的设计成果（a4）及电子 文档； 3、格式要求：装订按照要求的顺序依次装订成册，胶装封面，文档具体格 式参考格式模板； 4、纪律要求：集中在固定教室严格考勤，按照作息，一般不允许请假，如 遇特殊情况，需要填写请假条报院领导

10、批准，否则按照每天旷课 8 节处理。另 请假或旷课时数累计达全部设计时间的 1/3 以上，该课程设计按照零分计。 运输与物流工程系 2010 年 12 月 目目 录录 第一章第一章 概述概述 .1 1.1 设计背景和内容.1 1.2 概括问题的提出.2 1.2.1 配送作业问题的提出.2 1.2.2 配送路线优化问题的提出.2 1.3 本设计所做的工作及基本结构.3 1.3.1 本文的主要工作.3 1.3.2 本文的基本结构.4 第二章第二章 货运中心配送路线优化的研究现状货运中心配送路线优化的研究现状 .5 2.1 配送路线优化的意义.5 2.2 货运中心路线优化的方法.5 2.2.1 配送

11、路线优化问题的简化.6 2.2.2 配送路线的计划方法.7 2.2.3 配送路线优化分类.8 2.3 货运中心路线优化原则.10 第三章第三章 南城平安（深圳）货运公司配送线路现状南城平安（深圳）货运公司配送线路现状 .11 3.1 公司业务状况.11 3.1.1 公司简介.11 3.1.2 公司的业务状况.11 3.2 公司的配送路线.12 3.2.1 国内主要城市配送方式.12 3.2.2 省内主要配送方式.12 3.3 存在的主要问题及分析.13 第四章第四章 货运中心配送路线的优化设计货运中心配送路线的优化设计 .16 4.1 优化思路.16 4.2 市内配送优化.16 4.2.1 主

12、要状况.16 4.2.2 南城平安（深圳）货运公司配送路线优化模型.17 第五章第五章南城平安（深圳）货运公司线路优化模型的求解南城平安（深圳）货运公司线路优化模型的求解 .19 5.1 节约法的基本思想与步骤.19 5.1.1 节约法的基本思想.19 5.1.2 模型的求解步骤.20 5.2 简单节约法的求解.21 5.2.1 求解过程分析.21 5.2.2 节约法应注意的事项6.24 5.2.3 节约法的优缺点及改进建议.25 5.3 用改进的节约法制定配送计划.25 5.3.1 用 a，b 尺度制定配送计划.26 5.3.2 用 a,b 尺度制定配送计划.28 5.4 配送计划软件的实际

13、运用.29 5.4.1 计划软件的运用.29 5.4.2 配送和流通中心的关系.30 5.5 本章小结.31 第六章第六章 总结总结 .32 6.1 设计主要成果.32 6.2 需要进一步阐述的问题.32 6.3 对南城平安（货运）公司的几点建议.33 参参 考考 文文 献献 .35 第一章第一章 概述概述 1.1 设计背景和内容 在经济日益全球化的今天，现代物流作为“第三个利润源”正受到日益广 泛的重视，并面临着前所未的有发展机遇，我国物流业面对的机遇与挑战也愈 来愈明显，特别是加入 wto 以后，我国融入世界经济一体化的进程逐渐加快， 物流业已成为市场经济中一个竞争激烈的行业。我国的物流市

14、场被国外物流业 普遍看好，认为这是一块尚未很好开拓的领域，可以大有作为，因此纷纷来我 国开办物流企业，这也刺激了我国物流业的发展。 在市场经济下，如何赢得更多的利润是每一个企业追求的目标，现在很多 企业已经开始把目光投向了被经济学家称为继劳动力、自然资源、之后的“第 三和利润源泉”物流管理2。在这种形式下，物流配送也得到了相应的发 展。配送的基本含义是送货的意思，在美国的英语原词是 delivery，强调的是 将货物送达。在现代的物流配送中，为实现利润最大化，就得想方设法使送货 行为优化，于是出现了配送中心的车辆合理调度、仓储管理的优化、配送路线 的规划选择等问题。 配送是一种综合的物流形式，

15、几乎包括了所有物流功能要素，是物流的一 个缩影或在某小范围中物流全部活动的体现。配送中心是进行配送活动最主要 的硬件设施。其作业流程具体表现为配送中心进行生产的实际过程。配送流程 的合理，则配送的生产效率和效益就高，反之就低。因此对配送的研究具有很 高的实际意义和价值。 要搞好配送物流，就必须合理化配送中心的作业流程，从而最大化的利用 配送中心的资源。对于配送中心的一系列环节，应该首先着重研究哪些环节并 如何去解决这些问题，是本文所要提出和解决的问题。 在目前，配送中心的基本作业流程包括进货、储存、拣货、配货、送货等 环节，每个环节都与货物的搬运是分不开的，而其中把货物由配送中心搬运至 各顾客

16、点，就引发了一个如何使路线达到优化的问题，这是本文研究的重点， 对于路线优化的研究，可以提高企业的运作能力，有助于企业获取更多的利润 和选择更合理的配送经营决策。 对配送路线优化问题的研究，前人已经提出不少可行的方法和步骤，本文 在借鉴前人一些方法的基础上，通过一个实际的研究项目，对路线优化进一步 加以分析和研究。 1.2 概括问题的提出 1.2.1 配送作业问题的提出 随着消费需求的增长，市场对货物流通量的要求也逐渐增大，这就要求有 专门的配送中心对货物进行配送。在没有配送中心的情况下，由工厂直接运送 货物到用户，即使采用直接配送方式，其交叉运输是普遍存在的，这就导致了 运送路线延长，规模效

17、益差、运输成本高，如果采用配送的方式，便可消除交 叉运输。 如图 1-1 和图 1-2 所示： 图图 1.11.1 交叉运输交叉运输 图图 1.21.2 缓解交叉运输缓解交叉运输 工厂 1工厂 2工厂 3 客户 1客户 2客户 3 工厂 1工厂 2工厂 3 配送中心 客户 1客户 2客户 3 1.2.2 配送路线优化问题的提出 影响配送运输效果的因素很多：（1）动态因素，如车流量变化、道路施工、 配送客户的变动、可供调动的车辆变化； （2）静态因素，如配送客户的分布 区域、道路交通网络、车辆运行限制等。各种因素相互影响，很容易造成配送 方面的问题，主要有以下几个方面3： (1) 送货不及时，主

18、要是信息处理流程时间太长，配送方式落后； (2) 送货成本高，这不仅包括企业的运输成本，也包括客户的支付成本。 (3) 配送路径选择不当，这是造成配送问题很重要的一个方面。 在这些问题中，有些在短时间内无法改变，但对于配送路径的优化比较容 易实现并且效果明显，选择了一条合理的配送路线，不仅可以达到送货及时的 目标，同时也还可以节约送货成本，为企业创造了效益。当然，在实际过程中， 一条合理的配送路线的选择，要考虑到很多方面的因素，应尽可能综合考虑影 响配送路线的重要因素，所以解决该问题要站在综合、全面的角度进行考虑， 这样才能作出合理的决策。 1.3 本设计所做的工作及基本结构 1.3.1 本文

19、的主要工作 本文以配送路线的优化为研究目标，以南城平安（深圳）货运公司为研究对 象进行深入细致的分析和讨论，主要做了以下的工作； （1）在第二章中，针对货运中心配送路线优化的研究现状，了解并讨论路 线优化的原则；同时还归纳了现有的配送中心路线优化的研究方法，指出它的 使用范围和一些不足之处，最后指出货运中心路线优化的意义和目的。 （2）在第三章中，主要对本文的研究背景南城平安（深圳）货运公司 作一个现状的描述，从了解其业务状况入手，掌握它的配送路线和方法，进而 分析该公司存在的主要问题，为解决问题提供了依据。 （3）在第四章中，针对南城平安（深圳）货运公司配送路线存在的问题， 建立相应的路线优

20、化数学模型，并指出该模型的实际意义。 （4）第五章，围绕配送路线优化模型来展开具体的介绍该模型所使用的方 法，并采用相应的计算方法对模型进行求解，并利用优化后的方法和原始方法 做一个比较。最后指出使用该模型，公司是否比以前优化了，从而验证本文的 可行性。 （5）第六章，总结本文的主要成果，并列出一些需要进一步解决的问题， 最后针对南城平安（深圳）货运公司提出几点自己的看法和意见。 1.3.2 本文的基本结构 本文的基本结构可以用下面的框架图来表示： 图图 1.31.3 设计框架结构设计框架结构 公司配送现状（业务状况、目前 的配送路线、存在的主要问题） 绪 论（研究背景、问题的提出） 研究现状

21、（线路优化的原 则、情况分类、意义等） 公司配送路线优化过程（优化思 路、优化模型） 模型求解过程（基本节约法、 改进节约法、配送计划软件） 分析结果（总结、几点建议） 第二章第二章 货运中心配送路线优化的研究现状货运中心配送路线优化的研究现状 2.1 配送路线优化的意义 配送运输由于配送方法的不同，其运输过程也不尽相同，影响配送运输的 因素很多，如车流量的变化、道路状况、客户的分布状况和配送中心的选址、 道路交通网、车辆额定载重量以及车辆运行限制等，在不同情况下，这些因素 都会对配送路线起到不同程度的影响。配送路线的优化就是综合考虑影响配送 运输的各因素，恰当的利用现有的设备，及时、安全、方

22、便、经济的将客户所 需的物资准确送达客户手中，需根据不同客户的特点和要求，选择不同的设计 路线，最终达到节省时间、运行距离和费用的目的。 在实际生活中，特别是对于一个运输公司来说，配送路线的优化有着十分 重要的意义。 首先，加快了货物流通，有利于库存的周转。在实现了高水平的配送优化 路线后，不管是生产企业还是配送中心都可以完全依靠配送中心的准时而快捷 的运送而不需要保持自己的库存。或者，生产企业只需要保持少量保险储备而 不必留有经常储备，这就可以实现生产企业多年追求的“零库存” ，解放了大量 的储备资金，也提高了社会经济效益。 其次，节约了社会运力，缩短了货运时间。路线的优化，其目的就在于用

23、最少的运力提供最全面的服务。通过对配送路线的优化，不仅解决了送货在时 间、数量上的问题，而且使缺货次数降至最低。 再次，提高了物流服务水平。配送是随着物流业的发展而发展起来的一种 新的服务方式，配送路线的优化是物流服务中很重要的一部分，可以从侧面反 映出物流的服务水平。 2.2 货运中心路线优化的方法 为达到高效率的配送，做到时间少、距离短、成本低，必然要求选择最佳 的配送线路和车辆综合调度。很多中外学者在这领域进行了深入的研究，提出 了很多可行的方法。 2.2.1 配送路线优化问题的简化 （1）旅行商问题2。这个问题字面上的理解是：有一个推销员要到 n 个城 市去推销商品，他要找出一个包含所

24、有 n 个城市的具有最短路程的环线。tsp 问题的历史悠久，最早描述是 1759 年欧拉研究的骑士周游问题，即国际象棋棋 盘中的 64 个方格，走访 64 个方格一次且仅一次，并最终回到起点。 tsp 问题是运筹学、图论和组合优化中的著名问题，在实际生活中有着广 泛的应用前景。tsp 不仅可以解决最优巡回路线等类 tsp 问题，在交通车辆巡 回、学校教师课程计划安排、工厂装配线进度管理以及民航机组人员轮班等问 题上也有着广泛的应用前景。在处理现实生活中的具体问题时，可以对 tsp 附 加一些限制条件，例如在模型中假设该旅行者的时间有限，进而添加相应的时 间约束条件等，从而衍生出许多和 tsp

25、相关的问题。 （2）多回路运输问题3。多回路运输问题在物流中的解释是对一系列客户 的需求点设计适当的路线，使车辆有序的通过它们。在满足一定的约束条件下， 如货物需求量、发送量、交货时间、车辆载重量限制、行驶里程限制等等，达 到一定的优化目标，如里程最短、费用最少、时间最短、车队规模最少、车辆 利用率高等。 vrp 问题由 dantzig 和 ramser 于 1959 年首次提出3，该问题一经提出， 立即引起了运筹学、网络分析、物流、计算机应用等学科专家的极大关注，成 为运筹学和优化科学研究的前沿和热点问题。 vrp 和 tsp 问题的区别在于：客户群体的数量大，只有一辆车或一条路径 满足不了

26、客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题 的求解4。相对于 tsp 问题，vrp 问题更复杂，但也更接近实际情况。 （3）多个旅行商问题4。由于限制条件的增加，tsp 问题可以衍生出多个 旅行商问题。mtsp 问题就是一个出发点，m 个旅行商的 tsp，即所访问的客 户没有需求，车辆没有装载的限制，优化目标就是要便历所有的客户，达到总 里程最短。 vrp 问题是 mtsp 问题的普遍化，当客户的需求不仅仅是被访问，而是有 一定容积和重量的商品的装载和卸装，涉及到不同种类和型号或不同载重车辆 的调度策略时，mtsp 问题转化为 vrp 问题。 2.2.2 配送路线的计划方法

27、（1）精确式算法及其应用的局限性 vrp 问题是组合优化领域著名的 np 难题之一，其求解方法一般相当复杂， 通常的做法是应用相关技术将问题分解或者转化为一个或多个已研究过的基本 问题（如旅行商问题、指派问题、运输问题、最短路问题、最大流问题、最小 费用最大流问题、中国邮递员问题等） ，再使用相对比较成熟的基本理论和方法 进行求解，以求得原运输车辆调度问题的最优解或满意解。 精确式算法一般运用线性规划和非线性规划等数学规划技术，以便求得最 优解。精确式算法一般有以下几种：分枝定界法（bbp） 、割平面法（cpa） 、 网络流算法（nfa） 、动态规划方法（dpa）等。 精确式算法随着运输系统的

28、复杂和调度目标的增加，其计算量呈指数递增， 使得获取整个系统的精确最优解越来越困难，而用计算机求解大型化问题的时 间和费用又太大。因此，此类优化方法现在一般仅用于求解运输调度的局部优 化问题。 （2）启发式算法 为了克服精确优化法的不足，可以运用一些经验法则来降低优化模型的数 学精确程度，并通过模仿人的跟踪校正过程来求取运输系统的满意解。启发式 算法能同时满足详细描绘和求解问题的需要，较精确式算法更加实用。启发式 算法一般有以下几种： 最近邻点法 （nearest neighbor）5。这是一种用于解决 tsp 问题的启发 式算法。方法简单，但得到的解并不十分理想，可以作为进一步优化的初始解。

29、 求解的过程一共分四步：首先从 o 点开始作为整个回路的起点，然后找到离刚 刚加入到回路的上一节点最近的一个节点，并将其加入到回路中，重复上一步， 直到岁有的节点都加入到回路中，最后，将最后一个加入的节点和起点连接起 来，构成一个 tsp 问题的解。 最近插入法（nearest insertion）6。最近插入法是另一个 tsp 的求解方 法。它的求解过程也是四步：首先从一个节点出发，找到一个最近的节点，形 成一个往返式子回路，在剩下的节点，寻找一个离子回路中某一节点最近的节 点，再在子回路找到一个弧，使弧的两端节点到刚寻找到的最近节点的距离之 和减去弧长的值最小，实际上就是把新找到的节点加入

30、子回路以后使得增加的 路程最短，就把这个节点增加到子回路中。重复以上过程，直到所有的节点都 加入到子回路中，可以得到相对比较满意的解。 节约里程法（saving algorithm） 。节约算法是用来解决运输车辆数目不确 定的 vrp 问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两 个回路并为一个回路，每次使合并后的总运距减小得幅度最大，直到达到一辆 车的装载限制时，再进行下一辆车的优化，优化过程分为并行方式和串行方式 两种。 扫描算法（sweep algorithm） 。扫描算法也是求解车辆数目不限制的 vrp 问题的启发式算法。求解过程同样是四步：以起始点为原点建立极坐标系，

31、然 后从最小角度的两个客户开始建立一个组，按逆时针方向将客户逐个加入到组 中，直到客户的需求总量超出了车辆的载重定额，然后建立一个新的组，继续 该过程，直到将全部客户都加入到组中。 2.2.3 配送路线优化分类 在实际的配送过程中，每天的配送客户不一定是固定的，这就需要根据定 单情况，对配送路线进行优化。我们可以将这些情况进行分类： （1）某各临时客户，不在固定路线上。对于这种情况，如果货物量不多， 可以将该客户临时编入到最近的一条固定线路上；如果货物量很多，可以派出 整车，寻求一条最优路径。 图图 2.12.1 不在固定线上的小批量临时用户不在固定线上的小批量临时用户 固定点客户 a 固定点

32、客户 b 固定点客户 c 临时客户 e 固定点客户 d 配送中心 固定点客户 a 说明：小批量临时客户，将其纳入最近的配送线路，建立临时点。 说明：大批量临时客户，临时建立一条新的配送路线，选择配送中心到该 用户的最短路径。 （2）某条线路当日需要配送的客户非常少，派车不值得。对于这种情况， 可以考虑将其并到其他路线上，合并的原则是在满足客户配送要求的前提下， 以最低的成本来优化路线。 图图 2.32.3 某路线客户少的配送情况某路线客户少的配送情况 说明：图 2-3 中，客户 m 和客户 n 本来是划分给 c 区配送路线进行配送 的，但是由于当日 c 区线路的客户太少，派车成本高。故将客户

33、m、n 按就近 原则暂时分别归到 b 区和 c 区。 （3）客户要求紧急，需要紧急配送。在生活中常常会遇到紧急配送的情况。 固定点客户 d 配送中心 客户 m c 区 客户 n a 区b 区 临时客户 e 配送中心 固定点客户 b 固定点客户 c 固定点客户 a 图图 2.22.2 大批量用户临时配送大批量用户临时配送 对于这种情况，我们就得采取紧急的处理措施。一般是在运输配送过程中不装 别的货物，中途也不卸车，空车返回。如图所示： 图图 2.42.4 紧急配送紧急配送 （4）遇到道路紧急情况时，一般采取的是绕行的措施，或者，如果时间充 裕，可以考虑等道路状况变好后再进行配送。 2.3 货运中

34、心路线优化原则 任何一个货运中心在制定配送路线时，应根据客户的分布，道路的交通情 况，货运中心本身位置等因素，先制定一条或几条固定路线。配送时按照不在 同一线路的客户，其货物不能组成一车的原则，把货物进行分组。线路的划分 主要考虑以下几点： （1）集中原则：位置比较集中的客户尽量划分在一条线路上，这是路线优 化的基础。不仅可以极大的节约运力和运费，而且可以配送的及时性。 （2）线路最少原则：指在运力允许的条件下，尽量用最少的线路划分客户。 在实际运用中，减少一条线路，将会为企业节约极大的成本。 （3）线路最短原则：划分线路时，应尽量使线路最短。 配送中心 临时客户需紧急配送的客户 第三章第三章

35、 南城平安（深圳）货运公司配送线路现状南城平安（深圳）货运公司配送线路现状 3.1 公司业务状况 3.1.1 公司简介 南城平安（深圳）货运公司成立于 1995 年，毗邻长城储运货代市场，地理 位置优越，交通便利。公司目前拥有 20 尺货柜车、40 尺货柜车、45 尺货柜车、 5 吨、8 吨、10 吨大型车队，货物提货点多处自备吊车、叉车。 公司采用先进的管理机制，完善的交通信息网，成熟的物流管理（仓储、 搬运、资讯、服务） 。公司始终坚持“客户至上，时间第一”的原则。经过 10 年的努力，该公司已经达到多数客户要求的高速、高效、安全、低价格、优质 的跟踪服务目的，为客户及其他货运站提供了充足

36、、快捷的运输车辆。 公司主要承接深圳至上海、杭州、北京、昆明、重庆、呼和浩特等全国各 地的国内公路货运、铁路运输、航空运输及深港散件业务，同时也受理长短途 搬家迁厂等业务。公司自备人货车多辆，24 小时为客户服务。 3.1.2 公司的业务状况 目前，公司采用双回程营运、pos 实时追踪、门对门服务、全保联保、诚 信价平的运输策略。 （1）公路货运可至汽车所有到达的所有城市，当日发车，专线直达。 （2）铁路运输服务项目：行包专列、特快包裹物品托运、中铁快运、集装 箱、车皮运输及到货提付等业务。 （3）航空货运直达全国通航的四十余个城市。 （4）深港散件 24 小时内收到。 （5）提供大、中、小车

37、辆进行搬家迁厂。 良好的物流将增加企业的市场竟争能力，南城平安提供的服务主要有： （1）采用门对门优质服务。 （2）任何司乘人员都严格遵守厂规厂纪，配合工作人员完成装货事宜。 （3）准时、安全的将货物送到客户指定地点，并填好司乘人员追踪单。 （4）公司的电脑网络部可免费为客户进行电脑维护、安装、网站制作及对 员工进行电脑应用软件的培训。 3.2 公司的配送路线 该公司的运送方式是分送式运输，也就是一个供应点对应多个客户的共同 运输。其中包括公路货运、铁路货运和航空货运。 3.2.1 国内主要城市配送方式 该公司在国内主要城市的配送主要以铁路和航空运输为主，公路占少数一 部分，主要承接跨省的长途

38、货物运输，其运输量相对比较大，运输范围已达到 全国各大中城市，如上海、北京、天津、南京、合肥、武汉、兰州、长沙等。 其配送方式一般采取点对点式，在运输距离较远并且条件允许的情况下，可以 采取转运，采用铁路航空、航空铁路、铁路航空公路、航空铁路 公路等混合运输方式。 3.13.1 国内主要城市配送路线国内主要城市配送路线 3.2.2 省内主要配送方式 省内运输主要以公路运输为主。公路货运主要承接中短途货物的运输，运 输量相对较小，也有一部分长途运输。在省内各个城市之间的送货以简单的节 约法思想进行车辆的调度。 图图 3.23.2 省内主要城市的配送路线省内主要城市的配送路线 在深圳市内，在货运量

39、不大的情况下，运送方式主要以专线直达为主，一 户一送。运送范围也大部分集中在深圳市及周边地区。如图 3.3 所示： 图图 3.33.3 市内主要城市的配送路线市内主要城市的配送路线 深圳 3.3 存在的主要问题及分析 虽然目前公司发展迅速，物流业务也逐步趋于完善，但通过对这个公司的 深入调查和了解，我们还是可以发现该公司存在的一些问题，主要表现在： （1）调度问题 车辆调度是否合理直接影响到运输里程和运输成本。在配送路线的制定上, 该公司以基本的节约法为主要依据, 但节约法也有其自身的不足，主要体现在 以下几个方面： 第一，运用节约法选择配送路线过于强调节约里程，而没有考虑行程中的 时间因素。

40、在许多情况下，时间更能决定物流配送的成本与服务质量。例如城 市间配送时对高速公路的选择、城市内部上下班时间的道路拥挤，一个巡回配 送过程中的时间长短，直接影响配送人员的精神状态，而配送人员的精神状态 又与交通事故和配送错误相连，所以时间对配送路线的选择有时更重要。 第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。 由于现代的消费者的需求趋于个性化，引起企业的生产、销售和配送也愈来愈 倾向于小小批量、大多品种、多批次，而节约法更适合于需求稳定或是需求时 间不紧迫。这显然不能满足现代多变的市场环境。 最后值得一提的是，节约法在制定的配送路线并不是总的路程最短，原因 是节约法一方面要

41、缩短总路程，另一方面又要充分利用车辆的运输空间（载重/ 容积） ，减少配送车次，而且只要在前一条预设路线上运行的配送车辆的运输空 间允许，就必须按节约路程的大小顺序进行选择而不考虑其他预设路线。在事 实情况下选择的路线并不能“节约”路程和有效利用运输空间，而且运输的车 次也不一定减少。 (2) 其它问题 第一，gis 问题。众所周知，车辆优化调度需要一套详尽丰富同时实时更 新的地理信息系统（gis）支持。该公司面临的最大问题是 gis 的建设问题。 虽然目前该公司已经有了一套电子地图，但从使用结果来看，并不理想。一是 信息量太少，许多街道没有标出，尤其是小区小街或则郊区线路；二是系统更 新速度

42、太慢，维护跟不上，许多地区已经更名或改变，但在电子地图里还没有 变化。 第二，技术装备落后问题。从公司的现状来看，技术装备的落后主要表现 在缺少高效的装卸搬运设备，如叉车、吊车。在货运中心，好多装卸搬运工作 还要人工来完成。 第三，局部区域内货运量的不平衡。这是一个普遍的问题，由于个地区经 济发展水平的不同，这些地区间的货运量就不可能等同，这就导致了货运车辆 的空载现象，从而导致运力的下降，造成运输成本的增加。由于该公司是货物 的集散中心，这就造成了从货运中心向客户运送时经常满载，而返程空载的现 象，并随着货运周转量的增加，空载里程也随之增长。 在这些问题中，有些问题是在短时间内无法解决的，如

43、局部区域内货运量 的不平衡、gis 问题等，但对于车辆调度方面的问题我们可以采取相应的措施， 使得车辆的调度更加合理，这是可行的。如何解决该公司的运输路线问题，我 们将在以后的几章里具体介绍。 第四章第四章 货运中心配送路线的优化设计货运中心配送路线的优化设计 4.1 优化思路 在研究该公司配送路线优化时，可以先考虑该公司在深圳市内的配送路线， 并由深圳市内推广至整个广东省。所以，本文主要以研究深圳市及周边地区城 市的配送路线为主。 由前面的介绍我们可知，该公司在省内配送路线的制定依据是基本节约里 程法，本章运用节约法分析市内的配送路线。 4.2 市内配送优化 4.2.1 主要状况 南城平安（

44、深圳）货运公司位于广东省深圳市9。我们以该公司在深圳市 及周边地区的货物运输为例，取其中的布吉、横岗、龙华、平湖、风岗、龙岗、 坪山、坑梓、新圩、石岩、沙井、长安、清溪、樟木头、大朗等十五个城市作 为配送路线研究的背景。 设货运中心（深圳）为 po，各个客户分别为 pk,(k=1，2，15)，已知该 公司有 5t、8t、10t 的车型可用，发送的最大发送距离为 200（+20）公里。 各个客户的地理位置如下图： 图图 4.14.1 各客户的相对位置各客户的相对位置 表 4-1 客户及货运量对照表 （单位：吨） 客 户 布 吉 横 岗 龙 华 平 湖 风 岗 龙 岗 坪 山 坑 梓 新 圩 石

45、岩 沙 井 长 安 清 溪 樟 木 头 大 朗 p(k)p1p2p3p4p5p6p7p8p9p10p11p12p13p14p15 货运量 （t） 1.62.02.12.51.51.21.41.62.01.32.01.72.21.62.4 4.2.2 南城平安（深圳）货运公司配送路线优化模型 根据节约法的基本思路，针对南城平安（深圳）货运公司，我们可以建立 数学模型如下2： 配送中心：p0；可用车辆集合是q,k=1,2,，m ，q 为载重量。 用户gi，i=1，2，n ，gi为用户 i 的货运量，如果可以混装，则有 max g i q；用户 i 到用户 j 的最短距离记为 d i ,j； 定义

46、01 变量如下： yk,i=1，表示 i 的用户由车辆 k 完成，否则记为 yk,i=0； xi j k=1，表示车辆 k 从 i 行驶到点 j，否则记为 xi j k=0 min z=c y x y k （41） 其中： g i y kq k （4 i k 2） y k i =1 i=1，2，n （43） k y k i =1 or 0 i=0，1，n k x i j k= y k j j=0，1，n （4 i k 4） x i j k= y k i i=0，1，n （4 j k 5） x i j k=1 or 0 i，j=0，1，n k 公式中 c i , j表示从点 i 到点 j 的运输

47、成本，含义可以是距离、费用、时间等， 示情况而定。该问题的求解思想是在保证一条线路上各用户的货运量 不大于车 辆的载重的前提下，连接点对。 公式中 c i , j表示从点 i 到点 j 的运输成本，含义可以是距离、费用、时间等， 示情况而定。该问题的求解思想是在保证一条线路上各用户的货运量不大于车 辆的载重的前提下，连接点对。 首先，把各个点单独与配送中心相连，构建仅含一个点的初始路线，得到 费用 z=co ,i+ci, o，然后计算如果连接点 i 和 j 到同一线路上得到的节约值： s(i , j) =co i+ci o+co j+cj o-（co i+ cj o+ci j）= ci o+c

48、o j-ci j or s(i , j) = cj o+ co i-cj i s(i , j) 越大，说明把点 i 和 j 连接在一起时，节约的费用越多；如果 s(i , j) 为负值，表示连接后费用增加，此时就不应该把点 i 和点 j 连接到同一条线路上 来。 第五章第五章南城平安（深圳）货运公司线路优化模型的求解南城平安（深圳）货运公司线路优化模型的求解 5.1 节约法的基本思想与步骤 5.1.1 节约法的基本思想 在第二章的第二节里提到过配送路线的优化方法，其中最具代表性的就是 由 clarke 和 wright 提出的节约里程法2。下面我们来分析节约法的基本思想。 假设配送中心 p0，

49、m 个用户分别是 p1，p2，pm；pi和 pj之间的最短距 离是 di,j，且 di，j已知（i，j=1， 2，3， ，m） 。 如果发送车辆的吨位已知，并且每一辆车都可以满载，则研究的目标转化为 使所有参加发送的车辆的总发送距离在满足约束条件的基础上最小。 在考虑配送计划时，首先假定在任何情况下，运输网络中的任意两点都有路 径可通，并且都有最短路线，如图（a） 、 （b） 、 （c）所示： pi pj pi p0 pj pj pi p0 （a） （b） （c） 图图 5-15-1 节约法基本思想节约法基本思想 如果两点的运输不通畅，则可以将这些情况转化为相应的约束条件列入方 程组中，然后求

50、解。 如图 5.1 所示，如果把原来（a）的运输路线由 p0pi-1pip0和 p0pj1pjp0改为（b）的 p0pi-1pipj1pjp0，则改动之后的节约量 为：si,j=d0,i+d0,jdi,j。 图图 5-25-2 典型的节约方案（典型的节约方案（1 1） 如图 5.2，如果将原来（a）中由 p0分别向 pi 和 pj两点配送货物的往返运 输路线 p0pip0 和 p0pjp0改为（b）的 p0pipjp0，则总发送距离由 原来的 2(d0,i+d0,j)改变为 d0,i+d0,j+ di,j。也就是说，由于连接 pi和 pj而得到的节 约量是 2(d0,i+d0,j)（d0,i+

51、d0,j+ di,j）d0,i+d0,jdi,j。 图 5-3 典型的节约方案（2） 5.1.2 模型的求解步骤 根据节约法的原理和上述的基本思路，我们可以设计求解配送路线优化模 p0p0 pi pj pi pj pi pj pi p0 pj1 p0 pi-1 pj1 pi-1 pj 型的步骤如下： 第一，计算节约值 s(i , j)，令集合 s= s(i , j) | s(i , j) 0 ; 第二，集合中的元素按从大到小的顺序排序; 第三，如果集合 s=，则计算结束，否则对第一个元素 s(i , j)，考查对应的 （i，j）是否满足下列条件之一： 点 i 和点 j 都不在已经构成的线路上；

52、 点 i 和点 j 都在已经构成的线路上，但是不与配送中心相连； 点 i 和点 j 都在已经构成的两个线路上，都不与配送中心相连。其中一 个是线路的起点，另一个是线路的终点，转下一步，否则转步骤； 考查点 i 和点 j 连接后线路上总的货运量 q，如果 qq，转下一步，否 则转步骤； 连接点 i 和 j 到同一条线路上； 令 s= ss(i , j)，转步骤 5.2 简单节约法的求解 5.2.1 求解过程分析 （1）初始方案： 对每一个客户分别派车，空车返回。总的路线为 15 条。 总路程：s = 2 d0, i = 1106km ； 15 1i 派车情况：需 5t 的车 15 辆。 （2）节

53、约里程的线路优化方案： 表表 5-15-1 各个客户之间的距离表（单位：公里）各个客户之间的距离表（单位：公里） po 7p1 1412p2 221626p3 20141417p4 282219228p5 333120382018p6 37362647313013p7 444230503330129p8 545042543731212719p9 32263611273147575961p10 5146563145476475767420p1 1 565160354747647676722510p12 42363234221521343222405249p13 51444436312537494

54、63637433816p14 625659434541566865553835263519p15 第一步：计算节约里程 s i , j=po , i+ po , jpi, j，结果如下： 表表 5-25-2 节约里程表（单位：公里）节约里程表（单位：公里） q i po 1.67p1 2.0149p2 2.1221310p3 2.520132025p4 1.52813232840p5 1.233927173343p6 1.43783212263557p7 1.6449281631426572p8 2.0541126223751666479p9 1.332131043252918121725p1

55、0 2.0511294226322013193163p11 1.7561110432937251724386397p12 2.242132430405554455474344149p13 1.65114213740544739496946596977p14 2.4621317413749393141615678926994p15 第二步：根据上表计算所得的结果，将节约值从大到小分类，如下表： 表表 5-35-3 节约里程顺序表（单位：公里）节约里程顺序表（单位：公里） p11p12: 97 p7p8:72 p10p11: 63 p5p4: 54p6p14: 47p3p11: 42p6p15:

56、39p5p7: 35 p14p15: 94p12p14:69p10p12:63p6p13: 54p10p14: 46p8p15: 41p7p14: 39p10p13:34 p12p15: 92p13p15:69p9p15: 61p8p13: 54p7p13:45p11p13: 41p9p12: 38p4p6: 33 p8p9: 79p9p14: 69p11p14: 59p5p9: 51p3p12: 43p3p15: 41p5p12: 37p2p7: 32 p11p15: 78p6p9: 66p6p7: 57p5p15: 49p5p6: 43p4p13: 40p4p15: 37p5p11: 32

57、 p13p14: 77p6p8: 65p10p15: 56p8p14: 49p3p10: 43p4p14:40p4p9: 37p4p8: 31 p9p13: 74p7p9: 64p5p13: 55p12p13:49p5p8: 42p4p5: 40p3p14: 37 第三步：在节约里程表中选出最大的节约格 p11p12= 97，说明将用户 p11，p12连接所获得的节约量最大，所以将初始方案中的用两辆车分别向 p11，p12送货，改为用一辆车向 p11，p12巡回送货。运输距离 sp0,11p11,12p12,0511056117km200km。运量 qq11q122.01.73.7，故用 5t

58、 车运送。 进一步修正方案。在节约里程表中寻找与 p11，p12有关的节约量最大的格 子，符合条件的是 p12p1592。考虑如果将其并入该路线是否可行。此时运输 距离 sp0,11p11,12p12,15p15,051102662149km200km；运量 qq11q12q152.01.72.43.7，故用 5t 车运送，并入可行。 以同样的方法继续寻找这样的格子，我们可以将点 p14，p13并入该路线。 此时运输距离 s1p0,11p11,12p12,15p15,14p14,13p13,0511026191642164km 200km；运量 qq11q12q15q14q132.01.72.

59、41.62.29.9t， 故用 10t 车运送。由于装载量的限制，如果再将其中的一用户并入该路线，势 必有 q10t，而该公司没有 10t 以上的车型，故此路线配送结束，第一个计划 配送完成。结果如下： 表表 5-45-4 第一个配送计划结果第一个配送计划结果 配送车型5t 8t 10t 可用的车辆数（辆） 70 60 80 分配的车辆（辆） 11 0 1 在剩下的节约格子里寻找里程最大的格子，符合条件的是 p8p9=79，将其连 接，此时运输距离 s2p0,8p8,9p9,0441954119km200km；运量 qq8q91.62.23.8t，故用 5t 车运送，并入可行。按同样的方法可以

60、把 p7，p6，p5依次并入该路线，此时运输距离 sp0,5p5,6p6,9p9,8p8,7p7,028182119937132km200km ；运量 qq5q6q7q8q91.51.21.41.62.07.7t，故用 8t 车运 送。考虑到如果再将 p4并入，q=10.2t10t，超出了车型载重量，故不可行。 第二个配送计划结束。结果如下： 表表 5-55-5 第二个配送计划结果第二个配送计划结果 配送车型5t 8t 10t 可用的车辆数（辆） 70 60 80 分配的车辆（辆） 5 1 1 在剩下的节约格子里继续寻找里程最大的格子，符合条件的是 p3p10=43， 将其连接，同理可以依次并