Lagrangean relaxation algorithms for fixed-charge capacitated relay network design

Panitan Kewcharoenwong, Qiaofeng Li and Halit Üster

Omega, 2023, vol. 121, issue C

Abstract: We consider a fixed-charge capacitated relay network design problem (CRNDP), which has widespread applications in the design of telecommunication and transportation networks, where relay points are presented as signal regenerators, truckload driver and/or tractor exchange stations or electrical vehicle recharging station. Our CRNDP integrates the key features of single allocation hub location problem (SAHLP) and capacitated network design problem (CNDP). Typical range restrictions in truckload transportation, electrical vehicles as well as for keeping signal strength in telecommunications, and further limitations of flow on the links of an underlying network in these mediums motivate the use of distance constraints and link capacity constraints in the design of a relay network for this diverse set of applications. To efficiently solve our model, we propose a Lagrangean relaxation algorithm, where the upper bounds are enhanced by a heuristic during the iterations and the lower bound is improved by the introduction of surrogate constraints. The extensive computational studies are conducted to examine the performance of the algorithm and the results show that the solution method we propose can efficiently solve CRNDP and obtain good-quality solutions, even for very large size instances.

Keywords: Capacitated relay network design; Lagrangean relaxation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048323000907
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:121:y:2023:i:c:s0305048323000907

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2023.102926

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().