Optimal capacitated ring trees

We study a new network design model combining ring and tree structures under capacity constraints. The solution topology of this capacitated ring tree problem (CRTP) is based on ring trees which are the union of trees and 1-trees. The objective is the minimization of edge costs but could also incorp...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Alessandro Hill, Stefan Voß
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2016
Materias:	90C11 90C27 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/e8442715fd204038b9c8ac4b8d93152f
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e8442715fd204038b9c8ac4b8d93152f
record_format	dspace
spelling	oai:doaj.org-article:e8442715fd204038b9c8ac4b8d93152f2021-12-02T05:00:51ZOptimal capacitated ring trees2192-440610.1007/s13675-015-0035-xhttps://doaj.org/article/e8442715fd204038b9c8ac4b8d93152f2016-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000599https://doaj.org/toc/2192-4406We study a new network design model combining ring and tree structures under capacity constraints. The solution topology of this capacitated ring tree problem (CRTP) is based on ring trees which are the union of trees and 1-trees. The objective is the minimization of edge costs but could also incorporate other types of measures. This overall problem generalizes prominent capacitated vehicle routing and Steiner tree problem variants. Two customer types have to be connected to a distributor ensuring single and double node connectivity, respectively, while installing optional Steiner nodes. The number of ring trees and the number of customers supplied by such a single structure are bounded. After embedding this combinatorial optimization model in existing network design concepts, we develop a mathematical formulation and introduce several valid inequalities for the CRTP that are separated in our exact algorithm. For a set of literature-derived instances we consider various reliability scenarios and present computational results.Alessandro HillStefan VoßElsevierarticle90C1190C2790C90Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 4, Iss 2, Pp 137-166 (2016)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C11 90C27 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C11 90C27 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Alessandro Hill Stefan Voß Optimal capacitated ring trees
description	We study a new network design model combining ring and tree structures under capacity constraints. The solution topology of this capacitated ring tree problem (CRTP) is based on ring trees which are the union of trees and 1-trees. The objective is the minimization of edge costs but could also incorporate other types of measures. This overall problem generalizes prominent capacitated vehicle routing and Steiner tree problem variants. Two customer types have to be connected to a distributor ensuring single and double node connectivity, respectively, while installing optional Steiner nodes. The number of ring trees and the number of customers supplied by such a single structure are bounded. After embedding this combinatorial optimization model in existing network design concepts, we develop a mathematical formulation and introduce several valid inequalities for the CRTP that are separated in our exact algorithm. For a set of literature-derived instances we consider various reliability scenarios and present computational results.
format	article
author	Alessandro Hill Stefan Voß
author_facet	Alessandro Hill Stefan Voß
author_sort	Alessandro Hill
title	Optimal capacitated ring trees
title_short	Optimal capacitated ring trees
title_full	Optimal capacitated ring trees
title_fullStr	Optimal capacitated ring trees
title_full_unstemmed	Optimal capacitated ring trees
title_sort	optimal capacitated ring trees
publisher	Elsevier
publishDate	2016
url	https://doaj.org/article/e8442715fd204038b9c8ac4b8d93152f
work_keys_str_mv	AT alessandrohill optimalcapacitatedringtrees AT stefanvoß optimalcapacitatedringtrees
_version_	1718400863114887168

Optimal capacitated ring trees

Ejemplares similares