基于改进节约法的配送路线优化问题研究

收藏 |打印|下载word

作者：

轩华

作者简介：

轩华(1979-)，女，河南睢县人，工学博士，副教授，主要研究方向：物流优化与调度、生产计划与调度等，郑州大学，管理工程系，河南郑州 450001

原文出处：

物流技术

内容提要：

提出改进的节约法来解决考虑实际路况的配送路线优化问题，首先对配送线路进行等级划分，得到相应等级线路的转化系数，然后利用转化系数和实际距离的乘积确定配送点间的有效距离，进而利用改进节约法确定最佳配送线路。这使得配送线路优化分析更具有实际意义。

期刊代号：F14

分类名称：物流管理

复印期号：2011 年 04 期

关键词：

配送线路转化系数改进节约法　　distribution route conversion coefficient improved saving method

字号：大中小

doi：10.3969'j.issn.1005-152X.2010.h23.031

1 引言

在采用节约法求解配送车辆的线路优化问题(Vehicle Routing Problem，简称VRP)时，通常要满足以下基本约束：

(1)收货人对货物的要求；

(2)收货人对货物送达时间的要求；

(3)收货人对地点的要求；

(4)路线允许通行的时间限制；

(5)运输工具载重能力的限制；

(6)积载能力的限制；

(7)配送中心的能力；

(8)自然因素的限制。

然而，在实际配送中，城市道路日益显现出负担的繁重，交通阻塞问题已是社会常见的问题之一，要想及时准确、高效率地完成配送任务，必须对配送线路的路况进行充分的考虑，如果没有充分考虑路况，在配送时就不能保证及时、高效地完成任务，客户的服务水平就得不到保证。在以往的配送问题研究中[1-3]，常假设不存在道路受阻的情况，而未将交通的通畅度考虑在内，因此，得到的实际配送时间和计划配送时间并不吻合，甚至相差很大。例如：配送车辆在市中心行驶一百米，实际上要比在郊区线路上走一百米用的时间长，但在用节约法选择配送路线时，仅考虑了路程的长度。要解决这一问题，就需要对不同的配送路线进行一个有效距离的转化，使得所优化的“配送线路”更接近于现实中的配送线路，这样更能及时、准确、高效地完成客户的任务。

因此，本文提出了改进节约法求解配送线路优化问题，在该问题中，除了考虑上述基本约束条件，还考虑了“易忽略的其它重要影响因素”，包括：

(1)不同地方的道路状况：

(2)交通阻塞的时间；

(3)等交通指示灯的时间；

(4)道路的最高限速情况。

本文通过一定的转化，将这些“易忽略的其它重要影响因素”转化成有效距离来看待，通过“转化系数”来确定实际的有效距离，这样可将问题的求解难度降低。

2 典型节约法的原理

3 改进节约法的思路

节约法虽然考虑了路程的最大节约，但它没有把道路的不同状况考虑在内，针对这一问题，本文提出了改进的节约法。

改进的节约法的基本思路为：首先，计算出配送中心到各个被配送点的有效距离及各个被配送点之间的距离。其次，计算各被配送点之间相互间的“有效节约里程”的大小和各被配送点的收货数量或重量。最后，在车辆如载重允许的条件下，将各个可能入选的送货点衔接起来，形成一条配送线路，如果卡车不能满足全部送货要求，可先安排一辆，然后按照上述程序继续安排第二辆、第三辆或更多，直到全部被配送点连在多条配送线路上为止。

具体操作步骤为：

(1)对配送的公路进行划分。例如：划为“市区线路”、“城郊线路”、“乡镇线路”(还可划分的更细，如将“市区线路”按拥挤程度再划)，并进行有效距离的转化。假设“城郊线路”时速X km/h；“市区线路”时速Y km/h；“乡镇线路”时速Z km/h，根据实际情况并参照公路等级车速规定，取得对应等级线路车速，来计算其“转化系数”。

(2)计算有效最短距离。根据配送网络中的已知条件，计算配送中心到各个被配送点之间的最短距离。将实际距离转化为有效距离的步骤如下：

STEP1对“城郊线路”、“市区线路”和“乡镇线路”进行转化。

STEP2利用系统工程学的知识，求出相对应的权重，分别取各自权重的倒数，作为对应的转化系数。

STEP3利用实际距离和转化系数之积来确定有效距离。