A Genetic Algorithms Approach for Inverse Shortest Path Length Problems

A Genetic Algorithms Approach for Inverse Shortest Path Length Problems

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) and Francisco Câmara Pereira (Department of Informatics Engineering, University of Coimbra & Singapore-MIT Alliance for Research and Technology, Singapore, Singapore)
Copyright: © 2014 |Pages: 19
DOI: 10.4018/ijncr.2014100103

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.
Article Preview

Inverse Combinatorial Optimization

On a broad analysis, inverse optimization problems can be branched into two classes: inverse solution optimization problems and inverse objective value optimization problems (Hung & Director-Sokol, 2003). Briefly, inverse solution optimization problems require finding an arc costs vector that makes a desired solution optimal. Variations include the minimum cut problem (Zhang & Cai, 1998), inverse maximum flow problem (Yang, Zhang, & Ma, 1997), inverse center location problem (Cai, Yang, & Zhang, 1999), the inverse shortest path problem (ISPP) (Cai & Yang, 1994), among others. Inverse objective value optimization problems require that a solution is found that matches a desired value for the objective function rather than assuming there is a desired optimal solution. This type of problem has been much less explored than inverse solution optimization problems but the reverse center location (Zhang, Yang, & Cai, 1999) and the Inverse Shortest Path Length (ISPL) (Fekete, Hochstättler, Kromberg, & Moll, 1999) are examples, with ISPL probably being the most widely known. Heuberger (2004) presented various methods that had been successfully applied in the past to a set of inverse combinatorial problems on an extended survey. The following subsections further explore the two classes of inverse combinatorial optimization and previous work regarding each one.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 7: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing