| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Ave Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil
Total Affiliations: 1
|
| Document type: | Journal article |
| Source: | Computers & Operations Research; v. 103, p. 288-295, MAR 2019. |
| Web of Science Citations: | 1 |
| Abstract | |
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) | |
| FAPESP's process: | 16/00315-0 - Formulations and Algorithms for Arc Routing Problems |
| Grantee: | Rafael Kendy Arakaki |
| Support Opportunities: | Scholarships in Brazil - Doctorate |