Solved

Nearest neighbors for TSP

  • 31 May 2019
  • 2 replies
  • 183 views

Hi there,

I am trying to implement some form of heuristic for the TSP where I'm decreasing the size of the model by restricting the declaration of variables X(i,j) to those combination (i,j) for which j belong to the, say, 10 cities nearest to i. Here X(i,j) is an binary variable indicating whether or not edge (i,j) is in the tour.

I created a subset of the cities to find the nearest neighbors of city i, but how can I implement it in the model? Do I need to add an extra constraint or?

Added you'll find the code of my AIMMS project.
Thanks in advance!
icon

Best answer by mohansx 31 May 2019, 20:56

View original

This topic has been closed for comments

2 replies

Userlevel 5
Badge +5
@mennovaneersel

You will make the index domain of X(i, j) as

X(i, j) | j in NearestNeighbors(i)

That will create only those combinations of (i, j) where j is a nearest neighbor of the node i.
Userlevel 5
Badge +2
Hi, @mennovaneersel.

Aimms provides a TSP approach based on adding lazy constraints to avoid subtours.

https://github.com/aimms/examples/tree/master/Application%20Examples/Traveling%20Salesman

Hope it helps.

Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator