Search

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. [ABSTRACT FROM AUTHOR]

Move pruning is a low-overhead technique for reducing search cost in single-agent search problems by avoiding the generation of duplicate states. Redundant sequences of moves, where the effect of one sequence is provably identical to some other sequence of moves, are suppressed during search. We present an algorithm for automatically identifying redundant move sequences in a general class of single-agent search problems, and a method for selecting redundant move sequences to prune during search. We demonstrate that the redundant move sequences which are to be pruned must be chosen carefully, and give experimental results using our move pruning method which show a speedup of multiple orders of magnitude in a variety of domains. Finally, we give theoretical results on conditions where move pruning does, and does not, affect the correctness of different search algorithms. [ABSTRACT FROM AUTHOR]