IDEAS home Printed from https://ideas.repec.org/h/spr/sprchp/978-1-4419-0820-9_14.html
   My bibliography  Save this book chapter

An Active-set Algorithm for Discrete Network Design Problems

In: Transportation and Traffic Theory 2009: Golden Jubilee

Author

Listed:
  • Lihui Zhang

    (University of Florida)

  • Siriphong Lawphongpanich

    (University of Florida)

  • Yafeng Yin

    (University of Florida)

Abstract

In this paper, we formulate a discrete network design problem as a mathematical program with complementarity constraints and propose an active set algorithm to solve the problem. Each complementarity constraint requires the product of a pair of nonnegative variables to be zero. Instead of dealing with this type of constraints directly, the proposed algorithm assigns one of the nonnegative variables in each pair a value of zero. Doing so reduces the design problem to a regular nonlinear program. Using the multipliers associated with the constraints forcing nonnegative variables to be zero, the algorithm then constructs and solves binary knapsack problems to make changes to the zero-value assignments in order to improve the system delay. Numerical experiments with data from networks in the literature indicate that the algorithm is effective and has the potential for solving larger network design problems.

Suggested Citation

  • Lihui Zhang & Siriphong Lawphongpanich & Yafeng Yin, 2009. "An Active-set Algorithm for Discrete Network Design Problems," Springer Books, in: William H. K. Lam & S. C. Wong & Hong K. Lo (ed.), Transportation and Traffic Theory 2009: Golden Jubilee, chapter 0, pages 283-300, Springer.
    • Handle: RePEc:spr:sprchp:978-1-4419-0820-9_14
    DOI: 10.1007/978-1-4419-0820-9_14
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ximing Wang & Panos M. Pardalos, 2017. "A modified active set algorithm for transportation discrete network design bi-level problem," Journal of Global Optimization, Springer, vol. 67(1), pages 325-342, January.
    2. Zhang, Wenwei & Xu, Min & Wang, Shuaian, 2023. "Joint location and pricing optimization of self-service in urban logistics considering customers’ choice behavior," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    3. Wu, Di & Yin, Yafeng & Lawphongpanich, Siriphong, 2011. "Optimal selection of build–operate-transfer projects on transportation networks," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1699-1709.
    4. Bahrami, Sina & Roorda, Matthew J., 2020. "Optimal traffic management policies for mixed human and automated traffic flows," Transportation Research Part A: Policy and Practice, Elsevier, vol. 135(C), pages 130-143.
    5. Di, Xuan & Ma, Rui & Liu, Henry X. & Ban, Xuegang (Jeff), 2018. "A link-node reformulation of ridesharing user equilibrium with network design," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 230-255.
    6. Miralinaghi, Mohammad & Seilabi, Sania E. & Chen, Sikai & Hsu, Yu-Ting & Labi, Samuel, 2020. "Optimizing the selection and scheduling of multi-class projects using a Stackelberg framework," European Journal of Operational Research, Elsevier, vol. 286(2), pages 508-522.
    7. Chen, Zhibin & He, Fang & Yin, Yafeng, 2016. "Optimal deployment of charging lanes for electric vehicles in transportation networks," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 344-365.
    8. He, Fang & Wu, Di & Yin, Yafeng & Guan, Yongpei, 2013. "Optimal deployment of public charging stations for plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 47(C), pages 87-101.
    9. Matthews, Logan R. & Gounaris, Chrysanthos E. & Kevrekidis, Ioannis G., 2019. "Designing networks with resiliency to edge failures using two-stage robust optimization," European Journal of Operational Research, Elsevier, vol. 279(3), pages 704-720.
    10. Yang, Zhile & Li, Kang & Foley, Aoife, 2015. "Computational scheduling methods for integrating plug-in electric vehicles with power systems: A review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 51(C), pages 396-416.
    11. Hamid Farvaresh & Mohammad Sepehri, 2013. "A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem," Networks and Spatial Economics, Springer, vol. 13(1), pages 67-106, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:sprchp:978-1-4419-0820-9_14. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.