Two algorithms for finding a minimal ratio Hamiltonian cycle in a network

Abstract

Two parametric algorithms with the support of subroutine NHORSH for finding a Hamiltonian cycle in a network, which minimizes the time-to-profit ratio, are presented in this paper. The difficulty of solving this problem is concerned with the problem of finding a shortest Hamiltonian cycle in a network which may have negative cycles. An subroutine Algorithm NHORSH has been established to cope with this problem. Validation of the algorithms and two illustrative examples are given. Computational experience is also reported.