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

邱夢楠　朱夢茹　李進

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

【關鍵詞】圖論；物流運輸；Floyd；歐拉回路；Edmonds；Fleury

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

物流學作為當今頗具影響力的學科，它以物的動態轉化過程為主要研究對象，揭示了物流活動的內在聯系，使物流系統在經濟活動中從潛隱狀態顯現出來。物流網絡由線路和結點兩個重要部分構成，基本的網絡優化問題有：最短路徑問題、最小生成樹問題、最大流問題和最小費用問題等。物流運輸作為重要的物流網絡優化問題，其方案的設計真接影響企業的運輸成本和運輸時間等。

本文運用圖論理論，從圖與網絡的角度，以江蘇省泰州市海陵城區主干線為例，構建圖論模型，利用Floyd算法，給出城區主干線上的結點間最短路徑，并通過構建歐拉回路，給出最優巡回運輸路徑。

1 建立圖論模型

圖1

表1

設賦權連通無向圖G（V，E）是城市道路構成的網絡圖，其中，V表示圖中所有的頂點集（vi），E表示由城市道路構成的弧集，道路的長度用邊權d（vivj）表示，如圖1所示。

2 結點間的最短路徑

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

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

3 最優巡回運輸路線

圖G中有14個奇點，以它們為頂點集，作一完備圖，邊上的權為兩端點在原圖G中的最短距離，將此完備加權圖記為G1。

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

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

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

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

圖2

【參考文獻】

[1]辛宇.基于運籌學圖論的物流網絡優化研究[J].中國外資，2011，06：125+127.

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

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

[責任編輯：薛俊歌]

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

【關鍵詞】圖論；物流運輸；Floyd；歐拉回路；Edmonds；Fleury

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

物流學作為當今頗具影響力的學科，它以物的動態轉化過程為主要研究對象，揭示了物流活動的內在聯系，使物流系統在經濟活動中從潛隱狀態顯現出來。物流網絡由線路和結點兩個重要部分構成，基本的網絡優化問題有：最短路徑問題、最小生成樹問題、最大流問題和最小費用問題等。物流運輸作為重要的物流網絡優化問題，其方案的設計真接影響企業的運輸成本和運輸時間等。

本文運用圖論理論，從圖與網絡的角度，以江蘇省泰州市海陵城區主干線為例，構建圖論模型，利用Floyd算法，給出城區主干線上的結點間最短路徑，并通過構建歐拉回路，給出最優巡回運輸路徑。

1 建立圖論模型

圖1

表1

設賦權連通無向圖G（V，E）是城市道路構成的網絡圖，其中，V表示圖中所有的頂點集（vi），E表示由城市道路構成的弧集，道路的長度用邊權d（vivj）表示，如圖1所示。

2 結點間的最短路徑

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

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

3 最優巡回運輸路線

圖G中有14個奇點，以它們為頂點集，作一完備圖，邊上的權為兩端點在原圖G中的最短距離，將此完備加權圖記為G1。

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

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

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

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

圖2

【參考文獻】

[1]辛宇.基于運籌學圖論的物流網絡優化研究[J].中國外資，2011，06：125+127.

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

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

[責任編輯：薛俊歌]

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

【關鍵詞】圖論；物流運輸；Floyd；歐拉回路；Edmonds；Fleury

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

物流學作為當今頗具影響力的學科，它以物的動態轉化過程為主要研究對象，揭示了物流活動的內在聯系，使物流系統在經濟活動中從潛隱狀態顯現出來。物流網絡由線路和結點兩個重要部分構成，基本的網絡優化問題有：最短路徑問題、最小生成樹問題、最大流問題和最小費用問題等。物流運輸作為重要的物流網絡優化問題，其方案的設計真接影響企業的運輸成本和運輸時間等。

本文運用圖論理論，從圖與網絡的角度，以江蘇省泰州市海陵城區主干線為例，構建圖論模型，利用Floyd算法，給出城區主干線上的結點間最短路徑，并通過構建歐拉回路，給出最優巡回運輸路徑。

1 建立圖論模型

圖1

表1

設賦權連通無向圖G（V，E）是城市道路構成的網絡圖，其中，V表示圖中所有的頂點集（vi），E表示由城市道路構成的弧集，道路的長度用邊權d（vivj）表示，如圖1所示。

2 結點間的最短路徑

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

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

3 最優巡回運輸路線

圖G中有14個奇點，以它們為頂點集，作一完備圖，邊上的權為兩端點在原圖G中的最短距離，將此完備加權圖記為G1。

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

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

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

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

圖2

【參考文獻】

[1]辛宇.基于運籌學圖論的物流網絡優化研究[J].中國外資，2011，06：125+127.

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

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

[責任編輯：薛俊歌]