用二叉樹解決配送線路問題

姚樹魁　趙慶禎

摘要:物流配送是物流中的核心環節,配送成本在整個物流過程費用中占有很大的比重,因此為了減少配送成本有必要對其配送路線進行合理優化。運用二叉樹遍歷的知識并結合節約算法的思想,將貨物需求點作為葉子結點并適當增加一些需求量為零的葉子結點構造一種有特殊意義的二叉樹,提出了一種運用這種特殊二叉樹在滿足車輛額定載貨量的前提下尋求最優配送路線的方法,并通過實例證明了其正確性。

關鍵詞:物流配送;二叉樹;最優路線

中圖分類號: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個需求點和添加的結點作為葉子結點,建立一棵滿二叉樹。