Publicação:
The open capacitated arc routing problem

Página do item simplificado
dc.contributor.authorUsberti, Fabio Luiz
dc.contributor.authorFranca, Paulo Morelato [UNESP]
dc.contributor.authorMorelato Franca, Andre Luiz
dc.contributor.institutionUniversidade Estadual de Campinas (UNICAMP)
dc.contributor.institutionUniversidade Estadual Paulista (Unesp)
dc.date.accessioned2014-05-20T13:23:31Z
dc.date.available2014-05-20T13:23:31Z
dc.date.issued2011-11-01
dc.description.abstractThe 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.en
dc.description.affiliationUniv Estadual Campinas, Sch Elect & Comp Engn, BR-13083852 Campinas, SP, Brazil
dc.description.affiliationSão Paulo State Univ, Dept Math Stat & Comp, BR-19060900 Presidente Prudente, SP, Brazil
dc.description.affiliationUnespSão Paulo State Univ, Dept Math Stat & Comp, BR-19060900 Presidente Prudente, SP, Brazil
dc.description.sponsorshipConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.description.sponsorshipIBM
dc.format.extent1543-1555
dc.identifierhttp://dx.doi.org/10.1016/j.cor.2011.01.012
dc.identifier.citationComputers & Operations Research. Oxford: Pergamon-Elsevier B.V. Ltd, v. 38, n. 11, p. 1543-1555, 2011.
dc.identifier.doi10.1016/j.cor.2011.01.012
dc.identifier.issn0305-0548
dc.identifier.urihttp://hdl.handle.net/11449/7104
dc.identifier.wosWOS:000289604700009
dc.language.isoeng
dc.publisherPergamon-Elsevier B.V. Ltd
dc.relation.ispartofComputers & Operations Research
dc.relation.ispartofjcr2.962
dc.relation.ispartofsjr1,916
dc.rights.accessRightsAcesso restrito
dc.sourceWeb of Science
dc.subjectArc routingen
dc.subjectComputational complexityen
dc.subjectPath-scanning heuristicen
dc.titleThe open capacitated arc routing problemen
dc.typeArtigo
dcterms.licensehttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dcterms.rightsHolderPergamon-Elsevier B.V. Ltd
dspace.entity.typePublication
unesp.author.orcid0000-0002-0490-5515[2]
unesp.campusUniversidade Estadual Paulista (UNESP), Faculdade de Ciências e Tecnologia, Presidente Prudentept
unesp.departmentMatemática e Computação - FCTpt

Arquivos

Licença do Pacote

Agora exibindo 1 - 2 de 2
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:

Coleções

Presidente Prudente - FCT - Faculdade de Ciências e Tecnologia