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

An efficient ant colony optimization algorithm for the blocks relocation problem

Author

Listed:
  • Jovanovic, Raka
  • Tuba, Milan
  • Voß, Stefan

Abstract

In this paper we present an ant colony optimization (ACO) algorithm for the Blocks Relocation Problem (BRP). The method is applied to both versions of the problem most commonly considered in literature, i.e., the restricted (rBRP) and the unrestricted (uBRP) BRP with distinct due dates. In case of the uBRP a new heuristic is proposed and incorporated in a standard greedy algorithm. The performance of the basic greedy approach is enhanced by extending it to the ACO metaheuristic. In it, a novel approach for defining the pheromone matrix is proposed. More precisely, it only stores a small amount of information instead of the complete bay state. Further, we show that the proposed ACO method can easily be adapted for solving the BRP in which the objective function is related to the crane operation time. Our computational results show that the proposed approach manages to outperform existing methods for the BRP.

Suggested Citation

  • Jovanovic, Raka & Tuba, Milan & Voß, Stefan, 2019. "An efficient ant colony optimization algorithm for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 78-90.
    • Handle: RePEc:eee:ejores:v:274:y:2019:i:1:p:78-90
    DOI: 10.1016/j.ejor.2018.09.038
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718308208
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.09.038?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. Ku, Dusan & Arthanari, Tiru S., 2016. "Container relocation problem with time windows for container departure," European Journal of Operational Research, Elsevier, vol. 252(3), pages 1031-1039.
    2. Jin, Bo & Zhu, Wenbin & Lim, Andrew, 2015. "Solving the container relocation problem by an improved greedy look-ahead heuristic," European Journal of Operational Research, Elsevier, vol. 240(3), pages 837-847.
    3. Petering, Matthew E.H. & Hussein, Mazen I., 2013. "A new mixed integer program and extended look-ahead heuristic algorithm for the block relocation problem," European Journal of Operational Research, Elsevier, vol. 231(1), pages 120-130.
    4. Zehendner, Elisabeth & Feillet, Dominique & Jaillet, Patrick, 2017. "An algorithm with performance guarantee for the Online Container Relocation Problem," European Journal of Operational Research, Elsevier, vol. 259(1), pages 48-62.
    5. Yat‐wah Wan & Jiyin Liu & Pei‐Chun Tsai, 2009. "The assignment of storage locations to containers for a container stack," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(8), pages 699-713, December.
    6. Lehnfeld, Jana & Knust, Sigrid, 2014. "Loading, unloading and premarshalling of stacks in storage areas: Survey and classification," European Journal of Operational Research, Elsevier, vol. 239(2), pages 297-312.
    7. Caserta, Marco & Schwarze, Silvia & Voß, Stefan, 2012. "A mathematical formulation and complexity considerations for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 219(1), pages 96-104.
    8. Zehendner, Elisabeth & Caserta, Marco & Feillet, Dominique & Schwarze, Silvia & Voß, Stefan, 2015. "An improved mathematical formulation for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 415-422.
    9. Raka Jovanovic & Milan Tuba & Stefan Voß, 2017. "A multi-heuristic approach for solving the pre-marshalling problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(1), pages 1-28, March.
    10. Bortfeldt, Andreas & Forster, Florian, 2012. "A tree search procedure for the container pre-marshalling problem," European Journal of Operational Research, Elsevier, vol. 217(3), pages 531-540.
    11. Shishvan, Masoud Soleymani & Sattarvand, Javad, 2015. "Long term production planning of open pit mines by ant colony optimization," European Journal of Operational Research, Elsevier, vol. 240(3), pages 825-836.
    12. Katta G. Murty & Yat-wah Wan & Jiyin Liu & Mitchell M. Tseng & Edmond Leung & Kam-Keung Lai & Herman W. C. Chiu, 2005. "Hongkong International Terminals Gains Elastic Capacity Using a Data-Intensive Decision-Support System," Interfaces, INFORMS, vol. 35(1), pages 61-75, February.
    13. Lixin Tang & Wei Jiang & Jiyin Liu & Yun Dong, 2015. "Research into container reshuffling and stacking problems in container terminal yards," IISE Transactions, Taylor & Francis Journals, vol. 47(7), pages 751-766, July.
    14. Sreeja, N.K. & Sankar, A., 2015. "Ant colony optimization based binary search for efficient point pattern matching in images," European Journal of Operational Research, Elsevier, vol. 246(1), pages 154-169.
    15. Gambardella, L.M. & Montemanni, R. & Weyland, D., 2012. "Coupling ant colony systems with strong local searches," European Journal of Operational Research, Elsevier, vol. 220(3), pages 831-843.
    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. Wei Song & Shuailei Yuan & Yun Yang & Chufeng He, 2022. "A Study of Community Group Purchasing Vehicle Routing Problems Considering Service Time Windows," Sustainability, MDPI, vol. 14(12), pages 1-17, June.
    2. Jin, Bo & Tanaka, Shunji, 2023. "An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules," European Journal of Operational Research, Elsevier, vol. 304(2), pages 494-514.
    3. Teddy Nurcahyadi & Christian Blum, 2021. "Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study," Mathematics, MDPI, vol. 9(4), pages 1-23, February.
    4. Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Ruiz, Rubén & Tierney, Kevin, 2020. "Minimizing crane times in pre-marshalling problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 137(C).
    5. Jiménez-Piqueras, Celia & Ruiz, Rubén & Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon, 2023. "A constraint programming approach for the premarshalling problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 668-678.
    6. Azab, Ahmed & Morita, Hiroshi, 2022. "The block relocation problem with appointment scheduling," European Journal of Operational Research, Elsevier, vol. 297(2), pages 680-694.
    7. Bacci, Tiziano & Mattia, Sara & Ventura, Paolo, 2020. "A branch-and-cut algorithm for the restricted Block Relocation Problem," European Journal of Operational Research, Elsevier, vol. 287(2), pages 452-459.
    8. Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Parreño, Francisco, 2022. "A beam search algorithm for minimizing crane times in premarshalling problems," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1063-1078.
    9. Tanaka, Shunji & Voß, Stefan, 2019. "An exact algorithm for the block relocation problem with a stowage plan," European Journal of Operational Research, Elsevier, vol. 279(3), pages 767-781.
    10. Tanaka, Shunji & Voß, Stefan, 2022. "An exact approach to the restricted block relocation problem based on a new integer programming formulation," European Journal of Operational Research, Elsevier, vol. 296(2), pages 485-503.
    11. Zweers, Bernard G. & Bhulai, Sandjai & van der Mei, Rob D., 2020. "Optimizing pre-processing and relocation moves in the Stochastic Container Relocation Problem," European Journal of Operational Research, Elsevier, vol. 283(3), pages 954-971.
    12. Zhang, Canrong & Guan, Hao & Yuan, Yifei & Chen, Weiwei & Wu, Tao, 2020. "Machine learning-driven algorithms for the container relocation problem," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 102-131.
    13. Morin, Michael & Abi-Zeid, Irène & Quimper, Claude-Guy, 2023. "Ant colony optimization for path planning in search and rescue operations," European Journal of Operational Research, Elsevier, vol. 305(1), pages 53-63.

    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. Jin, Bo & Tanaka, Shunji, 2023. "An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules," European Journal of Operational Research, Elsevier, vol. 304(2), pages 494-514.
    2. Feng, Yuanjun & Song, Dong-Ping & Li, Dong & Zeng, Qingcheng, 2020. "The stochastic container relocation problem with flexible service policies," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 116-163.
    3. Raka Jovanovic & Shunji Tanaka & Tatsushi Nishi & Stefan Voß, 2019. "A GRASP approach for solving the Blocks Relocation Problem with Stowage Plan," Flexible Services and Manufacturing Journal, Springer, vol. 31(3), pages 702-729, September.
    4. Tanaka, Shunji & Voß, Stefan, 2019. "An exact algorithm for the block relocation problem with a stowage plan," European Journal of Operational Research, Elsevier, vol. 279(3), pages 767-781.
    5. Gharehgozli, Amir & Zaerpour, Nima, 2018. "Stacking outbound barge containers in an automated deep-sea terminal," European Journal of Operational Research, Elsevier, vol. 267(3), pages 977-995.
    6. Boge, Sven & Goerigk, Marc & Knust, Sigrid, 2020. "Robust optimization for premarshalling with uncertain priority classes," European Journal of Operational Research, Elsevier, vol. 287(1), pages 191-210.
    7. Boschma, René & Mes, Martijn R.K. & de Vries, Leon R., 2023. "Approximate dynamic programming for container stacking," European Journal of Operational Research, Elsevier, vol. 310(1), pages 328-342.
    8. Ting, Ching-Jung & Wu, Kun-Chih, 2017. "Optimizing container relocation operations at container yards with beam search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 17-31.
    9. Azab, Ahmed & Morita, Hiroshi, 2022. "The block relocation problem with appointment scheduling," European Journal of Operational Research, Elsevier, vol. 297(2), pages 680-694.
    10. Galle, Virgile & Barnhart, Cynthia & Jaillet, Patrick, 2018. "A new binary formulation of the restricted Container Relocation Problem based on a binary encoding of configurations," European Journal of Operational Research, Elsevier, vol. 267(2), pages 467-477.
    11. Huiling Zhu & Mingjun Ji & Wenwen Guo & Qingbin Wang & Yongzhi Yang, 2019. "Mathematical formulation and heuristic algorithm for the block relocation and loading problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 333-351, June.
    12. Feng, Yuanjun & Song, Dong-Ping & Li, Dong & Xie, Ying, 2022. "Service fairness and value of customer information for the stochastic container relocation problem under flexible service policy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    13. V. Galle & V. H. Manshadi & S. Borjian Boroujeni & C. Barnhart & P. Jaillet, 2018. "The Stochastic Container Relocation Problem," Transportation Science, INFORMS, vol. 52(5), pages 1035-1058, October.
    14. Zweers, Bernard G. & Bhulai, Sandjai & van der Mei, Rob D., 2020. "Optimizing pre-processing and relocation moves in the Stochastic Container Relocation Problem," European Journal of Operational Research, Elsevier, vol. 283(3), pages 954-971.
    15. Zehendner, Elisabeth & Feillet, Dominique & Jaillet, Patrick, 2017. "An algorithm with performance guarantee for the Online Container Relocation Problem," European Journal of Operational Research, Elsevier, vol. 259(1), pages 48-62.
    16. Zehendner, Elisabeth & Caserta, Marco & Feillet, Dominique & Schwarze, Silvia & Voß, Stefan, 2015. "An improved mathematical formulation for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 415-422.
    17. Andresson Silva Firmino & Ricardo Martins Abreu Silva & Valéria Cesário Times, 2019. "A reactive GRASP metaheuristic for the container retrieval problem to reduce crane’s working time," Journal of Heuristics, Springer, vol. 25(2), pages 141-173, April.
    18. Bacci, Tiziano & Mattia, Sara & Ventura, Paolo, 2020. "A branch-and-cut algorithm for the restricted Block Relocation Problem," European Journal of Operational Research, Elsevier, vol. 287(2), pages 452-459.
    19. Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Ruiz, Rubén, 2019. "Integer programming models for the pre-marshalling problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 142-154.
    20. Tanaka, Shunji & Voß, Stefan, 2022. "An exact approach to the restricted block relocation problem based on a new integer programming formulation," European Journal of Operational Research, Elsevier, vol. 296(2), pages 485-503.

    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:274:y:2019:i:1:p:78-90. 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.