Meta-heuristic Algorithms for Solving the Multi-Depot Vehicle Routing Problem

摘要

Multi-depot Vehicle Routing Problem is one of the most important and challenging variations of the classical Vehicle Routing Problem, where the goal is to find the routes for a fleet of vehicles to serve a number of customers, travelling from and to several depots. Due to the complexity of solving such problems, meta-heuristic algorithms are used. The Most Valuable Player algorithm is a recent technique used to solve continuous optimization problems. This study uses the Genetic Algorithm and the Ant Colony Optimization to solve the Multi-Depot Vehicle Routing Problem. A Hybrid Most Valuable Player algorithm is also proposed to solve the multi-depot vehicle routing problem. The algorithm was tested on 10 different problems and compared to two well-known techniques, Genetic Algorithm and Ant Colony Optimization. Results of the developed algorithm were satisfactory for small sized problems, however Genetic Algorithm surpassed both other algorithms in most test cases.