Branch-acid-bound parallelization strategies applied to a depot location and container fleet management problem

This paper presents branch-and-bound parallelization strategies applied to the location/ allocation problem with balancing requirements. This formulat ion is representative of a larger class of discrete network design and loca tion problems arising in many transportation logistics and telecommunicatio ns applications: it displays a multicommodity network flow structure and a complex objective function comprising fixed and variable flow costs. As for many problems of this class, the bounding procedure embedded in the branch -and-bound algorithm is complex and time-consuming. The parallelization str ategies that we describe are designed to exploit this feature. Parallelism is obtained by dividing the search tree among processors and performing ope rations on several subproblems simultaneously. The strategies differ in the way they manage the list of subproblems and control the search. We report and analyze experimental results, on a distributed network of workstations, which aim to compare different implementations of these strategies. (C) 20 00 Elsevier Science B.V. All rights reserved.