A Genetic Algorithms Approach for Inverse Shortest Path Length Problems

António Leitão, Adriano Vinhas, Penousal Machado and Francisco Câmara Pereira
Additional contact information
António Leitão: CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal
Adriano Vinhas: CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal
Penousal Machado: CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal
Francisco Câmara Pereira: Department of Informatics Engineering, University of Coimbra & Singapore-MIT Alliance for Research and Technology, Singapore, Singapore

International Journal of Natural Computing Research (IJNCR), 2014, vol. 4, issue 4, 36-54

Abstract: Inverse Combinatorial Optimization has become a relevant research subject over the past decades. In graph theory, the Inverse Shortest Path Length problem becomes relevant when people don't have access to the real cost of the arcs and want to infer their value so that the system has a specific outcome, such as one or more shortest paths between nodes. Several approaches have been proposed to tackle this problem, relying on different methods, and several applications have been suggested. This study explores an innovative evolutionary approach relying on a genetic algorithm. Two scenarios and corresponding representations are presented and experiments are conducted to test how they react to different graph characteristics and parameters. Their behaviour and differences are thoroughly discussed. The outcome supports that evolutionary algorithms may be a viable venue to tackle Inverse Shortest Path problems.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijncr.2014100103 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jncr00:v:4:y:2014:i:4:p:36-54

Access Statistics for this article

International Journal of Natural Computing Research (IJNCR) is currently edited by Xuewen Xia

More articles in International Journal of Natural Computing Research (IJNCR) from IGI Global
Bibliographic data for series maintained by Journal Editor ().