Time taken to solve depends on the ordering of vehicle capacity?

[Aniket Sharma]

I have tried to create a CVRPTW solution by combining CVRP and VRPTW from examples provided in the official documentation.

Since the code is big I cannot paste it here, so I am sharing a colab notebook demonstrating a short example reproducing the problem: https://colab.research.google.com/drive/1YN-6kABqGqSkQKxOtWD6YA2ZDlP8RfqD?usp=sharing

The quantities to deliver at each node are [0, 80, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1]

I have 22 vehicles, 21 vehicles with capacity 25 and 1 vehicle with capacity 600. If the vehicles are sorted in ascending order the example with 14 nodes take more than 200 seconds to solve and if they are sorted in descending order the same example gets solved in less than a second.

I am using Google OR Tools for the first time so I don't know if this was expected or not. I have tried adding Guided Local Search also but when I add a time limit to stop it stops without giving a solution.

I created an issue in the repo but it was converted to a Discussion.

https://github.com/google/or-tools/discussions/2554

I have also asked this question in Stack Overflow.

https://stackoverflow.com/q/67570171/8550821

[Laurent Perron]

I have answered an S.O. 

You can try different first solution heuristics.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
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/5fc578ba-8176-4699-9da1-de0670949446n%40googlegroups.com.

[Aniket Sharma]

Sure, I will try using different first solutions and post the result here again.

I am new to this mailing list so sorry but can you tell me the full form of S.O.?

[Mizux Seiha]

S.O. stands for Stack Overflow and Laurent answer -> https://stackoverflow.com/a/67573346/5710233

[Aniket Sharma]

Thanks, Laurent for your help.

It works properly when using SAVINGS, PARALLEL_CHEAPEST_INSERTION, and LOCAL_CHEAPEST_INSERTION.