Article Preview
TopIntroduction
The Network Design Problem (NDP) is one of the important problems in combinatorial optimization. The objective of NDP is to find a minimum cost network on the available arcs for each commodity which satisfy flows of commodities. Network design models have numerous applications in various fields such as transportation (Crainic et al., 1989; Magnanti & Wong, 1984) telecommunication (Gendron et al., 1998; Minoux, 1989, 2001) and distribution planning (Jayaraman & Ross, 2002).
The fixed-cost Capacitated Multicommodity Network Design (CMND) problem is one type of the network design models. In this model, multiple commodities such as goods, data, people, etc., must be routed between different points of origin and destination on the limited capacity arcs. In this problem, in addition to a unit cost (variable cost), a fixed cost is usually added due to the opening cost for the first time the arc is used (Ahuja et al., 1993). CMND problem seeks a network with minimum cost which satisfies demands of commodities. This minimum cost is the sum of the fixed and variable costs (Crainic, 2000).
Network design problems can easily be stated but solving them is too difficult (Balakrishnan et al., 1997). There are effective exact solution methods for uncapacitated network design problem. In exact algorithms, finding optimal solution is guaranteed. Benders decomposition and branch-and-bound methods have been the two most effective ones for this type of problem (Magnanti & Wong, 1984). Several surveys on network design models and their exact solution methods can be found in Balakrishnan et al. (1997), Crainic (2000), Frangioni and Gendron (2008), Magnanti and Wong (1984), and Minoux (1989, 2004). In addition, in Minoux (1989), a good survey on models and solution methods for multicommodity capacitated network design problems, especially simplex-based cutting plane and Lagrangian relaxation solution methods has been presented.
Adding capacity to the arcs of network design problem creates more complexity of this problem (Balakrishnan et al., 1997). Furthermore, large-scale network design problems which occur in real world applications are very difficult to solve (Magnanti & Wong, 1984). There are theoretical and empirical evidence that the capacitated network design problems are NP-hard (Balakrishnan et al., 1997; Magnanti & Wong, 1984). That is to say, there is no efficient algorithm which can solve them in polynomial time. As a result, the researchers proposed approximation methods to solve them. However, this type of solution methods cannot guarantee the optimality of the solutions. Metaheuristics that are a kind of approximation methods deal with these problems by introducing systematic rules to escape from local optima (Glover & Kochenberger, 2003).
To deal with CMND problems, several matheuristic algorithms have been proposed in the literature. Matheuristics are heuristic algorithms made by the interoperation of metaheuristics and mathematic programming techniques. This approach has begun to appear regularly in the metaheuristics literature (Blum et al., 2011; Boschetti et al., 2009; Caserta & Voß, 2009).