QueQat
An AI to optimise queue management
An AI built with Deep Q-Learning that optimises queue management in multi-queue systems, reducing waiting times by over 30%.
What...?
QueQat is an AI system built using Deep Q-Learning that optimises queue management in multi-queue systems. The system strategically assigns customers to different queues based on their predicted service times and current queue states, reducing average waiting times by over 30% compared to existing strategies. This can be applied to supermarkets, healthcare systems, etc.
How...?
Imagine the following scenario with 3 empty queues, and 5 customers walking in, their service times being 10, 10, 10, 3, 3 respectively.
If we let them choose their own queues, the 3 customers with service time 10 will obviously choose all 3 empty queues, and the 2 customers with service time 3 will have to wait for the customers with service time 10 to finish, despite having a shorter service time. The total waiting time will be 20.
However, if we instead assign the customers with service time 10 to queues 1 and 2 only, leaving queue 3 empty for the customers with service time 3, the total waiting time will be 13. This is a reduction of the total waiting time at a compromise of one person having to wait longer.
Now imagine more complicated queues, where we do not know when the next customer will come in or how long they will take to serve. How should we assign the current customer to minimise the total waiting time?
This is when machine learning comes into play. Through millions of simulations, QueQat can make use of historical data of service time distributions, the current state of the queues, and the estimated service time of the current customer, to predict the queue the current customer should be assigned to that will be the best for the future.
Performance Comparison
Shortest Queue
Customers choose the shortest available queue
Single Queue
All customers join one queue, served in order
QueQat
AI-optimised queue assignment
QueQat consistently outperforms traditional strategies with >30% reduction in waiting times
Technical Details
Deep Q-Learning
Input Layer: The states of each queue, and the estimated service time of the current customer.
Hidden Layers: A layer of 64 neurons with ReLU, and a layer of 32 neurons with ReLU.
Output Layer: Q-values for each queue. (How good each queue is, highest Q-value is chosen)
Reward Function: Negative total waiting time.
Frameworks
Training: Python PyTorch, TensorFlow
Frontend: Python Flask
Results
QueQat won 2nd runners-up in the 55th Joint School Science Exhibition, and had a 7-day exhibition at the Hong Kong Central Library.
QueQat was also reported by several local media and our team got on a radio show at RTHK.
Current Status
You missed the exhibition and now the server is no longer running.
What's next...?
Similar approaches could be applied to other scenarios that involve multiple people waiting, for example, elevator systems and traffic systems.
Might do this for my final year project, idk.