百源木业有限公司配送线路优化课件

1、 课课 程程 设设 计计课程名称课程名称: 交通运输组织学交通运输组织学 设计题目设计题目: 百源木业有限公司配送线路优化百源木业有限公司配送线路优化 学生姓名学生姓名: XXX 学学 号号: 20XXXXXXX 班班 级级: 交通运输交通运输 XXXX 院系名称院系名称: 交通运输工程学院交通运输工程学院 指导老师指导老师: 周骞周骞 叶鸿叶鸿 王佳王佳 2012 年年 12 月月交通运输组织学交通运输组织学课课 程程 设设 计计课程名称课程名称: 交通运输组织学交通运输组织学 设计题目设计题目: 百源木业有限公司配送线路优化百源木业有限公司配送线路优化 学生姓名学生姓名: XXXX 学学

2、号号: 20XXXXXXX 班班 级级: 交通运输交通运输 XXX 院系名称院系名称: 交通运输工程学院交通运输工程学院 指导老师指导老师: 周骞周骞 叶鸿叶鸿 王佳王佳 长沙理工大学课程设计任务书 交通运输工程 学院 交通运输 专业 2XX 级 X 班课程名称 交通运输组织学 题目 百源木业有限公司配送线路优化百源木业有限公司配送线路优化 学生姓名 XXXX 学号 20XXXXXXXXXX 同组设计者：无一、已知技术参数和设计要求一、已知技术参数和设计要求1、已知技术参数与参考资料、已知技术参数与参考资料交通运输部客货运组织与管理相关标准与规范董千里.交通运输组织学M .人民交通出版社，20

3、08 年李维斌.公路运输组织学 M .人民交通出版社，2005 年崔书堂，朱艳茹。交通运输组织学M.东南大学出版社，2008 年戴彤焱.运输组织学M.机械工业出版社，2008 年2、设计要求、设计要求本课程设计是针对学生学习和运用专业知识的综合考核和检查，使学生接受工程类基本训练的重要环节，是交通运输交通运输组织学专业课程学习的必修内容之一。本课程设计的特点是，内容所涉及的知识面较一般习题广，有较强的系统性和综合性，在运算、绘图、编写设计文本方面有较高的要求。本课程实际应针对交通运算组织学课程涉及的相关理论与方法，结合具体实践背景，解决实际问题。要求 所涉及方法、模型与理论知识与本课程相关；

4、有具体的实践背景； 课程实际要求完整、系统，从提出问题、解决问题与结论三个方面开展，思路清晰，条理清楚。二、课程设计应完成的任务二、课程设计应完成的任务 1、围绕课程中交通组织方面内容，完成对其方法、模型的阐述；2、结合实际背景，采用以上理论，进行运输组织优化等针对性设计，提出方案；3、对方案结果进行分析。三、工作计划三、工作计划本次课程设计安排时间为二周，2012 年 12 月 24 日至 2013 年 1 月 4 日，具体工作计划如下：1、2012 年 12 月 24 日25 日，项目背景资料的收集与整理；2、2012 年 12 月 26 日27 日，完成课程设计大纲；3、2012 年 1

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

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

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

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

9、时间的 1/3 以上，该课程设计按照零分计。运输与物流工程系2012 年 12 月目录目录引言.1第 1 章 物流配送概述.31.1 物流配送的概念.31.2 物流配送的功能.31.3 配送路线优化的意义.4第 2 章 百源木业有限公司配送运作现状.52.1 公司简介.52.2 公司配送现状.5第 3 章 物流配送模型及方法描述.73.1 多回路运输VRP 模型.73.2 节约算法.73.2.1 节约算法的基本原理.73.2.2 节约里程算法主要步骤.83.3 扫描算法.93.3.1 扫描算法的基本原理.93.3.2 扫描算法的主要步骤.93.4 改进后的最近插入法.93.4.1 最近插入法.

10、103.4.2 改进的最近插入法.10第 4 章 百源木业有限公司配送路线优化研究.114.1 建立 VRP 模型.114.2 百源木业公司的配送线路的分析与优化.114.2.1 原配送线路基本数据分析.124.2.2 基于节约算法的企业配送路线优化.134.2.3 基于扫描算法的企业配送路线优化.164.2.4 基于改进的最近插入法的企业配送路线优化.204.3 三种优化方案比较分析.21结论.24参考文献.251引言引言随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域” 。配送是现代物流的一个重要环节，

11、随着物流的全球化、信息化及一体化,配送在整个物流系统中的作用变得越来越重要。配送是连接生产与消费之间的一种中介服务。它是指按客户(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。配送不是单纯的运输或送货，而是运输与其他活动（集货，分货，配货）的组合，是“配”与“送”的有机结合。因此对于配送问题的研究可分为对 “配”和“送”两方面的研究。 “配”主要为配送中心选址问题， “送”包括旅行商问题(TSP)、车辆路线优化问题(VRP)。由于选址的外部因素（经济，基础设施，

12、环境等）及内部因素（企业战略，劳动力成本和素质等）的影响，单纯考虑距离问题的选址是不合理的，因此在本文中不对“配”进行研究，主要对“送”进行研究。配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速度、成本、效益影响很大。设计合理、高效的配送路线方案，不仅可以减少配送时间，降低作业成本，提高企业的效益，而且可以更好地为客户服务，提高客户的满意度，维护企业良好的形象。配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制） ，力争实现一定的目标（行驶里程最短，使用车辆尽

13、可能少） 。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要启发算法去求得近似最优解。本文将以百源木业有限公司当前的配送线路的优化问题作为研究对象，对各县市需求量及运距进行分析计算，建立 VRP 数学模型，运用节约算法和扫描2算法以及改进的最近插入法对建立的模型进行求解，对百源木业的配送路线进行优化。最后对三种方法求得的结果进行比较分析，从而为该公司提供较合理的配送方案，以期减少配送里程，降低物流运输成本，提高该公司物流运作效率，客户服务质量和整体竞争力。3第第 1 1 章章

14、 物流配送概述物流配送概述1.1 物流配送的概念配送（distribution）起源于“送货上门” 。20 世纪 60 年代初期，生产企业或中转仓库根据客户的需求，将货物准确的运送到客户手中，形成了配送的雏形“普通送货。随着客户对产品多样化和差异化的要求，为了满足客户的需求，原始的普通送货开始转向分拣、配货、送货一体化。因此产生了配送。按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”（GB/T 183542001） ，配送是指在经济合理区域范围内根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动1。1.2 物流配送的功能配送作为一种新型的物流

15、手段，伴随着生产的不断发展而日趋成熟。发展配送，无论对于物流系统的完善，企业的发展，还是整个经济社会效益的提高，都具有重要的作用。（1）配送完善和优化了物流系统。第二次世界大战后，高水平的干线运输呼唤支线运输和小搬运配套，但支线运输和小搬运在适应性、灵活性、服务性上的欠缺，致使运力不合理、运输成本过高。配送的出现使干线运输、支线运输及小搬运统一，输送过程得以优化和完善。（2）配送提高了末端物流的效益。配送通过大批量进货，集中发货，以及将多个小批量集中一起大批量发货，都能有效的节省运力，实现经济运输，降低成本，使末端的物流经济效益得到提高。（3）配送通过集中库存使企业实现低库存或零库存。采取准时

16、制配送方式之后，生产企业完全可以依靠配送中心的准时配送而不需保持自己的库存或保4持少量安全库存而不必留有经常库存。（4）配送简化事物，方便客服。采用配送的方式，客户只需向一处订购，或一个进货单位联系就可以订购到以往需要去许多地方才能顶到的货物，因此大大的减轻了客户的工作量和负担，也节省了事务的开支。（5）配送可以降低整个社会物资的库存水平。发展配送，实行集中库存，整个社会物资的库存总量必然低于各企业分散的库存总量。同时，配送有利于灵活高度，有利于发挥物资的作用。此外，集中库存可以发挥规模经济优势，降低库存成本 2。1.3 配送路线优化的意义配送合理化与否是配送决策系统的重要内容，配送线路的合理

17、与否又是配送合理化的关键。选择合的理配送路线，对企业和社会都具有很重要的意义。 对企业来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益3。 对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用 4。 5第第 2 2 章章 百源木业有限公司配送运作现状百源木

18、业有限公司配送运作现状2.1 公司简介百源木业有限公司地处江西婺源,公司以生产细木工板为主要产品，技术力量雄厚，工艺设备先进研发能力强。产品经国家人造板质量监督核准中心和省、市质量监督检测，GB/T5849-1999、GB18580-2001 标准 的 E1 级质量和环保标准。公司现有员工 370 余人，日均产量达 2500 张/天，年产量 60-80 万张，产值达 7000 余万元。 2.2 公司配送现状公司的客户可分为需求量稳定的大客户和需求量随机的小客户。大客户的需求具有时间和地点上的不确定性，需求量大的特点，一般采用租车进行点到点运输服务或客户自配卡车。小客户地点确定，主要位于其所在地

19、的周边县市，如图 1 所示，共有 9 个县市，如景德镇，黄山市，开化县等，但需求较小，公司为推广产品，采用每周专车送货上门服务。公司现拥有两辆 11 吨的货车，一辆 7 吨的货车，若车辆使用欠缺时，可租赁车辆。目前，对小客户公司采用的配送线路如图 2 所示，该配送线路的弊端在于：配送路线的选择不合理，优化不彻底，导致运距过长，消耗作业时间偏多，不能充分利用车辆配载容积，浪费较多人力和物力资源，影响公司盈利。各县市每星期需求细木工板的基本数据如表 1 所示。 表 2-1 各地区月货运量 客户1 景德镇2 乐平市3 鹰潭市4 贵溪市5 德兴市6 上饶市7 常山县8 开化县9 黄山市货运量18012

20、0120608022070902006数据来源：于百源木业有限公司内部资料图 2-1 百源木业有限公司配送网络图1710123456879 图 2-2 公司原有配送路线第第 3 3 章章 物流配送模型及方法描述物流配送模型及方法描述3.1 多回路运输VRP 模型多回路运输问题是现实中很普遍的一种调配问题，特别对于有大量服务对象的实体，例如拥有一个上千客户的企业。此类调配的核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型5。该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在

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

22、运输0v规章限制7。3.2 节约算法节约算法（Saving Algorithm）是用来解决运输车辆数目不确定的 VRP 问题，它是目前用来解决 VRP 模型最有名的启发式算法。3.2.1 节约算法的基本原理节约算法的核心思想是将运输问题中存在的两个回路（0， ，i，0）和（0，j， ，0）合并成一个回路（0， ，i，j，0） 。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离6。相应的变化值，叫做节约距离，如式（1）所示。ijC ijioojjiCccc（1）调整过程如图 3 所示8。 调整前 调整后 图 3-1 节约算法的图像描述0ji 0

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

24、中去除当前的节约里程，;iijjIIII 分析下一个客户对9。3.3 扫描算法扫描算法（Sweep Algorithm）也是用于求解车辆数目不限制的 VRP 问题，与节约算法不同的是，它属于亚启发式算法，而节约算法属于构造算法。3.3.1 扫描算法的基本原理扫描算法是一种“先分组后路线”的算法。所谓分组，即指派给每辆车一组点。一种简单的分组方法是将以配送中心为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车，然后扩充路线。如果在进行了一次“分组-路线”的路线构造后，还存在未分配点，则再进行“分组-路线”程序。如此反复，直到所有的点均已分配为止10。3.3.2 扫描算法的主

25、要步骤（1）以起始点 0 点作为极坐标系的原点，并一连通图中的任意一顾客点和10原点的连线定义为角度零，建立极坐标系。然后对所有的顾客所在的位置，进行极坐标变换。（2）分组 从最小角度的顾客开始建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量超出了负载的限制。然后继续建立一个新的组，继续按逆时针方向，将客户加入组中。（3）重复（2）中的过程，直到所有客户都被分类为止。（4）路径优化 对各个组内的单回路进行路径优化11。3.4 改进后的最近插入法TSP 模型是单回路运输问题的最为典型的一个模型，它的全称是 Traveling Salesman Problem1，中文叫做旅行商问

26、题。它是一个典型的 NP-Hard 问题，对于大规模的线路优化问题，无法获得最优解。最近插入法就是一种解决此问题的启发式算法。3.4.1 最近插入法 最近插入法是 Rosenkrantz 和 Stearns 等人在 1977 年提出的一种用于解决TSP(旅行商)问题的算法。最近插入法由四步完成：（1）找到最小的节点，形成一个子回路（subtour） ，。0iciv00,kTv v v（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。kv（3)在子回路中找到一条弧（i，j）,使得+-最小，然后将节点ikckjcijc插入到节点，之间，用两条新的弧(i，k)， （k，j）代替原来的弧iv

27、ivjv（i，j） ，并将节点加入到子回路中。kv（4）重复步骤（2） 、 （3） ，直到所有的节点都加入到子回路中。这样，子回路就演变为了一个 TSP 的解12。由于最近插入法解决的是单回路运输问题，故笔者在此方法基础上进行改进和修正，使其能解决多回路运输 VRP 问题。有改进的方法如下：113.4.2 改进的最近插入法（1）找到最小的节点，形成一个子回路（subtour） ，。0iciv00,kTv v v（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。若此kv时回路的总货运量未超过车的载重限制，则继续步骤（3） 。否则，转（1）寻找新的一条回路。（3）)在子回路中找到一条弧（

28、i，j）,使得+-最小，然后将节点ikckjcijc插入到节点，之间，用两条新的弧(i，k)， （k，j）代替原来的弧ivivjv（i，j） ，并将节点加入到子回路中。若此时该回路的总路程为未超过车辆的kv行程限制，则继续步骤（4） 。否则转步骤（1） ，寻找新的一条回路。（4）重复步骤（2）和（3） ，直到每一个节点都被归入某一个子回路中。第第 4 4 章章 百源木业有限公司配送路线优化研究百源木业有限公司配送路线优化研究4.1 建立 VRP 模型多回路运输问题时现实生活中十分常见的一种调配问题。此类调配问题的核心问题是车辆调度。因此 VRP 模型也应运而生，成了解决多回路问题的一个相当成功

29、的模型。据此对百源木业有限公司的配送系统建立 VRP 模型。基本条件：百源木业公司需给 9 个客户送货，客户依次为 1，2，,9，现有 1 辆 7 吨（长 7.8m,宽 2.2m,高 3.6m）的货车（每百公里油耗 21L） ，2 辆 11吨(长 9.5m,宽 2.3m,高 3.6m)的货车(每百公里油耗 27L)，柴油每升 7.07 元，司机每天工资 100 元。模型目标：确定所需要的车辆的数目 N、车辆类型、司机数量以及各车行走的路径，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输总费用最小。限制条件：12（1）基于人性化与安全的考虑，当运输里程超过 350 公里时，

30、需配备两名司机，为防止突发运输事件，车辆必须当天回到公司，减去去由于装卸货等影响因素，各车最大运输距离为 600 公里。（2） 每辆车完成任务之后都要回到源点 0 处。（3） 车辆的容量限制不能超过。7 吨的货车最多可装 300 张细木工板，11 吨的最多可装 500 张细木工板。11 吨货车运输单价比 7 吨的低，优先使用11 吨车，若不超过 300 张细木工板，则使用 7 吨货车。4.2 百源木业公司的配送线路的分析与优化已知百源木业公司为 0 点，分别向 9 个小客户点配送细木工板，其拥有一辆 7 吨的车和两辆 11 吨的车， 7 吨卡车最大容量为 300 张细木工板，11 吨卡车最大载

31、量为 500 张。设各点间的距离为，节约距离为,| ,1,2,9ijC Cci j。每辆车的载货量为 ，各点需求量为，每辆车的行驶里程ijcir1,2,9iR i 为，且公里，婺源为 0 点，客户点 1，2，9。1,2,9iL i 600iL 各县市的细木工板运量和配送距离如表 2 所示。表 4-1 运输任务表客户1 景德镇2 乐平市3 鹰潭市4 贵溪市5 德兴市6 上饶市7 常山县8 开化县9 黄山市货运量（张/周）18012012060802207090200配送距离（km）75.989.2186.7170.357.0153.887.081.582.54.2.1 原配送线路基本数据分析目前

32、，百源木业有限公司对小客户公司采用的配送模式如图 2 所示。各配送线路低得里程，所需司机数量及工资的基本情况如表 3 所示。13表 4-2 配送信息表路线运距运货量车型司机0-1-2-0213.7km3007吨货车10-3-4-0373.4km1807吨货车20-5-6-0315.4km3007吨货车10-7-8-0202.7km1607吨货车10-9-0165.0km2007吨货车1由上表可知，公司每周需 7 吨货车 5 车次配送，司机 6 人次，所需工资600 元，运输总里程为 1270.2 千米，消耗的柴油 266.75 升，所需燃油费1885.87 元，一共花费 2485.87 元。4

33、.2.2 基于节约算法的企业配送路线优化首先，确定各县市间的最短距离，县市间最距离表 4 所示。表 4-3 各县市间最短距离表 （单位：千米）县市0 婺源县1 景德镇2 乐平市3 鹰潭市4 贵溪市5 德兴市6 上饶市7 常山县8 开化县9 黄山市0 婺源县075.989.2186.7170.357.0153.887.081.582.51 景德镇048.6157.1173.886.1194.3161.2148.9154.72 乐平市097.3117.048.6143.1158.1156.4170.53 鹰潭市016.4125.098.5170.2206.3268.74 贵溪市0107.281.5

34、153.9190.1251.35 德兴市0104.6103.298.3103.16 上饶市083.3115.7232.0147 常山县034.2126.88 开化县091.49 黄山市0数据来源：谷歌地图然后，形成一初始解， ，令，最短路径iIi1,2,9i （ =1，9），且公里，载货量，且，对 92iL 0ici600iL iirR500ir 个客户点进行标记，且。1290BBBB2i其次，求节约里程。根据最短距离表，根据式（1）计算出用户间的节约里程,并由大到小排列，编制节约里程顺序表，如表 5 所示。ijc 表 4-4 节约里程顺序表 （单位：千米）连接点节约里程连接点节约里程连接点节

35、约里程连接点节约里程3-4340.63-5118.71-472.42-718.14-6242.61-2116.53-861.92-814.33-6242.05-6106.14-861.71-88.52-3178.61-3105.57-952.76-94.36-7157.53-7103.51-546.81-93.72-4142.54-7103.45-740.81-71.77-8124.32-699.95-840.54-91.54-5120.32-597.65-936.42-91.26-8119.68-972.61-635.43-90.5最后，按节约里程从大到小合并路径15（1）对于34340.6

36、:ckm3412060180500,rr。343434186.7*2 170.3*2340.6373.4600,0LLckmkm BB故合并3，4两点，则。1341134343,4 ,180,373.4,1,IIIrLkm BBII （2）对于46242.6:ckm16180220400500,rr。164646373.4 153.8*2242.6438.4600,1,0LLckmkm BB故合并4，6两点，则216113623463,4,6 ,400,438.4,1,2,IIIrLkm BBBIII （3）对于因为3与6处在同一回路中，故不满足合并条件。36242.0:ckm（4）对于故不满

37、足合并条件。23178.6:ckm22400 120520500,rr（5）对于67157.5:ckm2740070470500,rr。276767438.487*2 157.5454.9600,1,0LLckmkm BB故合并6，7两点，则3163337263,4,6,7 ,470,454.9,1,2,IIIrLkm BBBB。3467IIII （6）余下各点的货运量均大于30，故回路0-3-4-6-7-0不能再与其他点合并。接下来的讨论将跳过与点3，4，6，7相关的。ijc（7）对于12116.5:ckm12180 120300500,rr。12121275.9*289.2*2 116.5

38、213.7600,0LLckmkm BB故合并1，2两点，则。 4124412121,2 ,3000,213.7,1,IIIrLkm BBII （8）对于2597.6:ckm4530080380500,rr。452525213.757*297.6230.1600,1,0LLckmkmkm BB16故合并2，5两点，则545111521251,2,5 ,380,230.1,1,2,IIIrLkm BBBIII （9）对于8972.6:ckm8990200290300,rr。89898981.5*282.5*272.6255.4600,0LLckmkm BB故合并8，9两点，则。689448989

39、8,9 ,290,255.4,1,IIIrLkm BBII （10），故线路0-1-2-5-0与线路0-8-9-0不能45380290670500rr合并。至此，合并结束。最后得到的最优结果如表6所示，优化线路图如图4所示。表4-5节约法优化结果路线运距运货量车型司机0-3-4-6-7-0454.8km47011吨货车20-1-2-5-0230.1km38011吨货车10-8-9-0255.4km2907吨货车1由上表可知，公司每周需 11 吨货车 2 车次和 7 吨货车 1 车次配送，司机 4人次，所需工资 400 元，运输总里程为 940.3 千米，消耗的柴油 239.56 升，所需燃油费

40、 1686.60 元，一共花费 2086.60 元。170123456879图4-1 节约算法求解线路结果4.2.3 基于扫描算法的企业配送路线优化对百源木业周边的 9 个县市采用扫描算法进行配送线路的优化。首先建立极坐标系：以百源木业有限公司所在地婺源县作为原点，并以点1景德镇与原点的连线为零角度建立极坐标系，各点的货运量及极坐标的角坐标值如表7所示。坐标系如图5所示。表4-6 运量和极坐标的角坐标值客户1 景德镇2 乐平市3 鹰潭市4 贵溪市5 德兴市6 上饶市7 常山县8 开化县9 黄山市货运量（张/周）18012012060802207090200角坐标0344652611031521

41、69238180123456879图4-2 扫描算法的扫描过程然后分组：从角度为零向逆时针方向进行扫描，如图所示。第一个被分组的是客户 1， =180；继续转动，下个被分组的是客户 2， =180+120=300；继1r1r续转动，下个被分组的是客户 3，300+120=420；继续转动，下个被分组的是客户 4， =420+60=480；继续转动，下个被分组的是客户1r6， =480+80=560500，由于超过了限制，按分组规则，需要一个新的组，这1r样在第一组里只有客户 1，2，3，4， =480。1r进行第二组扫描，最先扫描到的是客户 5， =80；继续转动，下个被分组1r的是客户 6，

42、 =80+220=300；继续转动，下个被分组的是客户1r7， =300+70=370；继续转动，下个被分组的是客户 8， =370+90=460；继续1r1r转动，下个被分组的是客户 9， =460+200=660500，超过限制，所以需要一个1r新的组，这样在第二组中只有客户 5，6，7，8， =460。1r在第三组中只剩一个客户 9，故顾客 9 单独在一组， =200。1r19这时，可以得到如图 6 所示的分组结果。0123456879图4-3 扫描算法求解结果最后对各子回路内的线路优化：对上面的3个组，都已经是一个单回路运输问题，对每个组进行线路优化。供应点0是任何一个组的TSP问题的

43、起点和终点，用最近插入法分别对三个客户组进行求解。对第一组进行求解。比较表4-2 中从0出发的所有路径大小，001min|,1475.9iciNickm 这样，就有顾客点0，1构成一个子回路，。10,1,0T 然后考虑剩下顾客点2，3，4到0和1中某一点的最小距离：0112min,|,14,i148.6iicciNickm 且由于对称性，无论将2插入到0和1之间往返路径中，结果都是一样的，这样，构成了一个新的子回路。10,1,2,0T 接下来考虑剩下的顾客点3，4到0，1，2中某一点的最小距离01223min,|,14,i1,297.3iiiccciNickm 且顾客点3有3个位置可以插入，现

44、在分析将点3加入到哪里合适。（1） 插入到（0，1）之间，20。033101186.7 157.1 75.9267.9ccckm （2） 插入到（1，2）之间，。133212157.1 97.348.6205.8ccckm （3） 插入到（2，0）之间，。23302097.3 186.789.2194.8ccckm 比较可知，插入到（2，0）之间增量最小，所以将顾客点3加入到（2，0）间，结果为10,1,2,3,0T 重复上面的步骤，将顾客点4加入到子回路中，就可得到一个用最近插入法求得的可行解，总行驶距离为：。10,1,2,3,4,0T 1408.5Lkm对第二组进行求解，可得，总行驶距离为

45、：20,5,6,7,8,0T 。对第三组进行求解，可得，总行驶距离为：2360.6Lkm30,9,0T 。3165Lkm最后得到的最优结果如表8所示，优化线路图如图7所示。表4-7扫描算法优化结果路线运距运货量车型司机0-1-2-3-4-0408.5km48011吨货车20-5-6-7-8-0360.6km46011吨货车20-9-0165.0km2007吨货车1由上表可知，公司每周需 11 吨货车 2 车次和 7 吨货车 1 车次配送，司机 5人次，所需工资 500 元，运输总里程为 934.1 千米，消耗的柴油 242.31 升，所需燃油费 1713.11 元，一共花费 2213.11 元

46、。210123456879图4-4 扫描算法求解线路结果4.2.4 基于改进的最近插入法的企业配送路线优化令 T=0,N=0，1，2,10，比较表 4-2 中从 0 出发的所有路径大小。因为，所以就有顾客点 0，1 构成一个子回005min|,1957.0iciNickm 路，此时，。10,5,0T 180r1114.0Lkm然后在剩余顾客点（1，2，3，4，6，7，8，9）中寻找到 0 和 5 中某一点的最小距离，,因为0501min,|,19575.9iicciNiickm 且1180r ，所以在子回路插入点 1。由于对称性，无论将 151260500rr10,5,0T 插入到 0 和 5

47、 之间往返路径中，结果都是一样的，这样，构成了一个新的子回路，。10,1,5,0T 1260r1219.0Lkm再次寻找剩余顾客点到 0，1， 5 中某一点的最小距离：可知最小距离为1248.6ckm此时, ，因为，所以在子回路2120r 12260 120380500rr插入点 2。10,1,5,0T 将点 2 分别插入（0，1） ， （1，5） ， （5，0）中，比较得：插入到（1，5）中增22量最小，。12251548.648.686.111.1ccckm 此时构成了一个新的子回路，。10,1,2,5,0T 1380r1230.1Lkm再次对剩余的顾客点按照上诉方法进行优化，可构成另子回

48、路和子回路10,3,4,6,0T 10,7,8,9,0T 利用改进的最近插入法得到优化结果如表 9 所示，优化线路结果如图 8 所示。表4-8 改进的最近插入法优化结果路线运距运货量车型司机0-1-2-5-0230.1km47011吨货车10-3-4-6-0438.4km18011吨货车20-7-8-9-0295.1km49011吨货车1由上表可知，公司每周需 11 吨货车 3 车次和，司机 4 人次，所需工资 400元，运输总里程为 963.6 千米，消耗的柴油 260.17 升，所需燃油费 1839.42 元，一共花费 2239.42 元。0123456879图4-5 改进的最近插入法求解

49、线路结果234.3 三种优化方案比较分析由上文可知，通过节约算法，扫描算法和改进后的最近插入法分别对配送线路进行优化，可得到三种不同的优化方案，因此我们需要通过一系列指标来评价方案的优劣性。本文将以所需车辆数，行驶总里程，总油耗，人力资源和总费用这些指标，对三种优化后的方案进行评价分析，如表 10 所示。表 4-9 优化结果对比表优化后状态优化前节约算法扫描算法改进后的最近插入法7t5110各车型车次(次)11t0223总运输里程(km)1270.2940.3934.1963.6节约里程数（km）329.9336.1306.6油耗（L）266.75239.56242.31260.17节约油耗（

50、L）27.1924.446.58司机（次）6454节约人力（次）21224总费用（元）2485.872086.602313.112239.42节约费用（元）399.27172.76246.45从上表的对比中可知，从车次需求数的角度来看，优化后的三种方案需求车次数相同，但优化后的方案与优化前方案相比较节约了 2/5 的车次需求。优化后的方案需要使用更少的车次，减少了百源木业用车紧张进而租车情况的出现，使百源木业车辆安排使用上具有更大弹性。因此，在用车角度上考虑，优化后的方案均比优化前的方案合理，优化后的三种方案等价。从总运输里程角度考虑，优化后的三种方案的总运输里程分别为 940.3 千米，93

51、4.1 千米，963.6 千米，与原方案的 1303.4 千米相比较，均减少了车辆行驶的里程数。优化后的方案能减少了公司车辆的损耗和资源的浪费，给百源木业带去更多的效益。因此，从运输里程的角度考虑，优化后的方案扫描算法最优，节约算法次之，改进后的最近插入法再次之。从燃油消耗的角度考虑，优化后的三种方案的消耗分别为 239.56 升，242.31 升，260.17 升，与原方案的 266.75 升相比较，三种优化方案均降低了油耗量，改进后的插入法优化后的方案消耗更多的油耗。配送线路优化后，不仅能减少百源木业公司燃油费用的支出，还能降低社会资源的浪费。因此，从燃油消耗的角度上考虑，节约算法最优，扫

52、描算法次之。从公司人力资源消耗角度来考虑，优化后的方案所需司机依次为 4，5，4人次，减少人力的消耗为 2，1，2 人次。三种优化后的方案均能使公司在人员安排上将更具有弹性，还能降低公司费用的支出。因此，从百源木业人力资源消耗的角度考虑，节约算法和改进后的最近插入法最优，扫描算法次之。从支出的总费用角度来考虑，优化后的方案的费用支出依次 2086.60 元，2313.11 元，2239.42 元，与原方案的为 2485.87 元相比较，改进后的插入法优化后的方案花费更多的费用支出。因此，从支出总费用的角度考虑，节约算法最优，改进后的最近插入法次之。结合车次需求数，总运输里程，燃油消耗，人力资源

53、消耗，支出的总费用五个角度一齐分析，节约算法最优。但是，本文的配送距离略有超出配送最佳范围，模型存在着一定的缺陷。在计算过程中也将一些因素理想化了，与实际25情况不完全相符。例如，并未考虑具体的道路信息，运输规章等。因此，百源木业应该根据实际情况合理选择配送方案。结论结论百源木业为了推广品牌，扩大市场，对小客服实施了进行送货上门服务。但随之而来的就是配送成本的问题，公司为保持正常的盈利，降低配送成本则势在必行，这就意味着公司要对原配送路线进行优化。本文针对百源木业有限公司 9 个县市配送状况进行了线路规划，应用了节约算法、扫描算法及改进的最近插入法三种方法进行了计算分析，经过比较 3种结果，选择出了一个最优方案，经过效