A Graph Algorithm to Eliminate Hunger and Food Waste by Matching Excess Food to Demand
DOI:
https://doi.org/10.47611/jsrhs.v12i1.4297Keywords:
Food Distribution, Greedy, BipartiteAbstract
Millions of tons of food from grocery stores go to waste every year in the US, while many people consistently depend on community food banks. Having a plan to transport food surplus to the needy will eliminate both food waste and hunger at the same time. This problem is modeled as a bipartite graph with one set of vertices representing food donors with certain excess food of various types, and the other set representing food banks with demand of different types of food, and a cost of transportation on each edge. We create four heuristic algorithms to find low-cost transportation plans that satisfy all food needs, and compare them in terms of plan cost and runtime. We find that the basic greedy algorithm does the best in both aspects.
Downloads
References or Bibliography
[Asratian et al.] Asratian, A.S., Denley, T.M.J., &Haggkvist, R. [2008] Bipartite Graphs and Their Applications
[Chiles et al] Chiles, C.R., &Dau, M.T (2005). An analysis of current supply chain best practices in the retail industry with case studies of Wal-Mart and Amazon.com. http://hdl.handle.net/1721.1/33314
[DAILYBOWL] Daily Bowl https://dailybowl.org
[Gupta et al.] Gupta, A., Yadav, R., Nair, A., Chakraborty, Abhijnan.,Ranu, S.,Bagchi, A. (2022). Fairfoody: Bringing in fairness in food delivery. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11900-11907. https://doi.org/10.48550/arXiv.2203.08849
[Hochbaum et al.] Hochbaum, D.S., & Segev, A. [1989] Analysis of a flow problem with fixed charges. In Network, An International Journal Volume 19, Issue 3. https://doi.org/10.1002/net.3230190304
[Jain et al.] Jain, P., Goodrich, M.A. (2022). Processes for a Colony Solving the Best-of-N Problem Using a Bipartite Graph Representation. In: Matsuno, F., Azuma, Si., Yamamoto, M. (eds) Distributed Autonomous Robotic Systems. DARS 2021. Springer Proceedings in Advanced Robotics, vol 22. Springer, Cham.https://doi.org/10.1007/978-3-030-92790-5_29
[Joshi et al.] Joshi, M., Singh, A., Ranu, S, Bagchi, A., Karia, P. & Kala, P. (2021). Batching and matching for food delivery in dynamic road networks. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 2099-2104.https://doi.org/10.48550/arXiv.2008.12905
[Kim et al.] Kim, D., &Pardalos, P.M.,A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure[1999]. In Operations Research Letters,Volume 24, Issue 4,Pages 195-203,ISSN 0167-6377,https://doi.org/10.1016/S0167-6377(99)00004-8
[KimHJ et al.] Kim, HJ., &Hooker, J.N. Solving Fixed-Charge Network Flow Problems with a Hybrid Optimization and Constraint Programming Approach. In Annals of Operations Research 115, 95–124 (2002).https://doi.org/10.1023/A:1021145103592
[Michelson et al.] Michelson, H., Boucher, S., Cheng, X., Huang, J., & Jia, X. (2018). Connecting supermarkets and farms: The role of intermediaries in Walmart China's fresh produce supply chains. In Renewable Agriculture and Food Systems, 33(1), 47-59. https://doi.org/10.1017/S174217051600051X
[REFED] ReFED Insights Engine https://insights-engine.refed.org
[Vassilev et al.] Vassilev, T.S., Huntington, L. Algorithms for Matchings in Graphs. In Algorithms Research , Vol. 1 No. 4, 2012, pp. 20-30 (2012).
[Vyve] Van Vyve, M. (2011). Fixed-Charge Transportation on a Path: Linear Programming Formulations. In Günlük, O., Woeginger, G.J. (eds) Integer Programming and Combinatoral Optimization. IPCO 2011. Lecture Notes in Computer Science, vol 6655. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20807-2_33
Published
How to Cite
Issue
Section
Copyright (c) 2023 Neil Makur; Maya Mathews
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright holder(s) granted JSR a perpetual, non-exclusive license to distriute & display this article.
