一种解决配送规划问题的改进节约算法

      中图分类号：TP301.6 文献标识码：A 文章编号：1002-3100(2009)09-0029-03

      物流配送是现代化物流系统中的一个重要环节。配送是将货物从物流节点送达收货人的过程。合理选择配送路径，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较好的影响。配送规划问题可以简化为货运车辆优化调度问题(Vehicle Scheduling Problem，VSP)，是指对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如里程最短、费用最少、时间尽量少、使用车辆数尽量少等）。

      Dantzing和Ramser于1959年首次提出该问题[1]。由于VSP问题属于NP-困难问题，因此在实际中常采用启发式算法来求解。启发式算法的种类也很多，常见的有构造算法（如Clarke和Wright的C-W节约算法），两阶段算法和亚启发式算法（如模拟退火算法、遗传算法、神经网络算法等）。C-W节约算法是Clarke和Wright于1964年提出的，由于其简单性和一定程度的实用性，成为广泛使用的配送规划近似算法。然而，有些时候C-W算法的求解结果可能与最优解相差较大距离（见算例）。本文结合AK算法的思路对C-W节约算法进行改进，期望使节约算法更加实用。

      1 问题描述与模型建立

      问题描述：有一个车场0，拥有m辆容量为的车辆，第k辆车的最大运距为，现有i项货运任务需要完成，每辆车所运送的货物量不超过其载重量并且走行路程不超过其运距，每个需求点必须有且只需一辆车送货。

      

      

      2 改进的C-W节约算法

      AK算法是一种启发式的搜索算法，一般被用来解决0-1背包问题。算法的基本思想是，首先将最多k件物品放入背包，如果这k件物品的总重大于包裹容量，则放弃它。否则，剩余容量再按物品重量从大到小的顺序装入[3]。C-W节约算法中合并配送路径是从节约里程最大的点对开始合并，现将AK算法运用其中，首先选择任意小于等于k对的点对，如满足合并条件则进行合并，而后再按节约里程从大到小的顺序合并其他点对。针对从点对集中挑出不超过k对的点对的不同组合形成不同的方案，并比较每个方案的目标值，选择其中的最优的一个形成最终配送方案。

      改进的C-W算法：

      

      

      3 算例

      

      用传统C-W节约算法计算，合并2、3点，最终得到0-2-3-0、0-1-6-0、0-4-0、0-5-0，共用4辆车，总里程为109km。用改进后的方法计算，得到0-3-4-0，0-1-2-0，0-5-6-0，共用3辆车，总里程为96km。改进后的算法在优化程度上明显提高。

      

      

      4 结束语

      本文在对VSP问题进行简单描述的基础上，对AK算法与传统的C-W节约算法进行有效的结合，提出了求解该问题的一种改进算法，通过这种方法能够避免在某些情况下C-W节约算法求解结果与最优解相差较大的问题。然而，本算法计算复杂度为O，较C-W节约算法的计算次数多，k的取值可根据问题的规模n和计算机的速度来确定。