Optimising Goods Placement in Shopping Companions
This research focuses on developing innovative algorithms to enhance the efficiency and convenience of storage compartments in retail settings
1
Background and Research Questions
The integration of technology into the retail sector has introduced numerous innovative solutions aimed at improving the shopping experience. One such innovation is the shopping companion, designed to streamline the shopping process. However, the effectiveness of these devices largely depends on the optimal placement of goods within their storage compartments. This study aims to address this crucial aspect by developing an algorithm for optimal goods placement
2
Key research questions:
1. How can bin packing algorithms be applied to optimize the placement of goods within the storage compartment?
2. What is the optimal algorithm for placing goods within the storage compartment that maximizes storage capacity while ensuring ease of use and convenience for shoppers?
3
Research Approach and Methodology
To answer these questions, a systematic and rigorous approach was adopted:
1. Literature Review: Reviewed existing literature on bin packing algorithms to understand the current state of knowledge and identify potential gaps
2. Algorithm Implementation: Implemented and evaluated various bin packing algorithms to identify the most effective solution
Policy-Based Reinforcement Learning:
- Agent Learning: The agent learns a policy that maps states (current state of the bin and items) to actions (decision of item placement)
- Network Training: The neural network is trained to maximize the expected reward, optimizing space usage (refers to figure on the left)
4
Key Findings
1. Three-Dimensional Bin Packing Problem: The study provided a comprehensive overview of the three-dimensional bin packing problem, a key issue in combinatorial optimization
2. Branch-and-Bound Algorithm: Detailed analysis of this powerful technique revealed its limitations, particularly its slow performance with large problems
3. CLP Spreadsheet Solver: An open-source tool for solving and visualizing Container Loading Problems (CLPs), which facilitated the study of 3D bin packing problems (refers to figure on the left)
4. Online 3D Bin Packing with Constrained Deep Reinforcement Learning (CDRL): Identified as the most effective method for online 3D bin packing, outperforming existing heuristic and deep learning-based methods. This method utilizes advanced techniques in deep reinforcement learning to handle constraints (refers to figure below)
