Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

An efficiency-based path-scanning heuristic for the capacitated arc routing problem

Texto completo
Autor(es):
Arakaki, Rafael Kendy [1] ; Usberti, Fabio Luiz [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Ave Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: Computers & Operations Research; v. 103, p. 288-295, MAR 2019.
Citações Web of Science: 1
Resumo

The capacitated arc routing problem (CARP) is an important combinatorial optimization problem that has been extensively studied in the last decades. The objective is to optimize routes that service demands located on the edges of a graph, given a fleet of homogeneous vehicles with limited capacity that starts and ends its routes at a specific node (depot). This work proposes a new path-scanning heuristic for the CARP which introduces the concept of efficiency rule. Given the current vehicle location, its traversed distance and the amount of serviced demand, the efficiency rule selects the most promising edges to service next. Computational experiments conducted on a set of benchmark instances reveal that the proposed heuristic substantially outperformed all previous path-scanning heuristics from literature. (C) 2018 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 16/00315-0 - Formulações e Algoritmos para Problemas de Roteamento em Arcos
Beneficiário:Rafael Kendy Arakaki
Linha de fomento: Bolsas no Brasil - Doutorado