Solving an Open k-city Travelling Salesman Problem with Ordered Constraint: An Exact Lexi-search Algorithm

Abstract

Thetravelling salesman problem (TSP) with the usual closed-loop setup has been extensively considered. However, TSP with open-loop variant arises in several real-time transportationmodels but has been given very limited attention. This paper addresses anopen k-city travelling salesman problem with ordered constraint (kOTSPO), a variant of an openTSP in which the salesman need not return to the home city, enough to traverse k out of n cities and certain cities should be visited in the predetermined order. Although a wide variety of solution techniques for solving TSP and its variants are available in the literature, most of them are heuristic or meta-heuristic algorithmsdue to their NP-hard nature. Thus, very less consideration has been attained for the exact algorithms. This paper develops an exact Lexi-search algorithm (LSA) that effectively enumerates the feasible solutions and the exact solution can be obtained systematically.As there is no existing study on the current model, no comparative results are reported. A numerical example is also illustrated in the provision of the theory.