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

Introduction

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 = A_f ∪ A_v is the arc set (where A_f and A_v 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.