CVRPTW Or-Tools

[farka...@gmail.com]

Hi!

I would like to extend the CVRPTW example to allow the depot to be
revisited more than once (where the capacity of that particular
vehicle is zeroed), although I don't seem to succeed. Is there an easy
way to add this functionality to the cvrptw.cc?

My trials were the following:

If we have 1 vehicle with a capacity of 1 unit and 3 orders with a
demand of 1 unit then
this task could not be solved by CVRPTW, however it would be good to
have a solution
like the following:

vehicle goes to first point, goes back to depot and unloads
vehicle goes to second point, goes back to depot and unloads
...

In order to achieve this a choose to add another 2 mock depos (0,1,2
nodes are therefore considered to be
the same depot). The problem is that neither I can assign negative
demand to a node, nor I can "order" the
solver to set the remaining capacity of each vehicle back to 1 upon
visiting node 1 or 2 (another mock depos).

a) assigning negative value to the demand of an order leads to an
error
b) setting routing.CumulVar(1, kCapacity)->SetValue(0) does not set
back the capacity.

Are there any way to solve this? Any help would be greatly
appreciated!
Thank you for all your replies,

Mark

[Navjot Kukreja]

I am trying to solve the same problem. Mark, if you ever managed to solve this, I'd love to hear your solution. To the others, could you please suggest something?

[thomas...@ewetel.net]

Hello,

 

I think You can add virtual vehicles as a copy of Your real vehicles. This way it can be solved, because You will get more roundtrip routes for each real vehicle.

Further You should add a disjunction to allow skipping orders.

 

Thomas Masuth

[Navjot Kukreja]

That sounds like a good idea. But what kind of a constraint could avoid using a vehicle and its copy at the same time?

Also, continuing on the lines of adding non-depot copies of the depot node, why can't demand for a node be negative? In case of a pickup and delivery problem, the demand at the delivery node is negative. Why, then, are we not allowed to add negative values for demand at a node?