Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem

Hela Masri () and Saoussen Krichen ()
Additional contact information
Hela Masri: Tunis Business School
Saoussen Krichen: Institut Supérieur de Gestion de Tunis

Annals of Operations Research, 2018, vol. 267, issue 1, No 18, 353-377

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

Keywords: Multiobjective optimization; Metaheuristics; Multicommodity flow problem (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2667-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:267:y:2018:i:1:d:10.1007_s10479-017-2667-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2667-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().