  The convex hull cheapest insertion heuristic produces good solutions to the
Euclidean Traveling Salesperson Problem, but it has never been extended to the
non-Euclidean problem. This paper uses multidimensional scaling to first
project the points from a non-Euclidean space into a Euclidean space, enabling
the generation of a convex hull that initializes the algorithm. To evaluate the
proposed algorithm, non-Euclidean spaces are created by adding separators to
the TSPLIB data-set, or by using the L1 norm as a metric.
