×

MIP neighborhood search heuristics for a capacitated fixed-charge network design problem. (English) Zbl 1457.90028

Summary: 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.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
90C11 Mixed integer programming
Full Text: DOI

References:

[1] Alvarez, AM, González-Velarde, JL and De-Alba, K (2005). Scatter search for network design problem. Annals of Operations Research, 138(1), 159-178. · Zbl 1091.90006
[2] Atamtürk, A (2002). On capacitated network design cut-set polyhedra. Mathematical Programming, 92(3), 425-437. · Zbl 1008.90003
[3] Atamtürk, A and Rajan, D (2002). On splittable and unsplittable flow capacitated network design arc-set polyhedra. Mathematical Programming, 92(2), 315-333. · Zbl 1094.90005
[4] Bienstock, D and Günlük, O (1996). Capacitated network design — Polyhedral structure and computation. INFORMS Journal on Computing, 8(3), 243-259. · Zbl 0871.90031
[5] Chouman, M and TG Crainic (2010). A MIP-tabu search hybrid framework for multicommodity capacitated fixed-charge network design. Technical Report on CIRRELT-2010-31, Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Université de Montréal.
[6] Chouman, M, Crainic, TG and Gendron, B (2017). Commodity representations and cutset-based inequalities for multicommodity capacitated fixed-charge network design. Transportation Science, 51(2), 650-667.
[7] Crainic, TG, Frangioni, A and Gendron, B (2001). Bundle-based relaxation methods for multicommodity capacitated fixed charge network design problems. Discrete Applied Mathematics, 112(1-3), 73-99. · Zbl 1026.90010
[8] Fischetti, M and Fischetti, M (2018). Matheuristics. In Handbook of Heuristics, Martí, R, Pardalos, P and Resend, M (eds.), pp. 121-153. Cham: Springer.
[9] Fischetti, M and Lodi, A (2003). Local branching. Mathematical Programming98(1-3), 23-47. · Zbl 1060.90056
[10] Fischetti, M, Lodi, A and Salvagnin, D (2010). Just MIP it!, , Vol. 10, pp. 39-70. Boston: Springer US.
[11] Frangioni, A (2013). Multicommodity problems, http://www.di.unipi.it/optimize/Data/MMCF.html.
[12] Gendron, B, Hanafib, S and Todosijević, R (2018). Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design. European Journal of Operational Research, 268, 70-81. · Zbl 1403.90199
[13] Gendron, B, Hanif, S and Todosijević, R (2016). An efficient matheuristic for the multicommodity fixed-charge network design problem. IFAC-PapersOnLine, 49(12), 117-120.
[14] Ghamlouche, I, Cainic, TG and Gendreau, M (2011). Learning mechanisms and local search heuristics for the fixed charge capacitated multicommodity network design. International Journal of Computer Science Issues, 8(6), 21-32.
[15] Ghamlouche, I, Crainic, TG and Gendreau, M (2004). Path relinking, cycle-based neighborhoods and capacitated multicommodity network design. Annals of Operations Research, 131(1-4), 109-134. · Zbl 1067.90014
[16] Gilmore, PC and Gomory, RE (1961). A linear programming approach to the cutting stock problem. Operations Research, 9(6), 849-859. · Zbl 0096.35501
[17] Günlük, O (1999). A branch-and-cut algorithm for capacitated network design problems. Mathematical Programming, 86(1), 17-39. · Zbl 1015.90090
[18] Hewitt, M (2010). GT instances, https://www.researchgate.net/publication/304825234.
[19] Hewitt, M, Nemhauser, GL and Savelsbergh, MWP (2010). Combining exact and heuristics approaches for the capacitated fixed charge network flow problem, INFORMS Journal on Computing, 22(2), 314-325. · Zbl 1243.90031
[20] Holmberg, K and Yuan, D (2000). A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Operations Research, 48(3), 461-481. · Zbl 1106.90381
[21] Katayama, N (2015). A combined capacity scaling and local branching approach for capacitated multi-commodity network design problem. Far East Journal of Applied Mathematics92(1), 1-30. · Zbl 1325.90015
[22] Katayama, N, Chen, MZ and Kubo, M (2009). A capacity scaling procedure for the multi-commodity capacitated network design problem. Journal of Computational and Applied Mathematics, 232(2), 90-101. · Zbl 1178.90057
[23] Lamar, BW, Sheffi, Y and Powell, WB (1990). A capacity improvement lower bound for fixed charge network design problems. Operations Research, 38(4), 704-710. · Zbl 0728.90034
[24] Magnanti, TL and Wong, RT (1984). Network design and transportation planning: Models and algorithms. Transportation Science, 18(1), 1-55.
[25] Minoux, M (1989). Network synthesis and optimum network design problems: Models, solution methods and applications. Networks, 19(3), 313-360. · Zbl 0666.90032
[26] Momeni, M and Sarmadi, M (2016). A genetic algorithm based on relaxation induced neighborhood search in a local branching framework for capacitated multicommodity network design. Networks and Spatial Economics, 16(2), 447-468. · Zbl 1364.90375
[27] Munguía, L, Ahmed, S, Bader, DA, Nemhauser, GL, Goel, V and Shao, Y (2017). A parallel local search frame work for the fixed-charge multicommodity network flow problem. Computers & Operations Research, 77, 44-57. · Zbl 1391.90119
[28] Paraskevopoulos, DC, Bektaş, T, Crainic, TG and Potts, CN (2016). A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem. European Journal of Operational Research253(2), 265-279. · Zbl 1346.90224
[29] Pochet, Y and Vyve, MV (2004). A general heuristic for production planning problems. INFORMS Journal on Computing, 16(3), 316-327. · Zbl 1239.90043
[30] Raack, C, Koster, A, Orlowski, S and Wessäly, R (2011). On cut-based inequalities for capacitated network design polyhedra. Networks, 57(2), 141-156. · Zbl 1207.90023
[31] Rahmaniani, R, Crainic, TG, Gendreau, M and Rei, W (2018). Accelerating the benders decomposition method: Application to stochastic network design problems. SIAM Journal on Optimization, 28(1), 875-903. · Zbl 1396.90013
[32] Rodríguez-Martín, I and Salazar-Gonzáleza, JJ (2010). A local branching heuristics for the capacitated fixed-charge network design problem. Computers & Operations Research, 37(3), 575-581. · Zbl 1175.90072
[33] Scott, AJ (1969). The optimal network problem: Some computational procedures. Transportation Research, 3(2), 201-210.
[34] Yaghini, M and Foroughi, A (2014). ACO-based neighborhoods for fixed-charge capacitated multi-commodity network design problem. International Journal of Transportation Engineering, 1(4), 311-334.
[35] Yaghini, M, Karimi, M and Rahbar, M (2011). A hybrid simulated annealing and simplex method for fixed-cost capacitated multicommodity network design. International Journal of Applied Metaheuristic Computing, 2(4), 13-28.
[36] Yaghini, M, Karimi, M, Rahbar, M and Sharifitabaro, MH (2016). A cutting-plane neighborhood structure for fixed-charge capacitated multicommodity network design problem. INFORMS Journal on Computing, 27(1), 45-58. · Zbl 1327.90358
[37] Yaghini, M, Rahbar, M and Karimi, M (2013). A hybrid simulated annealing and column generation approach for capacitated multicommodity network design. Journal of the Operational Research Society, 64(7), 1010-1020.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.