Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2302.06582 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916309954985984 |
|---|---|
| author | Goutham, Mithun Menon, Meghna Garrow, Sarah Stockar, Stephanie |
| author_facet | Goutham, Mithun Menon, Meghna Garrow, Sarah Stockar, Stephanie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06582 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP Goutham, Mithun Menon, Meghna Garrow, Sarah Stockar, Stephanie Artificial Intelligence Systems and Control 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. |
| title | A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP |
| topic | Artificial Intelligence Systems and Control |
| url | https://arxiv.org/abs/2302.06582 |