Improvement Heuristics for Asymmetric TSP

Question

i have been solving the Time-Dependent Traveling Salesman Problem using an Ant Colony Optimization. Upon reading the ACO papers, there are several reminders which state that ACO performs best with daemon actions - improvement heuristics.

In the classical TSP, the most common improvement heuristic used is the k-opt exchange, which works particularly well because one does not need to calculate the whole solution cost, but only differentials on the updated solution.

When the problem is assymetric (which is the case for the time-dependent variation), this is not the case.

I wonder if there are usefull improvement heuristics which can be used as daemon actions to the Assymetric/time-dependent TSP.

I already did some research on this subject, but found no interesting material.

Answer 1

I have the exact same doubt now, so, I found your question because I did a heavy research about this theme and didn't find any good direction yet. As you, I'm currently working on TSP and VRP variations and solving it by the Ant's Colony Optimization Method.

I have an instance of 16 cities to be visited, one origin and one destination, I optimized it using pure ant's algorithms and the best result I got was 557 km, by comparation the nearest neighboor algorithm found 586 km as a result, however, I notice that the ant's algorithms aren't precise, sometimes it returns a very bad result, better than the nearest neighboor though. But I wasn't satified with this drawback, and I started to read about heuristics (daemons actions) to be coupled with the ant's algorithms, then It is very interesting that all of them assume that we are working with a symmetric matrix, but real problems are hardly symmetric.

I first tried to apply the 2-opt heuristic, because I read that it is fast and give a good result, so it suits for a real application that an user waits to get the answer as fast as possible and as good as possible. But latter I saw that the step of 2-opt which reverses a path when exchange edges is guaranteed only when working with symmetric matrices...

Well, After all, I applied a very simple heuristic, that I don't know the name yet, but I saw some comments that it is not a good solution (because doesn't solve the crossed arcs problem and may create more of them), even though, it helps me to provide better solutions and also more precise, as an example, the instance I told about above, it gives the result of 554 km almost all the time.

The heuristic I applied does this job: After the ACO build a solution, I refine it by exchange cities (in other words, exchange vertex or nodes), if it improves the solution, I save this new solution and continue the process of exchanging cities, using the new solution constructed until I reach the solution's vector length.

For example, if I have the following path as a solution given by the ACO:

A -> B -> C -> D -> E -> F

the heuristic moves B ahead in the path, for example:

A - > C -> B...

then:

A -> D -> C -> B -> E -> F

if it finds a better solution, for example, let's suppose the above solution is an improvement, then it continues moving the city in the second position in the solution vector:

A - > E -> C -> B-> D-> F

Then, it starts the same procedure to the third position city...

I'd like to add that the solution which updates the pheromone matrix is the solution built by the ACO and improved by this heuristic.

As I experienced, the ACO does a pretty good job creating solutions with very few crossed arcs, because this the heuristic applied is working fine, and as we are working with asymmetric matrix I think that it is possible to crossed arcs being better paths than paths without any crossed arc... But It is just my feeling, actually, I analyzed the solutions above only by the value of route's length in kilometer, but I did not plot them yet to see how they look like.

Well, I hope to help you with these informations, and if you have find any nice heuristic to couple with the ACO as a daemon action, keep me posted!