IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v289y2021i3p999-1007.html
   My bibliography  Save this article

The assignment and loading transportation problem

Author

Listed:
  • Homsi, Gabriel
  • Jordan, Jeremy
  • Martello, Silvano
  • Monaci, Michele

Abstract

We consider a generalization of the multiple knapsack problem that combines assignment and loading. The problem can arise in military and emergency situations in which one is required to refurnish a unit with a number of different goods available at different locations. We present a mathematical model and study Lagrangian and surrogate relaxations. We propose heuristic and metaheuristic approaches which we use to develop two overall approximation algorithms: a self-contained polynomial-time heuristic and a more time consuming matheuristic approach that makes use of a MILP solver. Solution times and accuracy of lower and upper bounds are computationally evaluated on a real military data set and on sets of both realistic and randomly generated instances.

Suggested Citation

  • Homsi, Gabriel & Jordan, Jeremy & Martello, Silvano & Monaci, Michele, 2021. "The assignment and loading transportation problem," European Journal of Operational Research, Elsevier, vol. 289(3), pages 999-1007.
    • Handle: RePEc:eee:ejores:v:289:y:2021:i:3:p:999-1007
    DOI: 10.1016/j.ejor.2019.07.039
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719306034
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.07.039?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. Simon, Jay & Apte, Aruna & Regnier, Eva, 2017. "An application of the multiple knapsack problem: The self-sufficient marine," European Journal of Operational Research, Elsevier, vol. 256(3), pages 868-876.
    2. Diaz, Juan Esteban & Handl, Julia & Xu, Dong-Ling, 2018. "Integrating meta-heuristics, simulation and exact techniques for production planning of a failure-prone manufacturing system," European Journal of Operational Research, Elsevier, vol. 266(3), pages 976-989.
    3. Zhen, Lu & Wang, Kai & Wang, Shuaian & Qu, Xiaobo, 2018. "Tug scheduling for hinterland barge transport: A branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 265(1), pages 119-132.
    4. Gralla, Erica & Goentzel, Jarrod, 2018. "Humanitarian transportation planning: Evaluation of practice-based heuristics and recommendations for improvement," European Journal of Operational Research, Elsevier, vol. 269(2), pages 436-450.
    5. Geir Dahl & Njål Foldnes, 2006. "LP based heuristics for the multiple knapsack problem with assignment restrictions," Annals of Operations Research, Springer, vol. 146(1), pages 91-104, September.
    6. Dimitrov, Nedialko B. & Solow, Daniel & Szmerekovsky, Joseph & Guo, Jia, 2017. "Emergency relocation of items using single trips: Special cases of the Multiple Knapsack Assignment Problem," European Journal of Operational Research, Elsevier, vol. 258(3), pages 938-942.
    7. 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.
    8. M. Dawande & J. Kalagnanam & P. Keskinocak & F.S. Salman & R. Ravi, 2000. "Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions," Journal of Combinatorial Optimization, Springer, vol. 4(2), pages 171-186, June.
    9. Kataoka, Seiji & Yamada, Takeo, 2014. "Upper and lower bounding procedures for the multiple knapsack assignment problem," European Journal of Operational Research, Elsevier, vol. 237(2), pages 440-447.
    Full references (including those not matched with items on IDEAS)

    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. Stefka Fidanova & Krassimir Todorov Atanassov, 2021. "ACO with Intuitionistic Fuzzy Pheromone Updating Applied on Multiple-Constraint Knapsack Problem," Mathematics, MDPI, vol. 9(13), pages 1-7, June.
    2. Martello, Silvano & Monaci, Michele, 2020. "Algorithmic approaches to the multiple knapsack assignment problem," Omega, Elsevier, vol. 90(C).
    3. Hans Kellerer & Joseph Y.‐T. Leung & Chung‐Lun Li, 2011. "Multiple subset sum with inclusive assignment set restrictions," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(6), pages 546-563, September.
    4. J. Álvaro Gómez-Pantoja & M. Angélica Salazar-Aguilar & José Luis González-Velarde, 2021. "The food bank resource allocation problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 266-286, April.
    5. Dell’Amico, Mauro & Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2019. "Mathematical models and decomposition methods for the multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(3), pages 886-899.
    6. Balcik, Burcu & Yanıkoğlu, İhsan, 2020. "A robust optimization approach for humanitarian needs assessment planning under travel time uncertainty," European Journal of Operational Research, Elsevier, vol. 282(1), pages 40-57.
    7. Rodríguez-Espíndola, Oscar & Ahmadi, Hossein & Gastélum-Chavira, Diego & Ahumada-Valenzuela, Omar & Chowdhury, Soumyadeb & Dey, Prasanta Kumar & Albores, Pavel, 2023. "Humanitarian logistics optimization models: An investigation of decision-maker involvement and directions to promote implementation," Socio-Economic Planning Sciences, Elsevier, vol. 89(C).
    8. Mohammadmehdi Hakimifar & Burcu Balcik & Christian Fikar & Vera Hemmelmayr & Tina Wakolbinger, 2022. "Evaluation of field visit planning heuristics during rapid needs assessment in an uncertain post-disaster environment," Annals of Operations Research, Springer, vol. 319(1), pages 517-558, December.
    9. Harwin De Vries & Luk N. Van Wassenhove, 2020. "Do Optimization Models for Humanitarian Operations Need a Paradigm Shift?," Production and Operations Management, Production and Operations Management Society, vol. 29(1), pages 55-61, January.
    10. Zhen, Lu & Wang, Kai & Wang, Shuaian & Qu, Xiaobo, 2018. "Tug scheduling for hinterland barge transport: A branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 265(1), pages 119-132.
    11. Dufour, Émilie & Laporte, Gilbert & Paquette, Julie & Rancourt, Marie–Ève, 2018. "Logistics service network design for humanitarian response in East Africa," Omega, Elsevier, vol. 74(C), pages 1-14.
    12. Bruni, M.E. & Khodaparasti, S. & Beraldi, P., 2020. "The selective minimum latency problem under travel time variability: An application to post-disaster assessment operations," Omega, Elsevier, vol. 92(C).
    13. Allahyari, Somayeh & Salari, Majid & Vigo, Daniele, 2015. "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 756-768.
    14. Sahin, Halenur & Kara, Bahar Yetis & Karasan, Oya Ekin, 2016. "Debris removal during disaster response: A case for Turkey," Socio-Economic Planning Sciences, Elsevier, vol. 53(C), pages 49-59.
    15. Diaz, Juan Esteban & Handl, Julia & Xu, Dong-Ling, 2018. "Integrating meta-heuristics, simulation and exact techniques for production planning of a failure-prone manufacturing system," European Journal of Operational Research, Elsevier, vol. 266(3), pages 976-989.
    16. Chowdhury, Sudipta & Emelogu, Adindu & Marufuzzaman, Mohammad & Nurre, Sarah G. & Bian, Linkan, 2017. "Drones for disaster response and relief operations: A continuous approximation model," International Journal of Production Economics, Elsevier, vol. 188(C), pages 167-184.
    17. Vahdani, Behnam & Veysmoradi, D. & Mousavi, S.M. & Amiri, M., 2022. "Planning for relief distribution, victim evacuation, redistricting and service sharing under uncertainty," Socio-Economic Planning Sciences, Elsevier, vol. 80(C).
    18. Tahir Andrabi & Benjamin Daniels & Jishnu Das, 2023. "Human Capital Accumulation and Disasters: Evidence from the Pakistan Earthquake of 2005," Journal of Human Resources, University of Wisconsin Press, vol. 58(4), pages 1057-1096.
    19. A. Anaya-Arenas & J. Renaud & A. Ruiz, 2014. "Relief distribution networks: a systematic review," Annals of Operations Research, Springer, vol. 223(1), pages 53-79, December.
    20. Dilsu Binnaz Ozkapici & Mustafa Alp Ertem & Haluk Aygüneş, 2016. "Intermodal humanitarian logistics model based on maritime transportation in Istanbul," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 83(1), pages 345-364, August.

    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:ejores:v:289:y:2021:i:3:p:999-1007. 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/locate/eor .

    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.