A hybrid genetic algorithm for solving the length-balanced two arc-disjoint shortest paths problem

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationAdvances in Applied Artificial Intelligence
Subtitle of host publication19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings
PublisherSpringer Verlag
Pages272-281
Volume4031 LNAI
ISBN (Print)3540354530, 9783540354536
StatePublished - 2006
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4031 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006
PlaceFrance
CityAnnecy
Period27 - 30 June 2006

Abstract

We consider a HAZMAT transportation problem, which is modeled as the length-balanced two arc-disjoint shortest paths problem (LB2SP). In LB2SP, we try to find two arc-disjoint paths on a given network. We hope to reach two objectives: a minimized sum of the path lengths, and a minimized length difference between the paths. These two objectives are independent and even conflicting. Therefore, the objective function of LB2SP is expressed as a weighted sum of two terms: sum of the path lengths and the length difference between the paths. LB2SP is known to be NP-Hard, and can be formulated as an Integer Programming (IP) model. We propose a genetic algorithm (GA) and hybridize a quick Lagrangian relaxation-based heuristic (LRBH) as a module with the proposed GA. Computational experiments are conducted to compare the performance of the hybrid GA with the CPLEX solver, showing that the GA with hybridization of LRBH Is efficient for LB2SP. © Springer-Verlag Berlin Heidelberg 2006.

Research Area(s)

  • Lagrangian relaxation, Length-balanced, Shortest path

Citation Format(s)

A hybrid genetic algorithm for solving the length-balanced two arc-disjoint shortest paths problem. / Li, Yanzhi; Lim, Andrew; Ma, Hong.

Advances in Applied Artificial Intelligence: 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings. Vol. 4031 LNAI Springer Verlag, 2006. p. 272-281 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4031 LNAI).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review