Approximate Methods For Uncertain And Large Scale Capacitated Arc Routing Problems

The Capacitated Arc Routing Problem (CARP) is a classic combinatorial optimization problem that seeks an optimal set of routes to cover a certain subset of edges and/or arcs in a given network subject to some specific constraints. For its wide range of practical applications, such as salting route, urban waste collection, and product delivery, CARP has drawn considerable attentions in the past few decades and a large amount of problem models and algorithms have been proposed. However, most investigations of CARP (or extensions of CARP) are formulated as deterministic problems while practical applications of CARP are usually stochastic. Moreover, most of the existing algorithms are limited to relatively small scale CARPs. Hence, new researches need to be carried on to fill this gap between research works and practical applications.The first problem addressed in this thesis is called Uncertain CARP (UCARP), which is a new extention of traditional CARP. UCARP can be treated as a robust optimization problem that contains four stochastic factors:the demands of tasks, the costs of edges, the presence of tasks, and the presence of edgeds. And its primary aim is to find a robust solution under all possible environments. Compared to the deterministic variants of CARP, UCARP is much closer to practical applications. However, research on this direction is still in its infancy. There exist no viable solutions to UCARP in literature. Although random variables in a robust optimization problem are usually assumed to follow specific distributions, in many practical problems the distribudtions of random variables are unkwon in advance, but can only be estimated using a number of different scenarios that are collected in the real word. Hence, a direct way is to seek a robust solution for a sample of deterministic scenarios. Based on this consideration, in this thesis, an UCARP is defined as a set of deterministic CARPs (called samples).We first pick the expected performance as the robustness measure of UCARP and propose a Memetic Algorithm with Multiple Populations (MAMP) to solve it. In MAMP, each sample (a deterministic CARP) has its own population. In each generation, only one population is selected to be improved. By forcing the algorithm to find out an improved solution for the more difficult samples, the search process is more likely to focus on the overall performance instead of being trapped on the easier samples. Moreover, MAMP emplys a large step-size local search operator, i.e., the Merge-Split operator, to get rid of local optimum on a selected population. The experimental results show that MAMP is capable of finding solutions with better robustness than other algorithms. However, because of the time-consuming Merge-Split operator and fitness evaluation, MAMP suffers from a high computational cost.In addition to the expected performance, people may aslo concern about the worst-case performance. Hence, we propose an Estimation of Distribution Algorithm with Stochastic Local Search (EDASLS) to optimize the worst performance on all samples. EDASLS builds probabilistic models that learn the adjacency of tasks and uses these models to gerate new solutoins during the searching process. To address the issue that fitness evaluation takes too much computational time, the probabilistic models are also ultilized in the novel Stochastic Local Search to avoid excessive fitness evaluation. Experimental results show that EDASLS has the ability to achieve solutions with better robustness than the compared algorithms. It is also competitive with respect to the computational time. Given the same number of fitness evaluation, EDASLS requires a shorter computational time. Further experiments indicate that the superiority of EDASLS should be credit to the Stochastic Local Search we proposed.The other topic we studied in this thesis is the Large-Scale CARP (LSCARP). A LSCARP is essentially a CARP with large problem size. Because of its large problem size, the performance of existing algorithms clearly deteriorates on LSCARP instances. In this thesis, we propose a Scalable Approach based on Hierarchical Decomposition (SAHiD). When the problem size grows rapidly, SAHiD can still provide solutions with acceptable performance in a relatively shot time (e.g., half an hour). By decomposing and ordering all the tasks in a hierarchical way, SAHiD is able to generate a solution with good performance quickly. The hierarchical decomposition processes extremely short and thus can be embedded to an iterated search process to optimize the current solution continuously. In order to validate the efficiency and effectiveness of EDASLS, we generate two new benchmark test sets based on the real road network of Hefei and Beijing, China. Both test sets are one order of magnitude larger than the existing ones. SAHiD is compared with some state-of-the-art CARP solvers and a newly proposed LSCARP solver on the above sets. Experimental studies show that SAHiD is much more competitive than other compared algorithms with respect to both solution quality (obtained within a given time budget) and computational time (to achieve a pre-defined solution quality), especially on instances with more than 400 tasks, which existing algorithms cannot handle. Moreover, experimental results on the existing largest test sets show that SAHiD can be a better choice when the computational recource (time) is quite poor (e.g., just a few minutes or even seconds).