IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v112y2018icp19-46.html
   My bibliography  Save this article

Exact and heuristic algorithms for finding envy-free allocations in food rescue pickup and delivery logistics

Author

Listed:
  • Rey, David
  • Almi’ani, Khaled
  • Nair, Divya J.

Abstract

Food rescue organizations collect and re-distribute surplus perishable food for hunger relief. We propose novel approaches to address this humanitarian logistics challenge and find envy-free allocations of the rescued food together with least travel cost routes. We show that this food rescue and delivery problem is NP-hard and we present a cutting-plane algorithm based on Benders’ decomposition for its exact solution. We introduce a novel heuristic algorithm that combines greedy and local search. We test our approaches using real data from food rescue organizations. Our results show that the proposed algorithms are able to efficiently provide envy-free and cost-effective solutions.

Suggested Citation

  • Rey, David & Almi’ani, Khaled & Nair, Divya J., 2018. "Exact and heuristic algorithms for finding envy-free allocations in food rescue pickup and delivery logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 112(C), pages 19-46.
    • Handle: RePEc:eee:transe:v:112:y:2018:i:c:p:19-46
    DOI: 10.1016/j.tre.2018.02.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554517307792
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2018.02.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    2. Tzeng, Gwo-Hshiung & Cheng, Hsin-Jung & Huang, Tsung Dow, 2007. "Multi-objective optimal planning for designing relief delivery systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 43(6), pages 673-686, November.
    3. Burcu Balcik & Seyed Iravani & Karen Smilowitz, 2014. "Multi-vehicle sequential resource allocation for a nonprofit distribution system," IISE Transactions, Taylor & Francis Journals, vol. 46(12), pages 1279-1297, December.
    4. Mladenović, Nenad & Urošević, Dragan & Hanafi, Saı¨d & Ilić, Aleksandar, 2012. "A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 220(1), pages 270-285.
    5. de la Torre, Luis E. & Dolinskaya, Irina S. & Smilowitz, Karen R., 2012. "Disaster relief routing: Integrating research and practice," Socio-Economic Planning Sciences, Elsevier, vol. 46(1), pages 88-97.
    6. Xu, Dongyang & Li, Kunpeng & Zou, Xuxia & Liu, Ling, 2017. "An unpaired pickup and delivery vehicle routing problem with multi-visit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 218-247.
    7. Huang, Michael & Smilowitz, Karen & Balcik, Burcu, 2012. "Models for relief routing: Equity, efficiency and efficacy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 2-18.
    8. Varian, Hal R., 1974. "Equity, envy, and efficiency," Journal of Economic Theory, Elsevier, vol. 9(1), pages 63-91, September.
    9. Wilpen Gorr & Michael Johnson & Stephen Roehrig, 2001. "Spatial decision support system for home-delivered services," Journal of Geographical Systems, Springer, vol. 3(2), pages 181-197, August.
    10. Irem Sengul Orgut & Julie Ivy & Reha Uzsoy, 2017. "Modeling for the equitable and effective distribution of food donations under stochastic receiving capacities," IISE Transactions, Taylor & Francis Journals, vol. 49(6), pages 567-578, June.
    11. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    12. Senay Solak & Christina Scherrer & Ahmed Ghoniem, 2014. "The stop-and-drop problem in nonprofit food distribution networks," Annals of Operations Research, Springer, vol. 221(1), pages 407-426, October.
    13. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    14. Ann Melissa Campbell & Dieter Vandenbussche & William Hermann, 2008. "Routing for Relief Efforts," Transportation Science, INFORMS, vol. 42(2), pages 127-145, May.
    15. Divya J. Nair & David Rey & Vinayak V. Dixit, 2017. "Fair allocation and cost-effective routing models for food rescue and redistribution," IISE Transactions, Taylor & Francis Journals, vol. 49(12), pages 1172-1188, December.
    16. John J. Bartholdi & Loren K. Platzman & R. Lee Collins & William H. Warden, 1983. "A Minimal Technology Routing System for Meals on Wheels," Interfaces, INFORMS, vol. 13(3), pages 1-8, June.
    17. Davis, Lauren B. & Sengul, Irem & Ivy, Julie S. & Brock, Luther G. & Miles, Lastella, 2014. "Scheduling food bank collections and deliveries to ensure food safety and improve access," Socio-Economic Planning Sciences, Elsevier, vol. 48(3), pages 175-188.
    18. Irem Sengul Orgut & Julie Ivy & Reha Uzsoy & James R. Wilson, 2016. "Modeling for the equitable and effective distribution of donated food under capacity constraints," IISE Transactions, Taylor & Francis Journals, vol. 48(3), pages 252-266, March.
    19. Walter Rei & Jean-François Cordeau & Michel Gendreau & Patrick Soriano, 2009. "Accelerating Benders Decomposition by Local Branching," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 333-345, May.
    20. Robert W. Lien & Seyed M. R. Iravani & Karen R. Smilowitz, 2014. "Sequential Resource Allocation for Nonprofit Operations," Operations Research, INFORMS, vol. 62(2), pages 301-317, April.
    21. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    22. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    23. Michael P. Johnson, 2001. "A spatial decision support system prototype for housing mobility program planning," Journal of Geographical Systems, Springer, vol. 3(1), pages 49-67, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Luo, Na & Olsen, Tava & Liu, Yanping & Zhang, Abraham, 2022. "Reducing food loss and waste in supply chain operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 162(C).
    2. Akbarpour, Mina & Ali Torabi, S. & Ghavamifar, Ali, 2020. "Designing an integrated pharmaceutical relief chain network under demand uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    3. Akkerman, Renzo & Buisman, Marjolein & Cruijssen, Frans & de Leeuw, Sander & Haijema, Rene, 2023. "Dealing with donations: Supply chain management challenges for food banks," International Journal of Production Economics, Elsevier, vol. 262(C).
    4. Li, Xun & Rey, David & Dixit, Vinayak V., 2018. "An axiomatic characterization of fairness in transport networks: Application to road pricing and spatial equity," Transport Policy, Elsevier, vol. 68(C), pages 142-157.
    5. Ohad Eisenhandler & Michal Tzur, 2019. "A Segment-Based Formulation and a Matheuristic for the Humanitarian Pickup and Distribution Problem," Transportation Science, INFORMS, vol. 53(5), pages 1389-1408, September.
    6. Tanzid Hasnain & Irem Sengul Orgut & Julie Simmons Ivy, 2021. "Elicitation of Preference among Multiple Criteria in Food Distribution by Food Banks," Production and Operations Management, Production and Operations Management Society, vol. 30(12), pages 4475-4500, December.
    7. Mahmoudi, Monirehalsadat & Shirzad, Khadijeh & Verter, Vedat, 2022. "Decision support models for managing food aid supply chains: A systematic literature review," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    8. Reusken, Meike & Laporte, Gilbert & Rohmer, Sonja U.K. & Cruijssen, Frans, 2024. "Vehicle routing with stochastic demand, service and waiting times — The case of food bank collection problems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 111-127.
    9. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2020. "A green delivery-pickup problem for home hemodialysis machines; sharing economy in distributing scarce resources," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).
    10. Esteban Ogazón & Neale R. Smith & Angel Ruiz, 2022. "Reconfiguration of Foodbank Network Logistics to Cope with a Sudden Disaster," Mathematics, MDPI, vol. 10(9), pages 1-20, April.
    11. Filippi, C. & Guastaroba, G. & Speranza, M.G., 2021. "On single-source capacitated facility location with cost and fairness objectives," European Journal of Operational Research, Elsevier, vol. 289(3), pages 959-974.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mahmoudi, Monirehalsadat & Shirzad, Khadijeh & Verter, Vedat, 2022. "Decision support models for managing food aid supply chains: A systematic literature review," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    2. Divya J. Nair & David Rey & Vinayak V. Dixit, 2017. "Fair allocation and cost-effective routing models for food rescue and redistribution," IISE Transactions, Taylor & Francis Journals, vol. 49(12), pages 1172-1188, December.
    3. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    4. Reusken, Meike & Cruijssen, Frans & Fleuren, Hein, 2023. "A food bank supply chain model: Optimizing investments to maximize food assistance," International Journal of Production Economics, Elsevier, vol. 261(C).
    5. Esteban Ogazón & Neale R. Smith & Angel Ruiz, 2022. "Reconfiguration of Foodbank Network Logistics to Cope with a Sudden Disaster," Mathematics, MDPI, vol. 10(9), pages 1-20, April.
    6. Ohad Eisenhandler & Michal Tzur, 2019. "The Humanitarian Pickup and Distribution Problem," Operations Research, INFORMS, vol. 67(1), pages 10-32, January.
    7. Ali Ekici & Okan Örsan Özener, 2020. "Inventory routing for the last mile delivery of humanitarian relief supplies," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 621-660, September.
    8. Akkerman, Renzo & Buisman, Marjolein & Cruijssen, Frans & de Leeuw, Sander & Haijema, Rene, 2023. "Dealing with donations: Supply chain management challenges for food banks," International Journal of Production Economics, Elsevier, vol. 262(C).
    9. Md Hafizul Islam & Julie Simmons Ivy, 2022. "Modeling the role of efficiency for the equitable and effective distribution of donated food," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 485-534, June.
    10. Ohad Eisenhandler & Michal Tzur, 2019. "A Segment-Based Formulation and a Matheuristic for the Humanitarian Pickup and Distribution Problem," Transportation Science, INFORMS, vol. 53(5), pages 1389-1408, September.
    11. Davis, Lauren B. & Jiang, Steven X. & Morgan, Shona D. & Nuamah, Isaac A. & Terry, Jessica R., 2016. "Analysis and prediction of food donation behavior for a domestic hunger relief organization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 26-37.
    12. Byrne, Anne T. & Just, David R., 2022. "Review: Private food assistance in high income countries: A guide for practitioners, policymakers, and researchers," Food Policy, Elsevier, vol. 111(C).
    13. Jon M. Stauffer & Manoj Vanajakumari & Subodha Kumar & Theresa Mangapora, 2022. "Achieving equitable food security: How can food bank mobile pantries fill this humanitarian need," Production and Operations Management, Production and Operations Management Society, vol. 31(4), pages 1802-1821, April.
    14. Tanzid Hasnain & Irem Sengul Orgut & Julie Simmons Ivy, 2021. "Elicitation of Preference among Multiple Criteria in Food Distribution by Food Banks," Production and Operations Management, Production and Operations Management Society, vol. 30(12), pages 4475-4500, December.
    15. Alkaabneh, Faisal & Diabat, Ali & Gao, Huaizhu Oliver, 2021. "A unified framework for efficient, effective, and fair resource allocation by food banks using an Approximate Dynamic Programming approach," Omega, Elsevier, vol. 100(C).
    16. Sanjay L. Ahire & Pelin Pekgün, 2018. "Harvest Hope Food Bank Optimizes Its Promotional Strategy to Raise Donations Using Integer Programming," Interfaces, INFORMS, vol. 48(4), pages 291-306, August.
    17. Sengul Orgut, Irem & Ivy, Julie S. & Uzsoy, Reha & Hale, Charlie, 2018. "Robust optimization approaches for the equitable and effective distribution of donated food," European Journal of Operational Research, Elsevier, vol. 269(2), pages 516-531.
    18. Yang, Yongjian & Yin, Yunqiang & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Dhamotharan, Lalitha, 2023. "Distributionally robust multi-period location-allocation with multiple resources and capacity levels in humanitarian logistics," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1042-1062.
    19. Reusken, Meike & Laporte, Gilbert & Rohmer, Sonja U.K. & Cruijssen, Frans, 2024. "Vehicle routing with stochastic demand, service and waiting times — The case of food bank collection problems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 111-127.
    20. Buisman, Marjolein E. & Haijema, Rene & Akkerman, Renzo & Bloemhof, Jacqueline M., 2019. "Donation management for menu planning at soup kitchens," European Journal of Operational Research, Elsevier, vol. 272(1), pages 324-338.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:112:y:2018:i:c:p:19-46. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.