Digging Deep: Dynamic Programming for Optimal Routing With Double‐Deep Autonomous Mobile Robot Picking

ABSTRACT Multi‐tote autonomous mobile robots (MT‐AMRs) are an emerging warehousing technology in which a mobile drive unit carries a lift‐based storage‐and‐retrieval mechanism with an extendable fork and a multi‐tote onboard buffer. On autonomous picking tours, an MT‐AMR visits storage locations, extracts product totes from racks, stores them in its onboard buffer, and delivers the collected totes to a human‐operated workstation. The extendable fork enables double‐deep access, that is, retrieval of second‐tier totes after temporarily removing blocking totes from the first tier. This capability changes the effective routing network in rectangular warehouses by creating alternative service options and motivating denser storage layouts. We study optimal MT‐AMR picking tours under three layouts: (i) conventional single‐deep racks on both sides of each aisle, where near‐side totes can be served from the adjacent aisle, reducing aisle entries; (ii) a 1.5‐deep layout with three rack tiers between neighboring aisles, where middle‐tier totes are accessible from either adjacent aisle; and (iii) double‐deep storage with two‐depth racks accessible only from their dedicated aisle, minimizing footprint but requiring additional removals for blocked second‐depth totes. For each layout, we model routing as an optimization problem on a structured warehouse graph and extend the state space of an established dynamic‐programming approach for rectangular‐warehouse routing to capture the additional service options induced by double‐deep access. We prove that all three extensions preserve polynomial‐time solvability and yield optimal tours. Using the resulting algorithms, we quantify the trade‐off between storage density and tour length and characterize when increased access flexibility translates into substantial travel savings.