A branch-and-bound algorithm for depot location and container fleet management

The multicommodity location problem with balancing requirements is related to one of the major logistics issues faced by distribution and transportation firms: the management of a fleet of vehicles over a medium to long term planning horizon. To solve this problem, this paper presents a branch-and-bound algorithm in which bounds are computed by a dual-ascent procedure. The paper particularly emphasizes the design of efficient branching, fathoming and preprocessing rules. The algorithm was tested on a wide variety of randomly generated problems, and on a large-scale application to the planning of the land operations of a heterogeneous container fleet. Results show that the algorithm is highly efficient, and outperforms other existing methods.