# A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems
## 1 Introduction
This method is the famous Clarke and Wright Saving (CWS) method mentioned earlier. [PERSON] et al. adopted CWS to solve single VRP, however, we decomposed the VRP into several Travelling Salesman Problems (TSPs) [11] and solved them respectively using CWS. For the TSP, the CWS released the vehicle capacity restriction, which can be performed easily and get near-optimal results quickly. [PERSON] and [PERSON] [12] presented a survey of genetic algorithms that are designed for solving MDVRP. Besides providing an up-to-date overview of the research that focuses on different genetic approaches, methods, and operators used in selection, crossover, and mutation, the results of a thorough experiment are presented and discussed, which evaluated the efficiency of different existing genetic methods on standard benchmark problems in detail. The specific methods, operators and settings are presented to help researchers and practitioners to optimize their solutions in further studies. Most of the papers adopted the local search algorithm. The local search algorithm is improved from the hill-climbing algorithm. The local search algorithm is simply a greedy search algorithm, which selects the best neighbor from the neighborhood of the current solution as the current solution of the next iteration until a local optimal solution is reached. [PERSON] et al. [13] employed two biased-randomized processes that relied on the use of the geometric probability distribution at different stages of the iterated local search (ILS) framework to solve MDVRP. The first process is assigning customers to depots using a randomized priority criterion and another is improving routing solutions associated with a \"promising\" allocation map. It is relatively easy to implement and can be parallelized in a very natural way. [PERSON] et al. [14] solved the MDVRP with simultaneous deliveries and pickups (MDVRPSDP) and put an adaptive neighborhood selection mechanism that employs a scoring rule into the improvement steps and the perturbation steps of iterated local search, respectively. They also proposed new perturbation operators to diversify the search. [PERSON] [15] devised a variable neighborhood search algorithm to solve the deterministic MDVRP model to facilitate humanitarian logistics operations. [PERSON] and [PERSON] [16] developed a hybrid algorithm composed of an adaptive large neighborhood search and variable neighborhood search to solve this problem in which the cargo space of each vehicle has multiple compartments, and each compartment is dedicated to a single type of product. [PERSON] et al. [17] combined a genetic algorithm with neighborhood selection mechanisms to manage diversity for a large class of vehicle routing problems with time-windows. The traditional MDVRP has often been studied mainly with a focus on economic benefits. In recent years, the growing concern about the effects of pollutions has forced researchers to address the socio-environmental concerns. [PERSON] et al. [18] considered minimizing the total transportation risk as to the objective function and proposed a fuzzy bilevel programming model to solve the problem of transporting hazardous materials from multiple depots to customers. They introduced a numerical, integration-based fuzzy simulation method combined with four heuristic algorithms (hybrid particle swarm optimization, genetic algorithm, ant colony algorithm, and simulated annealing algorithm) to find the optimal solutions assigning customers to depots and determining the best paths regarding each group of depots and customers. Illustrative examples showed the good performance of the proposed model and the four heuristics. [PERSON] et al. [19] proposed a cooperative coevolutionary algorithm which decomposed the MDVRP into some subproblems, that is, single depot VRPs which evolve separately. However, the quality of a solution depends on a good complete solution formed by one solution obtained by an individual cooperated with partial solutions from other populations.