CycleExpander to construct Directed Hamiltonian Circuit HexCycleSpanner to tighten Directed Hamiltonian Circuit

Abstract

HexCycleSpanner (HCS) is a novel tool designed to achieve an elementary cycle refinement operation (ECRO) that is used to tighten a Directed Hamiltonian Circuit (dHC) - to be used iteratively as an extremely powerful technique to transform any given dHC to an optimum Shortest Directed Hamiltonian Circuit.  Application to solving Asymmetric Travelling Salesman Problem (aTSP) is quite evident.  ECRO uses a HCS to achieve an exchange of an outgoing arc-triplet of the given dHC with a corresponding incoming arc-triplet from outside the given dHC, thus resulting in a reconstructed transformed permuted dHC, while retaining the original direction/orientation of the given dHC.  Effectively, the removal of the outgoing arc-triplet separates the given dHC into three cut-segments that are again rejoined by the incoming arc-triplet resulting in the reconstructed transformed permuted dHC wherein the original orientation of the dHC is retained - as defined by the orientation of the three cut-segments.  This ECRO is analogous to the simplex pivot operation of Linear Programming wherein an exchange of the outgoing basic variable row with the incoming nonbasic variable column is performed to transform a given simplex tableaux representation into another equivalent simplex tableau representation that may be closer to the optimum tableaux.

The concept of HexCycleSpanner can be generalized and extended to include incoming directed paths rather than incoming arcs to give rise to what may be called a CycleExpander (CyclExp) that may be used as an effective tool to construct a Directed Hamiltonian Circuit.

The absence of a ‘global effectiveness measure’ (‘gem’) for aTSP - unlike in the case of LP - requires one to use a reference data base of optimum/shortest directed path between pairs of nodes to enhance the computational efficiency of the proposed iterative ECRO algorithm.