A Hybrid Lagrangian Relaxation and Tabu Search Method for Interdependent-Choice Network Design Problems

A Hybrid Lagrangian Relaxation and Tabu Search Method for Interdependent-Choice Network Design Problems

Chi Xie (The University of Texas at Austin, USA), Mark A. Turnquist (Cornell University, USA) and S. Travis Waller (The University of Texas at Austin, USA)
DOI: 10.4018/978-1-61350-086-6.ch013
OnDemand PDF Download:


Hybridization offers a promising approach in designing and developing improved metaheuristic methods for a variety of complex combinatorial optimization problems. This chapter presents a hybrid Lagrangian relaxation and tabu search method for a class of discrete network design problems with complex interdependent-choice constraints. This method takes advantage of Lagrangian relaxation for problem decomposition and complexity reduction while its algorithmic logic is designed based on the principles of tabu search. The algorithmic advance and solution performance of the method are illustrated by implementing it for solving a network design problem with lane reversal and crossing elimination strategies, arising from urban evacuation planning.
Chapter Preview


The interest about hybrid optimization methods has grown rapidly for last few years (Talbi, 2002; Jourdan et al., 2009). Hybridization has become a pervasive trend and a very promising strategy in designing and developing improved metaheuristic solution methods, in view of their heuristic nature, greater flexibility and less strict mathematical property. A hybrid metaheuristic method combines structure and efficiency advantages from different principles and approaches and often provides a highly flexible and efficient tool in solving difficult combinatorial optimization problems.

A large number of production, communication, distribution and transportation infrastructure investment and planning problems can be characterized as network design problems. The common goal of a generic network design problem is to seek an optimal cost-effective network topology and capacity expansion solution with taking into account the infrastructure investment cost and the resulting network operation efficiency. Discrete network design problems, which deal with selecting (and deselecting) facility location and capacity at nodes or on arcs from a discrete choice set, are typically formulated as integer or mixed integer programming models (Wong, 1985). Many of these network design problems cause very difficult combinatorial issues, depending on the interrelationship between individual discrete choice components and the underlying network flow routing behaviors. Even in their simplest form, discrete network design problems pose the NP-hard computational complexity. Johnson et al. (1978) establishes its NP-completeness by showing that the classic knapsack problem is reducible to the simplest discrete network design problem; Wong (1980) showed that even finding an approximate discrete network solution is NP-hard.

Exact solution methods, such as branch and bound and Benders decomposition, are limited to solving discrete network design problems of small size (see, for example, Boyce et al., 1973; Hoang, 1973, 1982; LeBlanc, 1975; Dionne and Florian, 1979; Geoffrion and Graves, 1974; Magnanti and Wong, 1984; Magnanti et al., 1986; Sherali et al., 1991; Cordeau et al., 2006). In contrast, for large-scale applications, more research efforts have been devoted in the past two decades to developing heuristic and metaheuristic solution methods, including genetic algorithms (e.g., Xiong and Schneider, 1992; Jeon et al., 2006), memetic algorithms (Baños et al., 2007), simulated annealing (e.g., Lee and Yang, 1994; Drezner and Wesolowsky, 1997, 2003; Cantarella et al., 2006), tabu search (e.g., Mouskos, 1991; Crainic et al., 2000; Berger et al., 2000), and ant colony optimization (e.g., Poorzahedy and Abulghasemi, 2005), among others.

This chapter discusses a hybrid metaheuristic solution strategy for a class of network design problems that contain complex topological or temporal restrictions (or flexibilities) between discrete arc selection decisions subject to a limited amount of resources (i.e., budget, space, time, etc.). Specifically, given a network G = (N, A), where N is the node set and A = AfAv is the arc set (where Af and Av are the subsets of fixed arcs and variable arcs, respectively), such a generic form of network design problems is considered as below. For discussion convenience, the notation used in the problem formulation is presented first in Table 1.

Complete Chapter List

Search this Book: