30-10-2012, 04:51 PM
Solving Shortest Capacitated Path Problem Using a Bi-Objective Heuristic Approach
Solving Shortest Capacitated.pdf (Size: 934.38 KB / Downloads: 25)
Abstract
The shortest capacitated path problem is a well
known problem in the networking area, having a
wide range of applications. In the shortest
capacitated path problem, a traffic flow occurs from
a source node to a destination node in a certain
direction subject to a cost constraint. In this paper, a
new approach for dealing with this problem is
proposed. The proposed algorithm uses a special
way to build valid solutions and an improvement
technique to adjust the path. Some numerical
experiments are performed using randomly
generated networks having 25 - 200 nodes.
Empirical results are compared with the results
obtained using Genetic Algorithms which is an
established technique for solving networking
problems.
Introduction
In this paper, we deal with the shortest capacitated
path problem in which a flow must be sent from a
source node to a destination node in a certain
direction subject to cost constraints.
Two main objectives are formulated:
- cost of the path must be minimized
- the number of common edges whose
capacity is less then the required one must
be minimized (in fact, it must be 0).
The network studied is a capacitated network (which
means capacities are limited) and there is a cost on
each edge per unit of bandwidth. As reported in the
literature, huge amount of work has been done in
this area. Several different approaches have been
proposed for this problem: Tabu Search has been
used in [5], Multiobjective Genetic Algorithms have
been applied in [7], Genetic algorithms and other
machine learning techniques have been extensively
applied [1][2][4][8][9][10], Scaling algorithms were
used in [3] and [6].
Proposed Approach
We consider the following problem: a undirected
graph G= (V, E), a cost function cost: E ®R+ and a
capacity function capacity: E ® R+ are given. We
are given some requirements between one pair of
vertices (source and destination) (s, d) Î V. The
goal is to find a minimal (cost wise) path between
these nodes as well as to assure that the capacity of
the edges is not overloaded.
Conclusions
In this paper, a new technique for solving the
shortest capacitated path problem is proposed.
This approach starts with a set of solutions which
are built in a special way so that no invalid
solutions are created. These solutions are thereafter
improved by using a simple mechanism which rebuilds
certain parts of the existing path. Numerical
experiment and comparisons with genetic
algorithms show the efficiency of this new
proposed technique and its suitability for large
networks.