Metaheuristics for the Asymmetric Hamiltonian Path Problem

Abstract

One of the most important applications of the Asymmetric Hamiltonian Path Problem is in scheduling. In this paper we describe a variant of this problem, and develop both a mathematical programming formulation and simple metaheuristics for solving it. The formulation is based on a transformation of the input data, in such a way that a standard mathematical programming model for the Asymmetric Travelling Salesman Problem can be used on this slightly di erent problem. Two standard metaheuristics for the asymmetric travelling salesman are proposed and analysed on this variant: repeated random construction followed by local search with the 3-Exchange neighbourhood, and iterated local search based on the same neighbourhood and on a 4-Exchange perturbation. The computational results obtained show the interest and the complementary merits of using a mixed-integer programming solver and an approximative method for the solution of this problem.