- 配送主管實操范例
- 陳明星
- 894字
- 2020-07-31 14:53:49
1.5 單個運輸起點和終點間的路線選擇
典型問題及案例
找尋最佳路徑
美國ALK聯合公司開發的PC Miler和物流公司開發的COMPUMAP是兩種商用軟件，可以用在網絡中找尋最佳路徑。它將美國所有的公路和小城市構成的公路網絡輸入數據庫，用戶只要在任一軟件中敲入運輸的起點和終點，程序就可以馬上顯示出從起點到終點的確切路線，從而選出最短路徑，司機可以知道確切的道路、一條最短路徑。它所提供的信息非常詳細，在各個交叉路口走哪條路、旅途各程的距離，還可以得出各州內的行車里程數并出具各州的燃油稅報告，同時用于核查。
解讀與闡述
這類問題是最簡單的路線選擇問題，在實際生活中也很普遍。
這類問題的解決方法一般采用最短路徑法，即通過計算選出一條最短路線。它的計算方法，我們通過一個例子來說明。
例如，有一批貨希望通過汽車從北京運到上海，請選擇一條最短路徑。步驟如下：
1. 建立模型
我們可以畫出從北京到上海的公路路線，用點代表經過的縣或市，用線代表點的可行通道，并將距離標出，A為起點，J為終點。這樣我們得到一張北京到上海的高速公路示意圖，求出A到J的最短路線即可。
圖1-2 北京到上海的高速公路線路
2. 最短路線
計算步驟參照表1-13。
表1-13
續表
（1）第一個已解的節點就是起點A，與A直接相連的節點有B、C、D點；我們可以看出B是距A點最近的節點：記為AB。所以B點是下一站的起點。
（2）接著我們找距A、B點最近的其他點，找到C點；從A到C有A—C，A—B—C；計算A—B—C的距離為156，而A—C距離為138。
（3）我們接下來找距離A、B、C最近的點，有三個候選點D、E、F，計算出距離分別為348、174、228，其中BE的距離最短，E點就是第三次迭代的結果。
（4）重復上述過程直到到達終點J，即第八步，因此，確定出最優路線為A—B—E—I—J。
在節點很多的時候，手工計算比較麻煩，但現在隨著計算機技術的廣泛應用，最短路徑法可以通過計算機編程來解決。所以，只要把所有的路線信息（公路網的節點和節點間的距離）錄入數據庫，就可以借助計算機計算出所有城市間的距離，從而選擇最短路線。
關鍵點提示
利用最短路徑法解決起點和終點間不同路線選擇問題的方法有：
1. 利用最短路徑法來計算
2. 借助計算機程序來計算