現今物聯網定位技術主要運用感測器/iBeacon搭配智慧手持裝置來收集室內空間的人潮資訊以提供各種位置感知服務，人潮資訊包含空間人數、移動速度、區域密度等數據，然而現今定位資訊收集僅能提供當前時間的人潮狀態，無法準確預測未來時間的人潮變化。
在本篇論文中，我們採用物聯網定位技術收集使用者所在位置、空間人數和行走距離，以真實室內空間人潮密度數據集為基礎透過深度學習來預測未來時間的人潮變化，並將人潮密度轉換成移動時間以規劃出最短時間移動路線。
就目前所知，所提出方法為第一個能夠針對多重目標地點來預測不同時段之移動時間，進而安排出跨時段之最佳拜訪順序與行走路線的解決方案，實驗結果顯示我們所提出跨時段拜訪行程規劃解決方案優於現有方法，能夠有效減少使用者移動時間，並針對多重目標地點安排最佳拜訪順序與路線。

Internet of Things (IoT) localization technologies employ RFID, iBeacon, and sensors to obtain the crowd information of indoor people. The crowd information includes the number of indoor people, moving speeds, walking directions, and user density in specific areas.
In this work, iBeacon IoT devices are deployed in the indoor space, and Pedestrian Dead Reckoning through the smartphone accelerometer and gyroscope is used to derive continuous user locations based on occasional iBeacon positions. The user position, walking direction, and traveling distance can form a moving trajectory. We propose a visiting trip planning to plan the most efficient visiting order and the fastest walking paths. The proposed framework consists of a deep learning based crowd density prediction model and a time-dependent trip planning algorithm. The open crowd dataset of the Osaka Asia & Pacific Trade Center in Japan are used to evaluate the performance of existing works and ours.
Experimental results show that our framework outperforms existing methods and can accurately predict the future crowd density of indoor people. In particular, our framework determines the optimal visiting order of target places based on the predicted crowd density and can significantly reduce the total moving time in the entire visiting trip with multiple target places.

誌謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 論文架構 3
第二章 相關研究 4
2.1 空間預測模型(Spatial Prediction Model) 5
2.2 拜訪行程規劃(Visiting Trip Planning) 6
第三章 系統架構 9
第四章 拜訪行程規劃解決方案 11
4.1 密集卷積網路 11
4.2 人潮密度預測 14
4.2.1數據處理層 14
4.2.2密集卷積層 17
4.2.3時空融合層 18
4.3 跨時段行程規劃 20
第五章 效能評估 24
5.1 人潮預測效能分析 24
5.2 跨時段拜訪行程效能分析 26
第六章 結論 30
參考文獻 31

[1]S. P. Hoogendoorn and W. Daamen, “Design Assessment of Lisbon Transfer Stations using Microscopic Pedestrian Simulation,” WIT Transactions on The Built Environment, vol. 74, pp. 135-147, May 2004.
[2]D. Helbing and A. Johansson, “Pedestrian, Crowd and Evacuation Dynamics,” Encyclopedia of Complexity and Systems Science., vol. 16, pp. 6453-6495, Sep. 2013.
[3]A. Panangadan, M. Mataric, and G. Sukhatme, “Detecting Anomalous Human Interactions Using Laser Range-Finders,” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2136-2141, Oct. 2004.
[4]I. Bisio, M. Cerruti, F. Lavagetto, M. Marchese, M. Pastorino, A. Randazzo, and A. Sciarrone, “A Trainingless WiFi Fingerprint Positioning Approach Over Mobile Devices,” IEEE Antennas and Wireless Propagation Letters, vol. 13, pp. 832-835, Apr. 2014.
[5]Y. Kim, Y. Chon, and H. Cha, “Smartphone-Based Collaborative and Autonomous Radio Fingerprinting,” IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 42, no. 1, pp. 112-122, Dec. 2010.
[6]P. Martin, B. Ho, N. Grupen, S. Munoz, and M. Srivastava, “Demo Abstract: An iBeacon Primer for Indoor Localization,” Proceedings of the 1st ACM Conference on Embedded Systems for Energy-Efficient Buildings, pp. 190-191, Nov. 2014.
[7]J. Rezazadeh, R. Subramanian, K. Sandrasegaran, X. Kong, M. Moradi, and F. Khodamoradi, “Novel iBeacon Placement for Indoor Positioning in IoT,” IEEE Sensors Journal, vol 18, no. 24, pp. 10240-10247, Oct. 2018.
[8]H. Zhao, L. Zhang, S. Qiu, Z. Wang, N. Yang, and J. Xu, “Pedestrian Dead Reckoning Using Pocket-Worn Smartphone,” IEEE Access, vol. 7, pp. 91063-91073, July 2019.
[9]T. Chiang, K. Ou, J. Qiu, and Y. Tseng, “Pedestrian Tracking by Acoustic Doppler Effects,” IEEE Sensors Journal, vol. 19, no. 10, pp. 3893-3901, May 2019.
[10]W. Elloumi, A. Latoui, R. Canals, A. Chetouani and S. Treuillet, ‘‘Indoor Pedestrian Localization With a Smartphone: A Comparison of Inertial and Vision-Based Methods,” IEEE Sensors Journal, vol. 16, no. 13, pp. 5376-5388, July 2016.
[11]S. Yang, L. Ma, S. Jia, and D. Qin, ‘‘An Improved Vision-Based Indoor Positioning Method,” IEEE Access, vol. 8, pp. 26941-26949, Jan. 2020.
[12]R. F. Brena, J. P. García-Vázquez, C. E. Galván-Tejada, D. Muñoz-Rodriguez, C. Vargas-Rosales, and J. Fangmeyer, “Evolution of Indoor Positioning Technologies: A Survey,” Hindawi Journal of Sensors, pp. 1-21 Mar 2017.
[13]L. Zhu, F. R. Yu, Y. Wang, B. Ning, and T. Tang, “Big Data Analytics in Intelligent Transportation Systems: A Survey,” IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 1, pp. 383-398, Jan. 2019.
[14]H. Chen, R. H. L. Chiang, and V. C. Storey, “Business Intelligence and Analytics: from Big Data to Big Impact,” MIS Quarterly, vol. 36, no. 4, pp. 1165-1188, Dec. 2012.
[15]G. Qi, A. Huang, W. Guan, and L. Fan, “Analysis and Prediction of Regional Mobility Patterns of Bus Travellers Using Smart Card Data and Points of Interest Data,” IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 4, pp.1197-1214, Apr. 2019.
[16]S. Fang, L. Lin, Y. Yang, X. Yu, and Z. Xu, “CityTracker: Citywide Individual and Crowd Trajectory Analysis Using Hidden Markov Model,” IEEE Sensors Journal, vol. 19, no. 17, pp. 7693-7701, Sep. 2019.
[17]L. Cai, F. Jiang, W. Zhou, and K. Li, “Design and Application of an Attractiveness Index for Urban Hotspots Based on GPS Trajectory Data,” IEEE Access, vol. 6, pp. 55976-55985, Sept. 2018.
[18]R. Wu, G. Luo, Q. Yang, and J. Shao, “Learning Individual Moving Preference and Social Interaction for Location Prediction,” IEEE Access, vol 6, pp. 10675-10687, Feb. 2018.
[19]J. Qiu, L. Du, D. Zhang, S. Su, and Z. Tian, “Nei-TTE: Intelligent Traffic Time Estimation Based on Fine-Grained Time Derivation of Road Segments for Smart City”, IEEE Transactions on Industrial Informatics, vol. 16, no. 4, pp. 2659-2666, Apr. 2020.
[20]J. Wang, X. Kong, W. Zhao, A. Tolba, Z. Al-Makhadmeh, and F. Xia, “STLoyal: A Spatio-Temporal Loyalty-Based Model for Subway Passenger Flow Prediction”, IEEE Access, vol. 6, pp. 47461-47471, Aug. 2018.
[21]N. Sun, H. Shi, G. Han, B. Wang, and L. Shu, “Dynamic Path Planning Algorithms With Load Balancing Based on Data Prediction for Smart Transportation Systems,” IEEE Access, vol. 8, pp. 15907-15922, Jan. 2020.
[22]E. H. Lu, H. Chen, and V. S. Tseng, “An Efficient Framework for Multirequest Route Planning in Urban Environments,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 4, pp. 869-879, Apr. 2017.
[23]Z. Yu, H. Xu, Z. Yang, and B. Guo, “Personalized Travel Package With Multi-Point-of-Interest Recommendation Based on Crowdsourced User Footprints,” IEEE Transactions on Human-Machine Systems, vol. 46, no. 1, pp. 151-158, Feb. 2016.
[24]S. Jiang, X. Qian, T. Mei, and Y. Fu, “Personalized Travel Sequence Recommendation on Multi-Source Big Social Media,” IEEE Transactions on Big Data, vol. 2, no. 1, pp. 43-56, Mar. 2016.
[25]X. Zhou, M. Su, Z. Liu, and D. Zhang, “Smart Tour Route Planning Algorithm Based on Clustering Center Motive Iteration Search,” IEEE Access, vol. 7, pp. 185607-185633, Dec. 2019.
[26]W. Luan, G. Liu, C. Jiang, and M. Zhou, “MPTR: A Maximal-Marginal-Relevance-Based Personalized Trip Recommendation Method,” IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 11, pp. 3461-3474, Nov. 2018.
[27]X. Zhu, R. Hao, H. Chi, and X. Du, “FineRoute: Personalized and Time-Aware Route Recommendation Based on Check-Ins,” IEEE Transactions on Vehicular Technology, vol. 66, no. 11, pp. 10461-10469, Nov. 2017.
[28]Y. Wen, J. Yeo, W. Peng, and S. Hwang, “Efficient Keyword-Aware Representative Travel Route Recommendation,” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no.8, pp.1639-1652, Aug. 2017.
[29]S. Nutanong, E. Tanin, J. Shao, R. Zhang, and R. Kotagiri, “Continuous Detour Queries in Spatial Networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 24, no.7, pp.1201-1215, July 2012.
[30]D. Brscic, T. Kanda, T. Ikeda, and T. Miyashita, ‘‘Person Tracking in Large Public Spaces Using 3-D Range Sensors”, IEEE Transactions on Human-Machine Systems, vol. 43, no. 6, pp. 522-534, Nov. 2013.
[31]E. W. Dijkstra, “A Note on two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269-271, Dec. 1959.
[32]P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, Jul. 1968.
[33]S. Lin and B. W. Kernighan, “An Effective Heuristic Algorithm for the Travelling-Salesman Problem,” Operations Research, vol. 21, no. 2, pp. 498-516, Mar. 1973.
[34]F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S. H. Teng, “On Trip Planning Queries in Spatial Databases,” Proceedings of the 9th international conference on Advances in Spatial and Temporal Databases, vol. 3633, pp. 273-290, Aug. 2005.
[35]G. Huang, Y. Sun, Z. Liu, D. Sedra, and K. Q. Weinberger, “Deep networks with stochastic depth,” European Conference on Computer Vision, pp. 646-661, Jul. 2016.
[36]G. Larsson, M. Maire, and G. Shakhnarovich, “FractalNet: Ultra-Deep Neural Networks without Residuals,” International Conference on Learning Representations, pp. 1-11, May 2016.
[37]G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger, “Densely Connected Convolutional Networks,” IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2261-2269, July 2017.
[38]P. J. Brockwell and A. D. Richard, “Introduction to Time Series and Forecasting,” Springer Science & Business Media, 2006.
[39]S. Yin, D. Chen, Q. Zhang, M. Liu, and S. Li, “Mining Spectrum Usage Data: A Large-Scale Spectrum Measurement Study,” IEEE Transactions on Mobile Computing, vol. 11, no. 6, pp. 1033-1046, June 2012.
[40]X. Zhang, X. Xie, Y. Wang, X. Zhang, D. Jiang, C. Yu, and Y. Liang, “A Digital Signage Audience Classification Model Based on the Huff Model and Backpropagation Neural Network,” IEEE Access, vol. 8, no. 6, pp. 1033-1046, Apr. 2020.
[41]M. Nielsen, “Neural Network and Deep Learning,” Determination Press, 2015. [Online]. Available: http://static.latexstudio.net/article/2018/0912/neuralnetworksanddeeplearning.pdf.
[42]Z. Fang, S. M. Lo, and J. A. Lu, “On the Relationship Between Crowd Density and Movement Velocity,” International Journal of Fire Safety, vol. 38, no. 3, pp. 271-283, Apr. 2003.
[43]C. Zhang, H. Zhang, D. Yuan, and M. Zhang, “Citywide Cellular Traffic Prediction Based on Densely Connected Convolutional Neural Networks,” IEEE Communications Letters, vol. 22, no. 8, pp. 1656-1659, Aug. 2018.