Open main menu

A.F.C algorithm

The most efficient algorithm for T.S.P

Five years of R&D resulted in this fully functionnal polynomial approximation for the Traveller Salesman Problem. With a 10% average deviation from optimal tour and a N.Log(N) complexity, this algorithmic solution is the most efficient known solution for this famous NP-Hard problem.

Following are :

- a live demo to see the algorithm at work. You can run this demo both with randomly generated problems or with known TSP problems provided in tsplib format.

- some benchmarks performed both with random problems and known TSP problem.

Contact the author for any inquiry.

Try the live demo:

Create or load new problem

IMPORTANT : Please reload this page to ensure curent problem is flushed from session


Load from TSP url :
(URL's and optimal tours can be found here or here)

 

Benchmarks

TSP benchmarks

TSP benchmarks

 

ASP versus 22 classic heuristics.
See Investigating TSP Heuristics for Location-Based Services for more details.

 

Tour computed by A.F.C in 15,2 sec, for "pcb3038 : Drilling problem (Junger/Reinelt)"

pcb3038
COMMENT : Drilling problem (Junger/Reinelt)