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

姚樹魁　趙慶禎

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

關(guān)鍵詞:物流配送;二叉樹;最優(yōu)路線

中圖分類號:U116.2文獻(xiàn)標(biāo)識碼: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引言

隨著人們對物流重要性認(rèn)識的不斷深入,“ 第三利潤源泉”的理念已經(jīng)被越來越多的人們所認(rèn)同。如何降低物流成本,提高物流效率和物流服務(wù)水平,是倍受企業(yè)關(guān)注的一個問題。而配送是一種先進(jìn)的物流技術(shù),在物流活動中具有十分重要的地位,是實(shí)現(xiàn)降低物流成本,獲得良好經(jīng)濟(jì)效益的主要途徑。因此,人們對物流配送技術(shù)提出了更高的要求,要求在考慮各種因素的情況下更加合理地選擇配送線路和配載貨物的方法,以實(shí)現(xiàn)物流供貨系統(tǒng)的合理化[1-2]。本文應(yīng)用二叉樹的知識,對貨物配載和配送路線的選擇進(jìn)行了研究,并提出了一種配送路線距離最短的算法,來實(shí)現(xiàn)對物流供貨系統(tǒng)的優(yōu)化。

1貨物配送路線的選擇問題

配送中心是介于供貨方和需求方之間的一個特殊層,它有兩個不同的角色,一是存儲,二是轉(zhuǎn)運(yùn)。當(dāng)供貨方與客戶距離較遠(yuǎn)或運(yùn)費(fèi)較貴時,配送中心的存在可以降低物流的成本,因?yàn)樗鼈兊拇嬖诳梢耘窟M(jìn)、發(fā)貨物,集中儲運(yùn),從而降低物流系統(tǒng)成本,提高系統(tǒng)的效率[3],其模式如圖1。

貨物配送的一個基本問題是在已知客戶地點(diǎn)、需求量的情況下解決車輛的行駛路線的問題,即確定一個從配送中心到客戶端的最優(yōu)路線,使總的配送距離最小。在實(shí)際配送中,經(jīng)常會遇到車輛受承載能力、容積的限制,一輛車不能滿足所配送區(qū)域用戶的需求,此外客戶服務(wù)時間窗口、服務(wù)優(yōu)先等級、送貨與取貨混合等,均使配送運(yùn)輸問題變得復(fù)雜。解決運(yùn)輸復(fù)雜問題常用的方法就是VRP法。

VRP是最早由Dantzig于1959年提出,是運(yùn)籌學(xué)中的熱點(diǎn)問題。VRP是對一系列發(fā)貨點(diǎn)和收貨點(diǎn),調(diào)用一定的車輛,組織適當(dāng)?shù)男熊嚶肪€,使車輛有序地訪問它們,在滿足特定的約束條件下,力爭實(shí)現(xiàn)一定的目標(biāo)(如車輛空駛里程最短,運(yùn)輸總費(fèi)用最低等)。典型的VRP可描述為[4]:

(1)多個客戶同時需要運(yùn)輸服務(wù),且一輛車不能同時滿足這些客戶的需求。

(2)每個客戶只能被一輛車訪問一次。

(3)所有車輛從倉庫出發(fā),并最終回到倉庫。

(4)所有車輛必須滿足能力約束。

(5)車輛在路線上可以取、送貨。

2基于二叉樹的配送路線選擇方法

2.1問題定義

本文研究的路線選擇問題定義為:(1)所有車輛從物流配送中心出發(fā),并最終回到配送中心。(2)每個客戶只能被一輛車訪問,一輛車可以為多個需求點(diǎn)配送。(3)車輛的額定容量一定,配送車輛的載運(yùn)量不能超過其額定的容量。(4)貨物的裝載只考慮其重量,不考慮其體積。(5)有足夠多的可供支配的車輛。(6)各條路線的交通情況相同。

車輛配送路線問題就是研究在滿足配送要求的前提下,使車輛總的行駛路線最短。本文中研究的車輛總的行駛路線最短的問題是在滿足車輛額定容量的前提下實(shí)現(xiàn)的。

2.2相關(guān)知識

本文下面提出的基于二叉樹的配送路線選擇算法中用到的一些基本理論如下:

(1)二叉樹及其遍歷。二叉樹(binary tree)是一種樹型結(jié)構(gòu),它的特點(diǎn)是每個結(jié)點(diǎn)至多只有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點(diǎn)),并且,二叉樹的子樹有左右之分,其次序不能任意顛倒。

滿二叉樹:一棵深度為k,且有2的k次方-1個結(jié)點(diǎn)的二叉樹。特點(diǎn):每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。

完全二叉樹的定義:深度為k,有n個結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時,稱為完全二叉樹。 特點(diǎn):葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn);對任一結(jié)點(diǎn),若其右分支下子孫的最大層次l,則其左分支下子孫的最大層次必為l或l+1。

遍歷二叉樹(traversing binary tree)的問題,即如何按某條搜索路徑巡訪樹中每個結(jié)點(diǎn),使得每個結(jié)點(diǎn)均被訪問一次,而且僅被訪問一次。其中常見的有三種情況:分別稱之為先(根)序遍歷,中(根)序遍歷和后(根)序遍歷。前序遍歷運(yùn)算:即先訪問根結(jié)點(diǎn),再前序遍歷左子樹,最后再前序遍歷右子樹。前序遍歷運(yùn)算訪問二叉樹各結(jié)點(diǎn)是以根、左、右的順序進(jìn)行訪問的。

(2)節(jié)約算法[5]。如圖2所示,假設(shè)從配送中心向需求點(diǎn)i和j配送貨物,在由O,i,j組成的三角形中,由三角形的任意兩邊之和大于第三邊,配送方案b比配送方案a 能夠節(jié)約一定的里程。其節(jié)約的里程為:

S=C+C-C(1)

式中,S表示節(jié)約的里程;C表示配送中心O到客戶i的距離;C表示配送中心O到客戶j的距離;C表示客戶i到客戶j的距離。

2.3基于二叉樹的配送路線選擇方法

(1)建立一棵滿二叉樹。假設(shè)有n個需求點(diǎn),依次對這n個需求點(diǎn)隨機(jī)編號為1,2,…,n

-1,n。并添加適當(dāng)?shù)慕Y(jié)點(diǎn)(稱為空白結(jié)點(diǎn)),這些結(jié)點(diǎn)的編號都為-1,其需求量為零。使n個需求點(diǎn)和添加的結(jié)點(diǎn)作為葉子結(jié)點(diǎn),建立一棵滿二叉樹。