Publications-Theses
Article View/Open
Publication Export
-
題名 利用資料驅動方法解決汽車服務系統的位區途程問題
A data driven approach for solving the location-routing problem in vehicle service systems作者 林育丞
LIn, Yu-Cheng貢獻者 洪英超
Hung, Ying-Chao
林育丞
LIn, Yu-Cheng關鍵詞 位區途程問題
電動汽車充電設施
平均反應時間
等候理論
交通繁忙定理
有尺寸限制的分群問題
Location-routing problem
EV charging infrastructure
Mean response time
Queueing system
Heavy traffic approximation
Clustering with size constraints日期 2019 上傳時間 5-Sep-2019 15:41:29 (UTC+8) 摘要 汽車在行駛過程中會不斷消耗能源，由於車內能裝載的能源容量有限，且我們期望當有服務需求時，盡量縮短服務的花費時間，因此開發用於汽車服務系統的位區途程策略（Location-Routing Problem, LRP）是目前一項重要的目標。本文為第一篇利用資料驅動方法結合統計機器學習的概念來解決這個既重要又複雜的數學問題，我們介紹了如何在一固定區域內，以服務需求地點根據服務需求的歷史資料來建構尋找位區途程策略，找到最佳路由策略與最佳設施位置，並達成極小化平均反應時間（包含平均移動時間、平均等待時間、平均服務時間）的目標。，其中反應時間可拆解為三階段：移動時間、等待時間和服務時間。在交通繁忙定理與穩定性條件下，若服務需求地點夠多時，結果顯示此最佳化問題可近似於有各群點數限制之“K-medoids”分群問題，其中的中心點為服務設施位置，而分群結果即為路由策略，位於群內的服務需求地點會被路由策略引導至位於群中心的服務設施。然而此解決此分群問題並不是件容易的事，因為考慮的是-norm且穩定性條件限制了各群內的點數多寡，這是由於服務站會受到先天條件的限制，使各服務站的服務量多寡不一。為了解決此問題，我們設計了兩個演算法，一個是利用梯度下降法尋找最佳服務設施位置，另一個調整群內點數以達到穩定性條件。此外，此外，藉由由電腦模擬結果可得知當車速不超過某一臨界值時，不同分佈的服務需求地點與不同分配的服務需求間隔時間，皆可找出最佳的服務設施地點與對應的最佳路由策略。
Developing efficient routing strategies for vehicles as well as determining the optimal facility (such as the gasoline or charging station) locations is an important component of the service infrastructure. In this thesis, we introduce a location-routing problem for a general vehicle service system with stochastic demand arrivals and locations. The objective is to find the optimal routing strategy and the facility locations so as to minimize the mean response time (including travel, waiting and service time) of demands under some regulation conditions. Specifically, we have shown that under the stability and heavy traffic assumption, the optimization problem can be approximately formulated as a well-known K-medoids clustering problem based on a fairly large number of observed demand data. With such a formulation, a data driven approach is then proposed to estimate the “medoids” that correspond to the optimal facility locations, while the associated clustering boundaries constitute a routing strategy that directs the within-cluster demands (i.e. demands in a sub-region) to the service station located at the medoid. However, solving the clustering problem is not an easy task since the L2-norm distance is considered and a size constraint is placed on each cluster by the stability assumption. In order to solve the desired clustering problem with size constraints, we have introduced two algorithms – one is designed based on gradient search for finding the medoids and the other is designed for adjusting the cluster size so as to meet the constraint. In addition, computer simulations show promising results for systems with various demand inter-arrival time distributions and demand location densities when the vehicle speed is not particularly fast.參考文獻 [1] P. Hertzke, N.Müller, S. Schenk, and T. Wu.(2018) The global electric-vehicle market is amped up and on the rise. [Online]. Available: https://www.mckinsey.com/industries/automotive-and-assembly/our-insights/the-global-electric-vehicle-market-is-amped-up-and-on-the-rise[2] C. Luo, Y. F. Huang, and V. Gupta, “Placement of EV charging stations-balancing benefits among multiple entities,” IEEE Transactions on Smart Grid, vol. 8, no. 2, pp. 759-768, 2017.[3] R. Mehta, D. Srinivasan, A. M. Khambadkone, J. Yang, and A. Trivedi, “Smart charging strategies for optimal integration of plug-in electric vehicles within existing distribution system infrastructure,” IEEE Transactions on Smart Grid, vol. 9, no. 1, pp. 299-312, 2018.[4] H. Zhang, S. Moura, Z. Hu, and Y. Song, “PEVfast-charging station siting and sizing on coupled transportation and power networks,” IEEE Transactions on Smart Grid, vol. 9, no. 4, pp. 2595-2605, 2018.[5] T. D. Chen, K. M. Kockelman, and M. Khan, “Locating electric vehicle charging stations: Parking-based assignment method for seattle, washington,” Journal of the Transportation Research Board, vol. 2385, no. 1, pp. 28-36, 2013.[6] A. Y. S. Lam, Y. W. Leung, and X. Chu, “Electric vehicle charging station placement: Formulation, complexity, and solutions,” IEEE Transactions on Smart Grid, vol. 5, no. 6, pp. 2846-2856, 2014.[7] X. Wang, C. Yuen, N. U. Hassan, N. An, and W. Wu, “Electric vehicle charging station placement for urban public bus systems,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 1, pp. 128-139, 2017.[8] Q. Cui, Y. Weng, and C. W. Tan, “Electric vehicle charging station placement method for urban areas,” IEEE Transactions on Smart Grid, 2019, doi: 10.1109/TSG.2019.2907262.[9] Y. Xiong, J. Gan, B. An, C. Miao, and A. L. C. Bazzan, “Optimal electric vehicle charging station placement,” in Proceedings of the 24th International Conference on Artificial Intelligence, Buenos Aires, 2015, pp. 2662-2668.[10] D. Efthymiou, K. Chrysostomou, M. Morfoulaki, and G. Aifantopoulou, “Electric vehicles charging infrastructure location: a genetic algorithm approach,” European Transport Research Review, vol. 9, no. 27, 2017.[11] S. Deb, K. Kalita, and P. Mahanta, “Impact of electric vehicle charging station load on distribution network,” Energies, vol. 11, no. 178, 2018.[12] Z. Jiang, H. Tian, M. J. Beshir, S. Vohra, and A. Mazloomzadeh, “Analysis of electric vehicle charging impact on the electric power grid: Based on smart grid regional demonstration project - Los Angeles,” in Proceedings of the IEEE PES Transmission & Distribution Conference and Exposition-Latin America (PES T&D-LA), Morelia, 2016.[13] W. Khan, F. Ahmad, and M. S. Alam, “Fast EV charging station integration with grid ensuring optimal and quality power exchange,” Engineering Science and Technology, an International Journal, vol. 22, no. 1, pp. 143-152, 2019.[14] Q. Kong, M. Fowler, E. Entchev, H. Ribberink, and R. McCallum, “The role of charging infrastructure in electric vehicle implementation within smart grids,” Energies, vol. 11, no. 3362, 2018.[15] A. Arias, J. D. Sanchez, and M. Granada, “Integrated planning of electric vehicles routing and charging stations location considering transportation networks and power distribution systems,” International Journal of Industrial Engineering Computations, vol. 9, no. 4, pp. 535-550, 2018.[16] R. T. Berger, C. R. Coullard, and M. S. Daskin, “Location-routing problems with distance constraints,” Transportation Science, vol. 41, pp. 29-43, 2007.[17] T. W. Chien, “Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems,” Decision Sciences, vol. 24, pp. 995-1021, 1993.[18] J. Hof, M. Schneider, and D. Goeke, “Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops,” Transportation Research Part B Methodological, vol. 97, pp. 102-112, 2017.[19] Y. C. Hung and G. Michailidis, “Optimal routing for electric vehicle service systems,” European Journal of Operational Research, vol. 247, no. 2, pp. 515-524, 2015.[20] J. Paz, M. Granada-Echeverri, and J. Escobar, “The multi-depot electric vehicle location routing problem with time windows,” International Journal of Industrial Engineering Computations, vol. 9, no. 1, pp. 123-136, 2018.[21] J. Yang and H. Sun, “Battery swap station location-routing problem with capacitated electric vehicles,” Computers and Operations Research, vol. 55, no. C, pp. 217-232, 2015.[22] L. Wang and Y. B. Song, “Multiple charging station location-routing problem with time window of electric vehicle,” Journal of Engineering Science and Technology Review, vol. 8, no. 5, pp. 190-201, 2015.[23] T. Chen, B. Zhang, H. Pourbabak, A. Kavousi-Fard, and W. Su, “Optimal routing and charging of an electric vehicle fleet for high-efficiency dynamic transit systems,” IEEE Transactions on Smart Grid, vol. 9, no. 4, pp. 3563-3572, 2018.[24] W. Yuan, J. Huang, Y. Jun, and A. Zhang, “Competitive charging station pricing for plug-in electric vehicles,” IEEE Transactions on Smart Grid, vol. 8, no. 2, pp. 627-639, 2017.[25] Y. Marinakis (2008) Location Routing Problem. In : Floudas C., Pardalos P. (eds) Encyclopedia of Optimization. Springer, Boston, MA.[26] B. W. Silverman, Density Estimation for Statistics and Data Analysis. New York: Chapman and Hall, 1986.[27] Z. Drezner and H. W. Hamacher, Facility location: applications and theory. New York: Springer, 2004.[28] H. Min, V. Jayaraman, and R. Srivastava, “Combined location-routing problems: A synthesis and future research directions,” European Journal of Operational Research, vol. 108, no. 1, pp. 1-15, 1998.[29] C. Ortiz-Astorquiza, I. Contreras, and G. Laporte, “Multi-level facility location problems,” European Journal of Operational Research, vol. 267, no. 3, pp. 791–805, 2018.[30] W. Whitt, “Approximations for the GI/G/m queue,” Production and Operations Management, vol. 2, no. 2, pp. 114–161, 1993.[31] L. Kaufman and P. J. Rousseeuw, Clustering by means of Medoids. Amsterdam: North-Holland, 1987.[32] E. Schubert and P. Rousseeuw, “Faster k-medoids clustering: Improving the PAM, CLARA, and CLARANS algorithms,” arXiv.org, vol. cs.LG, 2018. [Online]. Available: https://arxiv.org/abs/1810.05691[33] S. Lloyd, “Least squares quantization in PCM,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, 1982.[34] J. B. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol.1. Berkeley: University of California Press, 1967, pp. 281–297.[35] C. Lemarecha, “Cauchy and the gradient method,” Documenta Mathematica Extra Volume ISMP, pp. 251–254, 2012.[36] E. Polak, Optimization : Algorithms and Consistent Approximations. New York: Springer-Verlag, 1997. 描述 碩士
國立政治大學
統計學系
106354018資料來源 http://thesis.lib.nccu.edu.tw/record/#G0106354018 資料類型 thesis dc.contributor.advisor 洪英超 zh_TW dc.contributor.advisor Hung, Ying-Chao en_US dc.contributor.author (Authors) 林育丞 zh_TW dc.contributor.author (Authors) LIn, Yu-Cheng en_US dc.creator (作者) 林育丞 zh_TW dc.creator (作者) LIn, Yu-Cheng en_US dc.date (日期) 2019 en_US dc.date.accessioned 5-Sep-2019 15:41:29 (UTC+8) - dc.date.available 5-Sep-2019 15:41:29 (UTC+8) - dc.date.issued (上傳時間) 5-Sep-2019 15:41:29 (UTC+8) - dc.identifier (Other Identifiers) G0106354018 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/125514 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 統計學系 zh_TW dc.description (描述) 106354018 zh_TW dc.description.abstract (摘要) 汽車在行駛過程中會不斷消耗能源，由於車內能裝載的能源容量有限，且我們期望當有服務需求時，盡量縮短服務的花費時間，因此開發用於汽車服務系統的位區途程策略（Location-Routing Problem, LRP）是目前一項重要的目標。本文為第一篇利用資料驅動方法結合統計機器學習的概念來解決這個既重要又複雜的數學問題，我們介紹了如何在一固定區域內，以服務需求地點根據服務需求的歷史資料來建構尋找位區途程策略，找到最佳路由策略與最佳設施位置，並達成極小化平均反應時間（包含平均移動時間、平均等待時間、平均服務時間）的目標。，其中反應時間可拆解為三階段：移動時間、等待時間和服務時間。在交通繁忙定理與穩定性條件下，若服務需求地點夠多時，結果顯示此最佳化問題可近似於有各群點數限制之“K-medoids”分群問題，其中的中心點為服務設施位置，而分群結果即為路由策略，位於群內的服務需求地點會被路由策略引導至位於群中心的服務設施。然而此解決此分群問題並不是件容易的事，因為考慮的是-norm且穩定性條件限制了各群內的點數多寡，這是由於服務站會受到先天條件的限制，使各服務站的服務量多寡不一。為了解決此問題，我們設計了兩個演算法，一個是利用梯度下降法尋找最佳服務設施位置，另一個調整群內點數以達到穩定性條件。此外，此外，藉由由電腦模擬結果可得知當車速不超過某一臨界值時，不同分佈的服務需求地點與不同分配的服務需求間隔時間，皆可找出最佳的服務設施地點與對應的最佳路由策略。 zh_TW dc.description.abstract (摘要) Developing efficient routing strategies for vehicles as well as determining the optimal facility (such as the gasoline or charging station) locations is an important component of the service infrastructure. In this thesis, we introduce a location-routing problem for a general vehicle service system with stochastic demand arrivals and locations. The objective is to find the optimal routing strategy and the facility locations so as to minimize the mean response time (including travel, waiting and service time) of demands under some regulation conditions. Specifically, we have shown that under the stability and heavy traffic assumption, the optimization problem can be approximately formulated as a well-known K-medoids clustering problem based on a fairly large number of observed demand data. With such a formulation, a data driven approach is then proposed to estimate the “medoids” that correspond to the optimal facility locations, while the associated clustering boundaries constitute a routing strategy that directs the within-cluster demands (i.e. demands in a sub-region) to the service station located at the medoid. However, solving the clustering problem is not an easy task since the L2-norm distance is considered and a size constraint is placed on each cluster by the stability assumption. In order to solve the desired clustering problem with size constraints, we have introduced two algorithms – one is designed based on gradient search for finding the medoids and the other is designed for adjusting the cluster size so as to meet the constraint. In addition, computer simulations show promising results for systems with various demand inter-arrival time distributions and demand location densities when the vehicle speed is not particularly fast. en_US dc.description.tableofcontents 第一章 研究動機 1第二章 汽車服務系統與穩定性問題 3第一節 汽車服務系統簡介 3第二節 系統穩定性 5第三章 最佳化問題 8第一節 路由策略 8第二節 位區途程的最佳化問題 10第三節 平均等待時間的估計 13第四節 將位區途程問題轉為分群問題 14第五節 設施地點成本和資源配置上限之考量 20第四章 電腦模擬 22第一節 均勻分配之需求地點分佈 23一、 需求間隔時間服從伽馬分配 23二、 需求間隔時間服從指數分配 26三、 最佳位區途程策略 28第二節 截斷常態分配之需求地點分佈 30一、 需求間隔時間服從伽馬分配 30二、 需求間隔時間服從指數分配 32三、 最佳位區途程策略 34第五章 結論與探討 37參考資料 39 zh_TW dc.format.extent 2331735 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0106354018 en_US dc.subject (關鍵詞) 位區途程問題 zh_TW dc.subject (關鍵詞) 電動汽車充電設施 zh_TW dc.subject (關鍵詞) 平均反應時間 zh_TW dc.subject (關鍵詞) 等候理論 zh_TW dc.subject (關鍵詞) 交通繁忙定理 zh_TW dc.subject (關鍵詞) 有尺寸限制的分群問題 zh_TW dc.subject (關鍵詞) Location-routing problem en_US dc.subject (關鍵詞) EV charging infrastructure en_US dc.subject (關鍵詞) Mean response time en_US dc.subject (關鍵詞) Queueing system en_US dc.subject (關鍵詞) Heavy traffic approximation en_US dc.subject (關鍵詞) Clustering with size constraints en_US dc.title (題名) 利用資料驅動方法解決汽車服務系統的位區途程問題 zh_TW dc.title (題名) A data driven approach for solving the location-routing problem in vehicle service systems en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] P. Hertzke, N.Müller, S. Schenk, and T. Wu.(2018) The global electric-vehicle market is amped up and on the rise. [Online]. Available: https://www.mckinsey.com/industries/automotive-and-assembly/our-insights/the-global-electric-vehicle-market-is-amped-up-and-on-the-rise[2] C. Luo, Y. F. Huang, and V. Gupta, “Placement of EV charging stations-balancing benefits among multiple entities,” IEEE Transactions on Smart Grid, vol. 8, no. 2, pp. 759-768, 2017.[3] R. Mehta, D. Srinivasan, A. M. Khambadkone, J. Yang, and A. Trivedi, “Smart charging strategies for optimal integration of plug-in electric vehicles within existing distribution system infrastructure,” IEEE Transactions on Smart Grid, vol. 9, no. 1, pp. 299-312, 2018.[4] H. Zhang, S. Moura, Z. Hu, and Y. Song, “PEVfast-charging station siting and sizing on coupled transportation and power networks,” IEEE Transactions on Smart Grid, vol. 9, no. 4, pp. 2595-2605, 2018.[5] T. D. Chen, K. M. Kockelman, and M. Khan, “Locating electric vehicle charging stations: Parking-based assignment method for seattle, washington,” Journal of the Transportation Research Board, vol. 2385, no. 1, pp. 28-36, 2013.[6] A. Y. S. Lam, Y. W. Leung, and X. Chu, “Electric vehicle charging station placement: Formulation, complexity, and solutions,” IEEE Transactions on Smart Grid, vol. 5, no. 6, pp. 2846-2856, 2014.[7] X. Wang, C. Yuen, N. U. Hassan, N. An, and W. Wu, “Electric vehicle charging station placement for urban public bus systems,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 1, pp. 128-139, 2017.[8] Q. Cui, Y. Weng, and C. W. Tan, “Electric vehicle charging station placement method for urban areas,” IEEE Transactions on Smart Grid, 2019, doi: 10.1109/TSG.2019.2907262.[9] Y. Xiong, J. Gan, B. An, C. Miao, and A. L. C. Bazzan, “Optimal electric vehicle charging station placement,” in Proceedings of the 24th International Conference on Artificial Intelligence, Buenos Aires, 2015, pp. 2662-2668.[10] D. Efthymiou, K. Chrysostomou, M. Morfoulaki, and G. Aifantopoulou, “Electric vehicles charging infrastructure location: a genetic algorithm approach,” European Transport Research Review, vol. 9, no. 27, 2017.[11] S. Deb, K. Kalita, and P. Mahanta, “Impact of electric vehicle charging station load on distribution network,” Energies, vol. 11, no. 178, 2018.[12] Z. Jiang, H. Tian, M. J. Beshir, S. Vohra, and A. Mazloomzadeh, “Analysis of electric vehicle charging impact on the electric power grid: Based on smart grid regional demonstration project - Los Angeles,” in Proceedings of the IEEE PES Transmission & Distribution Conference and Exposition-Latin America (PES T&D-LA), Morelia, 2016.[13] W. Khan, F. Ahmad, and M. S. Alam, “Fast EV charging station integration with grid ensuring optimal and quality power exchange,” Engineering Science and Technology, an International Journal, vol. 22, no. 1, pp. 143-152, 2019.[14] Q. Kong, M. Fowler, E. Entchev, H. Ribberink, and R. McCallum, “The role of charging infrastructure in electric vehicle implementation within smart grids,” Energies, vol. 11, no. 3362, 2018.[15] A. Arias, J. D. Sanchez, and M. Granada, “Integrated planning of electric vehicles routing and charging stations location considering transportation networks and power distribution systems,” International Journal of Industrial Engineering Computations, vol. 9, no. 4, pp. 535-550, 2018.[16] R. T. Berger, C. R. Coullard, and M. S. Daskin, “Location-routing problems with distance constraints,” Transportation Science, vol. 41, pp. 29-43, 2007.[17] T. W. Chien, “Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems,” Decision Sciences, vol. 24, pp. 995-1021, 1993.[18] J. Hof, M. Schneider, and D. Goeke, “Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops,” Transportation Research Part B Methodological, vol. 97, pp. 102-112, 2017.[19] Y. C. Hung and G. Michailidis, “Optimal routing for electric vehicle service systems,” European Journal of Operational Research, vol. 247, no. 2, pp. 515-524, 2015.[20] J. Paz, M. Granada-Echeverri, and J. Escobar, “The multi-depot electric vehicle location routing problem with time windows,” International Journal of Industrial Engineering Computations, vol. 9, no. 1, pp. 123-136, 2018.[21] J. Yang and H. Sun, “Battery swap station location-routing problem with capacitated electric vehicles,” Computers and Operations Research, vol. 55, no. C, pp. 217-232, 2015.[22] L. Wang and Y. B. Song, “Multiple charging station location-routing problem with time window of electric vehicle,” Journal of Engineering Science and Technology Review, vol. 8, no. 5, pp. 190-201, 2015.[23] T. Chen, B. Zhang, H. Pourbabak, A. Kavousi-Fard, and W. Su, “Optimal routing and charging of an electric vehicle fleet for high-efficiency dynamic transit systems,” IEEE Transactions on Smart Grid, vol. 9, no. 4, pp. 3563-3572, 2018.[24] W. Yuan, J. Huang, Y. Jun, and A. Zhang, “Competitive charging station pricing for plug-in electric vehicles,” IEEE Transactions on Smart Grid, vol. 8, no. 2, pp. 627-639, 2017.[25] Y. Marinakis (2008) Location Routing Problem. In : Floudas C., Pardalos P. (eds) Encyclopedia of Optimization. Springer, Boston, MA.[26] B. W. Silverman, Density Estimation for Statistics and Data Analysis. New York: Chapman and Hall, 1986.[27] Z. Drezner and H. W. Hamacher, Facility location: applications and theory. New York: Springer, 2004.[28] H. Min, V. Jayaraman, and R. Srivastava, “Combined location-routing problems: A synthesis and future research directions,” European Journal of Operational Research, vol. 108, no. 1, pp. 1-15, 1998.[29] C. Ortiz-Astorquiza, I. Contreras, and G. Laporte, “Multi-level facility location problems,” European Journal of Operational Research, vol. 267, no. 3, pp. 791–805, 2018.[30] W. Whitt, “Approximations for the GI/G/m queue,” Production and Operations Management, vol. 2, no. 2, pp. 114–161, 1993.[31] L. Kaufman and P. J. Rousseeuw, Clustering by means of Medoids. Amsterdam: North-Holland, 1987.[32] E. Schubert and P. Rousseeuw, “Faster k-medoids clustering: Improving the PAM, CLARA, and CLARANS algorithms,” arXiv.org, vol. cs.LG, 2018. [Online]. Available: https://arxiv.org/abs/1810.05691[33] S. Lloyd, “Least squares quantization in PCM,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, 1982.[34] J. B. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol.1. Berkeley: University of California Press, 1967, pp. 281–297.[35] C. Lemarecha, “Cauchy and the gradient method,” Documenta Mathematica Extra Volume ISMP, pp. 251–254, 2012.[36] E. Polak, Optimization : Algorithms and Consistent Approximations. New York: Springer-Verlag, 1997. zh_TW dc.identifier.doi (DOI) 10.6814/NCCU201900829 en_US
