臺灣博碩士論文加值系統

本研究以電動車共享系統租賃業者角度，利潤最大化為目標，求解每日營運前系統中各租賃站充電式電動車(Plug-in electric vehicles, EVs)佈署問題。本研究透過多層時空網路(Multi-layer Time Space Network)表示電動車於租賃系統內之流動情形，並以此網路建構車輛最佳配置模式，分別利用穩健最佳化(Robust Optimization, RO)與機會約束(Chance Constraint)技巧，處理在不確定與隨機需求情境下的車輛配置問題，雖然小規模範例可使用商業軟體，如Gurobi取得最佳解，但大規模範例則需使用數學啟發式演算法有效求解。
本研究以日月潭風景區之電動車共享系統業者，根據營運資料產生一組實驗數據，研究結果顯示，此模型可以有效地在需求確定性、不確定性與隨機性情境下，最佳化車輛配置問題。此外，此模型也測試於大規模範例，並驗證可透過啟發式演算法在合理時間內獲得品質好的解。另外也針對不同成本參數進行敏感度分析，並以穩健最佳化模式中常見之績效衡量指標，穩健價格(Robust Price)與避險值(Hedge Value)分析穩健解在不確定性需求下之效益與代價。本研究之貢獻與實務上可以協助電動車共享系統營運業者，有效地決定在不確定性與隨機性需求下，對於電動車輛的佈署。

This study addresses the optimal allocation of a fleet of plug-in electric vehicles (EVs) to the stations of an EV-sharing system at the beginning of each day. The objective is to maximize the profit of the system operator. A multi-layer time-space network flow is adopted to describe the movement of EVs in the system. An optimal fleet allocation model for EV-sharing systems is then developed based on the multi-layer time-space network. This study applies robust optimization and chance constraint techniques to deal with this fleet allocation problem with uncertain and stochastic demands, respectively. While small-scale instances of the problem can be optimally solve using commercial software such as Gurobi, a network decomposition-based mathheuristic is developed to efficiently solve large-scale instances.
A set of computational experiments were conducted based on the data provided by the operator of the EV-sharing system deployed in the Sun-Moon Lake National Park in Nantou, Taiwan. The results show that the proposed model is able to effectively generate optimal fleet allocations under determinstic, uncertain an stochastic demand scenarios. Moreover, the model and the heuristic were tested on a larger problem instance extended from the above-mentioned EV-sharing system. The heuristic is able to obtain good quality solutions in a reasonabe amount of time. Sensitivity analyses of the impact of model parameters on solution performances were also conducted. Two measures of effectiveness, robust price and hedge value, were examined to verify the price-paid and value-gained by applying the robust solution. This study contributes to provide a decision support tool that faciliates operators of EV-sharing systems in effectively determing the deployment of their fleets to stations considering uncertain and stochastic demands.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
圖目錄 viii
表目錄 ix
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 3
1.4 研究方法與流程 3
第二章 文獻回顧 5
2.1 國內外電動車共享系統之發展現況 5
2.1.1 中國 5
2.1.2 日本 6
2.1.3 英國 6
2.1.4 美國 6
2.1.5 國內共享電動車系統 6
2.2 電動車相關文獻 7
2.3 電動車共享系統相關文獻 7
2.4 時空網路相關文獻 8
2.5 穩健最佳化應用相關文獻 9
2.5.1 Robust Optimization (RO) 9
2.5.2 Robust Counterpart Optimization (RCO) 10
2.6 機會約束(Chance Constraint)應用相關文獻 13
2.7 小結 13
第三章 電動車共享系統車輛配置模式 15
3.1 問題描述 15
3.1.1 研究假設 15
3.1.2 人流時空網路 17
3.2 電動車共享車流時空網路 19
3.3 確定性需求電動車共享系統車輛佈署最佳化模式 22
3.4 小範例測試 24
3.4.1 參數設定 25
3.4.2 小範例測試結果 27
3.5 穩健電動車共享系統車輛佈署最佳化模式 29
3.5.1 不確定需求集合定義 29
3.5.2 穩健最佳化模式 30
3.6 機會約束(chance constraint) 31
3.7 車輛分解法(NDV) 32
第四章 小規模範例測試與結果 35
4.1 測試例題介紹 35
4.1.1 電動車共享系統之相關參數設定 35
4.1.2 模式輸入資料與環境設定 37
4.1.3 確定性需求資料 37
4.1.4 確定性需求測試結果 38
4.2 不確定性需求 39
4.2.1 橢圓狀(Ellipsoidal)需求資料 40
4.2.2 橢圓狀(Ellipsoidal)測試結果 41
4.2.3 凸包狀(Convex Hull)需求資料 42
4.2.4 凸包狀(Convex Hull)測試結果 43
4.3 隨機性需求 45
4.3.1 機會約束(α=95%)需求資料 45
4.3.2 機會約束(α=95%)測試結果 46
4.3.3 機會約束(α=98%)需求資料 48
4.3.4 機會約束(α=98%)測試結果 49
4.4 小結 50
第五章 大規模範例測試與結果 53
5.1 確定性需求 53
5.1.1 確定性需求資料 53
5.1.2 確定性測試結果 54
5.1.3 模式參數敏感度分析 56
5.2 不確定性需求 58
5.2.1 橢圓狀(Ellipsoidal)需求資料 59
5.2.2 橢圓狀(Ellipsoidal)測試結果 59
5.2.3 凸包狀(Convex hull)需求資料 60
5.2.4 凸包狀(Convex hull)測試結果 60
5.3 隨機性需求 61
5.3.1 機會約束(α=90%)需求資料 62
5.3.2 機會約束(α=90%)測試結果 62
5.3.3 機會約束(α=95%)需求資料 63
5.3.4 機會約束(α=95%)測試結果 63
5.3.5 機會約束(α=98%)需求資料 64
5.3.6 機會約束(α=98%)測試結果 65
5.4 穩健最佳化模式績效衡量指標 66
5.5 小結 67
第六章 結論與建議 75
6.1 結論 75
6.2 未來研究方向建議 76
參考文獻 77

[1] Arslan, O., Yıldız, B., & Karaşan, O. E. (2015). Minimum cost path problem for Plug-in Hybrid Electric Vehicles. Transportation Research Part E: Logistics and Transportation Review, 80, 123-141. doi:10.1016/j.tre.2015.05.011
[2] Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23(4), 769-805.
[3] Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations research letters, 25(1), 1-13.
[4] Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematic programming, 88(3), 411-424.
[5] Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53.
[6] Boyacı, B., Zografos, K. G., & Geroliminis, N. (2015). An optimization framework for the development of efficient one-way car-sharing systems. European Journal of Operational Research, 240(3), 718-733. doi:10.1016/j.ejor.2014.07.020
[7] David, A., Farr, D., Januszyk, R., & Diwekar, U. J. I. (2015). USG Uses Stochastic Optimization to Lower Distribution Costs. 45(3), 216-227.
[8] Ding, S. (2013). Uncertain multi-product newsboy problem with chance constraint. Applied mathematics and computation, 223, 139-146.
[9] Gurvich, I., Luedtke, J., & Tezcan, T. (2010). Staffing call centers with uncertain demand forecasts: A chance-constrained optimization approach. Management Science, 56(7), 1093-1115.
[10] He, J., Yang, H., Tang, T.-Q., & Huang, H.-J. (2018). An optimal charging station location model with the consideration of electric vehicle’s driving range. Transportation Research Part C, 86, 641-654.
[11] Kobayashi, Y., Kiyama, N., Aoshima, H., & Kashiyama, M. (2011). A route search method for electric vehicles in consideration of range and locations of charging stations. Paper presented at the Intelligent Vehicles Symposium (IV), 2011 IEEE, Baden-Baden, Germany.
[12] Lee, J., Park, G.-L., Kim, H.-J., Kang, M.-J., Kwak, H.-Y., Lee, S. J., . . . Kang, H. S. (2014). Design of a Multi-purpose Real-Time Tracking System for Electric Vehicles. In Ubiquitous Information Technologies and Applications (pp. 215-220): Springer.
[13] Liu, D., Xiao, Y., & Liu, M. (2015). A Time-Space Network Model for Medical Goods Order and Delivery Scheduling. In LISS 2014 (pp. 377-382): Springer.
[14] Liu, J., & Zhou, X. (2016). Capacitated transit service network design with boundedly rational agents. Transportation Research Part B, 93, 225-250.
[15] Lu, C.-C., Yan, S., & Huang, Y.-W. (2018). Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations. Transportation Research Part C: Emerging Technologies, 93, 479-500.
[16] Schneider, M., Stenger, A., & Goeke, D. J. T. S. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4), 500-520.
[17] Soyster, A. L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154-1157.
[18] Steinzen, I., Gintner, V., Suhl, L., & Kliewer, N. (2010). A time-space network approach for the integrated vehicle-and crew-scheduling problem with multiple depots. Transportation Science, 44(3), 367-382.
[19] Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Transactions, 40(5), 509-523.
[20] 行政院經濟部. (2014). 智慧電動車輛發展策略與行動方案.
[21] 行政院環保署. (2014a). 智慧電動車產業輔導推廣計畫.
[22] 行政院環保署. (2014b). 溫室氣體減量及管理法.
[23] 林韋捷. (2015). 公共電動車系統車輛配置最佳化模式.
[24] 楊瑞宇. (2012). 穩健公共自行車租用系統車輛配置模式. 1-73.
[25] 謝閔易. (2014). 以模擬為基礎之基因演算法求解公共電動車系統車輛配置最佳化問題. 1-83.
[26] 顏上堯, 蕭妃晏, & 謝潤曉. (2011). 跨校選授課專車排程規劃模式暨演算法之研究. 運輸計劃季刊, 369-392. doi:10.6402/TPJ.201112.0034