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.
References
[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
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