Mir Mohammad Alipour

The Vehicle Routing Problem (VRP) is a class of well-known combinatorial optimization problems. The great interest in the VRP is due to its practical importance, as well as the difficulty in solving it. The Capacitated Vehicle Routing Problem (CVRP) is the most common variant of the VRP. Most of the approaches that have been developed to solve this problem tend to solve the problem in a centralized way. There has been very little research done into solving this problem in a distributed manner. In this paper, we propose an innovative approach for solving CVRP in a distributed manner based on multi-agent systems and using the game theory, which consists of three types of intelligent agents: customer agent, vehicle agent, and depot agent and includes the two phases: cluster construction and clusters optimization. The cluster construction phase consists of playing a Game Theoretic Clustering Algorithm by customer agents to divide the customers into several clusters, each consisting of a cluster head and several member customers. Then, we present a Game Theoretic Clusters Optimization Algorithm for the cluster optimization phase, which is played by vehicle agents to minimize the cost of each vehicle’s route to optimize the quality of the solution. The performance of the proposed approach is evaluated on 48 instances from 10 standard benchmark sets and compared with some state-of-the-art methods in terms of execution time and quality of solutions. Our experiments illustrated that the proposed method can compete or even outperform much more complex algorithms.