- 學位論文
以模擬為基礎之基因演算法求解公共電動車系統車輛配置最佳化問題
A Simulation-Based Genetic Algorithm for Solving the Optimal Fleet Allocation Problem in an Electric Vehicle Sharing System
摘要
本研究站在公共電動車系統營運業者立場，求解需求不確定性下之每日營運前各租賃站電動車輛佈署問題，求解目標為系統總成本最小化。本研究發展一基因演算法，結合公共電動車系統模擬程式，在給定的車隊規模下，幫助業者決定每日營運前各個租賃站之最佳車輛配置數。為了測試本研究所發展的公共電動車系統車輛配置演算法應用於不同問題規模大小之績效，本研究以日月潭風景區電動車共享系統為參考對象，將其延伸成不同租賃站數與車隊規模之各種情境，產生多組測試例題，比較所發展之基因演算法與窮舉法之求解效能與效率。實驗結果發現，基因演算法求解效能良好，所有測試例題均可求得最佳解或近似最佳解且求解穩定度高，70%以上的測試次數均可求得最佳解，無法求得最佳解的測試中，基因演算法求得之目標函數值與最佳解目標函數值之差距也都在1%以內。在求解效率方面，隨著問題規模變大，使用窮舉法需耗費大量的求解時間，相較之下，基因演算法均可以於合理時間內求得最佳解或近似最佳解；特別是在某些大型問題，窮舉法無法於合理時間內求得最佳解，但基因演算法可於合理時間內得到較優解。
並列摘要
This study deals with the electric vehicle (EV) allocation problem in an EV-sharing system with uncertain demand. For a given fleet of electric vehicles, the objective is to determine optimal numbers of EVs in the rental stations of the EV-sharing system so as to minimize the total cost of the system operator. We propose a simulation-based genetic algorithm (GA) to solve this complex problem. A simulator is developed and embedded in the proposed algorithm to evaluate the cost of the EV-Sharing system under a given fleet allocation scheme. To examine the performance of the algorithm, this study conducts a set of computational experiments on various sized problem instances generated based on the EV-Sharing system operated in Sun Moon Lake scenic area. We compare the solutions of the GA with those of an enumeration method. The results show that the GA is effective and efficient on solving the problem. Specifically, the GA is able to obtain an optimal solution for more than 70% of the instances and for those that GA fails to obtain optimal solutions, the deviations of GA’s solutions from optimal solutions are all less than 1%. Moreover, while the computational time of the enumeration method increases dramatically with the size of the problem, GA is able to obtain optimal or close-to-optimal solutions in a reasonable amount of time.