某某有限公司配送线路优化方案研究与设计

1、某某有限公司配送线路优化方案研究与设计 摘要 高效率合理的配送是物流系统顺利运行的保证，配送线路安排的合理与否对配送速 度、成本、效益影响很大。正确合理地安排车辆的配送线路，实现合理的线路运输，可以有 效地节约运输时间，增加车辆利用率，从而降低运输成本，提高企业经济效益与客户服务水 平，使企业达到科学化的物流管理, 这也是企业提高自身竞争力的有效途径之一。物流配送 路径优化问题具有很高的计算复杂性，属于 np 完全难问题，高效的精确算法存在的可能性 不大，但可根据启发算法求得近似最优解。本文首先对物流配送进行概述，然后以婺源百源 木业有限公司的配送方案为例，对百源木业有限公司的配送现状进行分析

2、，并运用节约算法、 扫描算法以及改进后的最近插入法对百源木业有限公司的配送线路进行优化，提出最优配送 方案。 关键词 配送 车辆路径问题 节约算法 扫描算法 改进的最近插入法 research and designation of optimization of baiyuan wood co., ltd. distribution line abstract reasonable and efficient distribution is the insurance of a smooth running logistics system; distribution line arrange

3、ment is reasonable or not has a great influence on the speed of delivery, costs and benefits. to arrange a reasonable and correct delivery line for vehicle and achieve a reasonable transport line can effectively increase the utilization of vehicles, save transportation time, thus reducing transporta

4、tion costs, improving economic efficiency, enhancing customer service levels and enable enterprises to achieve scientific logistics management, which is one of the effective way for an enterprise to improve its competitiveness. the optimization of logistics distribution routing which has high comput

5、ational complexity is a np-hard problem, that is why efficient exact algorithm is unlikely to exist. in the beginning of this paper is an overview of logistics and distribution, and then take wuyuan baiyuan wood co., ltd. distribution as an example to analysis of the status of its distribution, and

6、use saving algorithm, scanning algorithm and the improved method has recently inserted to optimize the distribution lines for wuyuan baiyuan wood co., and at last, propose the best distribution scheme. key words distribution vehicle routing problem saving algorithm sweep algorithm improved nearest i

7、nsertion 目录 引言.4 第 1 章 物流配送概述.3 1.1 物流配送的概念 .3 1.2 物流配送的功能.4 1.3 配送路线优化的意义.4 第 2 章 百源木业有限公司配送运作现状.5 2.1 公司简介.5 2.2 公司配送现状 .5 第 3 章 物流配送模型及方法描述.8 3.1 多回路运输vrp 模型.8 3.2 节约算法.8 3.2.1 节约算法的基本原理 .8 3.2.2 节约里程算法主要步骤.9 3.3 扫描算法 .10 3.3.1 扫描算法的基本原理.10 3.3.2 扫描算法的主要步骤.10 3.4 改进后的最近插入法.10 3.4.1 最近插入法.10 3.4.2

8、 改进的最近插入法.11 第 4 章 百源木业有限公司配送路线优化研究.12 4.1 建立 vrp 模型.12 4.2 百源木业公司的配送线路的分析与优化 .12 4.2.1 原配送线路基本数据分析.13 4.2.2 基于节约算法的企业配送路线优化.13 4.2.3 基于扫描算法的企业配送路线优化.17 4.2.4 基于改进的最近插入法的企业配送路线优化 .21 4.3 三种优化方案比较分析 .22 结论.25 致谢语.26 参考文献.27 引言 随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日 益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域” 。配送

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

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

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

12、， 提高该公司物流运作效率，客户服务质量和整体竞争力。 第 1 章 物流配送概述 1.1 物流配送的概念 配送（distribution）起源于“送货上门” 。20 世纪 60 年代初期，生产企业或中转仓库 根据客户的需求，将货物准确的运送到客户手中，形成了配送的雏形“普通送货。随 着客户对产品多样化和差异化的要求，为了满足客户的需求，原始的普通送货开始转向分拣、 配货、送货一体化。因此产生了配送。 按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语” （gb/t 183542001） ，配送是指在经济合理区域范围内根据用户要求，对物品进行拣选、加工、 包装、分割、组配等作业，并按时

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

14、，使末端的物流经 济效益得到提高。 （3）配送通过集中库存使企业实现低库存或零库存。采取准时制配送方式之后，生产 企业完全可以依靠配送中心的准时配送而不需保持自己的库存或保持少量安全库存而不必留 有经常库存。 （4）配送简化事物，方便客服。采用配送的方式，客户只需向一处订购，或一个进货 单位联系就可以订购到以往需要去许多地方才能顶到的货物，因此大大的减轻了客户的工作 量和负担，也节省了事务的开支。 （5）配送可以降低整个社会物资的库存水平。发展配送，实行集中库存，整个社会物 资的库存总量必然低于各企业分散的库存总量。同时，配送有利于灵活高度，有利于发挥物 资的作用。此外，集中库存可以发挥规模经

15、济优势，降低库存成本 2。 1.3 配送路线优化的意义 配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关 键。选择合的理配送路线，对企业和社会都具有很重要的意义。 对企业来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加 车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到客户的手 中，提高客户满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞 争力与效益3。 对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企 业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少

16、噪声、尾气排放 等运输污染，对民生和环境也有不容忽视的作用 4。 第 2 章 百源木业有限公司配送运作现状 2.1 公司简介 百源木业有限公司地处江西婺源,公司以生产细木工板为主要产品，技术力量雄厚，工 艺设备先进研发能力强。产品经国家人造板质量监督核准中心和省、市质量监督检测， gb/t5849-1999、gb18580-2001 标准 的 e1 级质量和环保标准。公司现有员工 370 余 人，日均产量达 2500 张/天，年产量 60-80 万张，产值达 7000 余万元。 2.2 公司配送现状 公司的客户可分为需求量稳定的大客户和需求量随机的小客户。大客户的需求具有时间 和地点上的不确定

17、性，需求量大的特点，一般采用租车进行点到点运输服务或客户自配卡车。 小客户地点确定，主要位于其所在地的周边县市，如图 1 所示，共有 9 个县市，如景德镇， 黄山市，开化县等，但需求较小，公司为推广产品，采用每周专车送货上门服务。公司现拥 有两辆 11 吨的货车，一辆 7 吨的货车，若车辆使用欠缺时，可租赁车辆。 目前，对小客户公司采用的配送线路如图 2 所示，该配送线路的弊端在于：配送路线的 选择不合理，优化不彻底，导致运距过长，消耗作业时间偏多，不能充分利用车辆配载容积， 浪费较多人力和物力资源，影响公司盈利。 各县市每星期需求细木工板的基本数据如表 1 所示。 表 2-1 各地区月货运量

18、 客户1 景德镇2 乐平市3 鹰潭市4 贵溪市5 德兴市6 上饶市7 常山县8 开化县9 黄山市 货运量 18012012060802207090200 数据来源：于百源木业有限公司内部资料 图 2-1 百源木业有限公司配送网络图 1 1 0 1 2 3 4 5 6 8 7 9 图 2-2 公司原有配送路线 1. 图片来源：http:/ 第 3 章 物流配送模型及方法描述 3.1 多回路运输vrp 模型 多回路运输问题是现实中很普遍的一种调配问题，特别对于有大量服务对象的实体，例 如拥有一个上千客户的企业。此类调配的核心问题是如何对车辆进行调度。因此， vrp（vehicle routing

19、problem）模型也应运而生，成了解决多回路问题的一个相当成功 的模型5。 该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在 满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等） ，达到 一定的优化目标（如里程最短，费用最小，时间尽量少等） 。它涉及了多辆交通工具的服务 对象的选择和路径确定两方面问题6。 一个典型的 vrp 模型可以如下表述： （1）基本条件 现有 m 辆相同的车辆停在一个共同的源点，它需给 n 个客户提供货 0 v 物，顾客为。 12n ,vvv、 ， （2）模型目标 确定所需的车辆数 n，并指派这些车辆到一个回路中，同时

20、包括回路内 的路径安排和调度，使总费用最小。 （3）限制条件：n 不大于 m；每一个订单都要完成；每辆车完成任务后都要回到源点 ；车辆的容量限制不能超过；特殊问题还需考虑时窗限制；运输规章限制7。 0 v 3.2 节约算法 节约算法（saving algorithm）是用来解决运输车辆数目不确定的 vrp 问题，它是目 前用来解决 vrp 模型最有名的启发式算法。 3.2.1 节约算法的基本原理 节约算法的核心思想是将运输问题中存在的两个回路（0， ，i，0）和（0，j， ，0）合并成一个回路（0， ，i，j，0） 。在上面的合并操作中，整个运输问题的总运 输距离会发生变化，如果变化后总运输距

21、离下降，则称节约了运输距离6。相应的变化值， 叫做节约距离，如式（1）所示。 ij c （1） ijioojji cccc 调整过程如图 3 所示8。 调整前 调整后 图 3-1 节约算法的图像描述 0 j i 0 j i 3.2.2 节约里程算法主要步骤 已知条件:需求点集=1,2, n,各点需求量,各点间最短距离。 r n i r ij c 第一步,形成一个初始解。确定各车辆配送点集令, =1,2,n (先采 12 , m i ii j ijj 取单点配送)。 第二步,进行节约度的计算。计算所有点对的节约度，然后对计算结果进行升序 排列。 第三步，进行回路的合并。从升序排列的节约度序列中的

22、最上面的值开始，直到节约里 程的队列空为止,重复下列步骤:按照节约里程队列从大到小的顺序,分析客户 i 和 j 之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过 2),将 i, j 连接起来,即可令。如果不是这样,则从节约里程队列中去除当前的节约里; iijj iiii 程，分析下一个客户对9。 3.3 扫描算法 扫描算法（sweep algorithm）也是用于求解车辆数目不限制的 vrp 问题，与节约算 法不同的是，它属于亚启发式算法，而节约算法属于构造算法。 3.3.1 扫描算法的基本原理 扫描算法是一种“先分组后路线”的算法。所谓分组，即指派给每辆车一组点。一种

23、简 单的分组方法是将以配送中心为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区 域的点分派给一辆车，然后扩充路线。如果在进行了一次“分组-路线”的路线构造后，还 存在未分配点，则再进行“分组-路线”程序。如此反复，直到所有的点均已分配为止10。 3.3.2 扫描算法的主要步骤 （1）以起始点 0 点作为极坐标系的原点，并一连通图中的任意一顾客点和原点的连线 定义为角度零，建立极坐标系。然后对所有的顾客所在的位置，进行极坐标变换。 （2）分组 从最小角度的顾客开始建立一个组，按逆时针方向，将顾客逐个加入到组中， 直到顾客的需求总量超出了负载的限制。然后继续建立一个新的组，继续按逆时针方向，

24、 将客户加入组中。 （3）重复（2）中的过程，直到所有客户都被分类为止。 （4）路径优化 对各个组内的单回路进行路径优化11。 3.4 改进后的最近插入法 tsp 模型是单回路运输问题的最为典型的一个模型，它的全称是 traveling salesman problem1，中文叫做旅行商问题。它是一个典型的 np-hard 问题，对于大规模的线路优 化问题，无法获得最优解。最近插入法就是一种解决此问题的启发式算法。 3.4.1 最近插入法 最近插入法是 rosenkrantz 和 stearns 等人在 1977 年提出的一种用于解决 tsp(旅行商)问 题的算法。最近插入法由四步完成： （1

25、）找到最小的节点，形成一个子回路（subtour） ，。 0i c i v 00 , k tv v v （2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。 k v （3)在子回路中找到一条弧（i，j）,使得+-最小，然后将节点插入到节点， ik c kj c ij c i v i v 之间，用两条新的弧(i，k)， （k，j）代替原来的弧（i，j） ，并将节点加入到子回路中。 j v k v （4）重复步骤（2） 、 （3） ，直到所有的节点都加入到子回路中。 这样，子回路就演变为了一个 tsp 的解12。 由于最近插入法解决的是单回路运输问题，故笔者在此方法基础上进行改进和修正，使

26、 其能解决多回路运输 vrp 问题。有改进的方法如下： 3.4.2 改进的最近插入法 （1）找到最小的节点，形成一个子回路（subtour） ，。 0i c i v 00 , k tv v v （2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。若此时回路的总 k v 货运量未超过车的载重限制，则继续步骤（3） 。否则，转（1）寻找新的一条回路。 （3）)在子回路中找到一条弧（i，j）,使得+-最小，然后将节点插入到节点 ik c kj c ij c i v ，之间，用两条新的弧(i，k)， （k，j）代替原来的弧（i，j） ，并将节点加入到子回路 i v j v k v 中。若此时该

27、回路的总路程为未超过车辆的行程限制，则继续步骤（4） 。否则转步骤（1） ， 寻找新的一条回路。 （4）重复步骤（2）和（3） ，直到每一个节点都被归入某一个子回路中。 第 4 章 百源木业有限公司配送路线优化研究 4.1 建立 vrp 模型 多回路运输问题时现实生活中十分常见的一种调配问题。此类调配问题的核心问题是车 辆调度。因此 vrp 模型也应运而生，成了解决多回路问题的一个相当成功的模型。据此对 百源木业有限公司的配送系统建立 vrp 模型。 基本条件：百源木业公司需给 9 个客户送货，客户依次为 1，2，,9，现有 1 辆 7 吨 （长 7.8m,宽 2.2m,高 3.6m）的货车（

28、每百公里油耗 21l） ，2 辆 11 吨(长 9.5m,宽 2.3m, 高 3.6m)的货车(每百公里油耗 27l)，柴油每升 7.07 元，司机每天工资 100 元。 模型目标：确定所需要的车辆的数目 n、车辆类型、司机数量以及各车行走的路径，并 指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输总费用最小。 限制条件： （1）基于人性化与安全的考虑，当运输里程超过 350 公里时，需配备两名司机，为防 止突发运输事件，车辆必须当天回到公司，减去去由于装卸货等影响因素，各车最大运输距 离为 600 公里。 （2） 每辆车完成任务之后都要回到源点 0 处。 （3） 车辆的容量

29、限制不能超过。7 吨的货车最多可装 300 张细木工板，11 吨的最多 可装 500 张细木工板。11 吨货车运输单价比 7 吨的低，优先使用 11 吨车，若不超过 300 张细木工板，则使用 7 吨货车。 4.2 百源木业公司的配送线路的分析与优化 已知百源木业公司为 0 点，分别向 9 个小客户点配送细木工板，其拥有一辆 7 吨的车 和两辆 11 吨的车， 7 吨卡车最大容量为 300 张细木工板，11 吨卡车最大载量为 500 张。 设各点间的距离为，节约距离为。每辆车的载货量为 ，各点需,| ,1,2,9 ij c cci j ij c i r 求量为，每辆车的行驶里程为，且公里，婺源

30、为 0 点，1,2,9 i r i 1,2,9 i l i 600 i l 客户点 1，2，9。 各县市的细木工板运量和配送距离如表 2 所示。 表 4-1 运输任务表 客户1 景德镇2 乐平市3 鹰潭市4 贵溪 市 5 德兴市6 上饶市7 常山 县 8 开化 县 9 黄山 市 货运量（张/ 周） 18012012060802207090200 配送距离 （km） 75.989.2186.7170.357.0153.887.081.582.5 4.2.1 原配送线路基本数据分析 目前，百源木业有限公司对小客户公司采用的配送模式如图 2 所示。各配送线路低得里 程，所需司机数量及工资的基本情况如

31、表 3 所示。 表 4-2 配送信息表 路线运距运货量车型司机 0-1-2-0213.7km300 7吨货车 1 0-3-4-0373.4km180 7吨货车 2 0-5-6-0315.4km300 7吨货车 1 0-7-8-0202.7km160 7吨货车 1 0-9-0165.0km200 7吨货车 1 由上表可知，公司每周需 7 吨货车 5 车次配送，司机 6 人次，所需工资 600 元，运输 总里程为 1270.2 千米，消耗的柴油 266.75 升，所需燃油费 1885.87 元，一共花费 2485.87 元。 4.2.2 基于节约算法的企业配送路线优化 首先，确定各县市间的最短距离

32、，县市间最距离表 4 所示。 表 4-3 各县市间最短距离表 （单位：千米） 县市 0 婺源 县 1 景德 镇 2 乐平 市 3 鹰潭 市 4 贵溪 市 5 德兴 市 6 上饶 市 7 常山 县 8 开化 县 9 黄山 市 0 婺源县 075.989.2186.7170.357.0153.887.081.582.5 1 景德镇 048.6157.1173.886.1194.3161.2148.9154.7 2 乐平市 097.3117.048.6143.1158.1156.4170.5 3 鹰潭市 016.4125.098.5170.2206.3268.7 4 贵溪市 0107.281.515

33、3.9190.1251.3 5 德兴市 0104.6103.298.3103.1 6 上饶市 083.3115.7232.0 7 常山县 034.2126.8 8 开化县 091.4 9 黄山市 0 数据来源：谷歌地图 然后，形成一初始解， ，令，最短路径（ =1，9）， i ii1,2,9i 2 i l 0i ci 且公里，载货量，且，对 9 个客户点进行标记，600 i l ii rr500 i r 129 0bbb 且。b2 i 其次，求节约里程。根据最短距离表，根据式（1）计算出用户间的节约里程,并由大到 小排列，编制节约里程顺序表，如表 5 所示。 ij c 表 4-4 节约里程顺序

34、表 （单位：千米） 连接点 节约 里程 连接点 节约 里程 连接点 节约 里程 连接点 节约 里程 3-4340.63-5118.71-472.42-718.1 4-6242.61-2116.53-861.92-814.3 3-6242.05-6106.14-861.71-88.5 2-3178.61-3105.57-952.76-94.3 6-7157.53-7103.51-546.81-93.7 2-4142.54-7103.45-740.81-71.7 7-8124.32-699.95-840.54-91.5 4-5120.32-597.65-936.42-91.2 6-8119.68-

35、972.61-635.43-90.5 最后，按节约里程从大到小合并路径 （1）对于 34 340.6:ckm 34 12060180500,rr 。 343434 186.7*2 170.3*2340.6373.4600,0llckmkm bb 故合并3，4两点，则。 134113434 3,4 ,180,373.4,1,iiirlkm bbii （2）对于 46 242.6:ckm 16 180220400500,rr 。 164646 373.4 153.8*2242.6438.4600,1,0llckmkm bb 故合并4，6两点，则 21611362346 3,4,6 ,400,438

36、.4,1,2,iiirlkm bbbiii （3）对于因为3与6处在同一回路中，故不满足合并条件。 36 242.0:ckm （4）对于故不满足合并条件。 23 178.6:ckm 22 400 120520500,rr （5）对于 67 157.5:ckm 27 40070470500,rr 。 276767 438.487*2 157.5454.9600,1,0llckmkm bb 故合并6，7两点，则 316333726 3,4,6,7 ,470,454.9,1,2,iiirlkm bbbb 。 3467 iiii （6）余下各点的货运量均大于30，故回路0-3-4-6-7-0不能再与其

37、他点合并。接下来 的讨论将跳过与点3，4，6，7相关的。 ij c （7）对于 12 116.5:ckm 12 180 120300500,rr 。 121212 75.9*289.2*2 116.5213.7600,0llckmkm bb 故合并1，2两点，则。 412441212 1,2 ,3000,213.7,1,iiirlkm bbii （8）对于 25 97.6:ckm 45 30080380500,rr 。 452525 213.757*297.6230.1600,1,0llckmkmkm bb 故合并2，5两点，则 54511152125 1,2,5 ,380,230.1,1,2

38、,iiirlkm bbbiii （9）对于 89 72.6:ckm 89 90200290300,rr 。 898989 81.5*282.5*272.6255.4600,0llckmkm bb 故合并8，9两点，则。 689448989 8,9 ,290,255.4,1,iiirlkm bbii （10），故线路0-1-2-5-0与线路0-8-9-0不能合并。 45 380290670500rr 至此，合并结束。 最后得到的最优结果如表6所示，优化线路图如图4所示。 表4-5节约法优化结果 路线运距运货量车型司机 0-3-4-6-7-0454.8km470 11吨货车 2 0-1-2-5-0

39、230.1km380 11吨货车 1 0-8-9-0255.4km290 7吨货车 1 由上表可知，公司每周需 11 吨货车 2 车次和 7 吨货车 1 车次配送，司机 4 人次，所需 工资 400 元，运输总里程为 940.3 千米，消耗的柴油 239.56 升，所需燃油费 1686.60 元， 一共花费 2086.60 元。 0 1 2 3 4 5 6 8 7 9 图4-1 节约算法求解线路结果 4.2.3 基于扫描算法的企业配送路线优化 对百源木业周边的 9 个县市采用扫描算法进行配送线路的优化。 首先建立极坐标系：以百源木业有限公司所在地婺源县作为原点，并以点1景德镇与原 点的连线为零

40、角度建立极坐标系，各点的货运量及极坐标的角坐标值如表7所示。坐标系如 图5所示。 表4-6 运量和极坐标的角坐标值 客户1 景德 镇 2 乐平 市 3 鹰潭 市 4 贵溪 市 5 德兴 市 6 上饶 市 7 常山 县 8 开化 县 9 黄山 市 货运量（张/ 周） 18012012060802207090200 角坐标 034465261103152169238 0 1 2 3 4 5 6 8 7 9 图4-2 扫描算法的扫描过程 然后分组：从角度为零向逆时针方向进行扫描，如图所示。第一个被分组的是客户 1， =180；继续转动，下个被分组的是客户 2， =180+120=300；继续转动，下

41、个被分组 1 r 1 r 的是客户 3，300+120=420；继续转动，下个被分组的是客户 4， =420+60=480；继续 1 r 转动，下个被分组的是客户 6， =480+80=560500，由于超过了限制，按分组规则，需 1 r 要一个新的组，这样在第一组里只有客户 1，2，3，4， =480。 1 r 进行第二组扫描，最先扫描到的是客户 5， =80；继续转动，下个被分组的是客户 1 r 6， =80+220=300；继续转动，下个被分组的是客户 7， =300+70=370；继续转动， 1 r 1 r 下个被分组的是客户 8， =370+90=460；继续转动，下个被分组的是客户

42、 1 r 9， =460+200=660500，超过限制，所以需要一个新的组，这样在第二组中只有客户 1 r 5，6，7，8， =460。 1 r 在第三组中只剩一个客户 9，故顾客 9 单独在一组， =200。 1 r 这时，可以得到如图 6 所示的分组结果。 0 1 2 3 4 5 6 8 7 9 图4-3 扫描算法求解结果 最后对各子回路内的线路优化：对上面的3个组，都已经是一个单回路运输问题，对每 个组进行线路优化。供应点0是任何一个组的tsp问题的起点和终点，用最近插入法分别对 三个客户组进行求解。 对第一组进行求解。比较表4-2 中从0出发的所有路径大小， 001 min|,147

43、5.9 i cinickm 这样，就有顾客点0，1构成一个子回路，。 1 0,1,0t 然后考虑剩下顾客点2，3，4到0和1中某一点的最小距离： 0112 min,|,14,i148.6 ii ccinickm 且 由于对称性，无论将2插入到0和1之间往返路径中，结果都是一样的，这样，构成了一 个新的子回路。 1 0,1,2,0t 接下来考虑剩下的顾客点3，4到0，1，2中某一点的最小距离 01223 min,|,14,i1,297.3 iii cccinickm 且 顾客点3有3个位置可以插入，现在分析将点3加入到哪里合适。 （1） 插入到（0，1）之间，。 033101 186.7 157

44、.1 75.9267.9ccckm （2） 插入到（1，2）之间，。 133212 157.1 97.348.6205.8ccckm （3） 插入到（2，0）之间，。 233020 97.3 186.789.2194.8ccckm 比较可知，插入到（2，0）之间增量最小，所以将顾客点3加入到（2，0）间，结果为 1 0,1,2,3,0t 重复上面的步骤，将顾客点4加入到子回路中，就可得到一个用最近插入法求得的可行 解，总行驶距离为：。 1 0,1,2,3,4,0t 1 408.5lkm 对第二组进行求解，可得，总行驶距离为：。对第三组 2 0,5,6,7,8,0t 2 360.6lkm 进行求

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

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

47、将 1 插入到 0 和 5 之间往返路径中，结果都是一 1 0,5,0t 样的，这样，构成了一个新的子回路，。 1 0,1,5,0t 1 260r 1 219.0lkm 再次寻找剩余顾客点到 0，1， 5 中某一点的最小距离：可知最小距离为 12 48.6ckm 此时, ，因为，所以在子回路插入点 2。 2 120r 12 260 120380500rr 1 0,1,5,0t 将点 2 分别插入（0，1） ， （1，5） ， （5，0）中，比较得：插入到（1，5）中增量最小， 。 122515 48.648.686.111.1ccckm 此时构成了一个新的子回路，。 1 0,1,2,5,0t

48、1 380r 1 230.1lkm 再次对剩余的顾客点按照上诉方法进行优化，可构成另子回路和子回路 1 0,3,4,6,0t 1 0,7,8,9,0t 利用改进的最近插入法得到优化结果如表 9 所示，优化线路结果如图 8 所示。 表4-8 改进的最近插入法优化结果 路线运距运货量车型司机 0-1-2-5-0230.1km470 11吨货车 1 0-3-4-6-0438.4km180 11吨货车 2 0-7-8-9-0295.1km490 11吨货车 1 由上表可知，公司每周需 11 吨货车 3 车次和，司机 4 人次，所需工资 400 元，运输总 里程为 963.6 千米，消耗的柴油 260.

49、17 升，所需燃油费 1839.42 元，一共花费 2239.42 元。 0 1 2 3 4 5 6 8 7 9 图4-5 改进的最近插入法求解线路结果 4.3 三种优化方案比较分析 由上文可知，通过节约算法，扫描算法和改进后的最近插入法分别对配送线路进行优化， 可得到三种不同的优化方案，因此我们需要通过一系列指标来评价方案的优劣性。本文将以 所需车辆数，行驶总里程，总油耗，人力资源和总费用这些指标，对三种优化后的方案进行 评价分析，如表 10 所示。 表 4-9 优化结果对比表 优化后 状态优化前 节约算法扫描算法 改进后的最 近插入法 7t5110 各车型车 次(次) 11t0223 总运

50、输里程(km) 1270.2940.3934.1963.6 节约里程数 （km） 329.9336.1306.6 油耗（l） 266.75239.56242.31260.17 节约油耗（l） 27.1924.446.58 司机（次） 6454 节约人力（次） 212 总费用（元） 2485.872086.602313.112239.42 节约费用（元） 399.27172.76246.45 从上表的对比中可知，从车次需求数的角度来看，优化后的三种方案需求车次数相同， 但优化后的方案与优化前方案相比较节约了 2/5 的车次需求。优化后的方案需要使用更少的 车次，减少了百源木业用车紧张进而租车情况

51、的出现，使百源木业车辆安排使用上具有更大 弹性。因此，在用车角度上考虑，优化后的方案均比优化前的方案合理，优化后的三种方案 等价。 从总运输里程角度考虑，优化后的三种方案的总运输里程分别为 940.3 千米，934.1 千 米，963.6 千米，与原方案的 1303.4 千米相比较，均减少了车辆行驶的里程数。优化后的 方案能减少了公司车辆的损耗和资源的浪费，给百源木业带去更多的效益。因此，从运输里 程的角度考虑，优化后的方案扫描算法最优，节约算法次之，改进后的最近插入法再次之。 从燃油消耗的角度考虑，优化后的三种方案的消耗分别为 239.56 升，242.31 升， 260.17 升，与原方案

52、的 266.75 升相比较，三种优化方案均降低了油耗量，改进后的插入法 优化后的方案消耗更多的油耗。配送线路优化后，不仅能减少百源木业公司燃油费用的支出， 还能降低社会资源的浪费。因此，从燃油消耗的角度上考虑，节约算法最优，扫描算法次之。 从公司人力资源消耗角度来考虑，优化后的方案所需司机依次为 4，5，4 人次，减少 人力的消耗为 2，1，2 人次。三种优化后的方案均能使公司在人员安排上将更具有弹性， 还能降低公司费用的支出。因此，从百源木业人力资源消耗的角度考虑，节约算法和改进后 的最近插入法最优，扫描算法次之。 从支出的总费用角度来考虑，优化后的方案的费用支出依次 2086.60 元，2

53、313.11 元， 2239.42 元，与原方案的为 2485.87 元相比较，改进后的插入法优化后的方案花费更多的 费用支出。因此，从支出总费用的角度考虑，节约算法最优，改进后的最近插入法次之。 结合车次需求数，总运输里程，燃油消耗，人力资源消耗，支出的总费用五个角度一齐 分析，节约算法最优。但是，本文的配送距离略有超出配送最佳范围，模型存在着一定的缺 陷。在计算过程中也将一些因素理想化了，与实际情况不完全相符。例如，并未考虑具体的 道路信息，运输规章等。因此，百源木业应该根据实际情况合理选择配送方案。 结论 百源木业为了推广品牌，扩大市场，对小客服实施了进行送货上门服务。但随之而来的 就是

54、配送成本的问题，公司为保持正常的盈利，降低配送成本则势在必行，这就意味着公司 要对原配送路线进行优化。 本文针对百源木业有限公司 9 个县市配送状况进行了线路规划，应用了节约算法、扫描 算法及改进的最近插入法三种方法进行了计算分析，经过比较 3 种结果，选择出了一个最优 方案，经过效益分析，证明经过优化后的配送里程数缩短了 329.9km，节约燃油 27.17 升， 从而降低了每天的运输费用大概 375 元，除此以外，每周减少发车次数 2 次，司机 2 人次， 辆闲置下来的货车和司机还可以应对一些紧急情况，提高了公司的服务质量。 求解车辆路径问题的方法非常丰富，本文采用了 3 种方法虽然都能够

55、得到可行的配送运 输路径方案，但是只能是可行解而不是精确解。节约算法，扫描算法和改进后的最近插入法 都是解决 vrp 模型的算法。这类算法虽然能够比较快的解决有关问题，但其优劣往往取决 于算法设计者的实际经验以及处理样本空间的大小。在实际求解过程中，应根据各类算法的 使用范围，并针对配送优化问题的具体情况，寻找最适合的求解方法，找到最优配送路路线。 对于大部分企业来说，配送成本最低和满足客户对时间的高要求是配送中急需解决的问 题，这都需要研究物流配送路径优化模型和算法来解决。从配送中心到客户位置的物流在配 送领域是一个负载的调度问题。如果能通过比较科学的物流配送路径优化模型和算法，来实 现企业

56、的人工调度和车辆安排，使得物流中心本身运作效率更高，成本控制得当，企业的效 益也会不断提升。 在物流快速发展的大背景下，百源木业有限公司要充分运用物流理论，与实践相结合， 同时考虑到时代赋予产品特殊的意义，积极拓展自己的经营方式，与第三方物流公司保持积 极地合作，给企业注入新的血液和活力。 致谢语 值此拙作完成之际，我首先要衷心地感谢 xxx 指导老师，他为本人从事这一方向的研 究给予了充分的鼓励和悉心的指导。师从 xxx 老师，我不仅在学术研究和科研方面得到了 谆谆教诲，导师严谨细致的治学态度、宽厚正直的待人之道更是我学之不尽的人生财富。在 此，谨向周老师表示最真诚的感谢和崇高的敬意! 最后

57、，还要感谢 xx 大学所有关心和教育过学生的老师们，感谢 xx 大学图书馆对于论文 的帮助，以及百源木业有限公司提供宝贵的资料。同时，感谢评阅本文的各位专家，敬请提 出宝贵的意见，并予以指正。 衷心地感谢在我完成论文的过程中给与帮助和支持的所有老师、同学和朋友！ 参考文献 1 高晓亮,伊俊敏,甘卫华.仓储与配送管理m.清华大学出版社,2006. 2 孔少彻,梁彤铮.商品物流配送优化策略探讨j.市场论坛,2009(7):94-95. 3 elliot rabinovich, manus rungtusanatham and timothy m. laseter. physical distrib

58、ution service performance and internet retailer margins: the drop-shipping contextj.journal of operations management,2008(6):767-780. 4 蔡临宁.物流系统规划建模实例分析m.北京:机械工业出版社,2003.孔少彻,梁彤铮.商品物流配送优 化策略探讨j.市场论坛,2009(7):94-95. 5 孙焰.现代物流管理技术m.上海:同济大学出版社,2004. 6 gianpaolo ghiani. gilbert laporte. roberto musmanno.

59、introduction to logistics systems planning and control m. t&t productions ltd, london,2004(1):3-15. 7 王鑫.物流配送中车辆优化调度问题的研究与实践d.沈阳:沈阳航空工业学院计算机应用技术,2006. 8 徐剑,牟燕妮等.物流配送车辆调度优化方法比较研究j.物流科技,2006(2):46-49. 9 许星,物流配送路径优化问题的研究d.浙江:浙江大学计算机科学与技术学院计算机应用技术,2006. 10 韩世莲,物流配送线路多目标优化方法研究d.江苏:东南大学载运工具运用工程,2006. 11 h

60、enning rekersbrink, thomas makuschewitz, bernd scholz-reiter. a distributed routing concept for vehicle routing problemsj. logistics research,2009,(1):45-52. 12 李金苹.现代物流配送系统的运输优化调度方案j.物流技术,2002,(5):11-13. 気持今 flying get ！dou 都斗豆逗陡抖痘兜读 蚪窦篼蔸乧侸兠凟剅吺唗投斣枓梪橷毭氀浢渎渎瞗窬窦脰艔豆读逾郖酘酡钭鋀钭閗闘阧餖饾 斗鬦鬪鬬鬭 du 读度毒渡堵独肚镀赌睹杜督都犊妒