臺灣博碩士論文加值系統

良好的庫存管理是零售公司成功的最重要因素之一，庫存過多會導致庫存過剩，並可能影響零售金融資金的現金流。但是，庫存不足也會導致失去銷售機會，並可能對客戶滿意度產生負面影響。為了實現良好的庫存管理，庫存管理必須實施最合適的庫存補貨策略。最近，抓物機越來越受歡迎，導致了獎品庫存管理問題。抓物機的週期性補貨問題是週期性車輛路徑問題（PVRP）的一個變形問題。本研究以印尼雅加達為例，採用免疫演算法 (IA) 和遺傳演算法 (GA) 來獲得週期性供應問題的最佳週期性補貨路徑。本研究提供並討論此問題的最佳車輛選擇和最短路線的數值結果。IA 和 GA 的結果顯示，案例 1 中容量較大的車輛獲得了最短的補給路線，而案例 2 中的小型汽車以減少旅行時間和燃料成本實現了更有效和高效的供應管理。結果進一步顯示，大車和小車案例的收斂平均迭代次數沒有顯著差異。假設不同車輛成本的數值分析顯示，當大車和小車的成本只有微小差異時，大車是每天最有效率的車輛選擇，當兩種車型的成本差異適中時，小車為最有效率的車輛選擇，而當兩種車型的成本相差很大時，一大車和一小車的組合成為最有效率的選擇。實驗結果顯示，IA 優於 GA，並且 IA 收斂的平均迭代次數小於 GA。由於 IA 在演化中擁有記憶區，因此 IA 的平均 CPU 時間大於 GA。

Good inventory management is one of the most important factors for the success of retail companies. Excessive inventory will lead to over-stock and may affect the cash flow of retail’s financial capital. However, the lack of inventory will also lead to the loss of sales opportunities and may negatively affect customer satisfaction. To achieve good inventory management, the inventory planner has to implement the most suitable stock replenishment strategy. Recently, the claw machine has grown in popularity resulted in a prize stock management issue. The periodic replenishment problem of the claw machine is a variant of the periodic vehicle routing problem (PVRP). This study adopts an immune algorithm (IA) and genetic algorithm (GA) to obtain the optimal routing for the periodic supply problems with the case study in Jakarta, Indonesia. Numerical results of the best vehicle option and the shortest route for the problem are provided and discussed. The results from both IA and GA show that larger capacity vehicles in Case 1 can be used to obtain the shortest replenishment route while the small car in Case 2 achieved more effective and efficient supply management by reducing travel time as well as fuel cost. The results further implied that there is no significant difference for the average iteration of convergence between big cars and small cars. The analysis with various cost shows that big car in each day is the most efficient choice when there is a slight difference in the cost between big car and small car. The small car is the most efficient choice when there is a moderate difference in the cost between big car and small car, meanwhile, when the cost difference is significant, one big car and one small car become the most efficient choice. The experiment results show that IA outperforms GA and the average number of iterations to converge for IA is smaller than GA. Since IA possesses memory scheme in the evolution, the average CPU time for IA is larger than GA.

English Abstract.......................................................... i
Chinese Abstract.......................................................... iii
Acknowledgment............................................................ v
Table of Contents......................................................... vi
List of Tables............................................................ vii
List of Figures........................................................... viii
Chapter 1 Introduction.............................................. 1
1.1 Research Background and Motivation........................ 1
1.1.1 Claw Machine.............................................. 1
1.1.2 Claw Machine in Jakarta, Indonesia........................ 3
1.1.3 Claw Machine and Periodic Vehicle Routing Problem......... 4
1.2 Research Objectives....................................... 4
1.3 Research Outline.......................................... 5
1.4 Thesis Structure.......................................... 6
Chapter 2 Literature Review and Research Method..................... 7
2.1 Literature Review......................................... 7
2.1.1 Vehicle Routing Problem................................... 7
2.1.2 Periodic Vehicle Routing Problem.......................... 10
2.2 Research Method........................................... 11
2.2.1 Taguchi Method.......................................... 11
2.2.2 Immune Algorithm........................................ 17
2.2.3 Genetic Algorithm......................................... 21
Chapter 3 Problem, Encoding and Parameter Setting................... 26
3.1 Problem Description and Assumptions....................... 26
3.2 Encoding Method........................................... 27
3.3 Parameter Setting......................................... 32
Chapter 4 Test Problem, Results and Analysis........................ 36
4.1 Test Problem in Jakarta, Indonesia........................ 36
4.2 Analysis of IA and GA Results............................. 38
4.3 Analysis of Capacity and Cost of Vehicle.................. 42
4.4 Analysis of Best Replenishment Route...................... 44
4.5 Comparison of IA and GA................................... 45
Chapter 5 Conclusion................................................ 47
Reference................................................................. 49
Appendix I................................................................ 52
Extended Abstract

[1].J. E. Roller, 1999-2021, Vintage Amusements History, https://jamesroller.com/history/
[2].E. J. Beltrami and L. D. Bodin, “Networks and Vehicle Routing for Municipal Waste Collection”, Networks, 4(1), 65–94, 1974. Doi:10.1002/net.3230040106.
[3].P. Toth and D. Vigo, Vehicle Routing (Problems, Methods, and Applications (Second ed), Chapter 9: Four Variants of the Vehicle Routing Problem (pp. 241–271), MOS-SIAM, Philadelphia, 2014. Doi: 10.1137/1.9781611973594.
[4].G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem”, Management Science, 6, pp. 80-91, 1959. Doi: http://dx.doi.org/10.1287/mnsc.6.1.80.
[5].G. Clarke and J. W. Wright, “Scheduling of Vehicle Routing Problem from a Central Depot to a Number of Delivery Points”, Operations Research, 12, pp. 568-581, 1964. Doi: http://dx.doi.org/10.1287/opre.12.4.568.
[6].Kh. Pichka, B. Ashjari, A. Ziaeifar, and P. Nickbeen, “Open Vehicle Routing Problem Optimization under Realistic Assumptions”, International Journal of Research in Industrial Engineering, 3, pp. 46-55, 2014.
[7].J. Brandão, “A Memory-based Iterated Local Search Algorithm for the Multi-Depot Open Vehicle Routing Problem”, European Journal of Operational Research, 284, 2020. Doi: 10.1016/j.ejor.2020.01.008.
[8].T. Leelertkij, P. Parthanadee, and J. Buddhakulsomsiri, “Vehicle Routing Problem with Transshipment: Mathematical Model and Algorithm”, Journal of Advanced Transportation, 2021, pp. 1-15, 2021. Doi: 10.1155/2021/8886572.
[9].R. Moghdani, K. Salimifard, E. Demir, and A. Benyettou, “The Green Vehicle Routing Problem: A Systematic Literature Review”, Journal of Cleaner Production, 279, 2020. Doi: 123691. 10.1016/j.jclepro.2020.123691.
[10].D. Utama, D. S. Widodo, M. F. Ibrahim, and S. K. Dewi, “A New Hybrid Butterfly Optimization Algorithm for Green Vehicle Routing Problem”, Journal of Advanced Transportation, 2020, pp. 1-14, 2020. Doi: 10.1155/2020/8834502.
[11].M. Elbek and S. Wøhlk, “A Variable Neighborhood Search for the Multi-Period Collection of Recyclable Materials”, European Journal of Operational Research, 249(2), 2015. Doi: S0377221715007900.
[12].P. De Bruecker, J. Beliën, L. De Boeck, S. De Jaeger, and E. Demeulemeester, “A Model Enhancement Approach for Optimizing the Integrated Shift Scheduling and Vehicle Routing Problem in Waste Collection”, European Journal of Operational Research, 266(1), 2018. Doi: S0377221717307907.
[13].Y.-J. An, Y-D Kim, B. J. Jeong, and S.-D. Kim, “Scheduling Healthcare Services in a Home Healthcare System”, Journal of the Operational Research Society, 63(11), pp. 1589–1599, 2012.
[14].H.-L. Hsu, C.-W. Chu, and C.-S. Wu, “Short Term Strategies for Solving a Variant of Period Vehicle Routing Problem”, Journal of Marine Science and Technology, 23(5), pp. 579-590, 2017. Doi: 10.6119/JMST-013-0905-2.
[15].Z. Luo, H. Qin, C.H. Che, and A. Lim, “On Service Consistency in Multi-Period Vehicle Routing”, European Journal of Operational Research, 243(3), pp. 731–744, 2015.
[16].C. Archetti, E. Fernández, and D. L. Huerta-Muñoz, “The Flexible Periodic Vehicle Routing Problem”, Computers & Operations Research, 85, pp. 58–70, 2017.
[17].S. Coene, A. Arnout, and F.C.R. Spieksma. “On a Periodic Vehicle Routing Problem”, Journal of the Operational Research Society, 61(12), pp. 1719–1728, 2010.
[18].A. Parnianifard, A. S. Azfanizama, M. K. A. Ariffin, and M. I. S. Ismai, y“Robust Product Design: A Modern View of Quality Engineering in Manufacturing Systems”, Preprints, 2018. Doi: 3220-. 10.20944/preprints201807.0517.v1.
[19].J. Timmis, T. Knight, L. N. de Castro, and E. Hart, “An Overview of Artificial Immune Systems”, 2004. Doi: 10.1007/978-3-662-06369-9_4.
[20].D.E. Goldberg, J.H. Holland, “Genetic Algorithms and Machine Learning”, Machine Learning, 3, pp. 95–99, 1988. Doi: https://doi.org/10.1023/A:1022602019183
[21].A. Azadeh, S. Elahi, M. H. Farahani, and B. Nasirian, “A Genetic Algorithm-Taguchi Based Approach to Inventory Routing Problem of a Single Perishable Product with Transshipment”, Computers & Industrial Engineering, 104, 2016. Doi: 10.1016/j.cie.2016.12.019.
[22].Y.-B. Woo and B.S. Kim, “A genetic algorithm-based matheuristic for hydrogen supply chain network problem with two transportation modes and replenishment cycles”, Computers & Industrial Engineering, 127, 2019. Doi: 10.1016/j.cie.2018.11.027.
[23].A. Senoussi, S. Dauzère-Pérès, N. Brahimi, B. Penz, and N. Kinza Mouss, “Heuristics Based on Genetic Algorithms for the Capacitated Multi Vehicle Production Distribution Problem”, Computers & Operations Research, 96, pp. 108-119, 2018.