楊君子 張利民

[摘 要]最短路徑算法不僅具有重要的理論意義，而且具有重要的實(shí)用價(jià)值，它應(yīng)用于交通運(yùn)輸、設(shè)備更新、線路設(shè)計(jì)等各方面。本文介紹了Dijkstra算法，并針對衡水市某區(qū)域蔬菜農(nóng)產(chǎn)品配送到小區(qū)超市要求路線最短問題，建立數(shù)學(xué)模型給出最佳方案。

[關(guān)鍵詞]最短路徑;Dijkstra算法;農(nóng)產(chǎn)品

[中圖分類號]F326.6 [文獻(xiàn)標(biāo)識(shí)碼]A

最短路問題是圖論中非常重要的最優(yōu)化問題之一，它是一個(gè)在現(xiàn)實(shí)生活中經(jīng)常被用到的基本工具，它可以解決現(xiàn)實(shí)生活中的許多實(shí)際問題，如城市中的管道鋪設(shè)、交通運(yùn)輸、電子導(dǎo)航、線路安排、工廠布局、設(shè)備更新等。另外，它還可以解決最快路徑問題、最低費(fèi)用問題、郵政選址問題等其他最優(yōu)化問題。最短路問題，一般來說就是從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之間距離最短的一條路，就是從圖G中某對頂點(diǎn)vi和vj（i≠j）之間的所有路徑中權(quán)值之和最短的一條路徑作為頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。

1 Dijkstra算法

Dijkstra算法是在一個(gè)賦權(quán)有向圖中能夠?qū)ふ页鲎疃搪穯栴}的最好方法，它是由荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra在1959年提出來的，它適用于所有弧的權(quán)值為非負(fù)的情況（即wij≥0）。Dijkstra算法在圖論中是一種典型的單源最短路徑算法，可以用來計(jì)算從一個(gè)給定的節(jié)點(diǎn)vs到其他所有點(diǎn)中任意一個(gè)點(diǎn)vj的最短路。Dijkstra算法的基本思想：從指定的點(diǎn)vs出發(fā)，逐漸一層一層向外擴(kuò)充去尋找最短路。

2 農(nóng)產(chǎn)品配送最短路徑問題

由于農(nóng)產(chǎn)品中生鮮、鮮奶等時(shí)效性強(qiáng)，利用最短路徑算法解決配送的路線問題，以衡水市在某一個(gè)區(qū)域的農(nóng)產(chǎn)品運(yùn)輸路線為研究背景，我們將對運(yùn)輸流程做進(jìn)一步的研究，首先將實(shí)際生活中復(fù)雜的地理線路簡單化，然后將利用最短路徑的逐次逼近法來優(yōu)化出最佳配送路線，使送貨員到達(dá)每個(gè)小區(qū)超市的路徑最短。

路線的選擇是衡水市桃城區(qū)的一個(gè)區(qū)域，在將現(xiàn)實(shí)問題平面化、虛擬化的過程中還應(yīng)注意一些具體相關(guān)細(xì)節(jié)問題，考慮到現(xiàn)實(shí)與模型的差別和計(jì)算的方便以及一些其它因素，在此對現(xiàn)實(shí)情況的模型化做了如下的調(diào)整：①每條街道都想象成為直線，忽略現(xiàn)實(shí)兩個(gè)地點(diǎn)之間的道路是曲折的這一客觀因素;②一些胡同和小的路段忽略不計(jì)，只是標(biāo)記出醒目的街道和路;③不考慮路線的車流量以及擁堵問題，通過每條路的各個(gè)條件都相同;④在運(yùn)輸?shù)倪^程中不考慮經(jīng)過某個(gè)具體路段的時(shí)間要求，單純地考慮怎么樣規(guī)劃路程，使得送貨員在最后送到每個(gè)小區(qū)超市，所走的路線最短。

將現(xiàn)實(shí)道路虛擬化、模型化的過程：我們將日常生活中的實(shí)際問題轉(zhuǎn)化到我們的理論實(shí)踐當(dāng)中，從圖論的角度考慮，為了使送貨員到達(dá)每個(gè)小區(qū)超市路程最短，將實(shí)際圖轉(zhuǎn)化為網(wǎng)絡(luò)圖，如下圖（兩個(gè)區(qū)域之間的距離單位為：m）：

v1代表鑫城嘉苑，v2代表恒豐理想城，v3代表桃城苑，v4代表華世鑫城，v5代表萬和苑，v6代表中央名邸，v7代表廣廈上城，v8代表中和盛景

在圖1的網(wǎng)絡(luò)圖中，各個(gè)節(jié)點(diǎn)代表各個(gè)小區(qū)的名稱，每條邊上的權(quán)值可以體現(xiàn)出能夠直接連通區(qū)域之間的距離。求出圖1所示的賦權(quán)有向圖D中從v1到各點(diǎn)的最短距離。設(shè)從任意一點(diǎn)vi到任意一點(diǎn)vj都有一條弧，如果沒有，則添加一條?。╲i， vj），并令wi=+∞，記Pj = P（vi， vj）為從v1到點(diǎn)vj的最短路長。

初始狀態(tài)：

第一次迭代：

同理可得：

第二次迭代：

（下轉(zhuǎn)頁）

（上接頁）

第三次迭代：

第四次迭代：

算法終止。由上面的推導(dǎo)過程可以得到送貨員到達(dá)每個(gè)小區(qū)超市的最短路徑為：。

在日常生活中，不管是路程最短還是時(shí)間最短、費(fèi)用最短以及各種情況的選址問題等都可以應(yīng)用最短路徑算法來解決。新的最短路徑算法的不斷出現(xiàn)與經(jīng)典的圖論、發(fā)展更加完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)以及算法的有效結(jié)合都是密不可分的。最短路徑問題仍是計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、交通工程學(xué)、地理信息學(xué)等學(xué)科的一個(gè)研究熱點(diǎn)。

[參考文獻(xiàn)]

[1] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].清華大學(xué)出版社，2012.

[2] 周維，楊鵬飛.運(yùn)籌學(xué)[M].科學(xué)出版社，2008.

[3] 楊麗娟，劉渤海.基于Dijkstra拓展算法路線優(yōu)化[J].長春工業(yè)大學(xué)學(xué)報(bào)，2015（01）.

[4] 胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M].高等教育出版社，2004（04）.