# A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems
## 1 Introduction  
As people's living standards are improving increasingly, urban household and solid waste are also increasing greatly, which puts forward higher requirements for waste collection, transportation, and management. It also makes it difficult to collect, classify, transport and dispose of waste. Improper disposal can affect the urban landscape, occupy the land, pollute soil, pollute groundwater resources, affect air quality, spread diseases and affect environmental health and the health of residents. The cost of collecting and transporting urban household waste accounts for a large proportion of the total cost of the waste disposal system. Our primary task is to solve waste collection problems. It is of great practical significance to analyze and study the path optimization of automatic collection and vehicles for reducing waste disposal costs and increasing waste disposal speed. The vehicle routing problem (VRP) has been an open problem and the front of operational research and combinatorial optimization. As a variation of VRP, the multi-depot vehicle routing problem (MDVRP) has also attracted more attention from scholars. The MDVRP problem is to allocate customers with the demand to each depot under the condition that the supply of each depot is not be exceeded and arrange the order in which customers are visited by vehicles. The objective function is to minimize the total route length and the number of vehicles. Many heuristic algorithms have been applied to MDVRP. Heuristic algorithms are grouped in two as classical heuristics and modern metaheuristics. Since results obtained by heuristic algorithms are good in large scale problems, metaheuristic algorithms are used mostly in literature for types of the MDVRP. Ant colony optimization (ACO) is a relatively new optimization method proposed by [PERSON] et al. [1]. Ant Colony Optimization algorithms, inspired by the phenomenon that ants would find the closet route to search for food, which belongs to the class of metaheuristics, are used exhaustively in the literature for MDVRP and its variants. ACO includes many algorithms which are many diverse variants of the basic principle. [PERSON] and [PERSON] [2] proposed an approach based on ACO to solve MDVRP. [PERSON] et al. [3] presented a parallel improved ACO with a coarse-grain parallel strategy, ant-weight strategy and mutation operation for MDVRP. [PERSON] [4] dealt with the modified MDVRP (M-MDVRP) which altered the optimization criterion. The optimization criterion of the standard MDVRP is to minimize the total sum of routes of all vehicles, whereas the criterion of M-MDVRP is to minimize the longest route of all vehicles, i.e., the time traveled by the vehicle is as short as possible. For this problem, they also developed a metaheuristic algorithm based on the Ant Colony Optimization theory to solve the classic MDVRP instances--this has been modified and adapted for M-MDVRP. They also proposed an additional deterministic optimization process which further enhances the original ACO algorithm. They used [PERSON]'s benchmark instances to evaluate results. Some articles [5; 6; 7] adopted ACO to solve the variants of MDVRP, such as MDVRP with multiple objectives and MDVRP with time windows. The genetic algorithm also belongs to a class of metaheuristics. [PERSON] et al. [8] developed two hybrid genetic algorithms (HGAs). In HGA1, the initialization procedure is conducted randomly. HGA2 incorporated the Clarke and Wright saving method and the nearest heuristic neighbor to generate initial solutions. Based on a computational study, they compared the performance of the algorithms with different problem sizes. It is proven that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time. [PERSON] and [PERSON] [9] adopted a phased aggregation strategy to solve the VRP with the homogeneous trucks. [PERSON] and [PERSON] [10] considered multiple truck capacity as a further formulation. They proposed a saving method which may be readily performed and very fast in a computer application.