用二叉树解决配送线路问题

姚树魁　赵庆祯

摘要:物流配送是物流中的核心环节,配送成本在整个物流过程费用中占有很大的比重,因此为了减少配送成本有必要对其配送路线进行合理优化。运用二叉树遍历的知识并结合节约算法的思想,将货物需求点作为叶子结点并适当增加一些需求量为零的叶子结点构造一种有特殊意义的二叉树,提出了一种运用这种特殊二叉树在满足车辆额定载货量的前提下寻求最优配送路线的方法,并通过实例证明了其正确性。

关键词:物流配送;二叉树;最优路线

中图分类号:U116.2文献标识码:A

Abstract: Logistic distribution is the key point of logistics and the distribution cost take a major portion in the whole logistics procedure. So in order to minimize the distribution cost, it is necessary to optimize the distribution routes. This paper is using the knowledge of binary tree traversal combined with saving algorithm, taking the demand node as the leaf node and add some zero demand nodes as leaf node to form a particular binary tree, putting forward a method based on this particular binary tree to search for the optimal distribution routes under the premise of rated loading capacity of vehicles, and demonstrated its correctness.

Key words: logistic distribution; binary tree; optimal route

0引言

随着人们对物流重要性认识的不断深入,“ 第三利润源泉”的理念已经被越来越多的人们所认同。如何降低物流成本,提高物流效率和物流服务水平,是倍受企业关注的一个问题。而配送是一种先进的物流技术,在物流活动中具有十分重要的地位,是实现降低物流成本,获得良好经济效益的主要途径。因此,人们对物流配送技术提出了更高的要求,要求在考虑各种因素的情况下更加合理地选择配送线路和配载货物的方法,以实现物流供货系统的合理化[1-2]。本文应用二叉树的知识,对货物配载和配送路线的选择进行了研究,并提出了一种配送路线距离最短的算法,来实现对物流供货系统的优化。

1货物配送路线的选择问题

配送中心是介于供货方和需求方之间的一个特殊层,它有两个不同的角色,一是存储,二是转运。当供货方与客户距离较远或运费较贵时,配送中心的存在可以降低物流的成本,因为它们的存在可以批量进、发货物,集中储运,从而降低物流系统成本,提高系统的效率[3],其模式如图1。

货物配送的一个基本问题是在已知客户地点、需求量的情况下解决车辆的行驶路线的问题,即确定一个从配送中心到客户端的最优路线,使总的配送距离最小。在实际配送中,经常会遇到车辆受承载能力、容积的限制,一辆车不能满足所配送区域用户的需求,此外客户服务时间窗口、服务优先等级、送货与取货混合等,均使配送运输问题变得复杂。解决运输复杂问题常用的方法就是VRP法。

VRP是最早由Dantzig于1959年提出,是运筹学中的热点问题。VRP是对一系列发货点和收货点,调用一定的车辆,组织适当的行车路线,使车辆有序地访问它们,在满足特定的约束条件下,力争实现一定的目标(如车辆空驶里程最短,运输总费用最低等)。典型的VRP可描述为[4]:

(1)多个客户同时需要运输服务,且一辆车不能同时满足这些客户的需求。

(2)每个客户只能被一辆车访问一次。

(3)所有车辆从仓库出发,并最终回到仓库。

(4)所有车辆必须满足能力约束。

(5)车辆在路线上可以取、送货。

2基于二叉树的配送路线选择方法

2.1问题定义

本文研究的路线选择问题定义为:(1)所有车辆从物流配送中心出发,并最终回到配送中心。(2)每个客户只能被一辆车访问,一辆车可以为多个需求点配送。(3)车辆的额定容量一定,配送车辆的载运量不能超过其额定的容量。(4)货物的装载只考虑其重量,不考虑其体积。(5)有足够多的可供支配的车辆。(6)各条路线的交通情况相同。

车辆配送路线问题就是研究在满足配送要求的前提下,使车辆总的行驶路线最短。本文中研究的车辆总的行驶路线最短的问题是在满足车辆额定容量的前提下实现的。

2.2相关知识

本文下面提出的基于二叉树的配送路线选择算法中用到的一些基本理论如下:

(1)二叉树及其遍历。二叉树(binary tree)是一种树型结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

满二叉树:一棵深度为k,且有2的k次方-1个结点的二叉树。特点:每一层上的结点数都是最大结点数。

完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。 特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次l,则其左分支下子孙的最大层次必为l或l+1。

遍历二叉树(traversing binary tree)的问题,即如何按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。其中常见的有三种情况:分别称之为先(根)序遍历,中(根)序遍历和后(根)序遍历。前序遍历运算:即先访问根结点,再前序遍历左子树,最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。

(2)节约算法[5]。如图2所示,假设从配送中心向需求点i和j配送货物,在由O,i,j组成的三角形中,由三角形的任意两边之和大于第三边,配送方案b比配送方案a 能够节约一定的里程。其节约的里程为:

S=C+C-C(1)

式中,S表示节约的里程;C表示配送中心O到客户i的距离;C表示配送中心O到客户j的距离;C表示客户i到客户j的距离。

2.3基于二叉树的配送路线选择方法

(1)建立一棵满二叉树。假设有n个需求点,依次对这n个需求点随机编号为1,2,…,n

-1,n。并添加适当的结点(称为空白结点),这些结点的编号都为-1,其需求量为零。使n个需求点和添加的结点作为叶子结点,建立一棵满二叉树。