洪繼程

摘 要：提出了一種基于最小生成樹理論算法的物流配送路徑優(yōu)化方案，首先實現(xiàn)了物流配送復雜路徑向最小生成樹的轉(zhuǎn)化方案，通過轉(zhuǎn)移策略的建立，構(gòu)造了最小生成樹的算法，同時通過標記的方法實現(xiàn)了最優(yōu)化路徑設(shè)計，最后實現(xiàn)了物流配送的周轉(zhuǎn)總量最小的目標。軟件調(diào)試運行表明，研究中提出的算法切實有效，相對于傳統(tǒng)的算法其復雜程度得到了有效降低。

關(guān)鍵詞：最小生成樹；物流配送；路徑；優(yōu)化；算法

中圖分類號：TP301 文獻標志碼：A 文章編號：2095-2945（2017）31-0012-02

引言

現(xiàn)代物流管理已經(jīng)成為一種先進的組織方式與管理技術(shù)，是物流企業(yè)降低物流消耗，提高勞動生產(chǎn)率的有銷手段[1]。研究物流系統(tǒng)中路徑的優(yōu)化算法即采用計算機網(wǎng)絡(luò)技術(shù)對物流中的貨物、服務(wù)等要素進行高效流通與科學有序的控制。物流學的研究內(nèi)容包含物流點的選址問題、物流車輛的調(diào)度路徑以及物流庫存控制問題。本研究主要側(cè)重進行車輛的物流路徑優(yōu)化問題，研究要素主要包含配送中心、客戶位置以及道路網(wǎng)絡(luò)的情況等。物流路徑的優(yōu)化問題目前有精確算法、啟發(fā)式算法以及元啟發(fā)式算法[2]。精確算法主要有動態(tài)規(guī)劃法與分支定界法等兩個方面的內(nèi)容，但是精確算法只能適用于小規(guī)模的車輛路線優(yōu)化問題。元啟發(fā)式算法求解路徑優(yōu)化問題是目前研究的熱點，對應(yīng)的算法有蟻群算法、遺傳算法等。

遺傳算法對于研究領(lǐng)域所需要的知識程度要求較低，對于空間等因素的要求不高，在模型求解方面具有較強的適應(yīng)能力與通用性。蟻群算法采用的是正反饋機制，具有優(yōu)良的分布式特征，遺傳算法與蟻群算法在求解大規(guī)模路徑優(yōu)化問題時具有一定的優(yōu)越性，但是也同時存在收斂性差等方面的問題[3]。利用最小生成樹進行求解具有直接、有效、適應(yīng)強的優(yōu)勢，是目前路徑優(yōu)化的研究熱點。

1 提出問題

1.1 問題描述

物流的特征是多個車輛將貨物從不同的配送中心送至不同空間位置客戶，因此合理進行路徑的安排能夠使得總體配送費用成本最低是交通運輸與物流企業(yè)關(guān)注的現(xiàn)實問題。在研究中，車輛都是具有一定實際容量的，為了簡化問題，假設(shè)所有客戶的需求都由一個配送中心滿足，同時完成一次配送后，車輛需要回到配送中心后再次進行下一次配送。

1.2 研究思路

本研究中采用了最短路徑尋優(yōu)轉(zhuǎn)移策略，不斷進行可行解策略的構(gòu)造以及信息更新，根據(jù)優(yōu)化最小生成樹的基本原則，根據(jù)配送范圍進行交通路線圖的繪制以及抽象，形成一顆或者多顆最小生成樹（研究中設(shè)定這些樹為子樹），在子樹的基礎(chǔ)上進行合成就可以形成一顆最小生成樹，合成以后的最小生成樹就是路徑優(yōu)化的研究對象，采取這樣的方案較為實用，并有效降低了算法的復雜度[4]。

2 路徑優(yōu)化策略與算法

2.1 優(yōu)化策略

假設(shè)v0為物流系統(tǒng)的一個配送中心，需要向客戶送貨，客戶定義為vi與vj，其中就涉及到三個距離，首先是物流配送中心到兩個用戶的距離，其次就是兩個用戶之間的距離，配送的方案有以下兩種，如圖1所示。

根據(jù)之前配送要求返回中心的假設(shè)，轉(zhuǎn)移策略中第一種方案所需要的配送距離為2|voi|+2|voj|，第二種的配送距離為

|voi|+|voj|+|vij|，第二種方案與第一種方案距離的差值根據(jù)三角形的三邊關(guān)系|voi|+|voj|-|vij|>0。根據(jù)這樣的策略可以得出，如果物理配送中心向多個不同用戶配送貨物，車輛配送路線上客戶密度越高，則路徑更為優(yōu)化合理。

2.2 算法

在交通網(wǎng)絡(luò)中將其中的用戶節(jié)點標注為vi（其中i=1，2.....9）。各個節(jié)點之間的鏈接如圖2所示，節(jié)點之間的距離也不同，采用數(shù)字標記進行量度，任意確定其中的一個節(jié)點為配送中心，其算法構(gòu)成過程包含有交通線鏈接抽象，最小子樹構(gòu)造，合成樹構(gòu)造以及路線確定等四個不同的階段。

首先需要實現(xiàn)就是最小生成樹的構(gòu)造，確定配送中心為最小樹的樹根，在后續(xù)表達中簡稱為TRN，同時將配送中心節(jié)點定位為當前節(jié)點，并找出與當前節(jié)點具有連接關(guān)系的所有其他節(jié)點，并進行統(tǒng)計，尋找與當前節(jié)點最短的連接，并進行距離的存儲，如果節(jié)點距離值變大則重新進行節(jié)點的選擇，在此過程中可以采用三元向量組的方式對子樹集合進行記錄。對路徑中的節(jié)點進行標記，并遍歷所有的子樹，刪除路徑中無法實現(xiàn)的孤立節(jié)點，完成對應(yīng)子樹的生成。

在完成子樹的基礎(chǔ)上根據(jù)子樹的數(shù)目與節(jié)點的距離進行循環(huán)迭代運算，可以得到合并后的最小生成樹，作為算法優(yōu)化研究的對象。在距離計算過程中要能夠?qū)崿F(xiàn)有效距離的量度，科學規(guī)定節(jié)點之間實際的有效距離以及子樹之間的距離。

3 算法優(yōu)化與路徑確定

3.1 算法優(yōu)化

如果在實際過中配送中心向一個地點進行貨物的配送，則只需要從樹根的位置根據(jù)樹的深度進行有限遍歷算法進行配送目標的尋找，配送完成就按照原路返回，這樣單點的模式下就可以保證是最佳的配送路線。根據(jù)OSDVRP的實際情況，可以在以上的算法基礎(chǔ)上實現(xiàn)修正進行問題的求解。首先就是進行配送節(jié)點在最小生成樹中的求解，其核心思路是對樹根的子節(jié)點進行集合的定義，對子節(jié)點進行樹根假定，并進行深度優(yōu)先遍歷，最終確定配送中心節(jié)點的分布。

同時需要進行相關(guān)路徑必經(jīng)節(jié)點的求解，對子集合中的所有節(jié)點都要能夠通過深度優(yōu)先的方式進行遍歷查詢，對最小生成樹遍歷獲得的節(jié)點研究辨析，確定哪些節(jié)點處于同一路徑，對于處在同一路徑的節(jié)點進行標記并生成對應(yīng)的子集，確定在路徑中必經(jīng)節(jié)點的分布[10]。

3.2 多點配送最佳路線的確定

要實現(xiàn)多點最佳配送路線的確定，首先需要進行的就是對子樹合并以后樹根歲對應(yīng)的子集合進行實時判斷，當對應(yīng)的子集合為空集的時候，就刪除這個集合，如果是非空集合，則多點配送算法有以下幾個步驟。

S1：求解統(tǒng)計子集合的數(shù)量，并標記為n，如果n>1，則流程轉(zhuǎn)到S4，如果n=1則轉(zhuǎn)到步驟2，如果集合不存在，則轉(zhuǎn)到S6。

S2：根據(jù)最小生成樹的深度進行有限遍歷到每一個配送點，并從原路返回到配送節(jié)點，遍歷路徑與返回路徑即為所求解的最優(yōu)化配送路徑，同時進行集合的實時刪除。

S3：對集合之間的互通鏈路進行檢查，如果沒有相互直接的連接，則轉(zhuǎn)到S2。

S4：對其中每個集合進行直接互通線路集合的查詢，將其中沒有直接互通的節(jié)點構(gòu)成的子集與節(jié)點本身進行刪除。

S5：對所有子集合中進行交通連接圖的有效還原，對其中算法生產(chǎn)的步驟進行迭代與重復，最后形成只有三角形以及直線方式的子樹為止。

S6：確定子樹之間的線路配送路徑，同時對每個子樹種的配送路徑也進行確定，最終就可以得到多點配送過程中最優(yōu)化的配送路徑。

4 結(jié)束語

研究中采用了Jbuilder9對算法進行了仿真分析，結(jié)論表明，采用文中提出的算法能夠以最快的速度實施貨物的有效配送，同時也能夠有效降低物流配送的成本，在過路費用、動力費用與人力成本方面都具有顯著的改善，研究具有重要的理論意義與實踐價值。

參考文獻：

[1]張潛，高立群，胡祥培，等.物流配送路徑多目標優(yōu)化的聚類-改進遺傳算法[J].控制與決策，2003（04）.

[2]崔雪麗，馬良.有缺貨限制的VRP螞蟻算法研究[J].上海理工大學學報，2003（01）.

[3]張濤，王夢光.遺傳算法和3-opt結(jié)合求解帶有能力約束的VRP[J].東北大學學報，1999（03）.

[4]賀國光，胡學年，劉豹.用于公交線路優(yōu)化設(shè)計的四步啟發(fā)式算法[J].系統(tǒng)工程學報，1988（02）.

[5]韓艷，關(guān)宏志，趙紅征.通勤班車出行線路優(yōu)化研究[J].武漢理工大學學報（交通科學與工程版），2011（02）.endprint