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

邱夢楠 朱夢茹 李 進

（泰州職業技術學院，江蘇 泰州225300）

圖論起源于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 的最小權理想匹配，得到奇次頂點的最佳匹配：

在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.