Robotic Warehousing Operations: A Learn-Then-Optimize Approach to Large-Scale Neighborhood Search

References

• ABI Research (2021) Modern fulfillment trends: Warehouse robotics, handheld devices and wearables. Technical report, ABI Research, New York.Google Scholar
• Adamo T, Ghiani G, Guerriero E, Manni E (2017a) Automatic instantiation of a variable neighborhood descent from a mixed integer programming model. Oper. Res. Perspect. 4:123–135.Google Scholar
• Adamo T, Ghiani G, Grieco A, Guerriero E, Manni E (2017b) MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration. Comput. Oper. Res. 83:106–119.Google Scholar
• Ahuja R, Ergun Ö, Orlin J, Punnen A (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123(1–3):75–102.Google Scholar
• Allgor R, Cezik T, Chen D (2023) Algorithm for robotic picking in Amazon fulfillment centers enables humans and robots to work together effectively. INFORMS J. Appl. Anal. 53(4):266–282.Link, Google Scholar
• Anderson R, Huchette J, Ma W, Tjandraatmadja C, Vielma JP (2020) Strong mixed-integer programming formulations for trained neural networks. Math. Programming 183(1–2):3–39.Google Scholar
• Ang M, Lim YF, Sim M (2012) Robust storage assignment in unit-load warehouses. Management Sci. 58(11):2114–2130.Link, Google Scholar
• Azadeh K, De Koster R, Roy D (2019) Robotized and automated warehouse systems: Review and recent developments. Transportation Sci. 53(4):917–945.Link, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Google Scholar
• Bertsimas D, King A (2016) Or forum an algorithmic approach to linear regression. Oper. Res. 64(1):2–16.Link, Google Scholar
• Bertsimas D, Stellato B (2022) Online mixed-integer optimization in milliseconds. INFORMS J. Comput. 34(4):2229–2248.Link, Google Scholar
• Bertsimas D, Stock Patterson S (1998) The air traffic flow management problem with enroute capacities. Oper. Res. 46(3):406–422.Link, Google Scholar
• Boysen N, Briskorn D, Emde S (2017) Parts-to-picker based order processing in a rack-moving mobile robots environment. Eur. J. Oper. Res. 262(2):550–562.Google Scholar
• Boysen N, De Koster R, Weidinger F (2019) Warehousing in the e-commerce era: A survey. Eur. J. Oper. Res. 277(2):396–411.Google Scholar
• Briggs KM, Song L, Prellberg T (2009) A note on the distribution of the maximum of a set of Poisson random variables. Preprint, submitted March 25, https://arxiv.org/abs/0903.4373.Google Scholar
• Carlsson J, Song S (2017) Coordinated logistics with a truck and a drone. Management Sci. 64(9):4052–4069.Link, Google Scholar
• Cezik T, Graves SC, Liu AC (2022) Velocity-based stowage policy for semi-automated fulfillment system. Production Oper. Management, ePub ahead of print May 19, https://doi.org/10.1111/poms.13745.Google Scholar
• Chen X, Tian Y (2019) Learning to perform local rewriting for combinatorial optimization. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Red Hook, NY), 6281–6292.Google Scholar
• Chen Z, Alonso-Mora J, Bai X, Harabor DD, Stuckey PJ (2021) Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robotics Automation Lett. 6(3):5816–5823.Google Scholar
• Dabia S, Ropke S, Van Woensel T, De Kok T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):380–396.Link, Google Scholar
• Dey SS, Kazachkov A, Lodi A, Munoz G (2022) Cutting plane generation through sparse principal component analysis. SIAM J. Optim. 32(2):1319–1343.Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Google Scholar
• Florio AM, Absi N, Feillet D (2021) Routing electric vehicles on congested street networks. Transportation Sci. 55(1):238–256.Link, Google Scholar
• Gharehgozli A, Zaerpour N (2020) Robot scheduling for pod retrieval in a robotic mobile fulfillment system. Transportation Res. Part E Logist. Transportation Rev. 142:102087.Google Scholar
• Ghiani G, Laporte G, Manni E (2015) Model-based automatic neighborhood design by unsupervised learning. Comput. Oper. Res. 54:108–116.Google Scholar
• Goeke D, Schneider M (2021) Modeling single-picker routing problems in classical and modern warehouses. INFORMS J. Comput. 33(2):436–451.Abstract, Google Scholar
• Grand View Research (2021) Autonomous mobile robots market size, share & trends analysis report. Technical report.Google Scholar
• Grenouilleau F, van Hoeve WJ, Hooker JN (2019) A multi-label a* algorithm for multi-agent pathfinding. Benton J, Lipovetzky N, Onaindia E, Smith D, eds. Proc. Internat. Conf. Automated Planning Scheduling, vol. 29 (AAAI Press, Palo Alto, CA), 181–185.Google Scholar
• Gupta P, Gasse M, Khalil E, Mudigonda P, Lodi A, Bengio Y (2020) Hybrid models for learning to branch. Adv. Neural Inform. Processing Systems, 33, 18087–18097.Google Scholar
• Hottung A, Tierney K (2020) Neural large neighborhood search for the capacitated vehicle routing problem. Giacomo G, Catala A, Dilkina B, Milano M, Barro S, Bugarin A, Lang J, eds. Proc. Eur. Conf. Artificial Intelligence, vol. 325 (IOS Press, Amsterdam), 443–450.Google Scholar
• Jennings JS, Whelan G, Evans WF (1997) Cooperative search and rescue with a team of mobile robots. Bejczy A, Fiorini P, eds. Eighth Internat. Conf. Advanced Robotics Proc. (Cambridge University Press, Cambridge), 193–200.Google Scholar
• Khalil E, Le Bodic P, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. AAAI Conf. Artificial Intelligence, vol. 30 (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Larsen E, Lachapelle S, Bengio Y, Frejinger E, Lacoste-Julien S, Lodi A (2022) Predicting tactical solutions to operational planning problems under imperfect information. INFORMS J. Comput. 34(1):227–242.Link, Google Scholar
• Li S, Yan Z, Wu C (2021b) Learning to delegate for large-scale vehicle routing. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan J, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Red Hook, NY), 26198–26211.Google Scholar
• Li J, Tinka A, Kiesel S, Durham JW, Kumar TS, Koenig S (2021a) Lifelong multi-agent path finding in large-scale warehouses. Proc. Conf. AAAI Artificial Intelligence, vol. 35 (AAAI Press, Palo Alto, CA), 11272–11281.Google Scholar
• Liu D, Fischetti M, Lodi A (2022) Learning to search in local branching. Proc. Conf. AAAI Artificial Intelligence, vol. 36 (AAAI Press, Palo Alto, CA), 3796–3803.Google Scholar
• Liu M, Ma H, Li J, Koenig S (2019) Task and path planning for multi-agent pickup and delivery. Proc. Internat. Joint Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1152–1160.Google Scholar
• Liu D, Perreault V, Hertz A, Lodi A (2023) A machine learning framework for neighbor generation in metaheuristic search. Frontiers Appl. Math. Statist. 9:1128181.Google Scholar
• Liu Y, Yu Y, Zhang Y, Baldacci R, Tang J, Luo X, Sun W (2023) Branch-cut-and-price for the time-dependent green vehicle routing problem with time windows. INFORMS J. Comput. 35(1):14–30.Link, Google Scholar
• Ma H, Li J, Kumar Y, Koenig S (2017) Lifelong multi-agent path finding for online pickup and delivery tasks. Proc 16th Internat. Conf. Autonomous Agents MultiAgent Systems (AAMAS) (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 837–845.Google Scholar
• McKinsey Global Institute (2017) A future that works: AI, automation, employment, and productivity. Technical report.Google Scholar
• Mišić VV (2020) Optimization of tree ensembles. Oper. Res. 68(5):1605–1624.Link, Google Scholar
• Moll R, Perkins TJ, Barto AG (2000) Machine learning for subproblem selection. ICML (Morgan Kaufmann Publishers Inc., San Francisco), 615–622.Google Scholar
• Morabit M, Desaulniers G, Lodi A (2021) Machine-learning–based column selection for column generation. Transportation Sci. 55(4):815–831.Link, Google Scholar
• Ozbaygin G, Karasan OE, Savelsbergh M, Yaman H (2017) A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transportation Res. Part B Methodological 100:115–137.Google Scholar
• Poikonen S, Golden B (2020) The mothership and drone routing problem. INFORMS J. Comput. 32(2):249–262.Link, Google Scholar
• Qin H, Xiao J, Ge D, Xin L, Gao J, He S, Hu H, Carlsson JG (2022) JD.com: Operations research algorithms drive intelligent warehouse robots to work. INFORMS J. Appl. Anal. 52(1):42–55.Link, Google Scholar
• Salzman O, Stern R (2020) Research challenges and opportunities in multi-agent path finding and multi-agent pickup and delivery problems. Proc. 19th Internat. Conf. Autonomous Agents MultiAgent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1711–1715.Google Scholar
• Sambharya R, Hall G, Amos B, Stellato B (2024) Learning to warm-start fixed-point optimization algorithms. J. Machine Learn. Res. 25(166):1–46.Google Scholar
• Šišlák D, Volf P, Pěchouček M (2010) Agent-based cooperative decentralized airplane-collision avoidance. IEEE Trans. Intelligent Transportation Systems 12(1):36–46.Google Scholar
• Song J, Lanka R, Yue Y, Dilkina B (2020) A general large neighborhood search framework for solving integer linear programs. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Red Hook, NY), 20012–20023.Google Scholar
• Tang Y, Agrawal S, Faenza Y (2020) Reinforcement learning for integer programming: Learning to cut. Lawrence N, ed. Internat. Conf. Machine Learn. (PMLR, New York), 9367–9376.Google Scholar
• Valle CA, Beasley JE (2021) Order allocation, rack allocation and rack sequencing for pickers in a mobile rack environment. Comput. Oper. Res. 125:105090.Google Scholar
• Van Der Gaast JP, De Koster RB, Adan IJ, Resing JA (2020) Capacity analysis of sequential zone picking systems. Oper. Res. 68(1):161–179.Link, Google Scholar
• Wang Z, Sheu JB, Teo CP, Xue G (2022) Robot scheduling for mobile-rack warehouses: Human–robot coordinated order picking systems. Production Oper. Management 31(1):98–116.Google Scholar
• Weidinger F, Boysen N (2018) Scattered storage: How to distribute stock keeping units all around a mixed-shelves warehouse. Transportation Sci. 52(6):1412–1427.Link, Google Scholar
• Wurman PR, D’Andrea R, Mountz M (2008) Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine 29(1):9.Google Scholar
• Zhang M, Batta R, Nagi R (2009) Modeling of workflow congestion and optimization of flow routing in a manufacturing/warehouse facility. Management Sci. 55(2):267–280.Link, Google Scholar
• Zhang W, Jacquillat A, Wang K, Wang S (2023) Routing optimization with vehicle-customer coordination. Management Sci. 69(11):6876–6897.Link, Google Scholar