GRASP with path-relinking for the cooperative communication problem on ad hoc networks

C. Commander, P. Festa, C. A. S. Oliveira, P. M. Pardalos, M. G. C. Resende, and M. Tsitselis

Cooperative Networks: Control and Optimization, D.A. Grundel, R.A. Murphey, P.M. Pardalos, and O.A. Prokopyev (Eds.), Edward Elgar Publishing, Chapter 10, 2008


Ad-hoc networks are a new paradigm for communications systems in which wireless nodes can freely connect to each other without the need of a pre-specified structure. Difficult combinatorial optimization problem are associated with the design and operation of these networks. In this paper, we consider the problem of maximizing the connection time between a set of mobile agents in an ad-hoc network. Given a network and a set of wireless agents with starting nodes and target nodes, the objective is to find a set of trajectories for the agents that maximizes connectivity during their operation. This problem, referred to as the COOPERATIVE COMMUNICATION ON AD-HOC NETWORKS is known to be NP-hard. We look for heuristic algorithms that are able to efficiently compute high quality solutions to instances of large size. We propose the use of a greedy randomized adaptive search procedure (GRASP) to compute solutions for this problem. The GRASP is enhanced by applying a path-relinking intensification procedure. Extensive experimental results are presented, demonstrating that the proposed strategy provides near optimal solutions for the 900 instances tested.
PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified:12 June 2008

Copyright Notice