VRPTW and scheduling scenario

[Andrea Colombo]

Hi, I am trying to solve scenario that mixes scheduling and VRPTW, in detail the rules for the scenario are:
-items have a scheduled delivery time
-items need to be prepared before being available to delivery
-preparation and delivery are done by different group of workers
-delivery wroker can go back to home depot to load the next delivery

Up until now I was working with a semplification: keep the two problem separate, solve the scheduling first and use the worst time as starting time to solve VRPTW.

Now I am trying to work with a more complex model but I am not sure how actual add the constraint for preparation nor how to add the option to go back to depot.
I was thinking of using 2 different type of nodes for each item (preparation and delivery) connected through the depot and with constrain that boths the nodes need to be part of the solution but I have no idea on how to implement it.

Any suggestion is welcomed.

[blind.line]

Just a thought, but if the routing problem is pretty “easy” compared to the prep problem, you might have some luck modeling using the CP-SAT solver. 

In my work, I’ve found that complicated constraints surrounding the availability of workers and the execution of the orders (pickup and/or delivery actions that are non-trivial) are easier to express using the CP-SAT way of formulating problems.  Mostly this is because there are tons of examples and documentation for the CP-SAT solver.  Then the routing part can be added using CP-SAT’s circuit constraint. 

But if the routing problem is hard (lots of nodes, options for each trip, lots of trips to plan, etc) then the circuit constraint seems to be very slow compared to the routing solver. I think it is always possible to express complicated resource allocation type constraints in the old CP solver, but you’ll have to dig a bit to find examples. 

James

On Sep 17, 2021, at 10:34, Andrea Colombo <lgx...@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/c76909dd-fee8-435e-98a2-1d677a1581a8n%40googlegroups.com.