應用非支配排序簡化群體演算法佈署電動機車電池交換站選址系統

Non-dominated Sorting Simplified Swarm Optimization for Deploying Electric Scooter Battery-Swapping Location System

姚思微(Szu-Wei Yao)

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/碩士(2019年)

摘要

電動車能源補充站設置為一設施選址問題，已有許多學者研究相關領域。由於台灣地狹人稠的特點，以短距離移動的電動機車較廣為使用，而非多數國家以電動汽車為主；其次，台灣電動機車市場主要以電池交換方式補充能源，非多數國家以電池充電方式補充能源。因台灣的環境與國外推動電動車的國家有很大差異，無法將先前學者研究之模型套用於台灣電動車能源補充站選址系統。
此外，多數探討電動車能源補充站選址之研究著重於量化因素或質化因素單一面向，量化因素如成本最小化、服務能力最大化等，質化因素如基礎建設的狀況、當地人口密度等，較少研究同時考慮電動車能源補充站選址的量化與質性因素，以讓選址決策考慮更加全面。
為解決上述問題，本研究建構一符合台灣型態之電動機車電池交換站設施選址模式，並同時考慮量化與質化因素之多目標問題。由於電動機車電池交換站選址為一NP-hard問題，本研究以非支配排序簡化群體演算法（Non-dominated sorting simplified swarm optimization, NSSSO）佈署電動機車電池交換站選址系統，為產生可行解本研究提出兩項修復機制，以增加演算法的搜索能力，並與多目標進化式演算法中的非支配排序遺傳演算法（Non-dominated sorting genetic algorithm II, NSGAII）、非支配排序粒子群演算法（Non-dominated sorting particle swarm optimization, NSPSO）相互競爭。實驗結果顯示，本研究之方法所得到解的品質與運算時間皆有不錯的表現。

關鍵字

電動機車 ； 電池交換站 ； 簡化群體演算法 ； 非支配排序演算法 ； 有限容量設施選址

並列摘要

The setting of the electric vehicle battery energy supplement station is a facility location problem, and many scholars have made relevant research. Taiwan, is a small island, which has high population density, offers people busy transport network. Especially, electric scooter is more common than electric vehicle in Taiwan. Most of electric scooters in Taiwan use battery swapping station to supplement the electric scooters which is different from other counties use battery charging station to supplement electric vehicles.
Moreover, there is less study combine both quantitative factors and qualitative factors simultaneously to optimize battery energy supplement stations location problem. However, selecting the battery energy supplement station location in quantitative and qualitative factors will be more comprehensive.
To solve above problems, the research considers capacity constraint to fit the model in the electric scooter industry of Taiwan. Moreover, the research also considers quantitative and qualitative factors simultaneously to optimize battery swapping station location problem. Since the electric scooter battery swapping station located is an NP-hard problem, the research uses Non-dominated Sorting Simplified Swarm Optimization (NSSSO) to solve multi-objective battery swapping station location problem. Furthermore, for yielding feasible solutions, two repairer mechanisms are proposed to enhance searching efficiency. By comparing to Non-dominated Sorting Genetic Algorithm II (NSGAII) and Non-dominated Sorting Particle Swarm Optimization (NSPSO), numerical results show that NSSSO performs well in terms of solution quality and computational time.

並列關鍵字

Electric Scooter ； Battery Swapping Station ； Simplified Swam Optimization ； Non-dominated Sorting Algorithm ； Capacity Facility Location

參考文獻

[1] C. C. Chan, "The state of the art of electric, hybrid, and fuel cell vehicles," Proceedings of the IEEE, vol. 95, no. 4, pp. 704-718, 2007.

[2] Z. Liu, F. Wen, and G. Ledwich, "Optimal planning of electric-vehicle charging stations in distribution systems," IEEE Transactions on Power Delivery, vol. 28, no. 1, pp. 102-110, 2013.

[3] A. Ip, S. Fong, and E. Liu, "Optimization for allocating BEV recharging stations in urban areas by using hierarchical clustering," in Advanced Information Management and Service (IMS), 2010 6th International Conference on, IEEE, pp. 460-465, 2010.

[4] H. Gavranović, A. Barut, G. Ertek, O. B. Yüzbaşıoğlu, O. Pekpostalcı, and Ö. Tombuş, "Optimizing the electric charge station network of EŞARJ," Procedia Computer Science, vol. 31, pp. 15-21, 2014.

[5] Z. Tang, C. Guo, P. Hou, and Y. Fan, "Optimal siting of electric vehicle charging stations based on voronoi diagram and fahp method," Energy and power Engineering, vol. 5, no. 04, pp. 1404, 2013.