Object/目的
This is an implementation of a master thesis : "Automatic Metro Map Layout Using Multicriteria Optimization" by Jonathan Stott. In this paper, he proposed using Simulated annealing algorithm to turn geographical coordinate data to metro map.
這是一個實作Jonathan Stott的論文Automatic Metro Map Layout Using Multicriteria Optimization的專案，主要是以模擬退火演算法的概念將地理資料的座標轉換成我們常見的捷運圖。
Criteria of a metro map such as the angle of each lines, the distance of each stations, if the node snap to the grid, the position of the name of the station, line position changes due to overlap...etc. The idea of simulated annealing algorithm is when the particles of a metal vibrate around larger area in high temperature. After some iterations, the temperature goes low and the vibrate area of the particles become smaller, and finally, go into a stable state. This is a way to find better solution but not the best one. Combine those criteria into a scoring function. We move the metro station around the grid map and score the result with the scoring function. After some steps, the movable space of metro station decreased while the layout state is accepted only if the score is higher than previous one. At last, it will reach a stable state.
常見捷運圖的評估方式有：路線的角度，每個站點的距離，是否貼齊在格線上，站名的位置、線段是否因重疊而變更位置等。模擬退火演算法的想法是，在金屬高溫時，分子震動範圍較大，隨著每一次的迭代，溫度逐漸降低，分子震動的範圍小，最後達成一個穩定的型態，來求得一個較佳解，而非最佳解。用模擬退火演算法將捷運圖的各種評估項目設計成一個計分方式，將捷運站點在網格上移動，並以此計分函數評分。隨著迭代次數增加，站點能移動的空間越少，而每次的分數都需比前次好，最後達到一個穩定態產生結果。
Result/結果
The following is the result of Taipei MRT.
以下是拿台北市捷運站的地理資料轉換成捷運圖的結果。
