Best strategy for problem with lots of timewindows?

[Govert Versluis]

Hello,

I've been throwing Or-Tools at bigger and more realistic problems.

I currently have a problem with 120 stops, all of which have a time window from start til either 09:00, 12:00 or 17:00.

My vehicles need to start at 7:00 and end at 17:00.

However, it seems that no matter how many vehicles I give OR-Tools to work with, a solution is never reached. If I let the vehicles start really early (01:00), it will only use 3 vehicles, even if it can use 40.

I was assuming the problem might be in the first solution strategy, but I've tried nearly all of them without improvement.

I know the problem I have is feasible with the amount of vehicles I give the library (I've even tried 120 vehicles to match the stops), so I'm looking for pointers on how to proceed from here.

I'm probably misunderstanding or lacking knowledge on a certain part of the library.

If it helps I can post source code to reproduce, but since it seems like such a generic problem I've held off on that for now.

Best,

Govert

[Govert Versluis]

Hello,

Sorry to bother you again, but I was hoping my email might have slipped through the cracks.

Is there an assumption I am making which is incorrect? Is OR-tools capable of solving problems like this?

Kind regards,

Govert

[Vincent Furnon]

Hi,

The vehicle routing library in OR Tools should indeed handle this case. Have you tried making your stops optional (with a disjunction constraint) to see if it helps (at least helps debugging) ?

One approach for debugging your issue would be to start by solving your model with a small number of stops (small enough that you get a solution), then progressively increase the number of stops to try to identify anything particular with the failing stop(s).

I'm rather surprised even the insertion heuristics don't succeed since they are the most robust.

Have you checked that the callback used for the time dimension actually returns proper times and that all time units match ? Do you have capacity constraints ?

Vincent

--
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-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Govert Versluis]

Hi Vincent,

Thanks for your response, I apologize for my late reply, unfortunately your helpful response landed in my spam folder.

I have indeed tried making the stops optional, this seems to have made no difference.

The callback does indeed return the proper times and all time units match. I have not added capacity constraints yet.

I've spent some time today trying to extract the issue from my test project to reduce it to the bare essentials.

This has led to a reproducible C# programs as short as I can make it.

The program (https://pastebin.com/8QNK5MNA) uses weights and time-windows extracted from the data where we first encountered this problem.

This means it is still a bit lengthy due to the static data at the bottom, sorry.

It has the following scenarios:

70 stops, vehicles time window from 00:00 until 12:00, no disjuctions: Works, uses 2 out of 20 vehicles.

71 stops, vehicles time window from 00:00 until 12:00, no disjuctions: No solution found, hangs until time limit.

70 stops, vehicles time window from 02:00 until 12:00, no disjuctions: No solution found, hangs until time limit.

71 stops, vehicles time window from 00:00 until 12:00, disjuctions on all stops: No solution found, hangs until time limit.

The original problem used 150 stops (including start- and end-depot for each vehicle).

Can you see anything I'm doing wrong (or dare-I-say-it or-tools is)? Would you like me to file an issue?

Thanks for your time once again.

Best regards,

Govert

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Gwénaël Rault]

Hello,

From my experiment the first strategy PATH_CHEAPEST_ARC tends to exclude many stops.

Did your vehicles have multiple depots ? If so, prefer to use PARALLEL_CHEAPEST_INSERTION, if they have a single one, try with SAVINGS.

[Govert Versluis]

Hello Gwénaël,

Thanks for taking the time to respond.

With PARALLEL_CHEAPEST_INSERTION I get nearly the same results, except when I add disjunctions. Then I get a result within reasonable time.

However, the actual solution seems sub-optimal, with multiple routes overlapping and stops in the same street not being serviced by the same vehicle.

I'm reasonably sure our time matrix is accurate, but I will investigate by myself until I have something concrete to look at.

On a sidenote, is there a good description of each first solution strategy and what scenarios suit it best?

I've looked but came up empty.

Thanks both Vincent and Gwénaël for your help.

Best,

Govert