Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/72188
Type: Artigo de periódico
Title: The open capacitated arc routing problem
Author: Usberti, FL
Franca, PM
Franca, ALM
Abstract: The 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.
Subject: Arc routing
Computational complexity
Path-scanning heuristic
Country: Inglaterra
Editor: Pergamon-elsevier Science Ltd
Rights: fechado
Identifier DOI: 10.1016/j.cor.2011.01.012
Date Issue: 2011
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000289604700009.pdf462.83 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.