Reoptimizing the traveling salesman problem | Zendy

Archetti Claudia | Zendy; Bertazzi Luca | Zendy; Speranza M. Grazia | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Reoptimizing the traveling salesman problem

Author(s) -

Archetti Claudia,

Bertazzi Luca,

Speranza M. Grazia

Publication year - 2003

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.10091

Subject(s) - travelling salesman problem , node (physics) , heuristic , mathematical optimization , constant (computer programming) , computer science , mathematics , combinatorics , engineering , structural engineering , programming language

In this paper, we study the reoptimization problems which arise when a new node is added to an optimal solution of a traveling salesman problem (TSP) instance or when a node is removed. We show that both reoptimization problems are NP‐hard. Moreover, we show that, while the cheapest insertion heuristic has a tight worst‐case ratio equal to 2 when applied to a TSP instance, it guarantees, in linear time, a tight worst‐case ratio equal to 3/2 when used to add the new node and that also the simplest heuristic to remove a node from the optimal tour guarantees a tight ratio equal to 3/2 in constant time. © 2003 Wiley Periodicals, Inc.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research