本企劃主要需要進行下列事項:
以下將對這兩項作詳細的敘述。
建立都市交通模型
建立模型前,先考慮一個都市交通模型需要的要素:
首先先考慮前三點,使用有向圖將可模擬這三項要素。點代表路口,兩點間如果有兩條反向的線代表兩個方向的道路,居住地點與工作地點會出現在點上,而通勤者則是一組包含了人數、居住地點與工作地點的資訊。
接下來加入第四個要素,要如何去模擬不同的交通路線?本企劃的作法是使用不同的「圖層」作為不同的交通工具,而轉換交通工具就是連接不同圖層之間的道路。
最後考慮如何去模擬市民上班,首先需要知道每一條路通過所需的時間,於是道路的長度就被設定為通過所需時間。接下來,對第一組計算的通勤者,便可以使用 Dijkstra's Algorithm 去計算最短路徑,即為此組通勤者的合理上班路徑。而當道路的流量增加時,通過道路需要的時間便會加長,所以第二組通勤者是會根據第一組通勤者的路線不同而可能有不同的選擇,一樣選擇當時的最短路徑,依此反覆到最後所有通勤者都選完道路,最後再根據選擇的道路計算實際的時間。
這種選擇方法在現實中是合理的,因為一般人在選擇道路時如果沒有預知能力,那麼通常是依照現在的道路狀況去選擇的,所以會選擇他所看起來所需要時間最短的路徑,當然實際所花費的時間可能與他想像中的不同。
產生隨機地圖
在進行研究時,有時候會需要隨機地圖來做各種模擬的工作。
首先根據城市的大小產生工作地點與上班地點(1:3 的比例),並且加上道路,預設讓每條路都允許行人與汽車通行,這部分我們使用了 Prim's Algorithm 建立最小生成樹來確保地圖的聯通性,再將每個點與其最接近的三個點連接。
接著隨機產生通勤者,人數為 0~511 的簡單隨機分布。
實作GUI
本計劃實作 GUI 有以下兩個部份:
資料結構的部分如同上面模型建構所述,將車站則視為連接不同圖層的道路,把城市化簡為一張立體的有向圖,並且將相同位置道路的擁擠程度紀錄在一起(這部分是考慮到公車與汽車是共用相同的道路)。
最初我們想要用矩陣來儲存資料,卻發現必須存入大量的「0」,造成資料量過於龐大,運算上也沒有想像中的方便,所以最後採用了 Tree 的結構,但本小組無法使用 MATLAB 作出這較複雜的結構,於是就借助 Java 來建立資料結構,此外,使用 HashMap 與 HashSet 加速資料存取;使用 TreeMap 與 TreeSet 加速排序;使用 ArrayList 與 LinkedList 取代陣列以追求更穩定的結構。
而MATLAB的部分則負責了GUI的製作,為了讓製作 GUI 的人員能夠正確使用 Java 所製作的資料結構,製作資料結構時有同時生成 Javadoc供製作 GUI 時參考,這個檔案可以在相關檔案的地方找到。