An Effective Evolutionary Approach for Bicriteria Shortest Path Routing Problems

• Lin Lin

  Corresponding author. Waseda University, IPS.

• Gen Mitsuo

Abstract

Routing problem is one of the important research issues in communication network fields. In this paper, we consider a bicriteria shortest path routing (bSPR) model dedicated to calculating nondominated paths for (1) the minimum total cost and (2) the minimum transmission delay. To solve this bSPR problem, we propose a new multiobjective genetic algorithm (moGA): (1) an efficient chromosome representation using the priority-based encoding method; (2) a new operator of GA parameters auto-tuning, which is adaptively regulation of exploration and exploitation based on the change of the average fitness of parents and offspring which is occurred at each generation; and (3) an interactive adaptive-weight fitness assignment mechanism is implemented that assigns weights to each objective and combines the weighted objectives into a single objective function. Numerical experiments with various scales of network design problems show the effectiveness and the efficiency of our approach by comparing with the recent researches.

Journal

• IEEJ Transactions on Electronics, Information and Systems

  IEEJ Transactions on Electronics, Information and Systems 128 (3), 416-423, 2008

  The Institute of Electrical Engineers of Japan

Keywords

• bicriteria shortest path
• multiobjective genetic algorithm
• fuzzy logic control
• weighted-sum based fitness assignment

Details

• CRID: 1390282679580927232
• NII Article ID: 10021131692
• NII Book ID: AN10065950
• DOI: 10.1541/ieejeiss.128.416
• ISSN: 13488155
• ISSN: 03854221
• NDL BIB ID: 9401026
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I9401026
• Web Site: http://www.jstage.jst.go.jp/article/ieejeiss/128/3/128_3_416/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed