Metaheuristics for large-scale instances of the linear ordering problem

Autor(es)

Sakuraba, Celso S. ^[1] ; Ronconi, Debora P. ^[1] ; Birgin, Ernesto G. ^[2] ; Yagiura, Mutsunori ^[3]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Dept Prod Engn, Polytech Sch, BR-05508070 Sao Paulo - Brazil

^[2] Univ Sao Paulo, Inst Math & Stat, Dept Comp Sci, BR-05508090 Sao Paulo - Brazil

^[3] Nagoya Univ, Grad Sch Informat Sci, Dept Comp Sci & Math Informat, Nagoya, Aichi 4648603 - Japan

• Tipo de documento: Artigo Científico
• Fonte: EXPERT SYSTEMS WITH APPLICATIONS; v. 42, n. 9, p. 4432-4442, JUN 1 2015.
• Citações Web of Science: 2

Resumo

This paper presents iterated local search and great deluge trajectory metaheuristics for the linear ordering problem (LOP). Both metaheuristics are based on the TREE local search method introduced in Sakuraba and Yagiura (2010) that is the only method ever applied to a set of large-sized instances that are in line with the scale of nowadays real applications. By providing diversification and intensification features, the introduced methods improve all best known solutions of the large-sized instances set. Extensive numerical experiments show that the introduced methods are capable of tackling sparse and dense large-scale instances with up to 8000 vertices and 31,996,000 edges in a reasonable amount of time; while they also performs well in practice when compared with other state-of-the-art methods in a benchmark with small and medium-scale instances. (C) 2015 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: José Alberto Cuminato
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 10/08434-1 - Algoritmos de Otimização Não-Exatos para Problemas de Sequenciamento
• Beneficiário: Celso Satoshi Sakuraba
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 13/05475-7 - Métodos computacionais de otimização
• Beneficiário: Sandra Augusta Santos
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 10/10133-0 - Problemas de corte, empacotamento, dimensionamento de lotes e programação da produção, e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático