闽港纸箱包装有限公司配送路线优化研究

1、1闽港纸箱包装有限公司配送路线优化研究闽港纸箱包装有限公司配送路线优化研究 摘要 物流配送是物流的核心环节之一，而合理的选址和配送车辆的路线优化对于提高配送效率和质量具有重要影响。正确合理地安排车辆的配送线路，可以有效地增加车辆的利用率，实现合理线路运输，从而降低运输成本，节约运输时间，提高客户服务水平，提高经济效益，达到科学化的物流管理。这也是企业提高自身竞争力的有效途径之一。本文通过精确重心法对连云港市闽港纸箱有限公司的当前地址进行合理性的判断，并在此基础上通过对公司配送现状分析，利用“C-W”节约算法和扫描算法以及两种改进的最近插入法对该公司的配送路线进行优化。四种方法得到的结果均优于原

2、配送路线，都可达到降低运输成本的目的，而利用节约算法得到的结果更优。该选题对与闽港纸箱包装有限公司相类似企业的物流配送路线规划问题也具有一定的参考价值。 关键词 车辆路径问题 选址合理性判断 节约算法 扫描算法 改进的最近插入法2S Study of Delivery Route Optimization about The LianyungangCity Carton Company Abstract Physical distribution is a core part of logistics, while reasonable location and route optimizat

3、ion have a great effect on improving the efficiency and quality of delivery. Proper and reasonable arrangement for the delivery vehicle lines, can effectively increase the utilization of vehicles and achieve reasonable line transport. As a result, it will reduce transport costs, save transportation

4、time, improve customer service levels, enhance economic efficiency and achieve scientific logistics management. This is also one of the effective way to improve competitiveness of enterprises. In this paper, the rationality of the current location of the Lianyungang City Carton company is judged by

5、centre-of-gravity method. On this basis, the companys delivery status is analyzed, and the companys distribution route is improved by use of CW saving algorithm, sweep algorithm and two nearest insertion. the results obtained from four methods are better than the original distribution routes and can

6、 achieve the purpose of reducing transport costs, while the result obtained from saving algorithm best. The topic has some reference value for those companies that have similar business problems in logistics and route planning. Key Words vehicle routing problem saving algorithm sweep algorithm impro

7、ved nearest insertion3目录引言 .4第一章 物流配送概述 .51.1 物流配送的概念.51.2 物流配送的功能 .51.3 配送路线优化的意义及原则 .6第二章 闽港纸箱包装有限公司现状 .72.1 公司简介 .72.2 公司配送现状 .7第三章 模型及方法描述 .93.1 精确重心法.93.1.1 精确重心法基本原理.93.1.2 精确重心法主要步骤 .103.2 多回路运输VRP 模型.113.3 节约算法 .113.3.1 节约算法的基本原理.113.3.2 节约里程算法主要步骤.123.4 扫描算法 .133.4.1 扫描算法的基本原理 .133.4.2 扫描算法

8、的主要步骤 .133.5 改进后的最近插入法.133.5.1 最近插入法 .133.5.2 改进的最近插入法（一） .143.5.3 改进的最近插入法（二） .14第四章 基于精确重心法判断闽港纸箱包装有限公司选址合理性 .16第五章 闽港纸箱包装有限公司配送路线优化研究 .195.1 建立 VRP 模型 .195.2 优化闽港纸箱有限公司的配送线路.195.2.1 基于节约算法的企业配送路线优化 .205.2.2 基于扫描算法的企业配送路线优化 .235.2.3 基于改进的最近插入法（一）的企业配送路线优化 .265.2.4 基于改进的最近插入法（二）的企业配送路线优化 .285.2.5 四

9、种优化方案比较分析 .31结论.32致谢语 .33参考文献 .34附录.354引言引言随着物流业向全球化、信息化及一体化发展,配送在整个物流系统中的作用变得越来越重要。配送是物资供应的一种重要形式， 是连接生产与消费之间的一种中介服务。配送一般定义为:将货物从物流结点送到收货人的过程。配送是在集货、配货的基础上，完全按客户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送”的有机结合形式。对于配送问题的研究，一是“配”方面的研究，如配送中心选址问题，二是“送”方面的研究，如旅行商问题(TSP)、车辆路线优化问题(VRP)。合理的选址是公司建立完善的物流配送体系的先期条

10、件，同时合理的配送路径对于提高配送效率和质量，降低成本具有重要意义。在本文中主要对“送”进行研究。物流配送车辆的路线优化，是物流配送优化中的一个关键环节。因此设计合理、有效的车辆运输路线方案，尽量减少配送里程数和配送时间不仅可以减少资源浪费，提高企业的经济效益和竞争力，而且可以更好地为客户服务，加快对客户需求的响应速度,提高服务质量,增强客户对物流环节的满意度,维护企业良好的形象。优化运输物流,降低运输成本,是企业提高其自身竞争力的有效途径之一。大多数的物流配送运输调度问题可以归结为配送车辆的分配、行车路线的组织问题(V 即问题)，即根据不同要求-目标函数(例如运距最短、配送时间最短、运输费用

11、最少等)，将配送运输过程归结为表述问题的数学模型。然后求得合理可行的优化方案，在生产中付诸实施。VRP 问题或者称作车辆路径问题是组合优化领域中著名的 NP 难题。近二十年来，无论在国内还是国外，VRP 问题都是一个非常活跃的研究领域。本文将以连云港市闽港纸箱有限公司的当前选址问题和配送线路的优化问题作为研究对象，通过精确重心法对目前公司地址进行合理性判断，并且对各县市需求量及运距进行分析计算，建立 VRP 数学模型，运用节约算法和扫描算法以及两种改进的最近插入法对建立的模型进行求解。最后对四种方法求得的结论进行比较分析，从而为该公司提供合理的配送方案，以期降低物流运输成本，提高该公司物流运作

12、效率和整5体竞争力，亦期望能对类似企业的发展提供借鉴作用。第一章第一章 物流配送概述物流配送概述1.1 物流配送的概念物流配送的概念2001 年 4 月，中国国家标准物流术语将配送定义为：“在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。11”配送是物流系统的核心环节之一，配送在英语中的原意是“delivery” 。是交货送货的意思。在日本工业标准 JIS 中，将配送定义为“将货物从物流结点送交收货人” ，强调了送货的含义。可以说，物流配送是连接生产与消费之间的一种中介服务，是物资供应的一种重要形式。配送是“配”和“送”有机结合的

13、形式，它利用有效的分拣、配货等理货工作，使送货达到一定的规模，以利用规模优势取得较低的送货成本。221.2 物流配送的功能物流配送的功能发展配送，对于物流系统的完善、流通企业和生产企业的发展，以及整个经济社会效益的提高，无不具有重要的作用。（1）配送可以降低整个社会物资的库存水平。发展配送，实行集中库存，整个社会物资的库存总量必然低于各企业分散的库存总量。同时，配送有利于灵活高度，有利于发挥物资的作用。此外，集中库存可以发挥规模经济优势，降低库存成本。（2）配送有利于提高物流效率，降低物流费用。采用配送方式，批量进货，集中发货，以及将多个小批量集中一起大批量发货，都能有效的节省运力，实现经济运

14、输，降低成本，提高物流效益。6（3）对于生产企业来讲，配送可以实现低库存。实行高水平的定时配送方式之后，生产企业可以依靠配送中心准时配送或即时配送而不需保持自己的库存，这就可实现 生产企业的“零库存” ，节约储备资金，降低生产成本。（4）配送可以成为流通社会化、物资产业化的战略选择。实行社会集中库存、集中配送，能从根本上打破条块分割的分散流通体制，实现流通社会化、物流产业化。111.3 配送路线优化的意义及原则配送路线优化的意义及原则通常认为，配送是近距离，小批量，品种比较复杂，按用户需要搭配品种与数量的服务体系。从配送中心把货物送到所需的各个用户，有很多种不同的路线选择方案。合理的选择配送路

15、线，对企业和社会都具有很重要的意义。 对企业来说，(1)优化配送路线，可以提高配送效率，对配送车辆做到物尽其用，尽可能的降低配送成本。(2)可以准时、快速地把货物送到客户的手中，能极大地提高客户满意度。(3)有利于企业提高效益。 对社会来说，它可以节省运输车辆，缓解交通紧张状况，减少噪声、尾气排放等运输污染，为保护生态平衡、创造美好家园作出贡献33。 进行配送路线优化时，必须有明确的目标，遵循基本的原则。配送路线方案目标的选择可以从以下几个方面来考虑: (1)配送效益最高或配送成本最低。效益是企业追求的主要目标，可以简化为用利润来表示，或以利润最大化作为目标;成本对企业效益有直接的影响，选择成

16、本最低化作为目标值与前者有着直接的联系。当有关数据容易得到和容易计算时，就可以用利润最大化或成本最低作为目标值。(2)配送里程最短。如果配送成本与配送里程相关性较强，而和其他因素相关性较弱时，配送里程最短的实质就是配送成本最低。则可考虑用配送里程最短作为目标值，这样就可以大大简化线路选择和车辆调度方法。当配送成本不能通过里程来反映时，如道路收费、道路交通条件严重的影响成本，单以最短路程作为目标就不适合44。(3)配送服务水准最优。如准时配送要求成为第一位时，或需要牺牲成本来确保服务水准时，则应该在成本不失控的情况下，以服务水准为首选目标。这种成本的损失可能从其它方面弥补回来，如优质服务可以采取

17、较高的价格策略。7(4)配送劳动的消耗最小。即以物化劳动和活劳动消耗最小为目标，在许多情况下，如劳动力紧张、燃料紧张、车辆及设备较为紧张的情况下，限制了配送作业的选择范围，就可以考虑以配送所需的劳动力、车辆或其它有关资源作为目标值55。第二章第二章 闽港纸箱包装有限公司现状闽港纸箱包装有限公司现状2.1 公司简介公司简介连云港市闽港纸箱包装有限公司初建于 1996 年，占地面积 20 多亩，座落于江苏连云港市海州西门工业区，毗邻主干道路，公司现有员工 50 余人，注册资金 150 万元，年产值 2000 万元。公司以生产各种纸箱及各种规格纸板为主，是集设计、制作、印刷一体化的综合型包装生产企业

18、。公司具有国家商检局颁发的进出口包装许可证 。为适应企业发展的需要，在包装业市场上赢得竞争，公司引进了具有国内先进水平的包装检测设备，以满足不同客户的需求。 2.2 公司配送现状公司配送现状公司的客户主要位于其所在地的周边县市，如图 1 所示，共有 10 个县市，如赣榆县，新沂市，灌云县等。其中，大客户的月需求量一般约为 3 万平方米，小客户一般约为 5 千平方米，一般的客户约为 1 万平方米。公司与其客户建立了长期合作关系（一般为一年以上） ，通过签订合同，在每月约定时间交货。公司现拥有两部 5 吨的货车，一部 2 吨的货车，其余由物流公司提供配送服务。公司采用的是“点到点”直接配送模式。公

19、司原有的配送模式如图 2 所示，共需10 辆车，该模式的弊端在于：配送路线的选择不合理,没有得到优化；另外，剩余货运量进行直送时不能充分利用车辆配载容积，从而造成资源浪费，影响公司盈利。8（图片来源：http:/ 图 2-1 闽港纸箱包装有限公司配送网络图3204657119810 图 2-2 公司原有配送路线各地区的月需求量如表 1 所示。 表 2-1 各地区月货运量 （平方米/月）客户1 赣榆县2 新沂市3 东海县4 灌云县5 灌南县6 响水县7 滨海县8 郯城县9 临沭县10 沭阳县9货运量30800145001635082502710018600520017000755012000注：

20、数据来源于闽港纸箱包装有限公司内部资料第三章第三章 模型及方法描述模型及方法描述3.1 精确重心法精确重心法为了判断公司的选址是否合理，现将理想选址点的待选区域假设为一个平面，可能的选址位置的数量是无限的，即选址模型是连续的。而连续选址有两种模型，分别是交叉中值模型和精确重心法。由于交叉中值模型适用于小范围的城市内的选址问题，精确重心法适用于平面上大范围的选址，故选用精确重心法判断该公司的选址合理性。3.1.1 精确重心法基本原理精确重心法在评价的过程中使用的是欧几米德距离，即直线距离。它的目标是寻求加权的直线距离总和最小7。在使用了欧几米德距离后，目标函数如式（1）所示。 1n222ii=1

21、min Z = wisisxxyy（1）这是一个双变量系统，分别对和进行求偏微分，并且令其为零，这样就可以得到sxsy两个微分等式。应用这两个等式分别对和进行求解，即可以求出一对隐含有最优sxsy解的等式，如式（2） ， （3）所示。 sx11niiiisniiisw xdwd10（2） sy11niiiisniiisw ydwd（3） 这里， 。 isd1222isisxxyy（4） 该方程组由于不能求解，因此可通过迭代的方法求解，这需要提供一组初始值和。sxsy然后利用，再用它去求出，迭代公式如式（5） 、 （6）(1)s(j-1)is(j-1) y ds jx和求出 sj ysjx 和所

22、示。 1(1)1(1)niiiis jsjniiis jw xdxwd（5） 1(1)1(1)niiiis jsjniiis jw ydywd（6）若该迭代过程具有收敛性，那么经过无限次的迭代后，可以得到一个最优解。* yssx 和但是在实际中，可迭代的次数是有限的，所以在迭代过程中需确定一个中止准则：（1）根据经验和以前的实验结果设置迭代次数 N；（2）将每一次得到的迭代结果与前一次的相比，当结果变化小于某一阈值、时，迭代结束。 （3）求得最优解，limsitxlimsity使 Z 最小。3.1.2 精确重心法主要步骤 输入：n客户数，各客户点的坐标,各客户点对应的权重；( ,)iix yi

23、w输出：设施坐标 Z总运费6。(,)ssxy11具体步骤如下：（1）选取初始迭代点 A（） ，如，计算 A 点到各00,ssxy11nsoiixxn011nsiiyyn客户点的直线距离：=。0s0 Zisd和s0Z01niisiwd（2）令，计算和。1(1)1(1)niiiis jsjniiis jw xdxwd1(1)1(1)niiiis jsjniiis jw ydywdisjdsjZ（3）若，运费已无法减小，输出最优解：，(1)s jsjZZ(1)ss jxx(1)ss jyy。否则，转（2） 。(1)s jZZ3.2 多回路运输多回路运输VRP 模型模型多回路运输问题是现实中很普遍的一

24、种调配问题，特别对于有大量服务对象的实体。解决此类调配问题时，核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型。该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下，达到一定的优化目标。它涉及了多辆交通工具的服务对象的选择和路径（服务顺序）确定两方面问题7。一个典型的 VRP 模型可以如下表述：（1）基本条件 现有 m 辆相同的车辆停在一个共同的源点，它需给 n 个客户提0v供货物，顾客为。12n,vvv、 ，（2）模型目标 确定所需的车辆数 N，并指派

25、这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用最小。（3）限制条件：N 不大于 m；每一个订单都要完成；每辆车完成任务后都要回到源点；车辆的容量限制不能超过；特殊问题还需考虑时窗限制；运输规章限制。0v123.3 节约算法节约算法节约算法是用来解决运输车辆数目不确定的 VRP 问题，它是目前用来解决 VRP模型最有名的启发式算法。故首先选用该法对公司的配送路线进行优化。3.3.1 节约算法的基本原理节约算法的核心思想是将运输问题中存在的两个回路（0， ，i，0）和（0，j， ，0）合并成一个回路（0， ，i，j，0） 。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如

26、果变化后总运输距离下降，则称节约了运输距离7。相应的变化值，叫做节约距离，如式（7）所示。ijC， （7）ijioojjiCccc调整过程如图 3 所示。j i02调整前0ij调整后 图 3-1 节约算法的图像描述3.3.2 节约里程算法主要步骤已知条件:需求点集=1,2, n,各点需求量,各点间最短距离;车辆集合RNiRijc=1,2,m,各车辆最大载重量6。TNiW第一步,将按从大到小排序,使得;。TNiW1W2WnW第二步,对于所有的客户对(i, j),采用式（7）计算节约里程的值,其中, ijC13i=1,2,n; j=1,2,n,将大于零的从大到小排列形成队列。ijC第三步,求初始可

27、行解。确定各车辆配送点集令=j, j=1,2,n (先采12,mI IIjI取单点配送)。第四步,合并配送路径。直到节约里程的队列空为止,重复下列步骤:按照节约里程ijC队列从大到小的顺序,分析客户 i 和 j 之间合并的可能性(是否满足装载限制条件、ijC不在同一路径内以及合并次数不超过 2),将 i, j 连接起来,即可令。;iijjIIII 如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对。3.4 扫描算法扫描算法扫描算法也是用于求解车辆数目不限制的 VRP 问题，与节约算法不同的是，它属于亚启发式算法，而节约算法属于构造算法。故选用该法对公司的配送路线进行优化。3.

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

29、。14（3）重复（2）中的过程，直到所有客户都被分类为止。（4）路径优化 对各个组内的单回路进行路径优化9。3.5 改进后的最近插入法改进后的最近插入法3.5.1 最近插入法 最近插入法是 Rosenkrantz 和 Stearns 等人在 1977 年提出的一种用于解决 TSP(旅行商)问题的算法。最近插入法由四步完成：（1）找到最小的节点，形成一个子回路（subtour） ，。0iciv00,iTv v v（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。iv(3)在子回路中找到一条弧（a，b）,使得+-最小，然后将节点插入到节点aicibcabciv，之间，用两条新的弧(a，i

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

31、（3）在子回路中找到一条弧（a，b）,使得+-最小，然后将节点插入到节aicibcabciv点，之间，用两条新的弧(a，i)， （b，i）代替原来的弧（a，b） ，并将节点加avbviv入到子回路中。若此时该回路的总路程为未超过车辆的行程限制，则继续步骤（4） 。否则转步骤（1） ，寻找新的一条回路。15（4）重复步骤（2）和（3） ，直到每一个节点都被归入某一个子回路中。3.5.3 改进的最近插入法（二）（1）找到最小的节点，形成一个子回路（subtour） ，。0iciv00,iTv v v（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。若此时回路的iv总货运量和总路程均未超过

32、限制，则转步骤（3） 。否则，转步骤（4）（3）在子回路中找到一条弧（a，b）,使得+-最小，然后将节点插入到节aicibcabciv点，之间，用两条新的弧(a，i)， （b，i）代替原来的弧（a，b） ，并将节点加avbviv入到子回路中。（4）在余下的节点中，寻找一个离子回路中某一节点最近的节点（除去之前不满iv足插入条件的节点） ，若此时回路的总货运量和总路程均未超过限制，则转步骤（3） 。 否则。一直重复步骤（4） ，直到所有的节点都被尝试。这样得到了子回路 1。（5）找到最小的节点（排除已在子回路 1 中的节点） ，形成一个新的子回路0iciv（subtour） ，。然后重复步骤（2

33、） ， （3） （4） 。00,iTv v v 如是一直循环重复步骤，直到每一个节点都被归入某一个子回路中。16第四章第四章 基于精确重心法判断闽港纸箱包装有限公司选址合理性基于精确重心法判断闽港纸箱包装有限公司选址合理性首先建立坐标系：现以宿迁市为坐标原点，建立坐标系，如图 4 所示。4.8, 5.80.5, 2.62.8, 3.75.5, 2.2 6, 0.87.2, 1.58.5, 0.10.5, 4.62.6, 6.62.9, 1.1012345670123456789Y 轴8 2 9 3 3 1 4 10 6 5 75.3, 4.20 图 4-1 需求点坐标图（图中 0 点为连云港（

34、5.3，4.2） ，每单位 18km）然后，选取初始迭代点并进行第一次迭代：X 轴17 ，计算并以各县市的货运量为权重，计算过0011114.1,2.9nnsisiiixxyynn(1)is jd程如表 2 所示。 表 4-1 精确重心法计算一需求点（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6. 6.6，2. 9，1. 1权重iw30800145001635082502710018600520017000755012000距离0isd2.9833.6121.5261

35、.5652.8323.4015.2153.9813.992 2.1630iiswd10325.184014.4010714.295271.579569.215468.98997.124270.281891.285547.85代入相应数据求得，根据公式（5） ， （6）代入数据得10001472930.15SiisiZwd。114.1,3.0ssxy接着，计算1SZ：计算过程如表 3 所示。表 4-2 精确重心法计算二需求点（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6

36、. 6.6，2. 9，1. 1权重iw30800145001635082502710018600520017000755012000距离0isd2.8863.6221.4761.6122.9073.4445.273.943.92.24718代入相应数据求得， 。所以进行第二次迭代。101101383592.67SiissiZwdZ然后，进行第二次迭代表 4-3 精确重心法计算三需求点（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6. 6.6，2. 9，1. 1权重iw3

37、0800145001635082502710018600520017000755012000距离0isd2.8863.6221.4761.6122.9073.4445.273.943.92.2470iiswd10672.214003.3111077.245117.879322.335400.70986.724314.721935.905340.45根据公式（5） ， （6）代入数据得， 。224.2,3.1ssxy接着，计算2SZ：计算过程如表 4 所示。 表 4-4 精确重心法计算四需求点（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.

38、2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6. 6.6，2. 9，1. 1权重iw30800145001635082502710018600520017000755012000距离0isd2.7663.7341.5231.5812.9213.45.2433.9923.8482.38519代入相应数据求得， 。所以迭代结束。102211472479.2SiissiZwdZ最后，输出结果：=5.0，=2.4 ，即理想位置点坐标为（4.1，3.0） ，。1ssxx1ssyy383592.67Z 而公司的实际位置坐标为（5.3，4.2） ，这表明当前公司选址不是合理的，这将影

39、响到公司的配送效率。但是，考虑到重迁需要投入大量的人力物力。而公司目前的状况还不具备相应的能力。这意味着公司配送路线的优化变得尤为迫切。第五章第五章 闽港纸箱包装有限公司配送路线优化研究闽港纸箱包装有限公司配送路线优化研究5.1 建立建立 VRP 模型模型多回路运输问题时现实生活中十分普遍的一种调配问题。解决此类调配问题时，核心问题是如何对车辆进行调度1。因此 VRP 模型也应运而生，成了解决多回路问题的一个相当成功的模型。据此对闽港纸箱包装公司的配送系统建立 VRP 模型。基本条件：闽港纸箱有限公司需给 10 个客户送货，客户依次为 1，2，,10，现有 1 辆 2 吨（长 4.5m,宽 2

40、m,高 3.8m）的货车，2 辆 5 吨(长 7.2m,宽 2.2m,高 4m)的货车,其余由物流公司提供货车。故车辆数没有限制。模型目标：确定所需要的车辆的数目 N、车辆类型以及各车行走的路径，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输总费用最小。限制条件：（1）基于人性化的考虑，司机每天工作不超过 6 小时（配送车辆的车速一般控制在50 公里/小时。 ）由于在本模型中考虑时间窗的限制会加大解题的难度，因此对配送时间的限制转换为在规定时间内对行驶里程的限制，即各车最大运输距离为 300 公里。（2） 每辆车完成任务之后都要回到源点 0 处。（3） 车辆的容量限制不能

41、超过。由于用一辆 5 吨货车的运量约为 2 吨货车的 2 倍，20并且在运输路径、物流成本方面也会有很大的节约，因此先选用 5 吨的货车限制容量。5 吨的货车最多可装 6500 平方米的纸箱，2 吨的最多可装 3500 平方米。5.2 优化闽港纸箱有限公司的配送线路优化闽港纸箱有限公司的配送线路已知闽港公司为 0 点，分别向 10 个客户配送纸箱，其拥有两辆 5 吨的车和一辆 2吨的车， 5 吨卡车最大容量为 6500 平方米纸箱，2 吨卡车最大载量为 3500 箱平方米纸箱，设各点间的距离为 C，C= 1,10 ，节约距离为。每辆车的载ijc, i jijc重量为 ，各点需求量为（ =1，1

42、0） ，每辆车的行驶里程为（ =1，10） ，iriRiiLi且公里，连云港为 0 点，客户点 1，2，10300iL 各县市的纸箱货运量和配送距离如表 4 所示。表 5-1 运输任务表客户1 赣榆县2 新沂市3 东海县4 灌云县5 灌南县6 响水县7 滨海县8 郯城县9 临沭县10 沭阳县货运量（/2m月）30800145001635082502710018600520017000755012000配送距离（km）29.485.947.23155.751.782.881.565.268.9车辆调度采用以下方案：按需求量的多少选配车辆。如，赣榆县需求量为 30800平方米，先选用最大车型进行直

43、送（26000 平方米采用 4 辆 5 吨货车运送） ，剩余货运量（4800 平方米）利用节约原理进行配送，其他县市的货运量均按此方法进行整理，整理后如表 5 所示。 表 5-2 整理后的运输任务表客户1 赣榆县2 新沂市3 东海县4 灌云县5 灌南县6 响水县7 滨海县8 郯城县9 临沭县10 沭阳县剩余货运量（/月）2m480015003350175011005600170040001050550021配送距离（km）29.485.947.23155.751.782.881.565.2 基于节约算法的企业配送路线优化 在表 3 中，对有剩余货运量的 10 个县市采用节约法

44、进行配送路线的优化。首先，确定各城市间的最短距离。因为距离对称，所以=，县市间最短距离表ijcjic6 所示。表 5-3 各县市间最短距离表 （单位：千米）县市0 连云港1 赣榆县2 新沂市3 东海县4 灌云县5 灌南县6 响水县7 滨海县8 郯城县9 临沭县10 沭阳县0 连云港029.485.947.23155.751.782.881.565.268.91 赣榆087486083.978.5108.977.65087.62 新沂04181.596.2113.1140.22967.443.33 东海046.468.381112.541.146.843.64 灌云024.130.861.289

45、90.350.45 灌南023.945.2108.111456.36 响水029.6122.211677.67 滨海0150.914798.88 郯城043.166.29 临沭09010 沭阳0 其次，求节约里程。根据最短距离表，根据式（7）计算出用户间的节约里程,并由大到小排列，编制节约里程顺序表，如表 7 所示。ijc表 5-4 节约里程顺序表 （单位：千米）连接点节约里程连接点节约里程连接点节约里程连接点节约里程连接点节约里程222-8138.42-983.72-545.41-328.61-1010.72-10111.55-683.51-944.62-728.55-96.94-5110.

46、83-1072.59-1044.11-228.34-95.96-7104.95-1068.36-10432-624.51-73.38-9103.63-965.62-435.44-823.51-62.65-793.37-1052.93-534.63-617.91-51.22-392.14-752.61-833.33-717.57-913-887.64-651.93-431.87-813.46-90.98-1084.24-1049.55-829.16-8111-40.4再次，求初始解，令=i（ =1，10），最短路径iIi=2（ =1，10），且公里，载重量，且，对 10 个iL0ici300iL

47、 iirR26500irm客户点进行标记，且 2。12100BBBBi然后，按节约里程从大到小合并路径对于28138.4:ckm28282,8,1500400055006500,II rr 28282885.9*281.5*2 138.4196.4300,02LLckmkm BB 。128128282,82,8 ,5500,1,IIIrBBII 故合并两点，令。 对于不满足合并条2,10111.5:ckm1101102,10,55005500110006500,IIrr件。 对于不满足合并条件。67104.9:ckm67676,7,5600 170073006500IIrr， 对于不满足合并条

48、件。891919103.6:8,9,5500 105065506500,ckmII rr 对于5793.3:ckm57575,7,1100 170028006500,IIrr 575755.7*282.8*293.3183.7300,LLckmkm5702,BB故合并5，7两点。257257575,7 ,2800,1,IIIrBBII 令。 对于不满足合并条件。2392.1:ckm13132,3,5500335088506500,II rr 对于3887.6:ckm31133,8,5500335088506500,IIrr不满足合并条件。23 对于8,1011011084.2:8,10,110

49、006500,ckmIIrr不满足合并条件。 对于不满足合并条件。2983.7:ckm1192,9,I II195500 105065506500,rr 对于不满足合并条件。562683.5:5,6,ckmII262800560084006500,rr 对于不满足合并条件。3,1072.5,ckm3103103,10,3350550088506500,IIrr 对于不满足合并条件。5,1068.3:ckm2102105,10,2800550083006500,IIrr 对于3965.6:ckm39393,9,3350 105044006500,II rr3902,BB 393947.2*265

50、.2*265.6159.2300,LLckmkm故合并3,9两点。339339395,7 ,4400,1,IIIrBBII 令。 对于4562.6:ckm42424,5,1750280045506500,IIrr450,1,BB 2445183.731*262.6183.1300,LLckmkm故合并4，5两点。22425754,5,7 ,4550,2,1,IIIrBBI 令。 分析余下的各组，均不能满足合并条件。详见附录一。最后，得到优化结果如表 8 所示，优化线路结果如图 5 所示。 表 5-5 节约法优化结果路线运程（km）剩余配货量（）2m需车型及数量010 58.848005t 车一

51、辆0930159.244005t 车一辆0820196.455005t 车一辆04570183.145505t 车一辆0100137.855005t 车一辆060132.256005t 车一辆总运输里程为所有路径之和，求得为 838.7km。243204657119810 图 5-1 节约算法求解线路结果5.2.2 基于扫描算法的企业配送路线优化对有剩余货运量的 10 个县市采用扫描算法进行配送线路的优化。首先建立极坐标系：以闽港纸箱包装有限公司所在地连云港市作为原点建立极坐标系，各点的剩余需求量及极坐标的角坐标值如表 9 所示。坐标系如图 6 所示。 表 5-6 需求表和极坐标的角坐标值客户

52、1 赣榆县2 新沂市3 东海县4 灌云县5 灌南县6 响水县7 滨海县8 郯城县9 临沭县10 沭阳县剩余货运量（/月）2m4800150033501750110056001700400010505500角坐标/( )106197190276282306310178145232 25 1320465710 89 图 5-2 扫描算法的扫描过程然后分组：从角度为零向逆时针方向进行扫描，如图所示。第一个被分组的是客户 1，=4800；继续转动，下个被分组的是客户1Load2m9，=4800+1050=5850；继续转动，下个被分组的是客户1Load2m8，=5850+4000=98506500，由

53、于超过了限制，按分组规则，需要一个新1Load2m2m的组，这样在第一组里只有客户 1 和 9，=5850。在第二组中有客户1Load2m8，=4000；继续转动，下个被分组的是客户2Load2m3，=4000+3350=73506500，超过限制，所以需要一个新的组，这样在第2Load2m2m二组中只有客户 8，=4000。在第三组中有客户 3，load=3350，继续转2Load2m32m动；下个被分组的是客户 2，=3350+150048506500，超过限制，故需要一个新3Load2m2m的组，这样在第三组中只有客户 2 和 3，=4850。 。继续上面步骤，直到所有3Load2m的客

54、户都被分配完毕。这样可以得到如图 7 所示的分组结果。26 132046579 8 10 图 5-3 扫描算法求解结果最后对各子回路内的线路优化：对上面的 7 个组，都已经是一个单回路运输问题，对每个组进行线路优化。供应点 0 是任何一个组的 TSP 问题的起点和终点。从图 7 中可以看到，每个组最多只有 2 个客户，由对称性可知各小组的线路都是唯一的，故扫描优化结果如表 10 所示。总运输里程为所有路径之和，求得 999.3km,共需 7 辆车，其中 5 吨 5 辆、2 吨 2 辆。优化线路结果如图 8 所示。 表 5-7 扫描算法优化结果路线运程（km）剩余配货量（）2m需车型及数量（辆）

55、0190 144.658505t 车一辆08016340005t 车一辆0320174.148505t 车一辆0100137.855005t 车一辆0450110.828502t 车一辆060103.456005t 车一辆070165.617002t 车一辆273204657119810 图 5-4 扫描算法求解线路结果5.2.3 基于改进的最近插入法（一）的企业配送路线优化（1） ，001min/,110294kmiciNic 1010,Tv v v214800rm158.8lkm（2），。01044min,/,110131,1750iicciNiicr 且1465506500rr 不满足插

56、入条件。 （3），004min/,110,131kmiciNiic 241750rm 2040,Tv v v （4），04455min,/,1101,424.1,1100iicciNiicr 且 ，2451750 110028506500rrr20450,Tv v v v2110.8lkm （5），04556min,/,1101,4,523.9iiiccciNiic 且265600rm ，不满足插入条件。625600285084506500rr （6），003min/,110,1,4,547.2kmiciNiic 233350rm ，3030,Tv v v32*47.294.4lkm23335

57、0rm28 （7）0338min,/,1101,3,4,541.1iicciNiic 且 ，不满足插入条件。383350400073506500rr（8），006min/,110,1,3,4,551.7kmiciNiic 265600rm ，4060,Tv v v42*51.7103.4lkm245600rm（9）0669min,/,1101,3,4,5,629.6iicciNiickm 且 ，不满足插入条件。495600 170073006500rr（10），009min/,110,1,3,4,5,665.2kmiciNiic 5090,Tv v v（11）0992min,/,1101,3,

58、4,5,6,967.4iicciNiickm 且 ，291500 105025506500rr50290,Tv v v v5218.5lkm 252550rm（12），09228min,/,7,8,1029iiiccciN ickm ，不满足插入条件。582550400065506500rr（13），00,10min/,7,8,1068.9iciN ickm60100,Tv vv（14），0108,10min,/,7,866.2iicciN ickm ,不满足插入条件。685500400095006500rr（15）00,8min/,7,881.5iciN ickm ，7080,Tv v v2

59、74000rm（16），080,7min,/,782.8iicciN ickm774000 170057006500rr，不满足插入条件。70780,Tv v v v782.8 150.981.5315.2300lkmkm708077,4000,2*81.5163Tv v vrlkm 807088,1700,2*82.8165.6Tv v vrlkm利用改进的最近插入法（一）得到优化结果如表 8 所示，优化线路结果如图 5 所示。29表 5-8 改进后的最近插入法（一）结果路线运程（km）剩余配货量（）2m需车型及数量010 58.848005t 车一辆0450110.828502t 车一辆0

60、3094.433502t 车一辆060103.456005t 车一辆0290218.525502t 车一辆0100137.855005t 车一辆08016340005t 车一辆070165.617002t 车一辆总运输里程为所有路径之和，求得为 1052.3。km3204657119810图 5-5 改进后的最近插入法（一）求解线路结果5.2.4 基于改进的最近插入法（二）的企业配送路线优化（1） ，001min/,110294kmiciNic 1010,Tv v v214800rm158.8lkm（2），01044min,/,110131,1750iicciNiicr 且1465506500