Related Work

The TSPFN was studied in the two dimensional (2D) and three dimensional (3D) case. 

First the smallest reasonable neighborhoods, i.e., radius 0, 1, square root of 2, and 2, were studied and the following papers were published:

A. Fischer and P. Hungerländer.

The Traveling Salesman Problem on Grids with Forbidden Neighborhoods.

Journal of Combinatorial Optimization, accepted, 2017.

Preprint available from: http://www.optimization-online.org/DB_HTML/2016/04/5412.html.

 

M. Firstein, A. Fischer, and P. Hungerländer.

Closed almost knight's tours on 2d and 3d chessboards.

In Operations Research Proceedings 2017, 2017. Accepted.

Preprint available from: http://www.optimization-online.org/DB_HTML/2017/08/6152.html.

 

Later the work was continued by Anna Jellen, who implemented the visualization, for more information have a look here.

In 2018 Anna Jellen finished her Master Thesis with the Title "The Traveling Salesperson Problem on Regular 3D Grids", for which she won the ÖGOR Preis 2018. Also a related proceedings paper was published.

A. Fischer, P. Hungerländer, and A. Jellen.

The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 3D Grids.

Operations Research Proceedings 2017, accepted.

Preprint available from: http://www.optimization-online.org/DB_HTML/2017/08/6151.html.

 

Other related work in 2018:

P. Hungerländer, A. Jellen, S. Jessenitschnig, L. Knoblinger, M. Lackenbucher, and K. Maier.

The Multiple Traveling Salesperson Problem on Regular Grids.

Operations Research Proceedings 2018, submitted.

Preprint available from: http://www.optimization-online.org/DB_HTML/2018/08/6775.html.

 

P. Armbrust, P. Hungerländer, and A. Jellen.

A Heuristic for the Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 2D and 3D Grids.

Operations Research Proceedings 2018, submitted.

Preprint available from: http://www.optimization-online.org/DB_HTML/2018/09/6811.html.

Presentations

The TSPFN is a variant of the well known Traveling Salesperson Problem, a new and interesting problem that was also presented at several conferences.

 

  • Dec 2017: A Heuristic for the Traveling Salesperson Problem with Forbidden Neighborhoods on Regular Grids. 5th Alpen-Adria-Workshop on Optimization, Klagenfurt, Austria.
  • Sep 2017: The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 2D and 3D Grids. OR2017: International Conference on Operations Research, Berlin, Germany.
  • May 2017: Approaches for Three-Dimensional Traveling Salesperson Problem with Forbidden Neighborhoods. EURO/ORSC/ECCO Conference 2017 on Combinatorial Optimization, Koper, Slovenia.
  • Feb 2017: The Traveling Salesperson Problem with Forbidden Neighborhoods on 3D Grids. Institute of Statistic and Optimization and Discrete Mathematics, Graz University of Technology, Austria.
  • Dec 2016: The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 2D and 3D Grids. 4th Alpen-Adria-Workshop on Optimization, Klagenfurt, Austria.
  • Nov 2016: The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 2D and 3D Grids. ISOR-Colloquium, University of Vienna, Austria.
  • May 2016: The Traveling Salesperson Problem with Forbidden Neighborhoods. ECCO Conference 2016 on Combinatorial Optimization, Budapest, Hungary.