The Maximum Scatter TSP on a Regular Grid

Isabella Hoffmann (), Sascha Kurz () and Jörg Rambau ()
Additional contact information
Isabella Hoffmann: Universität Bayreuth
Sascha Kurz: Universität Bayreuth
Jörg Rambau: Universität Bayreuth

A chapter in Operations Research Proceedings 2015, 2017, pp 63-70 from Springer

Abstract: Abstract In the Maximum Scatter Traveling Salesman Problem the objective is to find a tour that maximizes the shortest distance between any two consecutive nodes. This model can be applied to manufacturing processes, particularly laser melting processes. We extend an algorithm by Arkin et al. that yields optimal solutions for nodes on a line to a regular ( $$m \times n$$ )-grid. The new algorithm $$\textsc {Weave}(m,n)$$ takes linear time to compute an optimal tour in some cases. It is asymptotically optimal and a ( $$\frac{\sqrt{10}}{5}$$ )-approximation for the ( $$3\times 4$$ )-grid, which is the worst case.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-42902-1_9

Ordering information: This item can be ordered from
http://www.springer.com/9783319429021

DOI: 10.1007/978-3-319-42902-1_9

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().