A GRASP and Path Relinking Heuristic for Rural Road Networks Development

Scaparra, Maria Paola and Church, Richard L. (2005) A GRASP and Path Relinking Heuristic for Rural Road Networks Development. Journal of Heuristics, 11 (1). pp. 89-108. ISSN 1381-1231. (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided)

The full text of this publication is not available from this repository. (Contact us about this Publication)


This paper presents a model for rural road network design that involves two objectives: maximize all season road connectivity among villages in a region and maximize route efficiency, while allocating a fix budget among a number of possible road projects. The problem is modeled as a bicriterion optimization problem and solved heuristically through a greedy randomized adaptive search procedure (GRASP) in conjunction with a path relinking procedure. The implementation of GRASP and path relinking includes two novel modifications, a new form of reactive GRASP and a new form of path relinking. Overall, the heuristic approach is streamlined through the incorporation of advanced network flow reoptimization techniques. Results indicate that this implementation outperforms both GRASP as well as a straightforward form of GRASP with path relinking. For small problem instances, for which optimality could be verified, this new, modified form of GRASP with path relinking solved all but one known instance optimally.

Item Type: Article
Subjects: H Social Sciences > HE Transportation and Communications
H Social Sciences > HD Industries. Land use. Labor > HD29 Operational Research - Applications
Divisions: Faculties > Social Sciences > Kent Business School > Management Science
Depositing User: Maria Paola Scaparra
Date Deposited: 21 Oct 2008 22:43
Last Modified: 06 Jun 2014 11:00
Resource URI: https://kar.kent.ac.uk/id/eprint/5377 (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year