Pareto mimic algorithm: An approach to the team orienteering problem. (June 2016) - Ke, Liangjun; Zhai, Laipeng; Li, Jing; Chan, Felix T.S.
Abstract: The team orienteering problem is an important variant of the vehicle routing problem. In this paper, a new algorithm, called Pareto mimic algorithm, is proposed to deal with it. This algorithm maintains a population of incumbent solutions which are updated using Pareto dominance. It uses a new operator, called mimic operator, to generate a new solution by imitating an incumbent solution. Furthermore, to improve the quality of a solution, it employs an operator, called swallow operator which attempts to swallow (or insert) an infeasible node and then repair the resulting infeasible solution. A comparative study supports the effectiveness of the proposed algorithm, especially, our algorithm can quickly find new better results for several large-scale instances. We also demonstrate that Pareto mimic algorithm can be generalized to solve other routing problems, e.g., the capacitated vehicle routing problem. Abstract : Highlights: A mimic operator is proposed for generating new solutions. A Pareto dominance based rule is proposed to select new incumbent solutions. A swallow operator is proposed to improve a solution. Our algorithm is fast and effective in contrast to the algorithms in the literature.