Deterministic Structure of Vertical Configurations in Minimal Picker Tours for Rectangular Warehouses
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914444017139712 |
|---|---|
| author | Dunn, George Stojanovski, Elizabeth Lamichhane, Bishnu Charkhgard, Hadi Eshragh, Ali |
| author_facet | Dunn, George Stojanovski, Elizabeth Lamichhane, Bishnu Charkhgard, Hadi Eshragh, Ali |
| contents | The picker routing problem seeks the shortest tour through a warehouse that visits every item in a given pick-list and returns to the depot. For rectangular warehouses, dynamic programming algorithms solve this problem by sequentially evaluating combinations of vertical edge configurations within subaisles and horizontal edge configurations between aisles. These methods proceed through stages one after another, but how those stages relate to each other has received limited structural analysis. Building on our recent structural result for rectangular warehouses, which shows that connecting double traversals are not required to maintain tour connectivity, we prove that for rectangular warehouses of any size, the horizontal edge structure of a minimal tour subgraph uniquely determines the required vertical edge configurations. The proof uses a case analysis on horizontal degree along each aisle and at merged-segment endpoints, showing that the admissible vertical pattern in each regime is uniquely determined by Eulerian parity and by minimizing traversal length. This deterministic relationship implies that vertical configuration stages in existing dynamic programming algorithms can be replaced by a direct inference step, reducing the combinatorial complexity of the problem and providing a structural foundation for developing more efficient exact methods for warehouse layouts of any size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00365 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Structure of Vertical Configurations in Minimal Picker Tours for Rectangular Warehouses Dunn, George Stojanovski, Elizabeth Lamichhane, Bishnu Charkhgard, Hadi Eshragh, Ali Optimization and Control The picker routing problem seeks the shortest tour through a warehouse that visits every item in a given pick-list and returns to the depot. For rectangular warehouses, dynamic programming algorithms solve this problem by sequentially evaluating combinations of vertical edge configurations within subaisles and horizontal edge configurations between aisles. These methods proceed through stages one after another, but how those stages relate to each other has received limited structural analysis. Building on our recent structural result for rectangular warehouses, which shows that connecting double traversals are not required to maintain tour connectivity, we prove that for rectangular warehouses of any size, the horizontal edge structure of a minimal tour subgraph uniquely determines the required vertical edge configurations. The proof uses a case analysis on horizontal degree along each aisle and at merged-segment endpoints, showing that the admissible vertical pattern in each regime is uniquely determined by Eulerian parity and by minimizing traversal length. This deterministic relationship implies that vertical configuration stages in existing dynamic programming algorithms can be replaced by a direct inference step, reducing the combinatorial complexity of the problem and providing a structural foundation for developing more efficient exact methods for warehouse layouts of any size. |
| title | Deterministic Structure of Vertical Configurations in Minimal Picker Tours for Rectangular Warehouses |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.00365 |