Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/125514
|
| Title: | 利用資料驅動方法解決汽車服務系統的位區途程問題
A data driven approach for solving the location-routing problem in vehicle service systems |
| Authors: | 林育丞
LIn, Yu-Cheng |
| Contributors: | 洪英超
Hung, Ying-Chao
林育丞
LIn, Yu-Cheng |
| Keywords: | 位區途程問題
電動汽車充電設施
平均反應時間
等候理論
交通繁忙定理
有尺寸限制的分群問題
Location-routing problem
EV charging infrastructure
Mean response time
Queueing system
Heavy traffic approximation
Clustering with size constraints |
| Date: | 2019 |
| Issue Date: | 2019-09-05 15:41:29 (UTC+8) |
| Abstract: | 汽車在行駛過程中會不斷消耗能源，由於車內能裝載的能源容量有限，且我們期望當有服務需求時，盡量縮短服務的花費時間，因此開發用於汽車服務系統的位區途程策略（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. |
| 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. |
| Description: | 碩士
國立政治大學
統計學系
106354018 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0106354018 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU201900829 |
| Appears in Collections: | [Department of Statistics] Theses
|
Files in This Item:
| File |
Size | Format | |
|---|
| 401801.pdf | 2277Kb | Adobe PDF2 | 0 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
