A GRASP and Path Relinking Heuristic for Rural Road Networks Development

Scaparra, Maria Paola, 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. (doi:10.1007/s10732-005-7000-4) (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) (KAR id:5377)

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.
Official URL: https://doi.org/10.1007/s10732-005-7000-4

Abstract

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
DOI/Identification number:	10.1007/s10732-005-7000-4
Subjects:	H Social Sciences > HE Transportation and Communications H Social Sciences > HD Industries. Land use. Labor > HD29 Operational Research - Applications
Divisions:	Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User:	Paola Scaparra
Date Deposited:	21 Oct 2008 22:43 UTC
Last Modified:	05 Nov 2024 09:37 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/5377 (The current URI for this page, for reference purposes)

University of Kent Author Information

Scaparra, Maria Paola.

Creator's ORCID:	https://orcid.org/0000-0002-2725-5439
CReDIT Contributor Roles:

Depositors only (login required):

Altmetric

Download Statistics

Total unique views for this document in KAR since July 2020. For more details click on the image.