A two-level strategy based on evolutionary algorithm to solve the inter-domain path computation under node-defined domain uniqueness constraint
Anh Do Tuan, Long Nguyen Hoang, Ta Bao Thang, Huỳnh Thị Thanh Bình, Simon M. Su · 2021
The Inter-Domain Path Computation problem under Node-defined Domain Uniqueness constraint (IDPC-NDU) is a recently investigated topic for finding the effective routing paths on the multi-domain network topology as well as transportation. The objective of the IDPC-NDU is to find the shortest path in the multi-domain directed graph that traverses every domain at most once. Since the IDPC-NDU belongs to NP-Hard class, this paper proposes a novel two-level approach based on an Evolutionary Algorithm (EA) to solve it. The first level aims to determine the sequence of crossed domains using an improved Genetic Algorithm (GA), while the second one aims to locate the minimally costly path between two nodes among the entire domains. Furthermore, we devise an approach to represent a chromosome, which reduces the chromosome length to the number of domains. Experiments on numerous sets of instances were implemented to show the effectiveness and characteristics of the proposed algorithm.