Using decomposition to improve greedy solutions of the optimal diversity management problem

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.