Paper Info
Title
A hybrid genetic algorithm for solving the length-balanced two arc-disjoint shortest paths problem
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. Areas: heuristic search, industrial application of AI, genetic algorithms.
Year
DOI
Venue
2006
10.1007/11779568_31
IEA/AIE
Keywords
Field
DocType
heuristic search,hazmat transportation problem,length difference,genetic algorithm,weighted sum,arc-disjoint shortest paths problem,hybrid genetic algorithm,arc-disjoint path,proposed ga,path length,hybrid ga,shortest path problem,computer experiment,transportation problem,objective function,lagrangian relaxation,shortest path
Mathematical optimization,Heuristic,Disjoint sets,Shortest path problem,Computer science,Algorithm,Integer programming,Floyd–Warshall algorithm,Lagrangian relaxation,Solver,Genetic algorithm
Conference
Volume
ISSN
ISBN
4031
0302-9743
3-540-35453-0
Citations 
PageRank 
References 
0
0.34
5
Authors
3
Name
Order
Citations
PageRank
Yanzhi Li16711.56
Andrew Lim2172.44
Hong Ma300.34