A variable neighborhood search for the multi-depot vehicle routing problem with loading cost

摘要

The purpose of this paper is to propose a variable neighbourhood search (VNS) for solving the multi-depot vehicle routing problem with loading cost (MDVRPLC). The MDVRPLC is the combination of multi-depot vehicle routing problem (MDVRP) and vehicle routing problem with loading cost (VRPLC) which are both variations of the vehicle routing problem (VRP) and occur only rarely in the literature. In fact, an extensive literature search failed to find any literature related specifically to the MDVRPLC. The proposed VNS comprises three phases. First, a stochastic method is used for initial solution generation. Second, four operators are randomly selected to search neighbourhood solutions. Third, a criterion similar to simulated annealing (SA) is used for neighbourhood solution acceptance. The proposed VNS has been test on 23 MDVRP benchmark problems. The experimental results show that the proposed method provides an average 23.77% improvement in total transportation cost over the best known results based on minimizing transportation distance. The results show that the proposed method is efficient and effective in solving problems.