A lagrangian relaxation based heuristic 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 publicationAI 2005: Advances in Artificial Intelligence
Subtitle of host publication18th Australian Joint Conference on Artificial Intelligence, Proceedings
PublisherSpringer Verlag
Pages1323-1326
Volume3809 LNAI
ISBN (Print)3540304622, 9783540304623
StatePublished - 2005
Externally publishedYes

Publication series

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

Conference

Title18th Australian Joint Conference on Artificial Intelligence, AI 2005: Advances in Artificial Intelligence
PlaceAustralia
CitySydney
Period5 - 9 December 2005

Abstract

We consider a HAZMAT transportation problem, which is modeled as the length-balanced two arc-disjoint shortest paths problem (LB2SP). The objective function of LB2SP is expressed as a weighted sum of two terms, i.e., the sum of the path lengths and the positive length difference between the paths. We demonstrate that LB2SP is NP-Hard, and formulate it as an Integer Programming (IP) model. We develop a Lagrangian relaxation based heuristic (LRBH) for LB2SP. Computational experiments are conducted to compare the performance of LRBH with the CPLEX solver, showing that the LRBH is efficient for LB2SP. © Springer-Verlag Berlin Heidelberg 2005.

Citation Format(s)

A lagrangian relaxation based heuristic for solving the length-balanced two arc-disjoint shortest paths problem. / Li, Yanzhi; Lim, Andrew; Ma, Hong.

AI 2005: Advances in Artificial Intelligence: 18th Australian Joint Conference on Artificial Intelligence, Proceedings. Vol. 3809 LNAI Springer Verlag, 2005. p. 1323-1326 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3809 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