Large Traveling Salesman Problem

[Francesco B]

Hello, 

as part of an assignment I am trying to solve traveling salesman problems using or-tools. I am able to get solutions for all problem apart from the largest one, which has almost 34,000 nodes. The issue at the moment is that the solver doesn't give a solution even though I set time_limit.seconds = 60 (while it worked for smaller problems up to around 18,000 nodes). I attach the code and data the reproduce it.

I suspect the reason is that it is taking forever to compute the initial solution, since I had the same problem when I initially wrote my nearest neighbour heuristic. I overcame that by using a dedicated data structure instead of the full distance matrix (but the quality of the solution is not good enough...) 

If that is the case, would it be possible to import the initial solution and use or-tools solver only for the local search part? Otherwise do you see any other problem in the code, and possible improvements?

Many thanks in advance for all possible insights that you would be able to provide.

Francesco

[Francesco B]

EDIT: This code worked well for smaller problems up to 1,800 nodes, not 18,000 nodes as I originally wrote.

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/Xtm7peGRbXI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8251e795-5a7b-4f29-9ceb-b8012d94e4a5n%40googlegroups.com.

[blind.line]

Set time limit to 10 minutes? Or 10 hours?  There’s no reason to expect a solution in one minute. 

James

On Aug 28, 2022, at 10:57, Francesco B <francesco....@gmail.com> wrote:



You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAGueyY0B7vbroSuZj2VqosUpw%2BUkJDy3bUOYMC__6PgYZNCAwA%40mail.gmail.com.

[Francesco B]

In this case I wasn't expecting a good solution in 1 minute, yet "a solution" since I set 60 seconds time limit in the local search algorithm. As far as I understand a local search algorithm is supposed to stop after the time limit is reached. 

[blind.line]

For large problems, the required time can be quite large. The complexity rises exponentially and all that. 

Maybe partition your problem for an initial solution, then recombine and solve the big problem with a feasible starting point?

James

On Aug 29, 2022, at 05:03, Francesco B <francesco....@gmail.com> wrote:

In this case I wasn't expecting a good solution in 1 minute, yet "a solution" since I set 60 seconds time limit in the local search algorithm. As far as I understand a local search algorithm is supposed to stop after the time limit is reached. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1f682e77-76e1-4f13-9a73-31f9829b132dn%40googlegroups.com.

[Francesco B]

Yes, that would be great. I have optimized the nearest neighbor heuristic, and what I have currently takes around 2-3 minutes to produce an initial solution. Is it possible to use the path from my initial solution as a starting point for the local search in the RoutingModel? 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/DB23A105-F50A-4697-AFDE-010AB4824C56%40gmail.com.

[Mizux Seiha]

yes, basically you just need to call routing.ReadAssignmentFromRoutes(initial_routes, True)
beware, first you must setup your search parameter and pass it using `routing.CloseModelWithParameters(search_parameters)` (ed some search parameters will be ignored in the subsequent routing.SolveFromAssignmentWithParameters())

Here an example; initial route 1,2,3,4 (note; optional nodes i.e. part of a disjunction can be dropped here node 5,6)
https://gist.github.com/Mizux/0bd1daadc4e64130b62492c942f163d5#file-vrp_new_order-py-L139-L156

[Francesco B]

Hi,

many thanks for sharing all this information and the code! 

I tried it and it works for the smaller problems, I am able to get the same objective as without the external solution assignment. However, for the largest problem (33810 nodes) it doesn't return a solution after completing routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)

I have tried to increase the time_limit.seconds from 60 to 3600, but still it didn't change the result. I have also noticed that in the largest problem the command routing.CloseModelWithParameters(search_parameters) takes about 30 minutes to complete.

Any idea of what is happening?

Many thanks
Francesco

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/11c08284-d7d4-4fc1-9b6a-db1d383964dbn%40googlegroups.com.