Pareto-Based Hybrid Algorithms for the Bicriteria Asymmetric Travelling Salesman Problem

摘要

We consider the bicriteria asymmetric travelling salesman problem (bi-ATSP): Given a complete directed graph where each arc is associated to a couple of positive weights, the aim is to find the Pareto set, consisting of all non-dominated Hamiltonian circuits. We propose new hybrid algorithms for the bi-ATSP using the adjacency-based representation of solutions and the operators that use the Pareto relation. Our algorithms are based on local search and evolutionary methods. The local search combines principles of the well-known Pareto Local Search procedures and Variable Neighborhood Search approach, realizing the search in width and depth. A genetic algorithm with NSGA-II scheme is applied to improve and extend a set of Pareto local optima by means of evolutionary processes. The experimental evaluation shows applicability of the algorithms to various structures of the bi-ATSP instances generated randomly and constructed from benchmark asymmetric instances with single objective.