Pareto mimic algorithm: An approach to the team orienteering problem. (June 2016)

• Record Type: Journal Article
• Authors: Ke, Liangjun; Zhai, Laipeng; Li, Jing; Chan, Felix T.S.
• Is Part Of: Omega. Volume 61(2016)
• Page Start: 155
• Page End: 166
• Publication Date: 2016-06
• Subjects: Vehicle scheduling -- Vehicle routing problem -- Team orienteering problem -- Pareto dominance; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2015.08.003
• Languages: English
• ISSNs: 0305-0483

Abstract

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.