Abstract
A major problem in communication networks is how to efficiently define the routing paths and to allocate bandwidths in order to satisfy a given collection of transmission requests. In this paper, we study this routing problem by modeling it as a bi-objective single path multicommodity flow problem (SMCFP). Two conflicting objective functions are simultaneously optimized: the delay and reliability of the generated paths. To tackle the complexity of this problem (NP-hard), most of the existing studies proposed approximate methods and metaheuristics as solution approaches. In this paper, we propose to adapt the augmented \(\epsilon \)-constraint method in order to solve small sized instances of the bi-SMCFP. For large scale problems, we develop three metaheuristics: a multiobjective multi-operator genetic algorithm, an adaptive multiobjective variable neighborhood search and new hybrid method combining the \(\epsilon \)-constraint with the evolutionary metaheuristic. The idea of the hybridization schema is to first use the metaheuristic to generate a good approximation of the Pareto front, then to enhance the quality of the solutions using the \(\epsilon \)-constraint method to push them toward the exact Pareto front. An intelligent decomposition scheme is used to reduce the size of the search space before applying the exact method. Computational results demonstrate the efficiency of the proposed hybrid algorithm using instances derived from real network topology and other randomly generated instances.
Similar content being viewed by others
References
Abdelkhalek, Ons, Masri, Hela, & Krichen, Saoussen. (2015). An adaptive variable neighborhood search for solving the multi-objective node placement problem. Electronic Notes in Discrete Mathematics, 47, 189–196.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs, NJ: Prentice-Hall.
Amiria, A., & Barkhic, R. (2001). The combinatorial bandwidth packing problem. European Journal of Operational Research, 208(1), 37–45.
Assad, A. A. (1978). Multicommodity network flows—A survey. Networks, 8, 37–91.
Baier, G., Kohler, E., & Skutella, M. (2002). On the k-splittable flow problem. In 10th annual european symposium on algorithms (pp. 101–113).
Barnhart, C., Hane, C. A., & Vance, P. H. (2000). Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research, 48(2), 318–326.
Barnhart, C., Hane, C. A., & Vance, P. H. (2010). An ant colony optimization metaheuristic for single-path multicommodity network flow problems. Journal of the Operational Research Society, 61(9), 1340–1355.
Chiang, M., Low, S. H., Calderbank, A. R., & Doyle, J. C. (2007). Layering as optimization decomposition: A mathematical theory of network architectures. Proceedings of the IEEE, 95(1), 255–312.
Contreras-Bolton, C., Gatica, G., Rey Barra, C., & Parada, V. (2016). A multi-operator genetic algorithm for the generalized minimum spanning tree problem. Expert Systems with Applications, 50, 1–8.
Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In Lecture notes in computer science (Vol. 1917, pp. 849–858).
Delorme, X., Gandibleux, X., & Degoutin, F. (2010). Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem. European Journal of Operational Research, 204(2), 206–217.
Eusbio, A., & Figueira, J. R. (2009). Finding non-dominated solutions in bi-objective integer network flow problems. Computers & Operations Research, 36(9), 2554–2564.
Eusbio, A., & Figueira, J. R. (2009). On the computation of all supported efficient solutions in multi-objective integer network flow problems. European Journal of Operational Research, 199(1), 68–76.
Geiger, M. J. (2004). Randomised Variable Neighbourhood Search for Multi Objective Optimisation. In Proceedings of EU/ME workshop: Design and evaluation of advanced hybrid meta-heuristics (pp. 34–42).
Haimes, Y. Y., Lasdon, L. S., & Wismer, D. A. (1971). On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Transaction on Systems, Man, and Cybernetics, 1(3), 296–29.
Hall, A., Hippler, S., & Skutella, M. (2007). Multicommodity flows over time: Efficient algorithms and complexity. Theoretical Computer Science, 379(3), 387–404.
Handler, G., & Zang, I. (1980). A dual algorithm for the constrained shortest path problem. Networks, 10, 293–310.
Holmberg, K., & Yuan, D. (2003). A multicommodity network-flow problem with side constraints on paths solved by column generation. INFORMS Journal on Computing, 15(1), 42–57.
Kleinberg, J. M. (1996). Approximation algorithms for disjoint paths problems. Ph.D. thesis, MIT, Cambridge, MA.
Koch, R., Skutella, M., & Spenke, I. (2005). Approximation and complexity of k-splittable flows, approximation and online algorithms. In Third international workshop, WAOA (pp. 244–257).
Leesutthipornchai, P., Charnsripinyb, C., & Wattanapongsakorn, N. (2010). Solving multiobjective routing and wavelength assignment in WDM network using hybrid evolutionary computation approach. Computer Communications, 33(18), 2246–2259.
Masri, H., Krichen, S., & Guitouni, A. (2011). An ant colony optimization metaheuristic for solving bi-objective multi-sources multicommodity communication flow problem. In Proceeding of 4th joint IFIP wireless and mobile networking conference (WMNC) (pp. 1–8).
Masri, H., Krichen, S., & Guitouni, A. (2017). Metaheuristics for solving the bi-objective single path multicommodity communication flow problem. International Transactions in Operational Research, 1–26.
Masri, H., Krichen, S., & Guitouni, A. (2014). A metaheuristic for solving the unsplittable multicommodity flow problem: The maritime surveillance case. International Journal of Business Intelligence and Data Mining, 9(3), 254–269.
Mavrotas, G. (2009). Effective implementation of the e-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213, 455–465.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers and Operations Research, 24(11), 1097–1100.
Moradi, S. (2010). The bi-objective multi-commodity minimum cost flow problem. In Proceedings of the 45th annual conference of the ORSNZ (pp. 28–38).
Moradi, S., Raith, A., & Ehrgott, M. (2015). A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem. European Journal of Operational Research, 244(2), 369–378.
Ouorou, P. A., Mahey, P., & Vial, J. (2000). A survey of algorithms for convex multicommodity flow problems. Management Science, 46(1), 126–147.
Raith, A., & Ehrgott, M. (2009). A two-phase algorithm for the biobjective integer minimum cost flow problem. Computers & Operations Research, 36(6), 1945–1954.
Raith, A., & Ehrgott, M. (2009). A comparison of solution strategies for biobjective shortest path problems. Computers & Operations Research, 36(4), 1299–1331.
Ribeiro, C. C., Martins, S. L., & Rosseti, I. (2007). Metaheuristics for optimization problems in computer communications. Computer Communications, 30(4), 656–669.
Rubio-Largo, A., Vega-Rodriguez, M. A., Gomez-Pulido, J. A., & Sanchez-Perez, J. M. (2010). Solving the routing and wavelength assignment problem in WDM networks by using a multiobjective variable neighborhood search algorithm. Advances in Intelligent and Soft Computing, 73, 47–54.
Sedeno-Noda, A., Gonzalez-Martin, C., & Gutierrez, J. (2005). The biobjective undirected two-commodity minimum cost flow problem. European Journal of Operational Research, 164, 89–103.
Sifaleras, A. (2016). Minimum cost network flows: Problems, algorithms, and software. Yugoslav Journal of Operations Research, 23(1), 3–17.
Stummer, C., & Sun, M. (2005). New multiobjective metaheuristic solution procedures for capital investment planning. Journal of Heuristics, 11(3), 183–199.
Sun, H., & Wang, G. (2003). Parallel machine earliness and tardiness scheduling with proportional weights. Computers & Operations Research, 30(5), 801–808.
Veldhuizen, D. A. V., & Lamont, G. B. (1999). Multiobjective evolutionary algorithm test suites. In Proceedings of the 1999 ACM symposium on applied computing (pp. 351–357).
Xing, H., & Qu, R. (2013). A nondominated sorting genetic algorithm for bi-objective network coding based multicast routing problems. Information Sciences, 233, 36–53.
Yen, J. Y. (1971). Finding the k-shortest loopless paths in a network. Management Science, 17, 712–716.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Masri, H., Krichen, S. Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem. Ann Oper Res 267, 353–377 (2018). https://doi.org/10.1007/s10479-017-2667-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-017-2667-0