Or-tools: [Question] How to specify which nodes a vehicle is allowed to visit in cscvrptw?

[eliaspax42]

What is the best way to specify (or limit) the nodes specific vehicles are allowed to visit (I know upfront what nodes a vehicle is allowed to visit)?
I'm trying to model 'skills vrp', i.e. each vehicle have a set of 'skills' and each location have a set of 'required skills'.
A vehicle should only be able to visit a location if the vehicle has all the skills required by the location.
Is there a C# example of this or something similar somewhere?
Any help appreciated (even if not C#).

[furnon]

To each node is attached a vehicle variable representing the vehicle
visiting the node. You can access it with model.VehicleVar(node). It's an
integer variable and can be constrained like any variable. In particular
you can restrict its domain to a set of values representing the vehicles
it's compatible with.

On Tue, Mar 7, 2017 at 12:27 AM, eliaspax42 [e-mail]
wrote:

What is the best way to specify (or limit) the nodes specific vehicles are
allowed to visit (I know upfront what nodes a vehicle is allowed to visit)?
I'm trying to model 'skills vrp', i.e. each vehicle have a set of 'skills'
and each location have a set of 'required skills'.
A vehicle should only be able to visit a location if the vehicle has all
the skills required by the location.
Is there a C# example of this or something similar somewhere?
Any help appreciated (even if not C#).

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/334, or mute the thread
https://github.com/notifications/unsubscribe-auth/AKjyUqSR8-MvBdomnXiT1Mzqj-Ib2Cs2ks5rjJZogaJpZM4MU1oC
.

[Mizux]

For API v7.0

Supposing you want to allow vehicle 2,3,4 to node 7

Python snippet should be:

index = manager.NodeToIndex(7)
routing.VehicleVar(index).SetValues([-1, 2,3,4])

In .Net should be (not tested):

var index = manager.NodeToIndex(7);
routing.VehicleVar(index).SetValues(new int[] {-1, 2,3,4});

note: you must allow the node to be not active, i.e. -1 since the solver build its solutions little by little and may require to first unassign the location to any vehicle then try to insert it later during the local search
ref:
https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/routing.h#L1003-L1005
https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/constraint_solver.h#L3990-L3991

[GuyBenhaim]

sorry, I didn't look that far back ...

I did not yet fully port to v7, can we do it with v6?

[Mizux]

I would say yes, it's an old API
https://github.com/google/or-tools/blob/40402496387799bae620622913276bb27a26fc6f/ortools/constraint_solver/routing.h#L856-L858

https://github.com/google/or-tools/blob/40402496387799bae620622913276bb27a26fc6f/ortools/constraint_solver/constraint_solver.h#L4090-L4091

from v6.10.X branch...

[GuyBenhaim]

This works. But, trying to speed-up solution I tried assigning only half of the vehicles to half of the Nodes, and the other half to the other half of the Nodes.
I was hoping that artificially splitting the problem (via these constraints) would speed it up, but several tests in different configurations showed solver run times change -10% - +10% - i.e. no improvement.

Any idea?

[Mizux]

I would say internally:

• solver still have array of vehicle size and need to check if each value is allowed or not so you don't get so much improvement than splitting in two separate sets directly when instantiating the RoutingIndexManager() i.e. running the solver two time on two separate instance (only a supposition reference needed)
• Also if your search space is big enough solver can still need to use the max time allowed to reach optimality.
• It is also likely possible that during the first "SolutionStrategy" step solver already split nodes in several set to minimize the distance so these constraints are redundant...

A good test would be to compare solution objectives over times to see if you have an initial speed up at first...

[karandeepakkanwar]

For API v7.0

Supposing you want to allow vehicle 2,3,4 to node 7

Python snippet should be:

index = manager.NodeToIndex(7)
routing.VehicleVar(index).SetValues([-1, 2,3,4])

In .Net should be (not tested):

var index = manager.NodeToIndex(7);
routing.VehicleVar(index).SetValues(new int[] {-1, 2,3,4});

note: you must allow the node to be not active, i.e. -1 since the solver build its solutions little by little and may require to first unassign the location to any vehicle then try to insert it later during the local search
ref:
https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/routing.h#L1003-L1005

https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/ortools/constraint_solver/constraint_solver.h#L3990-L3991

@Mizux Can you explain a little as to how to code this in Python in v7.0?
I have been trying but its a little difficult, syntax wise. I have features with customer 'skills req' and vehicles 'skills' and I can match them to get the relevant skills. But how to incorporate those features in ortools? Thanks in advance.