Solving Capacitated Arc Routing Problems With Meta-heuristics

Capacitated Arc Routing Problem (CARP) is a classic combinatorial optimization problem which has a wide real-world applications such as winter gritting, urban waste collection and post delivery. It has been receiving increasing research interest in the last few decades. However, due to its complicatedness, even for its simplest form, the optimal solution cannot be found in polynomial time of the problem size. For this reason, we consider solving it with approximation approaches, in particular, meta-heuristic approaches. Starting from the basic model of CARP, a problem-specific global repair operator is designed. The operator can be embedded in any search-based method for CARP to make it more efficient.From the viewpoint of the whole framework, the memetic algorithm (MA) has been demonstrated to achieve much success in many other computationally expensive real-world oriented, discrete and combinatorial optimization problems. It can be seen as a hybridization of genetic algorithm and local search. Due to the high selection pressure imposed by the employed local search, MA is able to find good solutions much faster than traditional EAs. When applied to CARP, we find that traditional local search (that is carried out by traditional small-step move operators) still cannot exploit the promis-ing areas efficiently and the solutions are faced with the risk of being stuck in local optima. For this reason, we propose a MA with extended neighborhood search to help such solutions jump from the current local optimum to another better local optimum. This algorithm has been demonstrated to be able to obtain much better solutions than the current state-of-the-art algorithms, although it needs more computational effort.Further, two complicated extensions of CARP are studied:the periodic CARP (PCARP) and the multi-objective CARP (MO-CARP). PCARP is an extension of CARP from single-period to multi-period, and introduces a new primary objective that is to minimize the number of vehicles used over the time horizon. The only objective of CARP, on the other hand, becomes the secondary objective. Observing that the pri-mary objective is quite insensitive to the traditional search operators, we propose an algorithm that tackles the two objectives separately. To be specific, a specifically de-signed operator is applied to optimize the primary objective of a solution before local search is called to it. The empirical results show that when solving the problems with some objectives insensitive to the search operators, it is better to optimize them sepa- rately from other sensitive objectives.MO-CARP is a quite challenging problem since it has the difficulties caused by both multi-objective problems and combinatorial optimization problems. By evaluating the existing strategies to address the evolutionary multi-objective optimization (EMO) issues in the context of MO-CARP, we combine the advantages of both the compet-itive approaches for single-objective CARP and the EMO strategies together to solve MO-CARP. Such combination has been verified to outperform both simply extending a CARP approach and directly using an existing MOEA.Finally, the uncertain CARP is investigated. So far, most of research work in solv-ing CARP are focused on its static version, in which the problem parameters, including the demands of tasks and the traversing costs between vertices, are fixed and known a priori. However, in many real-world applications, the exact value of them are not known, and one can only assume them to be in a certain range of value. In such a scenario, the objective is no longer to find the best solution in a single environment, but a robust solution over all the possible environments. In our investigation, a robustness measure of a CARP solution is defined in consideration of the practical requirements. Test instances are also generated by extending the existing static CARP benchmark instances.