A branch-and-cut algorithm for the target visitation problem

In this paper, we consider the target visitation problem (TVP) which arises in the context of disaster treatment. Mathematically speaking, the problem is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance travelled, a tour i...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Achim Hildenbrandt
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2019
Materias:	90C10 90C35 90C57 05C38 05C20 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/d867aa1b8ab94a7eb76553ca4d9915f5
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:d867aa1b8ab94a7eb76553ca4d9915f5
record_format	dspace
spelling	oai:doaj.org-article:d867aa1b8ab94a7eb76553ca4d9915f52021-12-02T05:01:12ZA branch-and-cut algorithm for the target visitation problem2192-440610.1007/s13675-019-00111-xhttps://doaj.org/article/d867aa1b8ab94a7eb76553ca4d9915f52019-09-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001167https://doaj.org/toc/2192-4406In this paper, we consider the target visitation problem (TVP) which arises in the context of disaster treatment. Mathematically speaking, the problem is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance travelled, a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinatorial optimization problems: the traveling salesman and the linear ordering problem. In this paper, we point out some polyhedral properties, develop a branch-and-cut algorithm for solving the TVP to optimality and present some computational results.Achim HildenbrandtElsevierarticle90C1090C3590C5705C3805C20Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 7, Iss 3, Pp 209-242 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 90C35 90C57 05C38 05C20 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 90C35 90C57 05C38 05C20 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Achim Hildenbrandt A branch-and-cut algorithm for the target visitation problem
description	In this paper, we consider the target visitation problem (TVP) which arises in the context of disaster treatment. Mathematically speaking, the problem is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance travelled, a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinatorial optimization problems: the traveling salesman and the linear ordering problem. In this paper, we point out some polyhedral properties, develop a branch-and-cut algorithm for solving the TVP to optimality and present some computational results.
format	article
author	Achim Hildenbrandt
author_facet	Achim Hildenbrandt
author_sort	Achim Hildenbrandt
title	A branch-and-cut algorithm for the target visitation problem
title_short	A branch-and-cut algorithm for the target visitation problem
title_full	A branch-and-cut algorithm for the target visitation problem
title_fullStr	A branch-and-cut algorithm for the target visitation problem
title_full_unstemmed	A branch-and-cut algorithm for the target visitation problem
title_sort	branch-and-cut algorithm for the target visitation problem
publisher	Elsevier
publishDate	2019
url	https://doaj.org/article/d867aa1b8ab94a7eb76553ca4d9915f5
work_keys_str_mv	AT achimhildenbrandt abranchandcutalgorithmforthetargetvisitationproblem AT achimhildenbrandt branchandcutalgorithmforthetargetvisitationproblem
_version_	1718400858055507968

A branch-and-cut algorithm for the target visitation problem

Ejemplares similares