【演算法】最佳化運輸問題

[平衡運輸問題的模型]

Min z : 目標式　　st. : 限制式
c : 成本　　x : 運輸量　　
a : 供給量　b : 需求量　　n : 需求點個數　　m : 供給點個數

註：若c = -1即該運輸路線為否

[演算法]
1. 判斷運輸問題是否為平衡模式checkBalacne()，若否則增加虛擬站點(供給/需求) addVP(diff)

2. 宣告並且建立矩陣 Cost, Solution (Col = 需求 + 1, Row = 供給 + 1) , Checking (Col,Row)

3. 填入成本值至Cost矩陣內

4. 填入需求量與供給量至 Cost, Solution矩陣

5. 以西北角法 northwest() 初始化基礎可行解 (Basic Solution)
　a. 從矩陣的左上角開始，分配最大的配送量 maxQuota(remainQuota, remainDemand)，記錄至Solution 矩陣 [setSolution(col,row,value,ref_array)]
　b. if 供給量全分配完 then 往下移一格設定最大的配送量 maxQuota()，記錄至Solution 矩陣 [setSolution()]，else 跳至 c
　c. 往右移一格，設定最大的配送量 maxQuota()，記錄至Solution 矩陣 [setSolution()]
　d. 重覆 b 和 c 的步聚，直至分配

6. 空格改進指數計算 (閉回路法)
　a. Search Solution 中的空格位置，searchNull(array,col,row) : array[x,y]
　b. for (i = 0:array.length) {
　　計算檢驗值 calCheckValue(array[i], cost) => Checking
　　
　}

7. 改進調運方案
　a. Search Checking的最小值，取得x,y值
　b. Search Solution 在回路內負號的最少值 adjustment = min(左上,右下)
　c. Solution[x,y] = adjustment
　d. Solution[x,y-1 or y+1] = Solution[x,y-1 or y+1] - adjustment
　e. Solution[x-1 or x+1,x] = Solution[x-1 or x+1,x] - adjustment
　f. Solution[x-1 or x+1,y-1 or y+1] = Solution[x-1 or x+1,y-1 or y+1] + adjustment

8. 重覆步驟6，計算檢驗值

9. if 所有Checking >= 0 then Solution 為最佳解，else 重覆 7、8步