An interactive memetic algorithm for production and manufacturing problems modelled as a multi-objective travelling salesman problem

Abstract

In this paper, a preference-based, interactive memetic random-key genetic algorithm (PIMRKGA) is developed and used to find (weakly) Pareto optimal solutions to manufacturing and production problems that can be modelled as a symmetric multi-objective travelling salesman problem. Since there are a large number of solutions to these kinds of problems, to reduce the computational effort and to provide more desirable and meaningful solutions to the decision maker, this research focuses on using interactive input from the user to explore the most desirable parts of the efficient frontier instead of trying to reproduce the entire frontier. Here, users define their preferences by selecting among five classes of objective functions and by specifying weighting coefficients, bounds, and optional upper bounds on indifference tradeoffs. This structure is married with the memetic algorithm – a random-key genetic algorithm hybridised by local search. The resulting methodology is an iterative process that continues until the decision maker is satisfied with the solution. The paper concludes with case studies utilising different scenarios to illustrate possible manufacturing and production related implementations of the methodology.

Keywords:

• multi-criterion decision making
• genetic algorithms
• Pareto optimisation
• metaheuristics
• interactive computing
• travelling salesman problems