基于最小生成樹的城市物流配送路線算法優(yōu)化研究

洪繼程

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2017）31-0012-02

引言

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

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

1 提出問題

1.1 問題描述

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

1.2 研究思路

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

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

2.1 優(yōu)化策略

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

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

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

2.2 算法

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

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

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

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

3.1 算法優(yōu)化

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

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

3.2 多點(diǎn)配送最佳路線的確定

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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