A new efficient and effective golden-ball-based technique for the capacitated vehicle routing problem

摘要

The Golden Ball (GB) algorithm is a relatively new meta-heuristic algorithm which can be used to solve the capacitated vehicle routing problem (CVRP). However, its application to solving that problem is still limited. This paper introduces a new technique based on the GB algorithm for solving the CVRP. Our proposed approach employs the solution representation in different way from the original one. More specifically, in this work, the team represents the CVRP solution and the players the routes in the team, while, in the previous work, the CVRP solution is modeled by a player. In the training process, the solution quality of players and teams is improved by using intra-route and inter-route improvement algorithms. The computational results have shown that our technique is better than both best known algorithms and previous GB-based algorithms in terms of efficiency and effectiveness.