The open capacitated arc routing problem

dc.creatorUsberti, FL
dc.creatorFranca, PM
dc.creatorFranca, ALM
dc.date2011
dc.dateNOV
dc.date2014-07-30T18:59:54Z
dc.date2015-11-26T17:49:58Z
dc.date2014-07-30T18:59:54Z
dc.date2015-11-26T17:49:58Z
dc.date.accessioned2018-03-29T00:33:06Z
dc.date.available2018-03-29T00:33:06Z
dc.identifierComputers & Operations Research. Pergamon-elsevier Science Ltd, v. 38, n. 11, n. 1543, n. 1555, 2011.
dc.identifier0305-0548
dc.identifierWOS:000289604700009
dc.identifier10.1016/j.cor.2011.01.012
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/72188
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/72188
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1289540
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionThe Open Capacitated Arc Routing Problem (OCARP) is a NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. A new integer linear programming formulation is given, followed by some properties of the problem. A reactive path-scanning heuristic, guided by a cost-demand edge-selection and ellipse rules, is proposed and compared with other successful CARP path-scanning heuristics from literature. Computational tests were conducted using a set of 411 instances, divided into three classes according to the tightness of the number of vehicles available; results reveal the first lower and upper bounds, allowing to prove optimality for 133 instances. (C) 2011 Elsevier Ltd. All rights reserved.
dc.description38
dc.description11
dc.description1543
dc.description1555
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionIBM
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.languageen
dc.publisherPergamon-elsevier Science Ltd
dc.publisherOxford
dc.publisherInglaterra
dc.relationComputers & Operations Research
dc.relationComput. Oper. Res.
dc.rightsfechado
dc.rightshttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dc.sourceWeb of Science
dc.subjectArc routing
dc.subjectComputational complexity
dc.subjectPath-scanning heuristic
dc.subjectRural Postman Problem
dc.subjectMeter Readers
dc.subjectLower Bounds
dc.subjectAlgorithm
dc.titleThe open capacitated arc routing problem
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución