[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 ***@***.***> 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 <#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:

or-tools/ortools/constraint_solver/routing.h

Lines 1003 to 1005 in 39f4470

	// Returns the vehicle variable of the node corresponding to index. Note that
	// VehicleVar(index) == -1 is equivalent to ActiveVar(index) == 0.
	IntVar* VehicleVar(int64 index) const { return vehicle_vars_[index]; }

or-tools/ortools/constraint_solver/constraint_solver.h

Lines 3990 to 3991 in 39f4470

	// This method intersects the current domain with the values in the array.
	virtual void SetValues(const std::vector<int64>& values);

[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

or-tools/ortools/constraint_solver/routing.h

Lines 856 to 858 in 4040249

	// Returns the vehicle variable of the node corresponding to index. Note that
	// VehicleVar(index) == -1 is equivalent to ActiveVar(index) == 0.
	IntVar* VehicleVar(int64 index) const { return vehicle_vars_[index]; }

or-tools/ortools/constraint_solver/constraint_solver.h

Lines 4090 to 4091 in 4040249

	// This method intersects the current domain with the values in the array.
	virtual void SetValues(const std::vector<int64>& values);

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...