MIP Neighborhood Search Heuristics for a Capacitated Fixed-Charge Network Design Problem
Author:
- 30 April 2020
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 37 (03)
Abstract
The fixed-charge capacitated multicommodity network design problem is a fundamental optimization problem arising in many network configurations. The solution of the problem provides an appropriate network design as well as routes of multicommodity flows aimed at minimizing the total cost, which is the sum of the flow costs and fixed-charge costs over a network with limited arc capacities. In the present paper, we introduce a combined approach with a capacity scaling procedure for finding an initial feasible solution and an MIP neighborhood search for improving the solutions. Besides, we modify the procedure for application to large-scale problems. Computational experiments demonstrate the effectiveness of the proposed approach, and high-quality solutions are obtained for two problem sets from the literature.Keywords
Funding Information
- JSPS (Japan Society for the Promotion of Science) KAKENHI (JP17K01268)
This publication has 30 references indexed in Scilit:
- On cut-based inequalities for capacitated network design polyhedraNetworks, 2011
- A local branching heuristic for the capacitated fixed-charge network design problemComputers & Operations Research, 2010
- A capacity scaling heuristic for the multicommodity capacitated network design problemJournal of Computational and Applied Mathematics, 2009
- Scatter Search for Network Design ProblemAnnals of Operations Research, 2005
- Local branchingMathematical Programming, 2003
- On capacitated network design cut?set polyhedraMathematical Programming, 2002
- On splittable and unsplittable flow capacitated network design arc-set polyhedraMathematical Programming, 2002
- A branch-and-cut algorithm for capacitated network design problemsMathematical Programming, 1999
- Networks synthesis and optimum network design problems: Models, solution methods and applicationsNetworks, 1989
- The optimal network problem: Some computational proceduresTransportation Research, 1969