基于最近插入法的X公司物流配送路线优化方案研究

【文章摘要】

高效合理的配送作业是物流系统顺利运行的保证，配送线路的合理安排对配送速度、配送成本以及配送效益影响很大。本文首先对物流配送的相关理论进行概述，然后以X公司的配送现状为例，运用改进后的最近插入法对配送线路进行优化，提出优化的配送方案。

【关键词】

配送；配送路线优化；最近插入法

1 物流配送概述

1.1配送的概念

配送位于物流活动的最末端，是直接与消费者相连的环节，在整个的物流成本中，占有相当高的比例。按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”（GB/T 18354—2001），配送是指在经济合理区域范围内根据用户要求，对物品进行拣选、加工、包装、分割、贴标签、组配等作业，并按时送达指定地点的物流活动。

1.2配送路线优化的意义

配送路线优化是指对多个发货点和收货点，组织适当的行车路线，使车辆有序的到达并通过，在满足一定的条件下，实现最终目标 。

对企业和社会来说，选择合理的配送路线具有很重要的意义：

（1）优化配送路线，可以减少配送时间，缩短配送里程，提高配送效率，增加车辆利用率，降低配送成本。

（2）优化配送路线，可以加快物流速度，更快速地将货物送到，提高客户满意度。

（3）优化配送路线，可以使配送作业合理，提高企业运营效率.

（4）优化配送路线，可以节省运输车辆，减少车辆空驶率，降低社会物流成本。

（5）优化配送路线，可以缓解交通压力，减少噪音、尾气排放等运输污染。

1.3配送路径问题的描述

一般的物流配送路径问题可描述为：

有N个客户点，每个客户点的需求量和位置确定，用T辆汽车从配送中心运输货物，分别到达这些客户点，完成任务后返回物流中心，要求合理安排行驶路线。同时还要满足：

（1）每条线路上的客户点总需求量不超过汽车的载重量；

（2）每条配送路线总长度不超过汽车一次配送的最大行驶距离；

（3）每个客户点的需求由一辆汽车来完成。

目的是总成本（距离、时间）最小。

2 最近插入法

2.1最近插入法

最近插入法是Rosenkrantz和Stearns等人在1977年提出的，共有四个步骤：

（1）找到c0i最小的节点vi，形成一个子回路（subtour），T={V0，VK，VO}；

（2）在剩下的节点中，寻找一个距离子回路中某一节点最近的节点VK；

（3）在子回路中找到一条弧（i，j），使得Cik+Ckj-Cij最小，然后将节点V i插入到节点vi，vj之间，用两条新的弧（i，k），（k，j）代替原来的弧（i，j），并 将 节点vk加入到子回路中；

（4）重复步骤（2）、（3），直到所有的节点都加入到子回路中。

这样，子回路就演变为了一个TSP的解。因为最近插入法解决的是单回路运输问题，所以需要在此方法基础上进行改进和修正，使其能解决多回路运输VRP问题。

2.2改进的最近插入法

（1）找到c0i最小的节点vi，形成一个子回路（subtour），T={V0，VK，VO}。

（2）在剩下的节点中，寻找一个距离子回路中某一节点最近的节点vk。若此时回路的总货运量未超过车的载重限制，则继续步骤（3）。否则，转（1）寻找新的一条回路。

（3）在子回路中找到一条弧（i，j）使得Cik+Ckj-Cij最小，然后将节点vi插入到节点vi，vj之间，用两条新的弧（i，k），（k，j）代替原来的弧（i，j），并 将节点vk加入到子回路中。若此时该回路的总路程为未超过车辆的行程限制，则继续步骤（4），否则转步骤（1），寻找新的一条回路。

（4）重复步骤（2）和（3），直到每一个节点都被归入某一个子回路中。

3 X公司的配送路线优化研究

3.1 X公司简介

X公司是位于西安的一家生产密度板的企业，技术力量雄厚，工艺设备先进。公司的客户分为需求量稳定的大客户和需求量随机的小客户两种。

大客户在时间和地点上的需求都不确定，但是需求量大，一般采用租赁车辆的方法进行点对点运输，有时也由客户自己运输。小客户地点确定，主要位于西安的周边县市，但需求量不大，不过公司为推广产品，每周用专车送货上门。公司现拥有两辆11吨的货车，一辆7吨的货车，如果车辆不够时，采取租赁车辆的办法。

目前，对小客户公司采用的配送线路如图2-1所示。

该 配 送 线 路 的 弊 端 在于：配 送 路 线选择不合理，运距过长，消耗作业时间多，不能充分利用车辆配载容积，浪费人力和物力资源，影响公司的收益。

3.2 X公司的配送线路分析与优化

基本条件：X公司需给9个客户送货，客户依次为1，2，3，…，9，现有车辆为1辆7T的货车（百公里油耗21L），2辆11T的货车（每百公里油耗27L），柴油每升7.14元，司机每天工资150元。目标：确定所需要的车辆数目、车辆类型、司机数量以及各车行走的路径，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输总费用最小。

限制条件：（1）运输里程超过350公里时，需配备两名司机，减去由于装卸货等影响因素，各车最大运输距离为600公里。

（2）为预防突发事件，每辆车完成任务之后都要回到源点0处。

（3）不能超过车辆的容量限制。7吨的货车最多可装300张密度板，11吨的最多可装500张密度板。

设各点间的距离为，9节约距离为Cij。每辆车的载货量为ri，各点需求量为，每辆车的行驶里程为，公里，西安为0点，客户点1，2，?，9。

各个配送点的运距和运量见表3-1。

3.2.1原配送线路基本数据分析

各配送线路总里程，所需运输车辆型号、数量以及所需司机数量见表3-2。

由上表可知，公司每周需7吨货车进行5次 配 送，需要司机6人，工资支出900元，总里程为1262.8KM，，消耗柴油265.2L，所需燃油费1894元，加上司机工资，一共花费2794元。

3.2.2基于改进的最近插入法的企业配送路线优化

令T={0}，N={0，1，2??，10}，比较从0出发的所有路径大小。因为，所以就有顾客点0，1构成一个子回路，，此时。

然后在剩余顾客点（1，2，3，4，6，7，8，9）中寻找到0和5中某一点的最小距离，且。

因为所以在子回路插入点1，由于对称性，无论将1插入到0和5之间往返路径中，结果都是一样的，这样，构成了一个新的子回路。

再次寻找剩余顾客点到0，1， 5中某一点的最小距离：可知最小距离为，此时，因为r1+ r2=260+120380<500，所以在子回路插入点2.将点2分别插入（0，1），（1，5），（5，0）中，比较得：插入到（1，5）增量最小，。

，此时构成了一个新的子回路。

再次对剩余的顾客点按照上诉方法进行优化，可构成另子回路T1={0，3，4，6，0}和子回路利用改进后的最近插入法得到公司优化结果。（表3-3）

由此得出，公司每周需要11吨货车配送3次，配送总里程939.7 km.，燃油费用1811元，司机4人次，工资600元，总共的配送费用为2411元。

3.2.3优化方案比较分析

本文将从所需车辆数，行驶总里程，总油耗，人力资源和总费用这些指标，对优化后的方案进行评价分析，从对比中可知，优化后的方案需要使用的车次更少，减少了X公司用车紧张的情况，使车辆安排使用上有了更大的弹性。因此，在用车角度上考虑，优化后的方案比优化前的方案合理。从总运输里程角度考虑，优化后的总运输里程为939.7千米，与原方案的1262.8千米相比较，减少了车辆行驶的里程数，减少了公司车辆的损耗和资源的浪费，带来更多效益。

从燃油消耗的角度考虑，优化后的方案的消耗为254升，与原方案的265.2升相比较，降低了油耗量。不仅减少X公司燃油费用的支出，还能降低社会资源的浪费。

从公司人力资源消耗角度来考虑，优化后的方案所需司机人数为4人，减少人力的消耗为2人次，使公司在人员安排上将更具有弹性，还能降低公司费用的支出。从支出的总费用角度来考虑，优化后的方案的费用支出为2413元，与原方案的为2794元相比较，节省了总费用的支出。

【参考文献】

[1]高晓亮，伊俊敏，甘卫华.仓储与配送管理[M].清华大学出版社，2006.

[2]Elliot Rabinovich， Manus Rungtusanatham and Timothy M. Laseter. Physical distribution service performance and Internet retailer margins： The drop-shipping context[J].Journal of Operations Management，2008（6）：767-780.

[3]孔少彻，梁彤铮.商品物流配送优化策略探讨[J].市场论坛，2009（7）：94-95

[4]Gianpaolo Ghiani. Gilbert Laporte. Roberto Musmanno. Introduction to Logistics Systems Planning and Control [M]. T&T Productions Ltd， London，2004（1）：3-15.

【作者简介】

张瑜，女，1981年，讲师，研究方向，物流管理。