CODEWITHSUNDEEP
pythonor-toolsvehicle-routing
aniketsharma00411
aniketsharma00411

Reputation: 35

Time taken to solve a Vehicle Routing Problem (CVRPTW) using Google OR Tools depends on the ordering of vehicle capacity

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 the official mailing list.

https://groups.google.com/g/or-tools-discuss/c/MHoMwkHQuoo

Upvotes: 2

Views: 1365

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11014

This is a well known property of OR solvers. Because they include lots of heuristics, they are very sensitive to the order of variables or constraints in the model.

Upvotes: 3

Related Questions