Retrieval sequencing in autonomous vehicle storage and retrieval systems

ABSTRACT

Autonomous vehicle storage and retrieval systems (AVS/RSs) are widely used in e-commerce warehouses due to their high throughput and flexibility. In such systems, storage and retrieval transactions are performed by lifts and vehicles. This paper focuses on the sequencing retrievals problem in an AVS/RS, which is an important problem for daily operations. We formulate this sequencing problem as a mixed-integer program to determine a retrieval sequence for the lift and the vehicles, one that minimises the makespan. A dynamic programming approach is proposed to solve the sequencing problem to optimality. However, the solution time of the dynamic programming method is exponentially increasing in the number of retrieval requests. To be more practical, we present a beam search heuristic that can solve large-sized instances in reasonable time. Computational experiments verify that near-optimal solutions can be found by the beam search heuristic. Compared to commonly used heuristics and straightforward heuristics, the beam search decreases the makespan by up to 15%. Finally, we analyse how vehicle modes impact the makespan, showing evidence that a small makespan can be achieved when considering a realistic mode of vehicles.

KEYWORDS:

• AVS/RS
• warehousing
• sequencing retrieval requests
• makespan minimisation
• dynamic programming

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are available from the corresponding author, [Jingjing Yang], upon reasonable request.

Additional information

Funding

This research is supported by the National Key R&D Program of China (No. 2018YFB1601401); the National Natural Science Foundation of China (Nos. 71991464/71991460, 72271225, 72091215/72091210,   71921001); Anhui Provincial Natural Science Foundation (No. 2208085J06); and the USTC Research Funds of the Double First-Class Initiative (No. YD2040002017).

Notes on contributors

Yugang Yu

Yugang Yu is Yangtze Scholar Distinguished Professor of Logistics and Operations Management at the University of Science and Technology of China (USTC). He obtained his PhD in Management Science and Engineering from the School of Management, USTC in 2003. His current research interests are in logistics, supply chain management and business analytics. He has published more than 100 papers in academic journals, including Manufacturing & Service Operations Management, Marketing Science, Productions and Operations Management, Transportation Science, IISE Transactions, International Journal of Production Research, European Journal of Operational Research, and Navel Research Logistics. His papers were cited more than 2000 times, and Elsevier ranked him as one of ‘the most cited researchers in the Mainland of China’ in 2014–2019. He received a career development VENI project from the Netherlands Organisation for Scientific Research (NWO), a distinguished research scholar grant from the National Science Foundation of China (NSFC), and won the First Prize of Humanities and Social Sciences of Ministry of Education of China.

Jingjing Yang

Jingjing Yang is a Ph.D candidate at School of Management, University of Science and Technology of China. Her research interests include warehousing, algorithm design and optimisation.

Xiaolong Guo

Xiaolong Guo is an Associate Professor at the School of Management, University of Science and Technology of China. He holds a Ph.D. in Management Science and Engineering from the University of Science and Technology of China. He has published a book ‘Storage Policies and Maintenance Support Strategies in Warehousing Systems’ in Springer and 40 articles in journals including Manufacturing & Service Operations Management, Production and Operations Management, Journal of Management Information Systems, International Journal of Production Research, European Journal of Operational Research, and Omega. His research has been recognised as outstanding achievement by the National Natural Science Foundation of China, and won the First Prize of Humanities and Social Sciences of Ministry of Education of the People's Republic of China.