A hybrid Tabu Search/Branch-and-Bound algorithm for the direct flight network design problem

This paper introduces a network design problem with a structure that is enc ountered in many transportation processes. The general organization of thes e systems is as follows. Freight has to be transported between a large numb er of origins and destinations. To consolidate the freight, it is first shi pped to a terminal. Next, it is transported directly to a terminal where it is re-loaded and shipped to its destination. The task is to decide which t erminals have to be used and how the freight is transported among the termi nals. We describe an, application where the terminals are airports and the freight is letter mail. Here, the transportation between terminals is by ai r, which is required due to temporal constraints. The economical impact of these decisions is huge because air transportation is costly and the proces s is repeated every night. We show how the problem can be modeled as a capa citated warehouse location problem with side constraints and propose a hybr id Tabu Search/Branch-and-Bound algorithm, which solves large real-world in stances with acceptable computation times.