人工智慧法於週期性街道樹灑水問題的研究

本研究我們探討週期性街道樹灑水問題（PWSTP），其中多種類型的車輛須定期對街道上不同類型的樹木進行灑水澆灌。根據樹木的不同種類，本文假設了不同澆水頻率，例如每天一次，每兩天一次，每三天一次。本文所探討的PWSTP是週期性車輛路徑問題（PVRP）的擴展問題，而PWSTP的目標是最小化車輛的總路線長度和車輛的成本，使得在六天的時間範圍內滿足所有街道樹木的各種澆灌需求。在本論文中，我們提出了一種新的編碼方法，可將任何隨機的整數序列直接轉換成PWSTP的可行解，然後我們將該新的編碼方法嵌入到免疫演算法和遺傳演算法中來解決PWSTP。最後，我們以越南胡志明市的一個實際問題為例，數值結果顯示，本論文提出的免疫演算法和遺傳演算法可以有效地解決這個PWSTP。此外，對於求解品質而言，免疫演算法優於遺傳演算法，然而，遺傳演算法比免疫演算法更迅速。

關鍵字

灑水問題；演算法；最佳化

並列摘要

In the paper, we investigate the periodic watering street tree problem (PWSTP) in which multiple types of vehicles are scheduled to periodically water different types of trees on the streets. Based upon the types of trees, various frequencies of watering are assumed in this study, for example, once per day, once per two days, and once per three days. The PWSTP is an extended problem of the periodic vehicle routing problem (PVRP) in which vehicles have to periodically deliver goods to multiple demand points. The objective of the considered PWSTP is to minimize the total routing length of vehicles and the cost of vehicles such that various watering demands are satisfied for all streets during the time horizon of six days. In this thesis, we propose a novel coding scheme to directly convert any random sequence of integers into a feasible solution of the PWSTP. The novel coding scheme is then embedded in immune algorithm and genetic algorithm to solve the PWSTP. Finally, a practical case in Ho Chi Minh city, Vietnam, was solved. Numerical results showed that the proposed immune algorithm and genetic algorithm can effectively solve this PWSTP. Additionally, immune algorithm outperforms genetic for solving the PWSTP. However, genetic algorithm is faster than immune algorithm.

並列關鍵字

PWSTP ； algorithm ； optimization

參考文獻

[28] Tran Thi Ngoc Huyen, (2014). “Use of SEM and FCM based approach to investigate User satisfaction towards Electronic document exchange system”, National Formosa University, Master thesis.

[1] Holland, J. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.

[2] Borenstein, Y., Shah, N., Tsang, E., Dorne, R., Alsheddy, A., & Voudouris, C. (2010). “On the portioning of dynamic workforce scheduling problems”, Journal of Scheduling, 13, pp.411 - 425.

[3] Tagmuoti, M., Gendreau, M., & Potvin, J. (2011). “A dynamic capacitated arc routing problem with time dependent service costs”, Transportation Research Part C: Emerging Technologies, 19, pp.20-28.

[4] Stahbock, R., & Voss, R. (2008). “Operation research at container terminals: a literature update”, OR Spectrum, 30, pp. 1-52.

國際替代計量

人工智慧法於週期性街道樹灑水問題的研究

未授權

主題瀏覽