Assignment Algorithms for Grocery Bill Reduction

摘要

This paper focuses on identifying an algorithm that can be utilized in grocery cost reduction within the consumer space. The algorithm produces the combination of grocery products to stores that net the lowest overall grocery cost for the consumer. This is often referred to as a combinatorial optimization problem, and is commonly used by many industries for resource or task assignment. To identify a solution for grocery cost reduction, the Kuhn-Munkres algorithm (often referred to as the Hungarian algorithm) and the Deepest Hole algorithm are explored in depth. After comparing the algorithms based on their implementation and performance, a third solution combining ideas from the Kuhn-Munkres algorithm and Deepest Hole algorithm was created to solve for the specific needs of this problem. This solution will be referred to as the KMDH Hybrid algorithm. Modifications include the ability for users to select the number of stores they wish to shop at, the ability to use a rectangular grid, and allowing for one-to-many assignments. All three algorithms were developed in Python, and tested on a dataset with a predefined list of stores, products, and prices. It is apparent that the proposed hybrid algorithm can be applied to the assignment problem, and has the potential to be applied to other similar applications.