最短路徑－洪明洲教授部落格

最短路徑

網路模型隨著不同應用目標會有不同計算，但最核心的計算在「一箭穿心」，亦即，只要把這支箭以及「穿（心）」的限制條件設定好，各種網路路徑都能找到最佳解。

「一箭穿心」的限制條件主要是流量（flow）計算，不管箭如河穿、路如何走、流量如何轉、流多大………，限制條件中網路節點若僅只於「通過」（passing），留存於節點的流量永遠是0（none），網路模型就是運用這一特性找出「最佳路徑」，它看起來簡單到難以思議。

本篇要介紹的「最短路徑」（shortest path）上述特性更為顯著。不管網路模型的路徑多曲折、複雜，每一中間要穿過的節點，流出與流入之和（淨流量）均為0，然後再設定好目標值的最小化，Excel的Solver就能找到最短路徑。

「最短路徑」與上一篇介紹的「最低運費路徑」，Excel的試算表格或Solver設定幾乎一樣，最大差別是「最短路徑」每一路徑沒有流量限制。下例出自Practical Management Science （Winston and Albright, 2018）第250頁，它共有10個節點，節點間的路徑標示距離。如何從1起點出發到10終點(目地)找到最短路徑??

圖15

如圖15，這10個節點的連結複雜、難理，最短路徑並不容易尋找。檢視路徑箭頭：起點出發箭頭是單向，連結到目地的路徑箭頭也是單向，彼此很靠近的節點路徑才會雙向。

將圖15的每一路徑兩端節點之標號放置到Excel表格，製作「T×4矩陣」，如表12.....第一個欄位是起點，第二個欄位是目地，第三個欄位是距離，第四個欄位是流量 (也是決策變數)。例如：1起點連到2、3、4三個節點目地：

1...2...70....(第四欄位空白)

1...3...63....(第四欄位空白)

1...4...56...(第四欄位空白)

其餘以此類推，藍色數值乃圖15的路徑距離。建置完成即是表12的「T×4矩陣」，接下來設定限制條件，亦即表12粗黑線框起來的區塊，10個節點，只有1與10節點的數值限制為1，前者是outflow = 1，後者inflow = 1，其餘(2-9)都是通過點， net outflow = 0，利用IF指令將outflow或inflow的值加總，使用@SUMIF公式計算：

** 1起點必須有流出量：亦即Outflow = 1，Outflow公式=SUMIF(起點,H17,流量)

** 2-9節點淨流出=0 ： Outflow-Inflow=0， Net Outflow公式 =SUMIF(起點,H6,流量) - SUMIF(目地,H6,流量)

**目地10節點必須有流入量：亦即 Inflow=1，Inflow公式 =SUMIF(目地,H17,流量)

Solver（規劃求解）的最後答案值放在第四欄位，1表示最短路徑經過的路徑，0表示最短路徑不經過的路徑。第三欄位與第四欄位相乘，或是距離與流量相乘，使用@sumproduct就可以算出來全部最短路徑距離，如果第四欄位流量=0，等同距離=0(不經過)距離值不會在目標值出現，這是最短距離，本例Solver（規劃求解）算出的最短距離是198。它經過的路徑是：1->4->6->10，亦即，只經過4、6兩個中間節點就到達目地(最短距離)。