Travel Scheduling Problem

[ 作業研究期末專案 ] 臺灣環島旅行規劃問題

Language : python
Package : pulp
main file : project_code.ipynb (主要程式碼說明)

定義問題

預設環島方式為開車，並且環島過程需要經過臺灣本島的每一個城市，因此將開車總距離作為環島旅行之成本考量，規劃出整趟環島旅行從嘉義火車站出發並於旅行者有預算限制下找出讓旅行者有最大滿意度的情況。

使用方法

此次專案使用線性規劃(Linear Programming) 問題來解決，期望在特定的預算限制下，找到使用者的最大滿意度，換言之「臺灣環島旅行規劃問題」是個目標式為最大化滿意度的問題，其限制式為使用者給的汽車油費預算，而決策變數則為景點與景點之間的路徑。

模型訂定

以下為線性規劃問題之模型訂定與公式解釋，式 1 為目標式，其餘的式 2~9 皆為限制式：

式 1：線性規劃中的目標式，其中𝑆𝑗為 j 地的滿意度，目標為加總求得最大的滿意度。

式 2：從景點 i 到所有景點的總和必須小於等於 1，若加總等於 0，則代表最後路線沒有從這個景點出發，若等於 1，則表示最後路線有從這個景點出發。

式 3：所有景點抵達景點 i 的總和必須小於等於 1，若加總等於 0，代表最後路線沒有抵達過此景點，若等於 1，則代表最後路線有抵達過此景點。

式 4：對於每個景點來說，有抵達此景點就會有從此景點出發，如果沒有抵達此景點，也就不會有從此景點出發的值，因此兩個值相減必為 0。

式 5：由於前提假設為環島路線必會經過每個縣市，且縣市之間具有順序性，環島一圈 後最後也會回到同個地點，如果縣市 A 必有條路徑是通往縣市 B，則在縣市 A 內所有景點到縣市 B 所有景點的路線加總必為 1，代表只有一條路可以通往 B 縣市，且縣市 A 只會進入縣市 B 一次。

式 6：除了縣市 A 內的景點外，所有其它縣市景點抵達縣市 B 的景點必為 0，以確保縣市之間旅遊的順序性。

式 7：在一公升汽油可跑 *11.6 公里，每公升 98 汽油 30 元的假設下，所有經過的景點路線距離加總必須小於使用者所輸入的價格限制。

備註 : 11.6 公里為 Mercedes-Benz，型號 GLC300 4Matic Coupe 汽油款的高速油耗，資料來源為能源局 2019 年 8 月份油耗測試的 2019 年 8 月進口小客車耗能證明核發資料 : 參考網址

式 8：為了避免縣市內的景點自成迴圈路徑，因此設定縣市內的景點限制從 2 ~(n-2) 個景點，使這些景點不能自成迴圈，因為有兩個景點會跨縣市，一個出去現在的縣市，一個進來此縣市，因此將上限設置在(n-2)。

分析結果

• 預算充足 : 12649 元

  • 繞完全臺灣 81 個景點
  • 總距離 4068.6公里
  • 最大滿意度 417

• 預算不足 : 2192 元

  • Program: Infeasible

• 預算有限 : 5916 元

  • 74 個景點
  • 總距離 2265.6 公里
  • 最大滿意度 399