Tabu search with exact neighbour evaluation for multicommodity location with balancing requirements

In this paper, we present a tabu search heuristic for solving the multicommodity location problem with balancing requirements. This heuristic improves upon a previous implementation by performing an exact, rather than approximate, evaluation of neighbouring solutions. It also includes a number of refinements, in particular, a new initialization procedure and enhanced neighborhood reduction techniques. The heuristic is shown to be very effective, as it identifies the optimal solution on every instance taken from a set of randomly generated problems. It also finds optimal or near-optimal solutions on a set of large-size instances derived from an actual application, with computation times that show little variance as compared with the currently best known exact method.