In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS networks restrict the number of paths that a commodity can use, for maintaining the quality of service (QoS) of the users, the demand of each commodity must be satisfied. Under the above conditions, some links in the network may be too much loaded, affecting the performance of the whole network drastically. For this problem, in [1], we proposed two mathematical models to describe it and a heuristic algorithm which quickly finds transmitting paths for each commodity are also presented. In this paper, we propose a new heuristic algorithm which finds a feasible path set for each commodity, and then select some paths from the path set through a mixed integer linear programming to transmit the demand of each commodity. This strategy reduces the scale of the original problem to a large extent. We test 50 instances and the results show the effectiveness of the new heuristic algorithm.
[1] Jiao, C.W., Yang, W.G. and Gao, S.X. (2014) The k-Splittable Flow Model and a Heuristic Algorithm for Minimizing Congestion in the MPLS Networks. International Conference on Natural Computation (ICNC2014), Xiamen University, 19-21 August 2014.
[2] Baier, G., Kohler, E. and Skutella, M. (2005) The k-Splittable Flow Problem. Algorithmica, 42, 231-248. http://dx.doi.org/10.1007/s00453-005-1167-9
[3] Kleinberg, J.M. (1996) Single-Source Unsplittable Flow. Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 68-77.
[4] Koch, R., Skutella, M. and Spenke, I. (2008) Maximum k-Splittable s,t-Flows. Theory of Computing Systems, 43, 56-66. http://dx.doi.org/10.1007/s00224-007-9068-8
[5] Kolliopoulos, S.G. (2005) Minimum-Cost Single-Source 2-Splittable Flow. Information Processing Letters, 94, 15-18. http://dx.doi.org/10.1016/j.ipl.2004.12.009
[6] Salazar, F. and Skutella, M. (2009) Single-Source k-Splittable Min-Cost Flows. Operations Research Letters, 37, 71-74. http://dx.doi.org/10.1016/j.orl.2008.12.004
[7] Truffot, J., Duhamel, C. and Mahey, P. (2005) Using Branch-and-Price to Solve Multicommodity k-Splittable Flow Problem. The Proceedings of International Network Optimisation Conference (INOC), Lisbonne, 20-23 March 2005.
[8] Truffot, J. and Duhamel, C. (2008) A Branch and Price Algorithm for the k-Splittable Maximum Flow Problem. Discrete Optimization, 5, 629-646. http://dx.doi.org/10.1016/j.disopt.2008.01.002
[9] Gamst, M., Jensen, P.N., Pisinger, D. and Plum, C. (2010) Two- and Three-Index Formulations of the Minimum Cost Multicommodity k-Splittable Flow Problem. European Journal of Operational Research, 202, 82-89. http://dx.doi.org/10.1016/j.ejor.2009.05.014
[10] Gamst, M. and Petersen, B. (2012) Comparing Branch-and-Price Algorithms for the Multi-Commodity k-Splittable Maximum Flow Problem. European Journal of Operational Research, 217, 278-286.
http://dx.doi.org/10.1016/j.ejor.2011.10.001
[11] Gamst, M. (2013) A Decomposition Based on Path Sets for the Multi-Commodity k-Splittable Maximum Flow Problem. Department of Management Engineering, Technical University of Denmark, DTU Management Engineering Report No. 6.
[12] Edmonds, J. and Karp, R.M. (1972) Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the ACM, 19, 248-264. http://dl.acm.org/citation.cfm?id=321699 http://dx.
doi.org/10.1145/321694.321699
[13] http://www.informatik.uni-trier.de/~naeher/Professur/research/generators/maxflow/tg/