臺灣博碩士論文加值系統

城市物流已與現代社會息息相關，在疫情嚴峻的情況下，更是達到了高峰。在城市成長造成日益嚴重的交通壅塞以及其他不確定因素下，找出物流配送的最佳路徑以及花費最少運輸成本為如今的首要目標。為了獲得穩健的派車策略與路徑規劃決策，本研究建構兩階段隨機規劃模型(two-stage stochastic programming model)，利用其善於解決不確定性問題之特性，求解旅行時間不確定之城市物流配送問題(Urban logistics distribution planning with uncertain travel times)，並以最小成本作為目標，同時求出規劃路徑結果。另外，藉由最佳化軟體求解測試範例以驗證數學模型的正確性。本研究為求突破求解效率，開發與設計適應性基因演算法(Adaptive Genetic Algorithm, AGA)。關於大規模實務案例，本研究使用台灣某生鮮食品公司作為物流配送研究對象，以開發之演算法規劃結果驗證演算法有效性。而於研究結尾進行敏感度分析，藉由分析不同參數變動下路徑規劃結果的變化，並探討這些影響，供實務案例進行決策時之參考依據以及未來策略建議。

Urban logistics has become integral to modern society, especially peaking during the pandemic. As urban growth leads to severe traffic congestion and other uncertainties, optimizing delivery routes and minimizing transportation costs have become crucial. In response, this study constructs a two-stage stochastic programming model to address urban logistics with uncertain travel times, aiming to minimize costs. The accuracy of the model is verified through test cases using optimization software. To further enhance efficiency, an Adaptive Genetic Algorithm (AGA) was developed. The algorithm's effectiveness is validated through practical case studies involving a Taiwanese fresh food company. Finally, sensitivity analysis is conducted to examine the changes in route planning under varying parameters, providing valuable references for practical decision-making and future strategic recommendations.

摘 要...i
Abstract...ii
誌 謝...iii
目 錄...iv
表目錄...vi
圖目錄...ix
第一章 緒論...1
1.1 研究背景與動機...1
1.2 研究目的...2
1.3 研究架構...3
第二章 文獻探討...5
2.1 隨機規劃法(Stochastic Programming)...5
2.2 兩階段隨機規劃法(Two-stage stochastic programming)...8
2.2.1基礎原理介紹...8
2.2.2兩階段隨機規劃法演化...10
2.3 隨機車輛途程問題(Stochastic Vehicle Routing Problem)...13
2.4 旅行時間不確定性車輛途程問題...18
2.5 具時窗多趟次多艙種/異質車輛途程問題...20
2.6 基因演算法(Genetic Algorithm)...21
第三章 問題定義...25
3.1 問題定義...25
3.2 數學規劃模型...25
3.3 測試問題...30
第四章 演算法測試與開發...35
4.1 適應性基因演算法(Genetic Algorithm, GA)...35
4.1.1 初始化參數名稱設定...37
4.1.2 染色體編碼...37
4.1.3 染色體初始群體建構及限制...38
4.1.4 適應值函數設計(fitness function)...39
4.1.5 染色體選擇(Selection)...39
4.1.6 染色體交配(Crossover)...40
4.1.7 染色體突變(mutation)...42
4.2 演算法參數設定...44
4.2.1 實驗設計-反應曲面法(Response Surface Methodology)...44
第五章 實務案例...50
5.1 案例說明...50
5.1.1 配送案例...51
5.1.2 情境期望值設定-Google Maps實際路況分析...57
5.2 適應性基因演算法規劃結果...62
5.2.1演算法配送規劃結果...63
5.2.2 案例結果小結...65
5.3 敏感度分析...65
5.3.1 門市據點需求量之影響...66
5.3.2 車輛固定成本之影響...67
5.3.3 配送趟次影響之結果...69
5.3.4 不同車流情境下影響...71
第六章 結論與建議...74
6.1 結論...74
6.2 建議...75
參考文獻...76
附錄A...82
附錄B...106
Extended Abstract...109

1.張益菁. (2007). 考量需求不確定之單階多廠產能規劃問題—以TFT-LCD產業為例 of thesis. 國立清華大學, 工業工程與工程管理學系, 碩士論文.
2.Ait Mamoun, K., Hammadi, L., El Ballouti, A., Novaes, A. G. N., & Souza de Cursi, E. (2023). “Modeling Uncertain Travel Times in Distribution Logistics”, Applied Sciences, Vol. 13, No. 20
3.Avineri, E., & Prashker, J. N. (2006). “The Impact of Travel Time Information on Travelers’ Learning under Uncertainty”, Transportation, Vol. 33, No. 4, pp. 393-408.
4.Basciftci, B., Ahmed, S., & Gebraeel, N. (2019). “Adaptive Two-stage Stochastic Programming with an Application to Capacity Expansion Planning”, arXiv: Optimization and Control
5.Bent, R., & Van Hentenryck, P. (2004). “Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers”, Operations Research, Vol. 52, No. pp. 977-987.
6.Bertsimas, D. (1992). “A Vehicle Routing Problem with Stochastic Demand”, Operations Research, Vol. 40, No. pp. 574-585.
7.Bertsimas, D., van Ryzin, G., & Management, S. (1991). “A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane”, Operations Research, Vol. 39
8.Birge, J. R., & Louveaux, F. V. (1988). “A multicut algorithm for two-stage stochastic linear programs”, European Journal of Operational Research, Vol. 34, No. 3, pp. 384-392.
9.Dantzig, G. B. (1955). “Linear Programming under Uncertainty”, Management Science, Vol. 1, No. 3-4, pp. 197-206.
10.Dávila, S., Alfaro, M., Fuertes, G., Vargas, M., & Camargo, M. (2021). “Vehicle Routing Problem with Deadline and Stochastic Service Times: Case of the Ice Cream Industry in Santiago City of Chile”, Mathematics, Vol. 9, No. 21
11.Ehmke, J. F., Campbell, A. M., & Urban, T. L. (2015). “Ensuring service levels in routing problems with time windows and stochastic travel times”, European Journal of Operational Research, Vol. 240, No. 2, pp. 539-550.
12.Gendreau, M., Laporte, G., & Séguin, R. (1996). “Stochastic vehicle routing”, European Journal of Operational Research, Vol. 88, No. 1, pp. 3-12.
13.Golari, M. (2015). Multistage Stochastic Programming and Its Applications in Energy Systems Modeling and Optimization. In: The University of Arizona.
14.Golden, B. L., Wasil, E. A., Kelly, J. P., & Chao, I. M. (1998). The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problem Sets, and Computational Results, Springer US, Boston, MA.
15.Han, J., Lee, C., & Park, S. (2014). “A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times”, Transportation Science, Vol. 48, No. pp. 373-390.
16.Haugland, D., Ho, S. C., & Laporte, G. (2007). “Designing delivery districts for the vehicle routing problem with stochastic demands”, European Journal of Operational Research, Vol. 180, No. 3, pp. 997-1010.
17.Hinsbergen, C. P. I. J., Hegyi, A., Lint, J. W. C., & van Zuylen, H. (2011). “Bayesian neural networks for the prediction of stochastic travel times in urban networks”, Intelligent Transport Systems, IET, Vol. 5, No. 4, pp. 259 – 265.
18.Holland, J. H. (1973). “Genetic Algorithms and the Optimal Allocation of Trials”, SIAM Journal on Computing, Vol. 2, No. 2, pp. 88-105.
19.Hood, S. J., Bermon, S., & Barahona, F. (2003). “Capacity planning under demand uncertainty for semiconductor manufacturing”, IEEE Transactions on Semiconductor Manufacturing, Vol. 16, No. 2, pp. 273-280.
20.Hou, D., Fan, H., Ren, X., Tian, P., & Lv, Y. (2021). “Time-Dependent Multi-Depot Heterogeneous Vehicle Routing Problem Considering Temporal–Spatial Distance”, Sustainability, Vol. 13, No. 9
21.Hu, H., Guo, S., Qin, Y., & Lin, W. (2023). “Two-stage stochastic programming model and algorithm for mitigating supply disruption risk on aircraft manufacturing supply chain network design”, Computers & Industrial Engineering, Vol. 175, No. 2, pp. 1-18.
22.Jiang, J., Ng, K. M., Poh, K. L., & Teo, K. M. (2014). “Vehicle routing problem with a heterogeneous fleet and time windows”, Expert Systems with Applications, Vol. 41, No. 8, pp. 3748-3760.
23.Joe, W., & Lau, H. C. (2020). “Deep Reinforcement Learning Approach to Solve Dynamic Vehicle Routing Problem with Stochastic Customers”, Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 30, No. 1, pp. 394-402.
24.John R. Birge , F. L. (1997). “Introduction to Stochastic Programming”, Springer Series in Operations Research and Financial Engineering, Vol. No. pp.
25.Kabadurmus, O., & Erdogan, M. S. (2023). “A green vehicle routing problem with multi-depot, multi-tour, heterogeneous fleet and split deliveries: a mathematical model and heuristic approach”, Journal of Combinatorial Optimization, Vol. 45, No. 3, pp. 89.
26.Katoch, S., Chauhan, S. S., & Kumar, V. (2021). “A review on genetic algorithm: past, present, and future”, Multimedia Tools and Applications, Vol. 80, No. 5, pp. 8091-8126.
27.Lambert, V., Laporte, G., & Louveaux, F. (1993). “Designing collection routes through bank branches”, Comput. Oper. Res., Vol. 20, No. 7, pp. 783–791.
28.Laporte, G., Louveaux, F., & Van hamme, L. (2002). “An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands”, Operations Research, Vol. 50, No. pp. 415-423.
29.Lecluyse, C., Van Woensel, T., & Peremans, H. (2009). “Vehicle routing with stochastic time-dependent travel times”, 4OR, Vol. 7, No. 4, pp. 363-377.
30.Lei, H., Laporte, G., & Guo, B. (2011). “The capacitated vehicle routing problem with stochastic demands and time windows”, Computers & Operations Research, Vol. 38, No. 12, pp. 1775-1783.
31.Li, J., Liu, R., & Wang, R. (2024). “Handling dynamic capacitated vehicle routing problems based on adaptive genetic algorithm with elastic strategy”, Swarm and Evolutionary Computation, Vol. 86, pp. 1-21.
32.Li, Q., Wang, J., Wang, Y., & Lv, J. (2022). “A Two-Stage Stochastic Programming Model for Emergency Supplies Pre-Position under the Background of Civil-Military Integration”, Sustainability, Vol. 14, No. 19, pp. 1-21.
33.Linderoth, J., & Wright, S. (2003). “Decomposition Algorithms for Stochastic Programming on a Computational Grid”, Computational Optimization and Applications, Vol. 24, No. 2, pp. 207-250.
34.Liu, S., He, L., & Shen, M. (2020). “On-Time Last-Mile Delivery: Order Assignment with Travel-Time Predictors”, Management Science, Vol. 67, No. pp. 4095–4119.
35.Marquez, J., Talero-Sarmiento, L. H., & Lamos, H. (2022). “Multistage Stochastic Programming to Support Water Allocation Decision-Making Process in Agriculture: A Literature Review”, Chemistry Proceedings, Vol. 10, No. 1, pp. 26.
36.Nikzad, E., & Bashiri, M. (2022). “A two-stage stochastic programming model for collaborative asset protection routing problem enhanced with machine learning: a learning-based matheuristic algorithm”, International Journal of Production Research, Vol. 61, No. pp. 1-33.
37.Ochelska-Mierzejewska, J., Poniszewska-Marańda, A., & Marańda, W. (2021). “Selected Genetic Algorithms for Vehicle Routing Problem Solving”, Electronics, Vol. 10, No. 24
38.Oyola, J., Arntzen, H., & Woodruff, D. L. (2018). “The stochastic vehicle routing problem, a literature review, part I: models”, EURO Journal on Transportation and Logistics, Vol. 7, No. 3, pp. 193-221.
39.Paeizi, A., Makui, A., & Pishvaee, M. S. (2023). “A multi-stage stochastic programming approach for an inventory–routing problem considering life cycle”, RAIRO-Oper. Res., Vol. 57, No. 5, pp. 2537-2559.
40.Rizqi, Z. U., Qinthara, D. U., Khairunisa, A., Helia, V. N., & Kusrini, E. (2023). “Applying adaptive genetic algorithm for heterogeneous vehicle routing problem with asymmetric distance and fuzzy demand (HVRPADFD)”, AIP Conference Proceedings, Vol. 2828, No. 1
41.Ruszczyński, A., & Świȩtanowski, A. (1997). “Accelerating the regularized decomposition method for two stage stochastic linear problems”, European Journal of Operational Research, Vol. 101, No. 2, pp. 328-342
42.Schultz, R., Stougie, L., & van der Vlerk, M. H. (1998). “Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis”, Mathematical Programming, Vol. 83, No. 1, pp. 229-252.
43.Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2009). Lectures on Stochastic Programming: Modeling and Theory,
44.Srinivas, M., & Patnaik, L. M. (1994). “Adaptive probabilities of crossover and mutation in genetic algorithms”, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 24, No. 4, pp. 656-667.
45.Tolooie, A., Maity, M., & Sinha, A. K. (2020). “A two-stage stochastic mixed-integer program for reliable supply chain network design under uncertain disruptions and demand”, Computers & Industrial Engineering, Vol. 148, No. pp. 106722.
46.Ulmer, M., Mattfeld, D., & Köster, F. (2015). Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests,
47.Uribe, A. M., Cochran, J. K., & Shunk, D. L. (2003). “Two-stage simulation optimization for agile manufacturing capacity planning”, International Journal of Production Research, Vol. 41, No. 6, pp. 1181-1197.
48.Van Slyke, R. M., & Wets, R. (1969). “L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming”, SIAM Journal on Applied Mathematics, Vol. 17, No. 4, pp. 638-663.
49.Wang, D., Zhu, J., Wei, X., Cheng, T. C. E., Yin, Y., & Wang, Y. (2018). “Integrated Production and Multiple Trips Vehicle Routing with Time Windows and Uncertain Travel Times”, Computers & Operations Research, Vol. 103, No. pp. 1-12.
50.Wang, J., Huang, J., Rao, S., Xue, S., & Yin, J. (2008). “An Adaptive Genetic Algorithm for Solving Traveling Salesman Problem”, Conference, Place
51.Wu, L., Hifi, M., & Bederina, H. (2017). “A new robust criterion for the vehicle routing problem with uncertain travel time”, Computers & Industrial Engineering, Vol. 112, pp. 607-615.
52.Zhang, J. (2021). “An Improved Genetic Algorithm for Vehicle Routing Problem”, Conference, Place, February 28.
53.Zhang, S., Chen, M., Zhang, W., & Zhuang, X. (2020). “Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations”, Expert Systems with Applications, Vol. 145, pp. 113123.
54.Zhen, L., Ma, C., Wang, K., Xiao, L., & Zhang, W. (2020). “Multi-depot multi-trip vehicle routing problem with time windows and release dates”, Transportation Research Part E: Logistics and Transportation Review, Vol. 135, pp. 101866.
55.Zhou, Z., Zhang, J., Liu, P., Li, Z., Georgiadis, M. C., & Pistikopoulos, E. N. (2013). “A two-stage stochastic programming model for the optimal design of distributed energy systems”, Applied Energy, Vol. 103, pp. 135-144.