Abstract
The Steiner multi-ring network design problem with revenues consists of designing node-disjoint multiple rings connected by a specific node (hub) and passing through all the nodes with high priority of service and some of the nodes with low priority of service. The number of nodes in each ring has an upper bound to assure a certain level of service. Besides the usual arc link costs, we also consider revenues between each pair of nodes in the same ring, even when they are not connected by a direct link. The objective is to minimize the difference between the total connection cost and total revenue. The problem is a generalization of the problem studied in Gouveia and Pires (Eur J Oper Res 133:21–31, 2001a) and it can also be seen as a combination of variants of two NP-Hard problems, the vehicle routing problem and the maximum edge-weighted clique problem. We introduce and discuss two types of integer linear programming formulations and propose some valid inequalities to strengthen the linear programming relaxation. Computational results are presented to evaluate the quality of the linear programming relaxation bounds associated with these formulations as well as efficiency of the models to obtain the optimal integer solutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baldacci R, Dell’Amico M (2010) Heuristic algorithms for the multi-depot ring-star problem. Eur J Oper Res 203:270–281
Baldacci R, Dell’Amico M, Salazar González J (2007) The capacitated M-ring-star problem. Ope Res 55:1147–1162
Berinsky H, Zabala P (2011) An integer linear programming formulation and branch-and-cut algorithm for the capacitated M-ring-star problem. Electr Notes Discret Math 37:273–278
Carroll P, Fortz B, Labbé M, McGarraghy S (2013) A branch-and-cut algorithm for the ring spur assignment problem. Networks 61(2):89–103
Carroll P, Fortz B, Labbé M, McGarraghy S (2011) Improved formulations for the ring spur assignment problem. In: Pahl J, Reiners T, Voss S (eds) Network optimization, vol 6701 of Lecture notes in computer science. Springer, Berlin, pp 24–36
Câmpelo M, Campos VA, Corrêa RC (2008) On the asymmetric representatives formulations for the vertex coloring problem. Discret Appl Math 156:1097–1111. doi:10.1016//j.dam.2007.05.058
Desrochers M, Laporte G (1991) Improvements to the Miller–Tucker–Zemlin subtour elimination constraints. Oper Res Lett 10:27–36
Gendreau M, Labbé M, Laporte G (1995) Efficient heuristics for the design of ring networks. Telecommun Syst 4:177–188
Gouveia L, Pesneau P (2006) On extend formulations for the precedence constrained asymmetric travelling salesman problem. Networks 48:77–89
Gouveia L, Pires J (2001a) Models for a Steiner ring network design problem with revenues. Eur J Oper Res 133:21–31
Gouveia L, Pires J (2001b) The Asymmetric travelling salesman problem: on generalizations of disaggregated of Miller–Tucker–Zemlin constraints. Discret Appl Math 112:129–145
Gouveia L, Pires J (1999) The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints. Eur J Oper Res 112:134–146
Klincewicz J, Luss H, Yan D (1998) Designing tributary networks with multiple ring families. Comput Oper Res 25:1145–1157
Labbé M, Laporte G, Rodríguez Martín I, Salazar González J (2004) The ring star problem: polyhedral analysis and exact algorithm. Networks 43:177–189
Naji-Azimi Z, Salari M, Toth P (2012) An integer linear programming based heuristic for the capacitated M-ring-star problem. Eur J Oper Res 217:17–25
Naji-Azimi Z, Salari M, Toth P (2010) A heuristic procedure for the capacitated M-ring-star problem. Eur J Oper Res 207:1227–1234
Pires JM (2001) Formulações Para O Problema Do Caixeiro Viajante Assimétrico E Sua Aplicação a Um Problema De Desenho De Redes Com Topologia Em Forma De Anel. Faculdade de Ciências da Universidade de Lisboa, Departamento de Estatística e Investigação Operacional
Sarin SC, Sherali HD, Bhootra A (2005) New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Oper Res Lett 33:62–70
Sherali H, Sarin S, Tsai P (2006) A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints. Discret Optim 3:20–32
Toth P, Vigo D (eds) (2002) The vehicle routing problem, vol 9 of SIAM monographs on discrete mathematics and applications, chapter 1. SIAM, Philadelphia, pp 1–26
Acknowledgments
This work is supported by National Funding from FCT - Fundação para a Ciência e a Tecnologia, under the project: PEst-OE/MAT/UI0152. The authors would like to thank the anonymous referees for the helpful comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bautzer, A., Gouveia, L., Paias, A. et al. Models for a Steiner multi-ring network design problem with revenues. TOP 24, 360–380 (2016). https://doi.org/10.1007/s11750-015-0388-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-015-0388-6