本論文研究救護車之最佳動態區位配置，在需求點全被涵蓋之基本要求下，使得所有需求點獲得最公平救護資源，以達到需求越密集的區域所得到的救護資源相對越多之目標。本研究分成兩大部份：一、預測緊急救護需求量分布，二、建立救護車區位配置模型，根據預測需求量，求出最佳區位配置。對某個時段需求量預測，本研究採用前幾周與前一年同個日期的前後幾周內同個時段的已知需求量，求出平滑平均需求 (smoothed average demand) 來做預測，並同時考慮時段內單位小時的最大需求量，來解決同時間內可能有些區域有較密集的需求量，而需要較多的救護支援之問題。在救護車之動態區位配置，採用一個有效的最適化演算法JPSO (Jumping Particle Swarm Optimization)，求得最佳區位配置。在實驗測試部分，利用新北市消防局提供的2015年救護需求歷史資料，來預測2016年度的救護需求量並求得救護車配置，再與官方現行的救護車配置比較需求之涵蓋率。本研究也將求出的救護車配置對歷史案件做模擬派遣，求得派遣救護車與案件現場的距離，稱之為反應距離，再與官方配置下派遣的救護車之反應距離作比較。

This study considers the two-fold dynamic ambulance allocation problem, which includes forecasting the distribution of Emergency Medical Service (EMS) requesters and allocating ambulances dynamically according to the predicted distribution of requesters. EMS demand distribution forecasting is based on on-record historical demands. A multi-objective ambulance allocation model (MOAAM) is then solved by a so-called Jumping Particle Swarm Optimization (JPSO) mechanism according to the forecasted distribution of demands. Experiments were conducted using the recorded historical data for Emergency Medical Service requesters in Banqiao district of New Taipei City, Taiwan, for the years 2015 and 2016. Emergency Medical Services demand distribution for 2016 is forecasted according to the on-record historical demand of 2015. Ambulance allocation for 2016 is then determined based on the forecasted demand distribution. The proposed allocation strategy is compared with the official strategy, in terms of the demand coverage rates of the real demand distribution. A so-called response distance, defined as the distance between the allocation site of the dispatched ambulance and the EMS scene, is used to evaluate and compare the efficiency of the strategies based on different allocations. The experimental results show that the proposed allocation method provides higher demand coverage rates and shorter response distances than the official allocation.

Table of Contents
Chapter 1 Introduction	1
Chapter 2 Block-wise demand forecast	3
2.1 Qradtree Decomposition	3
2.2 Demand forecast	4
2.3 Performance of demand forecast	5
Chapter 3 Ambulance allocation	8
3.1 Covered region of request block by allocation site	8
3.2 Multi-objective ambulance allocation model (MOAAM)	10
3.3 Optimal ambulance allocation solved by PSO	12
Chapter 4 Experimental results	18
4.1 Comparison of demand coverage rates	18
4.2 Simulation of ambulance dispatch	21
Chapter 5 Conclusion and future work	30
References	32

List of Figures
Figure 1. Qradtree decomposition of Banqiao district of New Taipei based on the distribution of demand on 2015	3
Figure 2. Errors (NormRMSE) of forecasted demand for 8-hour periods during the week of 1/4/2016.	6
Figure 3. Errors (NormEP) of forecasted demand for 8-hour periods during the week of 1/4/2016.	7
Figure 4. Covered region by Nanya fire station within 4 minutes	9
Figure 5. Regional coverage rate of each block covered by Nanya fire station whinin 4 minutes	10
Figure 6. Dynamic ambulance allocation result without f4 on 08:00~15:59 1/4/2016	19
Figure 7. Dynamic ambulance allocation result with f4 on 08:00~15:59 1/4/2016	20
Figure 8. Demand coverage rates at 21 time periods during the week of 1/4/2016	21
Figure 9. Ambulance turnaround flowchart	23
Figure 10. Distribution of response distances for ALS cases on 5 random days using (a) official strategy, (b) proposed strategy	29

List of Tables
Table 1. Records of EMS cases from 0:00 to 7:59 on 1/1/2016	22
Table 2. Sequence of states for ambulances during simulation for the first five EMS cases on 1/1/2016	26
Table 3. Response distances (in kilometers) for three different strategies for EMS cases during 0:00 to 7:59 on 1/1/2016	27
Table 4. Average response distances for three strategies for 8-hour periods of 1/1/2016	27
Table 5. Means and standard deviations of response distances for three strategies on 5 random days	28
Table 6. Comparisons of response distance of the strategies for ALS demand	28

[1] L. H. Brown, E. B. Lerner, B. Larmon, T. LeGassick, and M. Taigman, “Are EMS call volume predictions based on demand pattern analysis accurate?” Prehospital Emergency Care, vol. 11, no. 2, pp. 199–203, 2007.
[2] K. Cantwell, A. Morgans, K. Smith, M. Livingston, T. Spelman, and P. Dietze, “Time of day and day of week trends in ems demand,” Prehospital Emergency Care, vol. 19, no. 3, pp. 1–7, 2015.
[3] A. Y. Chen and T.-Y. Lu, “A gis-based demand forecast using machine learning for emergency medical services,” International Conference on Civil and Building Engineering, pp. 1634–1641, 2014.
[4] A. Y. Chen, T.-Y. Lu, M. Huei, M. Ma, and W.-Z. Sun, “Demand forecast using data analytics for the pre-allocation of ambulances,” IEEE Journal of Biomedical and Health Informatics, vol. 20, no. 4, pp. 1178–1187, 2016.
[5] A. Chohlas-Wood, A. Merali, W. Reed, and T. Damoulas, “Mining 911 calls in New York City: Temporal patterns, detection and forecasting.,” 29th AAAI Conference on Artificial Intelligence, (AAAI 2015), Austin, Texas, USA, pp. 4–10, 2015.
[6] N. Channouf, P. L´Ecuyer, A. Ingolfsson, and A. Avramidis, “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.
[7] A. Marcikic and B. Radovanov, “Multivariate models for forecasting demand in ambulance services,” XIV International Symposium SYMORG 2014: New Business Models and Sustainable Competitiveness, A. Marković and S. B. Rakočević, Eds., pp. 768–773, 2014.
[8] H. Setzler, C. Saydam, and S. Park, “Ems call volume predictions: A comparative study,” Computers & Operations Research, vol. 36, no. 6, pp. 1843–1851, 2009.
[9] C. Toregas, R. Swain, C. ReVelle, and L. Bergman, “The location of emergency service facilities,” Operations Research, vol. 19, no. 6, pp. 1363–1373, 1971.
[10] D.-M. Shiah and S.-W. Chen, “Ambulance allocation capacity model,” 9th International Conference on e-Health Networking, Application & Services (HEALTHCOM 2007), pp. 40–45, 2007.
[11] M. Gendreau, G. Laporte and F. Semet, “A dynamic model and parallel Tabu search heuristic for real-time ambulance relocation,” Parallel Computing, vol. 27, no. 12, pp. 1641–1653, 2001.
[12] L. Brotcorne, G. Laporte, and F. Semet, “Ambulance location and relocation models,” European Journal of Operational Research, vol. 147, pp. 451–463, 2003.
[13] R. Church and C. R. Velle, “The maximal covering location problem,” Papers in regional science, vol. 32, no. 1, pp. 101–118, 1974.
[14] M. Gendreau, G. Laporte, and F. Semet, “Solving an ambulance location model by tabu search,” Location Science, vol. 5, no. 2, pp. 75–88, 1997.
[15] M. S. Daskin, “A maximum expected covering location model: Formulation, properties and heuristic solution,” Transportation Science, vol. 17, no. 1, pp. 48–70, 1983.
[16] R. McCormack and G. Coates, “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, no. 1, pp. 294–309, 2015.
[17] H. Toro-DíAz, M. E. Mayorga, S. Chanta, and L. A. Mclay, “Joint location and dispatching decisions for emergency medical services,” Computers & Industrial Engineering, vol. 64, no. 4, pp. 917–928, 2013.
[18] H. M. Rabie, I. El-Khodary, and A. A. Tharwat, “Applying particle swarm optimization for the absolute p-center problem,” International Journal of Computer and Information Technology, vol. 2, no. 5, pp. 1010–1015, 2013.
[19] W. L. W. Hatta, C. S. Lim, A. F. Z. Abidin, M. H. Azizan, and S. S. Teoh, “Solving maximal covering location with particle swarm optimization,” International Journal of Engineering and Technology, vol. 5, no. 4, pp. 3301–3306, 2013.
[20] R. A. Finkel and J. L. Bentley, “Quad trees: A data structure for retrieval on composite keys,” Acta Informatica, vol. 4, no. 1, pp. 1–9, 1974.
[21] F. Olken and D. Rotem, “Sampling from spatial databases,” Ninth International Conference on Data Engineering, pp. 199–208, 1993.
[22] Mapzen. Isochrone service API reference, used on July 25, 2017 from https://mapzen.com/documentation/mobility/isochrone/api-reference/
[23] J. Kennedy and R. Eberhart, “Particle swarm optimization,” IEEE International Conference on Neural Networks, Perth, Australia, pp. 1942–1948, 1995. doi:10.1109/ICNN.1995.488968.
[24] F. J. M. García and J. A. M. Pérez, “Jumping frogs optimization: A new swarm method for discrete optimization,” Technical Report DEIOC 3/2008, Dept. of Statistics, O.R. and Computing, Univ. of La Laguna, Tenerife, Spain, 2008.
[25] S. Balaji and N. Revathi, “A new approach for solving set covering problem using jumping particle swarm optimization method,” Natural Computing, pp. 1–15, 2015.