陳 纓,陳向宜,王雪輝

（國(guó)網(wǎng)四川省電力公司電力科學(xué)研究院,四川成都,610072）

基于集成物流網(wǎng)絡(luò)的路徑優(yōu)化問(wèn)題探究

陳 纓,陳向宜,王雪輝

（國(guó)網(wǎng)四川省電力公司電力科學(xué)研究院,四川成都,610072）

由于物流集成網(wǎng)絡(luò)能夠規(guī)劃物流作業(yè)流程，整合物流資源，從而提高物流運(yùn)作效率，發(fā)揮物流規(guī)模化優(yōu)勢(shì)，因此，本文在集成物流網(wǎng)絡(luò)的背景下，探討路徑優(yōu)化問(wèn)題，在傳統(tǒng)的Dijkstra算法基礎(chǔ)上，采用了完全二叉樹(shù)對(duì)Dijkstra算法進(jìn)行改進(jìn)，并以煙草商業(yè)企業(yè)為例說(shuō)明集成物流網(wǎng)絡(luò)的特點(diǎn)與優(yōu)勢(shì)，驗(yàn)證算法的有效性。研究結(jié)果表明：改進(jìn)后的Dijkstra算法能夠降低時(shí)間復(fù)雜度，提高運(yùn)行效率，為企業(yè)大規(guī)模的集成物流網(wǎng)絡(luò)分析應(yīng)用提供了一種的有效的方法。

集成物流網(wǎng)絡(luò)；Dijkstra算法；路徑優(yōu)化；煙草商業(yè)企業(yè)

0 引言

隨著全球經(jīng)濟(jì)的發(fā)展以及競(jìng)爭(zhēng)的加劇，物流作為第三利潤(rùn)源泉越來(lái)越受到企業(yè)的重視。企業(yè)通過(guò)利用現(xiàn)代物流和信息技術(shù)，建立了完整的物流網(wǎng)絡(luò)，使其不斷的向集成化、自動(dòng)化、信息化發(fā)展。路徑優(yōu)化是物流網(wǎng)絡(luò)規(guī)劃的關(guān)鍵問(wèn)題，本文以集成物流網(wǎng)絡(luò)為背景，結(jié)合Dijkstra算法，旨在探究Dijkstra算法在物流網(wǎng)絡(luò)的應(yīng)用，實(shí)現(xiàn)路徑優(yōu)化，降低物流成本。同時(shí)，為了提高Dijkstra算法的運(yùn)行速度和效率，本文將對(duì)Dijkstra算法進(jìn)行改進(jìn)，并進(jìn)行數(shù)值仿真分析以驗(yàn)證算法的有效性。

1 問(wèn)題的描述與Dijkstra算法

隨著我國(guó)物流產(chǎn)業(yè)的發(fā)展，物流配送中心建設(shè)逐步完善，這為集成物流網(wǎng)絡(luò)的發(fā)展奠基了基礎(chǔ)，集成物流網(wǎng)絡(luò)強(qiáng)調(diào)的是物流倉(cāng)儲(chǔ)、配送的集成性，應(yīng)用“系統(tǒng)集成”的思維，從物流網(wǎng)絡(luò)運(yùn)作整體要素角度，對(duì)當(dāng)前的物流網(wǎng)路進(jìn)行合理規(guī)劃，保證貨物的及時(shí)配送，及時(shí)滿(mǎn)足顧客的需求，降低物流成本。其中，路徑優(yōu)化是物流網(wǎng)絡(luò)的關(guān)鍵問(wèn)題，合理的路徑安排不僅可以節(jié)約物流總成本，還可以減少物流配送過(guò)程中的不確定性，降低物流風(fēng)險(xiǎn)，保障物流服務(wù)的效率。

集成物流網(wǎng)絡(luò)的優(yōu)化問(wèn)題主要是解決起點(diǎn)到終點(diǎn)的最短路

2 改進(jìn)的Dijkstra算法

由于傳統(tǒng)的Dijkstra算法需要遍歷每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，降低了運(yùn)行效率，鑒于此，本文采用完全二叉樹(shù)原理對(duì)Dijkstra算法進(jìn)行了改進(jìn)。完全二叉樹(shù)是效率較高的數(shù)據(jù)結(jié)構(gòu)，經(jīng)常應(yīng)用于堆排序，而采用完全二叉樹(shù)對(duì)Dijkstra算法進(jìn)行改進(jìn)時(shí)，為了維護(hù)節(jié)點(diǎn)集合的數(shù)據(jù)結(jié)構(gòu)，需要通過(guò)建立優(yōu)先級(jí)隊(duì)列，并且隊(duì)列數(shù)組中每一個(gè)節(jié)點(diǎn)各自都有一個(gè)相應(yīng)的關(guān)鍵字。其相應(yīng)的步驟為：

（2）最短路徑的選?。簩?duì)優(yōu)先級(jí)隊(duì)列進(jìn)行調(diào)整，調(diào)用SelectBT選擇節(jié)點(diǎn)，找到出發(fā)到的最小路徑。

（5）算法終止。

從遍歷節(jié)點(diǎn)數(shù)目而言，Dijkstra算法則是遍歷了所以的節(jié)點(diǎn)，運(yùn)行時(shí)間是，而改進(jìn)的Dijkstra算法只需要遍歷完全二叉樹(shù)的節(jié)點(diǎn)即可，每次調(diào)整都是將新節(jié)點(diǎn)加到完全二叉樹(shù)的最后一層，運(yùn)行時(shí)間是，說(shuō)明采用改進(jìn)的Dijkstra算法要比傳統(tǒng)的Dijkstra算法執(zhí)行效率更高，大大節(jié)約了計(jì)算時(shí)間。另一方面，還可以對(duì)完全二叉樹(shù)進(jìn)行改進(jìn)，通過(guò)建立索引等方式提高完全二叉樹(shù)的查找能力，快速定位網(wǎng)絡(luò)節(jié)點(diǎn)，縮短時(shí)間，進(jìn)一步優(yōu)化算法。

3 集成物流網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題的Dijkstra算法實(shí)現(xiàn)

為了說(shuō)明集成物流網(wǎng)絡(luò)路徑優(yōu)化的Dijkstra算法實(shí)現(xiàn)問(wèn)題，本文以煙草商業(yè)企業(yè)的物流網(wǎng)絡(luò)為例。從整體上看，我國(guó)煙草商業(yè)企業(yè)的物流網(wǎng)絡(luò)大多是按照行政區(qū)域劃分，由總公司將卷煙中轉(zhuǎn)到各分公司，再由各分公司負(fù)責(zé)配送到當(dāng)?shù)氐牧闶蹜?hù)手中，這種層級(jí)式的物流配送造成了物流組織結(jié)構(gòu)臃腫，物流資源運(yùn)行效率低下，不利于實(shí)現(xiàn)規(guī)模化效益。因此，煙草商業(yè)企業(yè)在煙草專(zhuān)賣(mài)制度下，對(duì)物流進(jìn)行整合，降低物流網(wǎng)絡(luò)層次，形成集成物流網(wǎng)絡(luò)，即在一定區(qū)域內(nèi)建立幾個(gè)規(guī)模較大的配送中心，打破原有的行政區(qū)域劃分，由一個(gè)配送中心負(fù)責(zé)多個(gè)行政區(qū)域的卷煙配送。具體來(lái)說(shuō)，由卷煙工業(yè)公司將卷煙送往幾個(gè)大的配送中心；接著，配送中心按照客戶(hù)的需求將卷煙直接配送至零售戶(hù)，或者是配送到中轉(zhuǎn)站；最后，中轉(zhuǎn)站再負(fù)責(zé)相關(guān)零售戶(hù)的配送。

由于整合之后增加了物流配送中心的網(wǎng)點(diǎn)數(shù)目，假設(shè)其中一個(gè)配送中心需要配送的網(wǎng)點(diǎn)數(shù)較多，為54個(gè)，分布情況如圖1所示。其中，節(jié)點(diǎn)20是配送中心，即起點(diǎn)，其余節(jié)點(diǎn)是零售戶(hù)或是中轉(zhuǎn)站，各個(gè)節(jié)點(diǎn)之間的距離如表1所示，、表示節(jié)點(diǎn)，表示距離?，F(xiàn)該配送中心需要向中轉(zhuǎn)站和零售戶(hù)配送卷煙，需要計(jì)算配送中心到各節(jié)點(diǎn)的最短路徑，以安排車(chē)輛運(yùn)輸，以發(fā)揮配送的時(shí)效性，縮短物流配送時(shí)間。計(jì)算過(guò)程如下。

Study on Path Optimization Based on the Integrated Logistics Network

Chen Ying,Chen Xiangyi,Wang Xuehui
(State Grid Electric Power Company Electric Power Research Institute of Sichuan Province,Sichuan Chengdu,610072)

Because the integrated logistics network can standard operating processes and integrate logistics resources in order to improve the efficiency of logistics operation and develop scale superiority of logistics,this paper discusses the path optimization problem under the background of the integrated logistics network,and on the basis of traditional Dijkstra algorithm,it adopts complete binary tree to improve the Dijkstra algorithm.Meanwhile,this paper takes the tobacco commercial enterprise as an example to indicate the characteristics and advantages of the integrated logistics network and verify the validity of the improved Dijkstra algorithm. The results show that the improved Dijkstra algorithm can reduce the time complexity and improve operational efficiency,which provides an effective method for companies to analyze large-scale integrated logistics network.

integrated logistics network;Dijkstra algorithm;path optimization;tobacco commercial enterprise

圖1 物流集成網(wǎng)絡(luò)圖