Premium
Using decomposition to improve greedy solutions of the optimal diversity management problem
Author(s) -
Agra Agostinho,
Cerdeira Jorge Orestes,
Requejo Cristina
Publication year - 2013
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12004
Subject(s) - greedy algorithm , mathematical optimization , automotive industry , simulated annealing , computer science , decomposition , greedy randomized adaptive search procedure , genetic algorithm , mathematics , engineering , ecology , biology , aerospace engineering
Abstract The optimal diversity management problem is a special case of the p ‐median problem, which arises in the production of wire harness for the automotive industry. Instances are typically very large and graphs consist of several nonconnected components. The greedy algorithm is normally applied to handle these large instances, producing solutions that are considered quite good. We design an approach that uses decomposition combined with a genetic algorithm and simulated annealing algorithm to improve greedy solutions of the optimal diversity management problem. We report computational results that render this approach as capable of improving greedy solutions on real instances from a company manufacturing wire harness for automobiles.