邱夢(mèng)楠 朱夢(mèng)茹 李 進(jìn)

（泰州職業(yè)技術(shù)學(xué)院，江蘇 泰州225300）

圖論起源于18 世紀(jì)的哥尼斯堡七橋問(wèn)題，發(fā)展于四色問(wèn)題，用點(diǎn)和邊來(lái)描述事物和事物之間的關(guān)系，是對(duì)實(shí)際問(wèn)題的一種抽象，能夠把紛雜的信息變得有序、直觀、清晰。近30 年，由于與計(jì)算機(jī)技術(shù)的結(jié)合，成為數(shù)學(xué)中發(fā)展十分迅速新興分支，現(xiàn)已廣泛應(yīng)用于工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、通訊、電力、經(jīng)濟(jì)管理、工程技術(shù)、生理學(xué)、控制論等領(lǐng)域，因此，圖論越來(lái)越受技術(shù)與管理人員的重視。

物流學(xué)作為當(dāng)今頗具影響力的學(xué)科，它以物的動(dòng)態(tài)轉(zhuǎn)化過(guò)程為主要研究對(duì)象，揭示了物流活動(dòng)的內(nèi)在聯(lián)系，使物流系統(tǒng)在經(jīng)濟(jì)活動(dòng)中從潛隱狀態(tài)顯現(xiàn)出來(lái)。 物流網(wǎng)絡(luò)由線路和結(jié)點(diǎn)兩個(gè)重要部分構(gòu)成，基本的網(wǎng)絡(luò)優(yōu)化問(wèn)題有：最短路徑問(wèn)題、最小生成樹問(wèn)題、最大流問(wèn)題和最小費(fèi)用問(wèn)題等。 物流運(yùn)輸作為重要的物流網(wǎng)絡(luò)優(yōu)化問(wèn)題，其方案的設(shè)計(jì)真接影響企業(yè)的運(yùn)輸成本和運(yùn)輸時(shí)間等。

本文運(yùn)用圖論理論，從圖與網(wǎng)絡(luò)的角度，以江蘇省泰州市海陵城區(qū)主干線為例，構(gòu)建圖論模型，利用Floyd 算法，給出城區(qū)主干線上的結(jié)點(diǎn)間最短路徑，并通過(guò)構(gòu)建歐拉回路，給出最優(yōu)巡回運(yùn)輸路徑。

1 建立圖論模型

圖1

表1

設(shè)賦權(quán)連通無(wú)向圖G(V,E)是城市道路構(gòu)成的網(wǎng)絡(luò)圖，其中，V 表示圖中所有的頂點(diǎn)集(vi)，E 表示由城市道路構(gòu)成的弧集，道路的長(zhǎng)度用邊權(quán)d(vivj)表示，如圖1 所示。

2 結(jié)點(diǎn)間的最短路徑

該圖論模型，共有24 個(gè)結(jié)點(diǎn)，38 條路徑。

由Folyd 算法求出結(jié)點(diǎn)間的最短路徑，如表1 所示（單位：km）。

3 最優(yōu)巡回運(yùn)輸路線

圖G 中有14 個(gè)奇點(diǎn)，以它們?yōu)轫旤c(diǎn)集，作一完備圖，邊上的權(quán)為兩端點(diǎn)在原圖G 中的最短距離，將此完備加權(quán)圖記為G1。

用Edmonds 算法求出G1 的最小權(quán)理想匹配，得到奇次頂點(diǎn)的最佳匹配：

在G 中沿配對(duì)頂點(diǎn)之間的最短路徑添加重復(fù)邊，得歐拉圖G2，如圖2 所示。

再由Fleury 算法求出G2 中的歐拉巡回，即G2 中的一條歐拉巡回就是G 的一條最佳巡回運(yùn)輸路線，權(quán)值為87.1km。

圖2

［1］辛宇.基于運(yùn)籌學(xué)圖論的物流網(wǎng)絡(luò)優(yōu)化研究[J].中國(guó)外資，2011，06:125+127.

［2］王銳，甘凱.圖論優(yōu)化法在物流運(yùn)輸中的運(yùn)用[J].商場(chǎng)現(xiàn)代化，2005，28:137-138.

［3］郭培俊，毛海舟.高職數(shù)學(xué)建模[M].浙江：浙江大學(xué)出版社，2010，12.