23
$\begingroup$

I want to solve the Asymmetric TSP for a large-scale problem for an industrial application where the company cannot buy a commercial software license. For their applications, it is very important to find good solutions within a short computation time. What are the main algorithms (either approximation, randomized, heuristic, dynamic programming, etc.) that are able to find good solutions as fast as possible? And, the same problem arises for the vehicle routing problem.

Although metaheuristic algorithms are powerful algorithms, they are not guaranteed to find good solutions and they may converge to different solutions in each replication of the algorithm.

Improve this question
$\endgroup$
7
  • $\begingroup$ There are many powerful metaheuristics described in the literature (see, e.g., sciencedirect.com/science/article/pii/S037722171300800X). I somehow thought that the source code related to this article was open source, but it was not. You could, however, replicate it, but that is quite an effort. $\endgroup$
    – Albert Schrotenboer
    Commented May 31, 2019 at 9:24
  • $\begingroup$ @AlbertSchrotenboer Thanks. But because metaheuristic algorithms do not necessarily converge to the same solutions in each replication, it might raise some concern about the developed software. $\endgroup$
    – Amin
    Commented May 31, 2019 at 9:50
  • 2
    $\begingroup$ Amin, one way to eliminate that random behaviour is to fix the seed while running replications, so that 'the same' random behaviour is observed. Or, alternatively, you could use deterministic metaheuristics such as Variable Neighborhood Descent which will converge to the same solutions. $\endgroup$
    – Albert Schrotenboer
    Commented May 31, 2019 at 9:56
  • 5
    $\begingroup$ You could also try the google-or tools that feature a TSP (developers.google.com/optimization/routing/tsp) module and some VRP (developers.google.com/optimization/routing/vrp) extensions. It has an Apache 2.0 license that allows commercial use. $\endgroup$
    – JakobS
    Commented May 31, 2019 at 10:12
  • $\begingroup$ Thank you all. I missed the point to use the same seed in metaheuristic algorithms. $\endgroup$
    – Amin
    Commented May 31, 2019 at 10:17

5 Answers 5

Reset to default
19
$\begingroup$

If you are interested in solving the TSP, the Concorde TSP solver is a very powerful and easy-to-use tool. I do not know what the licensing options are for commercial applications, but for research purposes it is free and easy to use (if you are familiar with C/C++)

Improve this answer
$\endgroup$
3
  • $\begingroup$ @alberSchrotenboer Thank you so much. I have not tried this solver. I am actually familiar with C# and I use this programming language. Does it support C#? $\endgroup$
    – Amin
    Commented May 31, 2019 at 10:13
  • $\begingroup$ I really don't know. $\endgroup$
    – Albert Schrotenboer
    Commented May 31, 2019 at 10:58
  • 2
    $\begingroup$ As Concorde is written in C, you can use the following approach to call the library in C# stackoverflow.com/questions/11425202/… $\endgroup$
    – JakobS
    Commented May 31, 2019 at 11:07
17
$\begingroup$

If you cannot use Concorde as suggested by Albert, I'd suggest you look for an implementation of the Lin-Kerninghan-Heuristic (which is also included in Concorde). It iterates between 2-opt and 3-opt to find a good solution quickly. If you are interested in the best solution or need to know a bound on the best possible solution, then Concorde is the way to go. Gurobi also has an example code that solves the problem (but is only free for academic purposes).

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ Helsgaun's implementation is possibly the best-known one. $\endgroup$
    – Alberto Santini
    Commented May 31, 2019 at 10:07
  • $\begingroup$ @JakobS. Thanks. I edited my question. I actually want to solve an ATSP. Is this algorithm a good choice for ATSP? $\endgroup$
    – Amin
    Commented May 31, 2019 at 10:15
  • 2
    $\begingroup$ Yes, see for example here akira.ruc.dk/~keld/research/LKH/Soler_results.html $\endgroup$
    – JakobS
    Commented May 31, 2019 at 10:17
  • 1
    $\begingroup$ One might want to add that Helsgaun's implementation is licensed for usage only in an academic or non-commercial environment. $\endgroup$
    – JakobS
    Commented May 31, 2019 at 10:18
9
$\begingroup$

You could also give a try to VROOM, which can be used for commercial use. It can solve TSP and some variants of the VRP such as VRPTW and CVRP.

Here is the API documentation : https://github.com/VROOM-Project/vroom/blob/master/docs/API.md

What you can is to start with the demo server to see if it can fit on small instances and then install it to use it as an API or integrate it as a library.

Improve this answer
$\endgroup$
5
$\begingroup$

Just a (maybe obvious) remark: by doubling the number of nodes you can transform any ATSP instance into an STSP one, so you can use Concorde or any other STSP exact/heuristic code.

Improve this answer
$\endgroup$
1
$\begingroup$

If you are interested to develop an optimization model (specifically MIP), based on your specific problem and also you would like to solve your problem using the commercial solvers to obtain the optimal solution, you could try writing your model in an algebraic modelling language like AMPL or GAMS and feeding that into the NEOS server which contains many open-source and commercial solvers like CPLEX, GUROBI, CBC and ..., Then get the solution.

AFAIK, the NEOS have had some useful APIs which can be connected to the other programming languages and optimization software.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.