تقرير
A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP
| العنوان: | A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP |
|---|---|
| المؤلفون: | Goutham, Mithun, Menon, Meghna, Garrow, Sarah, Stockar, Stephanie |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Artificial Intelligence, Electrical Engineering and Systems Science - 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. Comment: Revised manuscript submitted on 2 July 2024 to the Operations Research Letters |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2302.06582 |
| رقم الأكسشن: | edsarx.2302.06582 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |