Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Thais Ávila, Ángel Corberán, Isaac Plana, José M. Sanchis
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2017
Materias:	90C10 90C27 90C57 90B99 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/93c8b2370ace48008f469dc1890230c0
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:93c8b2370ace48008f469dc1890230c0
record_format	dspace
spelling	oai:doaj.org-article:93c8b2370ace48008f469dc1890230c02021-12-02T05:01:02ZFormulations and exact algorithms for the distance-constrained generalized directed rural postman problem2192-440610.1007/s13675-015-0053-8https://doaj.org/article/93c8b2370ace48008f469dc1890230c02017-09-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000848https://doaj.org/toc/2192-4406The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distance (or time) constraint all of them have to satisfy. We introduce four formulations for this problem, propose some families of valid inequalities, and present four branch-and-cut algorithms for its solution. The formulations and the algorithms are compared on a large set of instances.Thais ÁvilaÁngel CorberánIsaac PlanaJosé M. SanchisElsevierarticle90C1090C2790C5790B99Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 5, Iss 3, Pp 339-365 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 90C27 90C57 90B99 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 90C27 90C57 90B99 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Thais Ávila Ángel Corberán Isaac Plana José M. Sanchis Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
description	The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distance (or time) constraint all of them have to satisfy. We introduce four formulations for this problem, propose some families of valid inequalities, and present four branch-and-cut algorithms for its solution. The formulations and the algorithms are compared on a large set of instances.
format	article
author	Thais Ávila Ángel Corberán Isaac Plana José M. Sanchis
author_facet	Thais Ávila Ángel Corberán Isaac Plana José M. Sanchis
author_sort	Thais Ávila
title	Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
title_short	Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
title_full	Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
title_fullStr	Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
title_full_unstemmed	Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
title_sort	formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
publisher	Elsevier
publishDate	2017
url	https://doaj.org/article/93c8b2370ace48008f469dc1890230c0
work_keys_str_mv	AT thaisavila formulationsandexactalgorithmsforthedistanceconstrainedgeneralizeddirectedruralpostmanproblem AT angelcorberan formulationsandexactalgorithmsforthedistanceconstrainedgeneralizeddirectedruralpostmanproblem AT isaacplana formulationsandexactalgorithmsforthedistanceconstrainedgeneralizeddirectedruralpostmanproblem AT josemsanchis formulationsandexactalgorithmsforthedistanceconstrainedgeneralizeddirectedruralpostmanproblem
_version_	1718400842184261632

Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

Ejemplares similares