早期救護車配置相關研究大都是以解決「集合涵蓋問題」（Set covering problems, SCO）[4]為主，尋求可以涵蓋最多需求量的配置策略。配置方式大都考慮單位區域人口數或過去的救護案件量或預測的救護案件量，救護車配置地點大都是限制在某些特定地點，比如新北市救護車只配置在消防分隊內。這樣的配置限制，對於離消防分隊較遠的地點無法得到有效的救護服務，配置結果比較無法達到公平的資源分布。
　　本研究有兩部分, 第一部分旨在提出一個救護車動態配置，即每一固定時段根據需求分布重新計算配置之方法，而且任何一點都是可能的配置位置，而非只限制在消防分隊內。提出的配置方法除了讓救護車的涵蓋範圍能達到最大化，還期望每個需求點得到的救護服務能最平均。此部分我們假設需求分布已事先預測出來。第二部分旨在提出一個能讓救護車在兩個連續時段的配置位置能迅速移動的方法，也就是對兩個連續時段的兩組配置位置做匹配，使得新舊時段匹配點距離和能最小化。如此所有救護車從一個時段的配置位置移動至下一個時段的配置位置之總移動距離，可期望達到最小化。

Most early research on ambulance allocation focus on the solutions to the Set COvering problems (SCO) [4], seeking an allocation strategy that achieves the maximal coverage of demand. The allocation strategies are generally based on the population density distribution, the historical demand distribution, or a predicted demand distribution. In most related research or real cases, candidate locations for ambulance allocation sites are restricted to certain locations. For example, the ambulances owned by the New Taipei City government can be deployed in the fire branches only. However, this restriction might cause unfair distribution of resources, namely, some demand points gain much more ambulance service than others.
	The paper will consist of two parts: ambulance allocation and matching between two sets of allocation locations. For the first part, we focus on dynamic allocation or regular periodical allocation, considering all points as candidate allocation locations rather than merely the fire stations. We use a genetic algorithm to find the best allocation based on the criterion of fairness and according to the predicted demand distribution, which is assumed being available. For the second part, the best matching between two sets of allocation locations for two consecutive periods is searched, so that ambulances can efficiently move from one period to the next period. That is, we tend to a match between two sets of locations so that the total displacement of ambulances is minimized.

目錄
第一章 緒論	1
第二章 配置方法	4
2.1 積分影像	4
2.2 問題定義	5
2.3配置問題模式	9
2.4 以基因演算法求解配置問題	11
2.4.1 複製運算	12
2.4.2 交配運算	12
2.4.3 突變運算	15
第三章 配置點最佳匹配法	19
3.1 匈牙利演算法	20
3.2 貪婪搜尋法	23
第四章 實驗結果	28
第五章 結論	39
參考文獻	40
附錄：英文論文 43

圖目錄
圖 1  矩陣IntA 為矩陣A的積分影像 4
圖 2  需求點分布矩陣Dmd	5
圖 3  服務涵蓋矩陣SrvCvg1 (r = 1) 6
圖 4  服務涵蓋矩陣SrvCvg2 (r = 2) 6
圖 5  救護車配置矩陣SrvAlc 7
圖 6  服務指數矩陣GainedSrv 8
圖 7  染色體C的2×n矩陣表示法 12
圖 8  單點交換示意圖，zpi為親代、tci為中間產出序列、zci為子代 13
圖 9  merge演算法 14
圖 10  兩個親代中前半子序列和整體的crossover範例 15
圖 11  Mutation-on-αj演算法 16
圖 12  親代中前半子序列的基因之mutation範例(k < j) 17 
圖 13  親代中前半子序列的基因之mutation範例(k > j) 18
圖 14  親代中後半子序列的基因之mutation範例 18
圖 15  八個城市間的距離表格 20
圖 16  (a) Step 1 結果 (b) Step 2結果 (c) Step 3結果 (d) Step 4結果 (e) Step 4結果 (f) Step 3結果 (g) Step 4結果 (h) Step 4結果 (i) Step 3結果 (j) 匹配矩陣Mat 22
圖 17  貪婪搜尋配置演算法 24
圖 18  距離矩陣Dt 25
圖 19  貪婪搜尋法求得的匹配矩陣Mat (a)由上而下掃描每列，(b)由下而上掃描每列，(c)由左而右掃描每行，(d)隨機列順序(2, 1, 3, 4)掃描每列 25
圖 20 (a)(b)權重設定為w1= 1、w2 = 0.975、w3 = 1、w4 = 0.5、w5= 0.5的配置結果 29
圖 21 (a)(b)權重w2設定為0的配置結果	30
圖 22 (a)(b)權重w3設定為0的配置結果	31
圖 23 (a)(b)權重w4設定為0的配置結果	32
圖 24 (a)(b)權重w5設定為0的配置結果	33
圖 25 (a)匈牙利演算法得到的匹配結果(Q = 15) (b)貪婪演算法(w = 0.55)得到的匹配結果(Q = 15)	37
圖 26 (a)貪婪演算法(w = 0.55)得到的匹配結果(Q = 80) (b)匈牙利演算法得到的匹配結果(Q = 80)	38

表格目錄
表格 1  貪婪搜尋法效能評估	27
表格 2  貪婪演算法的結果與計算時間與匈牙利演算法比較 (Q = 15)	35
表格 3  貪婪演算法的結果與計算時間與匈牙利演算法比較 (Q = 80)	36

[1] 黃國平、吳青翰. 緊急醫療救護系統資源配置及績效評估之模擬研究－以台南市為例. 台灣衛誌, 26(3), pp. 184-195, 2007.
[2] Aickelin, U., “An indirect genetic algorithm for set covering problems,” Journal of the Operational Research Society, vol. 53, pp. 1118–1126, 2002.
[3] Alessandrini, E., Sajani, S. Z., Scotto, F., Miglio, R., Marchesi, S., and Lauriola, P., “Emergency ambulance dispatches and apparent temperature: a time series. analysis in Emilia-Romagna,” Italy. Environ Res, vol. 111, pp. 1192–1200, 2011.
[4] Aytug, H. and Saydam, C., “Solving large-scale maximum expected covering location problems by genetic algorithms: a comparative study,” European Journal of Operational Research, vol. 141, pp. 480–494, 2002.
[5] Beraldi, P. and Bruni, M.- E., “A probabilistic model applied to emergency service vehicle location,” European Journal of Operational Research, vol. 196, pp. 323–331, 2009.
[6] Brown, L. H., Lerner, E. B., Larmon, B., LeGassick, T., and Taigman, M., “Are EMS call volume predictions based on demand pattern analysis accurate?,” Prehospital Emergency Care, vol. 11, no. 2, pp. 199–203, 2007.
[7] Cantwell, K., Morgans, A., Smith, K., Livingston, M., Spelman, T., and Dietze, P., “Time of day and day of week trends in EMS demand,” Prehospital Emergency Care, vol. 19, no. 3, pp. 425–431, 2015.
[8] Channouf, N., L’Ecuyer, P., Ingolfsson, A., and Avramidis, A. N., “The application of forecasting techniques to modeling emergency medical system calls in calgary, alberta”, Health care management science, vol. 10, no. 1, pp. 25–45, 2007.
[9] Chen, A.- Y., Lu, T.-Y., Ma, M. H.- M., and Sun, W.-Z., “Demand forecast using data analytics for the pre-allocation of ambulances,” IEEE Journal of Biomedical and Health Informatics, pp. 1178–1187, 2015.
[10] Chohlas-Wood, A., Merali, A., Reed, W., and Damoulas, T., “Mining 911 calls in New York City: Temporal patterns, detection and forecasting,” 29th AAAI Conference on Artificial Intelligence, Austin, Texas, USA, pp. 4–10, 2015.
[11] Gendreau, M., Laporte, G., and Semet, F., “Solving an ambulance location model by tabu search. Location Science,” Location Science, vol. 5, pp. 75–88, 1997.
[12] Huang, C.- Y. and Wen, T.- H., “Optimal installation locations for automated external defibrillators in Taipei 7-Eleven stores: using GIS and a genetic algorithm with a new stirring operator,” Computational and Mathematical Methods in Medicine, pp. e241435, 2014.
[13] Kuhn, H. W., “The Hungarian Method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, pp. 83–97, 1955.
[14] Li, X., Zhao, Z., Zhu, X., and Wyatt, T., “Covering models and optimization techniques for emergency response facility location and planning: A review,” Mathematical Methods of Operations Research, vol. 74, pp. 1–30, 2011.
[15] McCormack, R. and Coates, G., “A simulation model to enable the optimization of ambulance fleet allocation and base station location for increased patient survival,” European Journal of Operational Research, vol. 247, pp. 294–309, 2015.
[16] Munkres, J., “Algorithms for the Assignment and Transportation Problems,” Journal of the Society for Industrial and Appied Mathematics, vol. 5, pp. 32–38, 1957.
[17] Rajagopalan, H. K., Saydam, C., and Xiao, J., “A multiperiod set covering location model for dynamic redeployment of ambulances,” Computers and Operations Research, vol. 35, no. 3, pp. 814-826, 2008.
[18] Sasaki, S., Comber, A., Suzuki, H., and Brunsdon, C., “Using genetic algorithms to optimise current and future health planning - the example of ambulance Locations,“ International Journal of Health Geographics, vol. 9, no. 1, pp. 4, 2010.
[19] Shariff, S.- S. R., Moin, N.- H., and Omar, M., “Location allocation modeling for healthcare facility planning in Malaysia,” Computers and Industrial Engineering, vol. 62, pp. 1000–1010, 2012.
[20] Toregas, C., Swain, R., ReVelle, C., and Bergman, L., “The location of emergency service facilities,” Operations Research, vol. 19, pp. 1363–1373, 1971.
[21] Toro-Díaz, H., Mayorga, M.- E, Chanta, S., and McLay, L.- A., “Joint location and dispatching decisions for emergency medical services,” Computers & Industrial Engineering, vol. 64, pp. 917–928, 2013.
[22] Tsai, Y.-S., Ko, P.- C.- I., Huang, C.-Y., and Wen, T.-H., “Optimizing locations for the installation of automated external defibrillators (AEDs) in urban public streets through the use of spatial and temporal weighting schemes,” Applied Geography, vol. 35, no. 1, pp. 394–404, 2012.
[23] Yin, P. and Mu, L., “Modular capacitated maximal covering location problem for the optimal siting of emergency vehicles,” Applied Geography, vol. 34, pp. 247-254, 2012.
[24] Zarandi, M.- H.- F., Davari, S., and Sisakht, S.- A.- H., “The large-scale maximal covering location problem,” Mathematical and Computer Modelling, vol. 57, pp. 710–719, 2013.