Affiliations: Department of Computer Science, Multimedia and Telecommunication, IN3-Open University of Catalonia, Barcelona, Spain. E-mails: {sgonzalezmarti, ajuanp, drierat, jcastellav, aperezbon}@uoc.edu | Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA. E-mail: rodmk@mit.edu
Note: [] Corresponding author: Sergio González-Martín, Department of Computer Science, Multimedia and Telecommunication, IN3-Open University of Catalonia, 156 Rambla Poblenou, 08018 Barcelona, Spain. E-mail: sgonzalezmarti@uoc.edu.
Abstract: The Capacitated Arc Routing Problem (CARP) is a combinatorial optimization problem similar to the well-known Capacitated Vehicle Routing Problem (CVRP). In the CARP, the customers' demands are located on the edges (arcs) of a general (not necessarily complete) graph. This is in contrast to the CVRP, where demand is located on the nodes of a complete graph. While the CVRP has been extensively studied over the past couple of decades, the number of articles and research results on the CARP is significantly lower. To partially fill this gap in the literature, a new heuristic and two new algorithms for the CARP are proposed and evaluated. Our Savings-based Heuristic for the ARP (SHARP) is inspired on the popular Clarke and Wright savings heuristic for the CVRP. The SHARP procedure outperforms the classical Path Scanning heuristic (PSH) and thus it can be integrated into most meta-heuristics to provide a ‘good’ and fast initial solution to medium-to-large size ARPs which cannot be solved using exact approaches. Using both SHARP and PSH as a base, two randomized algorithms are developed in this paper. These are multi-start algorithms which introduce a biased randomization process to each heuristic. This randomization process uses biased probability distributions, such as the geometric one, in order to induce some degree of randomness in the solution-construction stage while keeping most of the heuristic ‘common sense’. In order to state their efficiency, both randomized algorithms are compared and evaluated using a standard set of benchmarks. The results show that our randomized version of SHARP, RandSHARP, is quite competitive and far superior to the PSH-based randomized algorithm.
