A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design Problem

作者：Yaghini Masoud^*; Karimi Mohammad; Rahbar Mohadeseh; Sharifitabar Mohammad Hassan

来源：INFORMS Journal on Computing, 2015, 27(1): 48-58.

DOI：10.1287/ijoc.2014.0609

• fixed-charge capacitated multicommodity network design
• cutting-plane neighborhood
• tabu search
• design of experiments

In this paper, a cutting-plane neighborhood structure is proposed for the fixed-charge capacitated multicommodity network design (CMND) problem. In the proposed structure, different strategies are used to select an open arc in the incumbent solution to be closed. Then a linear programming (LP) model is generated on the basis of the modified incumbent solution by relaxing binary variables and adding new constraints. The generated LP solution is improved using different cutting-plane inequalities. Subsequently, a new sub-mixed integer programming (MIP) model is created by fixing a number of variables in the generated LP solution. Then the local branching algorithm is used to solve the sub-MIP model and its solution is considered as a neighboring solution. A tabu search algorithm is used to evaluate the proposed neighborhood structure. To tune the parameters of the tabu search algorithm, we have used the design of experiments method. Standard problems with different sizes are employed to evaluate the proposed tabu search algorithm. Results show the efficiency and effectiveness of the tabu search algorithm compared to the best methods found in the literature.

• 出版日期2015