Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem

Eduardo Lalla-Ruiz, Belén Melián-Batista, J. Marcos Moreno-Vega

    Research output: Contribution to journalArticleAcademicpeer-review

    44 Citations (Scopus)

    Abstract

    This paper considers the Dynamic Berth Allocation Problem, in which vessels are assigned to discrete positions in berths. This problem, whose goal is to minimize the total time the vessels stay at the port, constitutes one of the most important processes at any containers terminal. We propose a hybrid metaheuristic that combines Tabu Search with Path Relinking, T2S˜+PR. The results reached by this hybrid algorithm are compared with the optimal values given by the best mathematical model that appears in the literature for this problem, GSPP, and with a tabu search algorithm from the literature, T2S. For small instances, the algorithm T2S˜+PR is able to obtain most of the optimal solutions in an amount of computational time that is lower than the time required to solve the GSPP model. For medium and large size instances, GSPP cannot be solved to optimality, whereas the proposed hybrid algorithm outperforms T2S. Moreover, the computational experiments carried out in this paper confirm the robustness of the proposed algorithm with respect to both the parameters governing the procedure and the problem size.
    Original languageEnglish
    Pages (from-to)1132-1141
    JournalEngineering applications of artificial intelligence
    Volume25
    Issue number6
    DOIs
    Publication statusPublished - 1 Sep 2012

    Fingerprint

    tabu
    Tabu search
    artificial intelligence
    Artificial intelligence
    heuristics
    Containers
    Mathematical models
    Heuristics
    Allocation problem
    experiment
    time
    Hybrid algorithm
    Experiments
    literature

    Cite this

    @article{f2d36a73a64c4e56b935dbcdaf52dbc2,
    title = "Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem",
    abstract = "This paper considers the Dynamic Berth Allocation Problem, in which vessels are assigned to discrete positions in berths. This problem, whose goal is to minimize the total time the vessels stay at the port, constitutes one of the most important processes at any containers terminal. We propose a hybrid metaheuristic that combines Tabu Search with Path Relinking, T2S˜+PR. The results reached by this hybrid algorithm are compared with the optimal values given by the best mathematical model that appears in the literature for this problem, GSPP, and with a tabu search algorithm from the literature, T2S. For small instances, the algorithm T2S˜+PR is able to obtain most of the optimal solutions in an amount of computational time that is lower than the time required to solve the GSPP model. For medium and large size instances, GSPP cannot be solved to optimality, whereas the proposed hybrid algorithm outperforms T2S. Moreover, the computational experiments carried out in this paper confirm the robustness of the proposed algorithm with respect to both the parameters governing the procedure and the problem size.",
    author = "Eduardo Lalla-Ruiz and Bel{\'e}n Meli{\'a}n-Batista and {Marcos Moreno-Vega}, J.",
    year = "2012",
    month = "9",
    day = "1",
    doi = "10.1016/j.engappai.2012.06.001",
    language = "English",
    volume = "25",
    pages = "1132--1141",
    journal = "Engineering applications of artificial intelligence",
    issn = "0952-1976",
    publisher = "Elsevier",
    number = "6",

    }

    Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem. / Lalla-Ruiz, Eduardo; Melián-Batista, Belén; Marcos Moreno-Vega, J.

    In: Engineering applications of artificial intelligence, Vol. 25, No. 6, 01.09.2012, p. 1132-1141.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem

    AU - Lalla-Ruiz, Eduardo

    AU - Melián-Batista, Belén

    AU - Marcos Moreno-Vega, J.

    PY - 2012/9/1

    Y1 - 2012/9/1

    N2 - This paper considers the Dynamic Berth Allocation Problem, in which vessels are assigned to discrete positions in berths. This problem, whose goal is to minimize the total time the vessels stay at the port, constitutes one of the most important processes at any containers terminal. We propose a hybrid metaheuristic that combines Tabu Search with Path Relinking, T2S˜+PR. The results reached by this hybrid algorithm are compared with the optimal values given by the best mathematical model that appears in the literature for this problem, GSPP, and with a tabu search algorithm from the literature, T2S. For small instances, the algorithm T2S˜+PR is able to obtain most of the optimal solutions in an amount of computational time that is lower than the time required to solve the GSPP model. For medium and large size instances, GSPP cannot be solved to optimality, whereas the proposed hybrid algorithm outperforms T2S. Moreover, the computational experiments carried out in this paper confirm the robustness of the proposed algorithm with respect to both the parameters governing the procedure and the problem size.

    AB - This paper considers the Dynamic Berth Allocation Problem, in which vessels are assigned to discrete positions in berths. This problem, whose goal is to minimize the total time the vessels stay at the port, constitutes one of the most important processes at any containers terminal. We propose a hybrid metaheuristic that combines Tabu Search with Path Relinking, T2S˜+PR. The results reached by this hybrid algorithm are compared with the optimal values given by the best mathematical model that appears in the literature for this problem, GSPP, and with a tabu search algorithm from the literature, T2S. For small instances, the algorithm T2S˜+PR is able to obtain most of the optimal solutions in an amount of computational time that is lower than the time required to solve the GSPP model. For medium and large size instances, GSPP cannot be solved to optimality, whereas the proposed hybrid algorithm outperforms T2S. Moreover, the computational experiments carried out in this paper confirm the robustness of the proposed algorithm with respect to both the parameters governing the procedure and the problem size.

    U2 - 10.1016/j.engappai.2012.06.001

    DO - 10.1016/j.engappai.2012.06.001

    M3 - Article

    VL - 25

    SP - 1132

    EP - 1141

    JO - Engineering applications of artificial intelligence

    JF - Engineering applications of artificial intelligence

    SN - 0952-1976

    IS - 6

    ER -