Simulation Budget Allocation for Improving Scheduling and Routing of Automated Guided Vehicles in Warehouse Management

doi:10.1007/s40305-024-00553-0

摘要/Abstract

Abstract: Simulation budget allocation is a widely used technique for evaluating and optimizing dynamic discrete event stochastic system via efficient sampling. In warehouse management, the scheduling and routing algorithms of automated guided vehicles aim to optimize order assignments and travel paths under certain constraints to achieve specific objectives. However, these algorithms often rely on deterministic optimization methods, neglecting the dynamic and stochastic nature of warehouse management systems. In this work, we propose an efficient method that integrates simulation budget allocation methods with deterministic scheduling and routing algorithms to enhance overall system performance. The proposed method leverages the benefits of both simulation optimization and deterministic optimization techniques, accounting for the inherent uncertainty of the system. We adopt a discrete event simulation model used in the Case Study Competition of the 2022 Winter Simulation Conference, where the objective is to minimize the adjusted average order cycle time (ACT) in a given warehouse simulation scenario. Numerical examples demonstrate that the use of simulation budget allocation methods can significantly further reduce the ACT, thereby highlighting the effectiveness of our proposed method.

Key words: Simulation optimization, Scheduling and routing, Automated guided vehicles, Warehouse management

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2025, 13(3): 775-809.

Gong-Bo Zhang, Hao-Bin Li, Xiao-Tian Liu, Yi-Jie Peng. Simulation Budget Allocation for Improving Scheduling and Routing of Automated Guided Vehicles in Warehouse Management[J]. Journal of the Operations Research Society of China, 2025, 13(3): 775-809.

参考文献

[1] Adamo, T., Bektaş, T., Ghiani, G., Guerriero, E., Manni, E.: Path and speed optimization for conflictfree pickup and delivery under time windows. Transp. Sci. 52(4), 739-755(2018)
[2] An, Y., Li, M., Lin, X., He, F., Yang, H.: Space-time routing in dedicated automated vehicle zones. Transp. Res. Part C Emerg. Technol. 120, 102777(2020)
[3] Chen, C.-H., Chick, S.E., Lee, L.H., Pujowidianto, N.A.: Ranking and selection: efficient simulation budget allocation. In: Handbook of Simulation Optimization, pp. 45-80(2015)
[4] Chen, C.-H., He, D., Fu, M., Lee, L.H.: Efficient simulation budget allocation for selecting an optimal subset. INFORMS J. Comput. 20(4), 579-595(2008)
[5] Chen, C.-H., Lee, L.H.: Stochastic Simulation Optimization: An Optimal Computing Budget Allocation, vol. 1. World Scientific, Singapore (2011)
[6] Chen, C.-H., Lin, J., Yücesan, E., Chick, S.E.: Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dyn. Syst. 10, 251-270(2000)
[7] Chen, Y., Ryzhov, I.O.: Balancing optimal large deviations in sequential selection. Manage. Sci. 69(6), 3457-3473(2023)
[8] Corréa, A.I., Langevin, A., Rousseau, L.-M.: Scheduling and routing of automated guided vehicles: a hybrid approach. Comput. Op. Res. 34(6), 1688-1707(2007)
[9] Ding, L., Hong, L.J., Shen, H., Zhang, X.: Knowledge gradient for selection with covariates: consistency and computation. Naval Res. Logist. 69(3), 496-507(2022)
[10] Du, J., Gao, S., Chen, C.-H.: A contextual ranking and selection method for personalized medicine. Manuf. Serv. Op. Manag. 26(1), 167-181(2024)
[11] De Ryck, M., Versteyhe, M., Debrouwere, F.: Automated guided vehicle systems, state-of-the-art control algorithms and techniques. J. Manuf. Syst. 54, 152-173(2020)
[12] Fazlollahtabar, H., Saidi-Mehrabad, M.: Methodologies to optimize automated guided vehicle scheduling and routing problems: a review study. J. Intell. Robot. Syst. 77, 525-545(2015)
[13] Fransen, K., Van Eekelen, J., Pogromsky, A., Boon, M.A., Adan, I.J.: A dynamic path planning approach for dense, large, grid-based automated guided vehicle systems. Comput. Op. Res. 123, 105046(2020)
[14] Frazier, P.I., Powell, W.B., Dayanik, S.: A knowledge-gradient policy for sequential information collection. SIAM J. Control. Optim. 47(5), 2410-2439(2008)
[15] Fu, M.C.: Stochastic gradient estimation. In: Handbook of Simulation Optimization, pp. 105-147(2015)
[16] Gao, S., Chen, W.: A new budget allocation framework for selecting top simulated designs. IIE Trans. 48(9), 855-863(2016)
[17] Gao, S., Chen, W.: Efficient feasibility determination with multiple performance measure constraints. IEEE Trans. Autom. Control 62(1), 113-122(2016)
[18] Glynn, P., Juneja, S.: A large deviations perspective on ordinal optimization. In: 2004 Winter Simulation Conference, pp. 577-585. IEEE (2004)
[19] Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100-107(1968)
[20] Hong, L.J., Fan, W., Luo, J.: Review on ranking and selection: a new perspective. Front. Eng. Manag. 8(3), 321-343(2021)
[21] Hong, L.J., Jiang, G., Zhong, Y.: Solving large-scale fixed-budget ranking and selection problems. INFORMS J. Comput. 34(6), 2930-2949(2022)
[22] Hu, H., Jia, X., He, Q., Fu, S., Liu, K.: Deep reinforcement learning based AGVs real-time scheduling with mixed rule for flexible shop floor in industry 4.0. Comput. Ind. Eng. 149, 106749(2020)
[23] Hu, H., Yang, X., Xiao, S., Wang, F.: Anti-conflict AGV path planning in automated container terminals based on multi-agent reinforcement learning. Int. J. Prod. Res. 61(1), 65-80(2023)
[24] Hunter, S.R., Nelson, B.L.: Parallel ranking and selection. In: Advances in Modeling and Simulation: Seminal Research from 50 Years of Winter Simulation Conferences, pp. 249-275. Springer (2017)
[25] Kabir, Q.S., Suzuki, Y.: Comparative analysis of different routing heuristics for the battery management of automated guided vehicles. Int. J. Prod. Res. 57(2), 624-641(2019)
[26] Kamiński, B., Szufel, P.: On parallel policies for ranking and selection problems. J. Appl. Stat. 45(9), 1690-1713(2018)
[27] Keslin, G., Nelson, B.L., Plumlee, M., Pagnoncelli, B.K., Rahimian, H.: A classification method for ranking and selection with covariates. In: 2022 Winter Simulation Conference, pp. 1-12. IEEE (2022)
[28] Kim, S.-H., Nelson, B.L.: Selecting the best system. Handb. Oper. Res. Manag. Sci. 13, 501-534(2006)
[29] Li, H., Lam, H., Peng, Y.: Efficient learning for clustering and optimizing context-dependent designs. Oper. Res. 72(2), 617-638(2024)
[30] Li, H., Peng, Y., Xu, X., Heidergott, B.F., Chen, C.-H.: Efficient learning for decomposing and optimizing random networks. Fundam. Res. 2(3), 487-495(2022)
[31] Li, H., Xu, X., Peng, Y., Chen, C.-H.: Efficient learning for selecting important nodes in random network. IEEE Trans. Autom. Control 66(3), 1321-1328(2020)
[32] Li, Y., Fu, M.C., Xu, J.: An optimal computing budget allocation tree policy for Monte Carlo tree search. IEEE Trans. Autom. Control 67(6), 2685-2699(2021)
[33] Liu, X., Peng, Y., Zhang, G., Zhou, R.: An efficient node selection policy for value network based Monte Carlo tree search. Available at SSRN 4450999(2023)
[34] Lee, C.Y.: An algorithm for path connections and its applications. IRE Trans. Electron. Comput. 3, 346-365(1961)
[35] Lee, J.H., Lee, B.H., Choi, M.H.: A real-time traffic control scheme of multiple AGV systems for collision free minimum time motion: a routing table approach. IEEE Trans. Syst. Man Cybern. Part A Syst. Hum. 28(3), 347-358(1998)
[36] Lee,L.H.,Chew,E.P.,Tan,K.C.,Wang,Y.:Vehicle dispatching algorithms for container transshipment hubs. OR Spectr. 32, 663-685(2010)
[37] Luo, X., Li, L., Zhao, L., Lin, J.: Dynamic intra-cell repositioning in free floating bike-sharing systems using approximate dynamic programming. Transp. Sci. 56(4), 799-826(2022)
[38] Luo, J., Hong, L.J., Nelson, B.L., Wu, Y.: Fully sequential procedures for large-scale ranking-and-selection problems in parallel computing environments. Oper. Res. 63(5), 1177-1194(2015)
[39] Ni, E.C., Ciocan, D.F., Henderson, S.G., Hunter, S.R.: Efficient ranking and selection in parallel computing environments. Oper. Res. 65(3), 821-836(2017)
[40] Peng, Y., Chong, E.K., Chen, C.-H., Fu, M.C.: Ranking and selection as stochastic control. IEEE Trans. Autom. Control 63(8), 2359-2373(2018)
[41] Peng, Y., Zhang, G.: Thompson sampling meets ranking and selection. In: 2022 Winter Simulation Conference, pp. 3075-3086. IEEE (2022)
[42] Powell, W.B., Ryzhov, I.O.: Ranking and selection. Optim. Learn. 841, 71-88(2012)
[43] Russo, D.: Simple Bayesian algorithms for best-arm identification. Oper. Res. 68(6), 1625-1647(2020)
[44] Ryzhov, I.O.: On the convergence rates of expected improvement methods. Oper. Res. 64(6), 1515- 1528(2016)
[45] Shen, H., Hong, L.J., Zhang, X.: Ranking and selection with covariates for personalized decision making. INFORMS J. Comput. 33(4), 1500-1519(2021)
[46] Shi, X., Peng, Y., Zhang, G.: Top-two thompson sampling for contextual top-mc selection problems. arXiv:2306.17704(2023)
[47] Shi, Z., Peng, Y., Shi, L., Chen, C.-H., Fu, M.C.: Dynamic sampling allocation under finite simulation budget for feasibility determination. INFORMS J. Comput. 34(1), 557-568(2022)
[48] Vis, I.F.: Survey of research in the design and control of automated guided vehicle systems. Eur. J. Oper. Res. 170(3), 677-709(2006)
[49] Vis, I.F., De Koster, R., Roodbergen, K.J., Peeters, L.W.: Determination of the number of automated guided vehicles required at a semi-automated container terminal. J. Oper. Res. Soc. 52(4), 409-417(2001)
[50] Yücesan, E., Luo, Y.-C., Chen, C.-H., Lee, I.: Distributed web-based simulation experiments for optimization. Simul. Pract. Theory 9(1-2), 73-90(2001)
[51] Zhang, G., Chen, B., Jia, Q.-S., Peng, Y.: Efficient sampling policy for selecting a subset with the best. IEEE Trans. Autom. Control 68(8), 4904-4911(2023)
[52] Zhang, G., Chen, S., Huang, K., Peng, Y.: Efficient learning for selecting top-m context-dependent designs. IEEE Trans. Autom. Sci. Eng. (2024). https://doi.org/10.1109/TASE.2024.3391020
[53] Zhang, G., Li, H., Peng, Y.: Sequential sampling for a ranking and selection problem with exponential sampling distributions. In: 2020 Winter Simulation Conference, pp. 2984-2995. IEEE (2020)
[54] Zhang, G., Peng, Y., Xu, Y.: An efficient dynamic sampling policy for monte carlo tree search. In: 2022 Winter Simulation Conference, pp. 2760-2771. IEEE (2022)
[55] Zhang, G., Peng, Y., Zhang, J., Zhou, E.: Asymptotically optimal sampling policy for selecting top-m alternatives. INFORMS J. Comput. 35(6), 1261-1285(2023)
[56] Zhang, S., Lee, L.H., Chew, E.P., Xu, J., Chen, C.-H.: A simulation budget allocation procedure for enhancing the efficiency of optimal subset selection. IEEE Trans. Autom. Control 61(1), 62-75(2015)
[57] Zhen, L., Wu, Y.-W., Zhang, S., Sun, Q.-J., Yue, Q.: A decision framework for automatic guided vehicle routing problem with traffic congestions. J. Oper. Res. Soc. China 8, 357-373(2020)
[58] Zhong, Y., Hong, L.J.: Knockout-tournament procedures for large-scale ranking and selection in parallel computing environments. Oper. Res. 70(1), 432-453(2022)
[59] Zhong, Y., Liu, S., Luo, J., Hong, L.J.: Speeding up Paulson’s procedure for large-scale problems using parallel computing. INFORMS J. Comput. 34(1), 586-606(2022)