圖論在物流運輸中的實例研究

邱夢楠　朱夢茹　李進

【摘 要】本文主要研究圖論在物流運輸中的應(yīng)用，以江蘇省泰州市海陵城區(qū)為實例，通過Floyd算法，給出城區(qū)主干線上的結(jié)點間的最短路徑，并通過構(gòu)建歐拉回路，優(yōu)化城市物流路徑，提高運輸效率。

【關(guān)鍵詞】圖論；物流運輸；Floyd；歐拉回路；Edmonds；Fleury

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

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

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

1 建立圖論模型

圖1

表1

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

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

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

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

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

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

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

M=v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■

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

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

圖2

【參考文獻】

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

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

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

[責任編輯：薛俊歌]

【摘 要】本文主要研究圖論在物流運輸中的應(yīng)用，以江蘇省泰州市海陵城區(qū)為實例，通過Floyd算法，給出城區(qū)主干線上的結(jié)點間的最短路徑，并通過構(gòu)建歐拉回路，優(yōu)化城市物流路徑，提高運輸效率。

【關(guān)鍵詞】圖論；物流運輸；Floyd；歐拉回路；Edmonds；Fleury

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

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

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

1 建立圖論模型

圖1

表1

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

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

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

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

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

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

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

M=v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■

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

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

圖2

【參考文獻】

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

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

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

[責任編輯：薛俊歌]

【摘 要】本文主要研究圖論在物流運輸中的應(yīng)用，以江蘇省泰州市海陵城區(qū)為實例，通過Floyd算法，給出城區(qū)主干線上的結(jié)點間的最短路徑，并通過構(gòu)建歐拉回路，優(yōu)化城市物流路徑，提高運輸效率。

【關(guān)鍵詞】圖論；物流運輸；Floyd；歐拉回路；Edmonds；Fleury

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

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

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

1 建立圖論模型

圖1

表1

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

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

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

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

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

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

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

M=v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■

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

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

圖2

【參考文獻】

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

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

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

[責任編輯：薛俊歌]