這真的是最快嗎?
這個答案由作業研究的精確演算法(分支定界)算出,每一步都能檢查。下面五項檢查,每一項都可以重跑、可以挑戰。
① 上下界收斂曲線
求解時同時記兩個數字:「目前找到最好的方案要多久」(上界,只會往下降),和「任何方案都不可能比這更快」(下界,只會往上升)。兩條線碰在一起,就是證明,不是猜測。
模擬 · 合成損傷圖 · 種子 5 · 搶修機具 3 組、排爆 1 組 · 挖土機 3・裝載機 3・卡車 6・攪拌車 3・掃道車 1・勘災無人機 2 · 分支定界:155 個位置中完整計算 20 個
數據表
| # | 上界:目前最好的方案 | 下界:不可能更快 |
|---|
| 0 | — | 1 小時 28 分 |
| 1 | 1 小時 54 分 | 1 小時 28 分 |
| 2 | 1 小時 54 分 | 1 小時 28 分 |
| 3 | 1 小時 54 分 | 1 小時 31 分 |
| 4 | 1 小時 32 分 | 1 小時 31 分 |
| 5 | 1 小時 32 分 | 1 小時 31 分 |
| 6 | 1 小時 32 分 | 1 小時 31 分 |
| 7 | 1 小時 32 分 | 1 小時 31 分 |
| 8 | 1 小時 32 分 | 1 小時 31 分 |
| 9 | 1 小時 32 分 | 1 小時 31 分 |
| 10 | 1 小時 32 分 | 1 小時 31 分 |
| 11 | 1 小時 32 分 | 1 小時 31 分 |
| 12 | 1 小時 32 分 | 1 小時 31 分 |
| 13 | 1 小時 32 分 | 1 小時 31 分 |
| 14 | 1 小時 32 分 | 1 小時 31 分 |
| 15 | 1 小時 32 分 | 1 小時 31 分 |
| 16 | 1 小時 32 分 | 1 小時 31 分 |
| 17 | 1 小時 32 分 | 1 小時 31 分 |
| 18 | 1 小時 32 分 | 1 小時 31 分 |
| 19 | 1 小時 32 分 | 1 小時 31 分 |
| 20 | 1 小時 31 分 | 1 小時 31 分 |
② 每個位置為什麼不可能更快
每一個可能的起降帶位置都有一個「再怎麼排都不可能更快」的下界,附一句白話理由。灰色長條都高於藍線,所以不必細算;低於藍線的少數位置已完整計算過,也證實不會更快。
模擬 · 合成損傷圖 · 種子 5 · 搶修機具 3 組、排爆 1 組 · 挖土機 3・裝載機 3・卡車 6・攪拌車 3・掃道車 1・勘災無人機 2 · 全部 155 個候選位置的下界
最接近的幾個位置(完整計算)
- 距跑道頭 0–1,500 公尺,偏右 15 公尺最快 1 小時 32 分,比建議方案慢 1 分鐘 · 坑 C8 在未爆彈 U1 的安全範圍內:排爆至少 24 分鐘,再修 67 分鐘,所以不可能早於 1 小時 31 分。另有 5 個相鄰位置要修同樣的坑,結果相同
- 距跑道頭 450–1,950 公尺,偏右 7.5 公尺最快 1 小時 32 分,比建議方案慢 1 分鐘 · 坑 C8 在未爆彈 U1 的安全範圍內:排爆至少 24 分鐘,再修 67 分鐘,所以不可能早於 1 小時 31 分。另有 3 個相鄰位置要修同樣的坑,結果相同
- 距跑道頭 300–1,800 公尺,偏右 15 公尺最快 1 小時 35 分,比建議方案慢 4 分鐘 · 坑 C8 在未爆彈 U1 的安全範圍內:排爆至少 24 分鐘,再修 67 分鐘,所以不可能早於 1 小時 31 分。另有 2 個相鄰位置要修同樣的坑,結果相同
- 距跑道頭 600–2,100 公尺,偏右 15 公尺最快 1 小時 37 分,比建議方案慢 6 分鐘 · 坑 C8 在未爆彈 U1 的安全範圍內:排爆至少 24 分鐘,再修 67 分鐘,所以不可能早於 1 小時 31 分。
- 距跑道頭 650–2,150 公尺,偏右 15 公尺最快 1 小時 37 分,比建議方案慢 6 分鐘 · 坑 C8 在未爆彈 U1 的安全範圍內:排爆至少 24 分鐘,再修 67 分鐘,所以不可能早於 1 小時 31 分。另有 1 個相鄰位置要修同樣的坑,結果相同
- 距跑道頭 1,000–2,500 公尺,沿中線最快 1 小時 38 分,比建議方案慢 7 分鐘 · 這段要先排除 3 枚未爆彈,1 組排爆最快 98 分鐘,合計不可能早於 1 小時 38 分。另有 1 個相鄰位置要修同樣的坑,結果相同
③ 和其他排法比
同一張損傷圖、同樣的人力,照常見的白板做法排,結果如下。再隨機抽 1 萬個可行方案畫成分布:最佳解應該落在最左邊,沒有任何一個方案贏它。
模擬 · 合成損傷圖 · 種子 5 · 搶修機具 3 組、排爆 1 組 · 挖土機 3・裝載機 3・卡車 6・攪拌車 3・掃道車 1・勘災無人機 2 · 四種白板排法,同一張損傷圖、同樣人力
1 萬個隨機可行方案的完成時間
計算中…
④ 兩個獨立求解器互相對答案
網頁裡的求解器之外,另用 Google OR-Tools(CP-SAT)從原始幾何重新建模、獨立求解。兩邊答案必須完全一致,這組對照放在自動測試裡,任何程式修改只要對不上就會被擋下來。
- 100 組隨機損傷圖、搶修 1–6 班、排爆 1–2 組:100 組全部一致
- 小題目另以全部排列逐一列舉(暴力法)驗證:一致
- 每個位置的下界都另外驗證「不高於真正的最快時間」
⑤ 假設改變時,答案還成立嗎?
「最佳」只在假設成立時才是最佳。修坑工時、排爆時間、班數都是假設,所以一次改一個,看建議會不會換。
計算中…