[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A Lagrangian Relaxation Based Heuristic for Solving the Length-Balanced Two Arc-Disjoint Shortest Paths Problem

  • Conference paper
AI 2005: Advances in Artificial Intelligence (AI 2005)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 3809))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Hazardous materials shipments. Office of Hazardous Materials Safety, U.S. Department of Transportation, Washington DC (October 1998)

    Google Scholar 

  2. Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming 73, 129–196 (1996)

    MathSciNet  MATH  Google Scholar 

  3. Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM 7(4), 326–329 (1960)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept of Industrial Engineering and Logistics Management, Hong Kong Univ of Science and Technology, Clear Water Bay, Kowloon, Hong Kong

    Yanzhi Li, Andrew Lim & Hong Ma

  2. School of Computer Science & Engineering, South China University of Technology, Guang Dong, P.R.China

    Andrew Lim

Authors
  1. Yanzhi Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Lim
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hong Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Guangxi Normal University, College of CS and IT, Guilin, China, and University of Technology, Faculty of Engineering and Information Technology, Sydney, Australia

    Shichao Zhang

  2. Department of Electrical and Computer Systems Engineering, Monash University, 3800, Melbourne, Victoria, Australia

    Ray Jarvis

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Li, Y., Lim, A., Ma, H. (2005). A Lagrangian Relaxation Based Heuristic for Solving the Length-Balanced Two Arc-Disjoint Shortest Paths Problem. In: Zhang, S., Jarvis, R. (eds) AI 2005: Advances in Artificial Intelligence. AI 2005. Lecture Notes in Computer Science(), vol 3809. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11589990_196

Download citation

  • DOI: https://doi.org/10.1007/11589990_196

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-30462-3

  • Online ISBN: 978-3-540-31652-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation