• Login
    View Item 
    •   TECNALIA Publications Home
    • TECNALIA
    • TECNALIA
    • View Item
    • TECNALIA Publications Home
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm

    View/Open
    Accepted_Manuscript.pdf (535.3Kb)
    Identifiers
    URI: http://hdl.handle.net/11556/1271
    ISSN: 1877-7503
    DOI: 10.1016/j.jocs.2022.101578
    Bibliography Export
    RefworksRisMendeleyEndNote
    Statistics
    View Usage Statistics
    Full record
    Show full item record
    Author/s
    Murua, M.; Galar, D.; Santana, R.
    Date
    2022-04
    Keywords
    Graph theory
    Multi-objective optimization
    Discrete optimization problems
    Hamiltonian cycle problem
    Branching algorithm
    Abstract
    The Hamiltonian cycle problem consists of finding a cycle in a given graph that passes through every single vertex exactly once, or determining that this cannot be achieved. In this investigation, a graph is considered with an associated set of matrices. The entries of each of the matrix correspond to a different weight of an arc. A multi-objective Hamiltonian cycle problem is addressed here by computing a Pareto set of solutions that minimize the sum of the weights of the arcs for each objective. Our heuristic approach extends the Branch-and-Fix algorithm, an exact method that embeds the problem in a stochastic process. To measure the efficiency of the proposed algorithm, we compare it with a multi-objective genetic algorithm in graphs of a different number of vertices and density. The results show that the density of the graphs is critical when solving the problem. The multi-objective genetic algorithm performs better (quality of the Pareto sets) than the proposed approach in random ...
    Type
    article

    © TECNALIA 2021  | All rights reserved
    Contact Us | Send Feedback
     

     

    Browse

    All of TECNALIA PublicationsAuthorsTitlesTypesKeywordsThis CollectionAuthorsTitlesTypesKeywords

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    Of interest

    About TECNALIA
    Open AireOpen DoarRecolectaSHERPA/ROMEO

    © TECNALIA 2021  | All rights reserved
    Contact Us | Send Feedback