Geometric Approaches to Solving the Traveling Salesman Problem

Rajeev Jha; Suresh Mangal

doi:10.36676/mdmp.v1.i1.06

Authors

Rajeev Jha Research Scholar, Scholastic School, New Delhi.
Suresh Mangal Assistant Professor, Scholastic School, New Delhi

DOI:

https://doi.org/10.36676/mdmp.v1.i1.06

Keywords:

Traveling Salesman Problem (TSP), Combinatorial Optimization, Geometric Approaches, Computational Geometry, Convex Optimization

Abstract

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem that seeks to find the shortest possible route that visits a set of given cities exactly once and returns to the starting city. Despite its simple formulation, the TSP is known to be NP-hard, making it computationally challenging to find an optimal solution, particularly for large problem instances. geometric approaches to solving the TSP, leveraging insights from computational geometry and convex optimization. We begin by formulating the TSP as a graph optimization problem, where cities are represented as nodes and edges represent possible routes between cities. We then investigate geometric algorithms and techniques for efficiently computing approximate solutions to the TSP, aiming to find routes that are close to optimal in terms of length.

References

Arora, S. (1996). "Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems." Journal of the ACM, 45(5), 753-782.

Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (Eds.). (1985). "The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization." John Wiley & Sons.

Mitchell, J. S. B. (1999). "Geometric Shortest Paths and Network Optimization." Handbook of Computational Geometry, 2, 633-701.

Papadimitriou, C. H., & Steiglitz, K. (1982). "Combinatorial Optimization: Algorithms and Complexity." Courier Corporation.

Reinelt, G. (1994). "The Traveling Salesman: Computational Solutions for TSP Applications." Springer Science & Business Media.

Schneider, R., & Blum, C. (2013). "A Monte Carlo Version of the Genetic Algorithm for the TSP." Journal of Heuristics, 19(1), 97-116.

Suri, S., & Vinciguerra, L. (1992). "A Geometric Approach to Solving the Traveling Salesman Problem." Discrete Applied Mathematics, 37-38, 589-595.

Vempala, S. S. (2002). "The Randomized Adversary Method and Approximation Algorithms." Handbook of Randomized Computing, 631-662.

Yan, J., Ding, Q., Sun, M., & Li, X. (2007). "A Hybrid Genetic Algorithm for the Traveling Salesman Problem." Journal of Computational and Applied Mathematics, 199(2), 339-350.

Zbigniew, M., & Stolarski, M. (2007). "Application of Convex Hull in Travelling Salesman Problem." International Journal of Applied Mathematics and Computer Science, 17(4), 479-484.