A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem

Büdenbender, Klaus; Grünert, Tore; Sebastian, Hans-Jürgen
November 2000
Transportation Science;Nov2000, Vol. 34 Issue 4, p364
Academic Journal
This paper introduces a network design problem with a structure that is encountered in many transportation processes. The general organization of these systems is as follows. Freight has to be transported between a large number of origins and destinations. To consolidate the freight, it is first shipped 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 terminals have to be used and how the freight is transported among the terminals. We describe an application where the terminals are airports and the freight is letter mail. Here, the transportation between terminals is by air, which is required due to temporal constraints. The economical impact of these decisions is huge because air transportation is costly and the process is repeated every night. We show how the problem can be modeled as a capacitated warehouse location problem with side constraints and propose a hybrid Tabu Search/Branch-and-Bound algorithm, which solves large real-world instances with acceptable computation times.


Related Articles

  • Tabu Search, Partial Elementarity, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time Windows. Desaulniers, Guy; Lessard, François; Hadjar, Ahmed // Transportation Science;Aug2008, Vol. 42 Issue 3, p387 

    The vehicle routing problem with time windows consists of delivering goods at minimum cost to a set of customers using an unlimited number of capacitated vehicles assigned to a single depot. Each customer must be visited within a prescribed time window. The most recent successful solution...

  • An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints. Iori, Manuel; Salazar-González, Juan-José; Vigo, Daniele // Transportation Science;May2007, Vol. 41 Issue 2, p253 

    We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a...

  • Thumbs up for Devon freight depot after seven-year wait. Tindall, Chris // Commercial Motor;1/17/2008, Vol. 207 Issue 5263, p12 

    The article reports on the outline planning permission granted by the East Devon District Council (EDDC) in England for a major multimodal freight depot in Devon, which will reduce truck journeys in favour of rail freight movements. The first phase of construction, on 50 of the site's 160...

  • Collaboration II. Havat, Mohammad Saadat // Air Cargo World;Oct2002, Vol. 92 Issue 10, p96 

    Commercial aviation is the segment of the transportation industry that takes the greatest hit every time there is any kind of uproar, be it war threats between Pakistan and India, terrorist activity, or just a simple economic slowdown. Airlines and freight forwarders can and do work together. If...

  • Revised-Modified Penalties for Fixed Charge Transportation Problems. Lamar, Bruce W.; Wallace, Chris A. // Management Science;Oct97, Vol. 43 Issue 10, p1431 

    Conditional penalties are used to obtain lower bounds to subproblems in a branch-and-bound procedure that can be tighter than the LP relaxation of the subproblems. For the fixed charge transportation problem (FCTP), branch-and-bound algorithms have been implemented using conditional penalties...

  • A NEW BRANCH-AND-BOUND ALGORITHM FOR THE FIXED-CHARGE TRANSPORTATION PROBLEM. Kennington, Jeff; Unger, Ed // Management Science;Jun76, Vol. 22 Issue 10, p1116 

    A new branch-and-bound procedure specialized for the fixed-charge transportation problem has been developed. The technique strongly exploits the underlying transportation structure. The relaxed problem assumes this form and simple penalties are easily constructed from the optimal solution of...

  • Mixed Integer Models for the Stationary Case of Gas Network Optimization. Martin, Alexander; Möller, Markus; Moritz, Susanne // Mathematical Programming;Feb2006, Vol. 105 Issue 2/3, p563 

    A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are...

  • A Dual-Bounded Algorithm for the p-Median Problem. Galv�o, Roberto O. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1112 

    The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is...

  • Classical Cuts for Mixed-Integer Programming and Branch-and-Cut. Padberg, Manfred // Annals of Operations Research;Oct2005, Vol. 139 Issue 1-4, p321 

    We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory’s fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics