The "VRP" (Vehicle Routing Problem) constraint.
The direct graph where arc #i (from tails[i] to head[i]) is present iff literals[i] is true must satisfy this set of properties:
- #incoming arcs == 1 except for node 0.
- #outgoing arcs == 1 except for node 0.
- for node zero, #incoming arcs == #outgoing arcs.
- There are no duplicate arcs.
- Self-arcs are allowed except for node 0.
- There is no cycle in this graph, except through node 0.
- Note
- Currently this constraint expects all the nodes in [0, num_nodes) to have at least one incident arc. The model will be considered invalid if it is not the case. You can add self-arc fixed to one to ignore some nodes if needed.
- Todo
- (user): It is probably possible to generalize this constraint to a no-cycle in a general graph, or a no-cycle with sum incoming <= 1 and sum outgoing <= 1 (more efficient implementation). On the other hand, having this specific constraint allow us to add specific "cuts" to a VRP problem.
Definition at line 3709 of file CpModel.pb.cs.
|
| static pb::MessageParser< RoutesConstraintProto > | Parser [get] |
| static pbr::MessageDescriptor | Descriptor [get] |
| pbc::RepeatedField< int > | Tails [get] |
| pbc::RepeatedField< int > | Heads [get] |
| pbc::RepeatedField< int > | Literals [get] |
| pbc::RepeatedField< int > | Demands [get] |
| long | Capacity [get, set] |
| pbc::RepeatedField< global::Google.OrTools.Sat.RoutesConstraintProto.Types.NodeExpressions > | Dimensions [get] |
| | Expressions associated with the nodes of the graph, such as the load of the vehicle arriving at a node, or the time at which a vehicle arrives at a node. Expressions with the same "dimension" (such as "load" or "time") must be listed together. This field is optional. If it is set, the linear constraints of size 1 or 2 between the variables in these expressions will be used to derive cuts for this constraint. If it is not set, the solver will try to automatically derive it, from the linear constraints of size 1 or 2 in the model (this can fail in complex cases).
|
| pbc.RepeatedField<global.Google.OrTools.Sat.RoutesConstraintProto.Types.NodeExpressions> Google.OrTools.Sat.RoutesConstraintProto.Dimensions |
|
get |
Expressions associated with the nodes of the graph, such as the load of the vehicle arriving at a node, or the time at which a vehicle arrives at a node. Expressions with the same "dimension" (such as "load" or "time") must be listed together. This field is optional. If it is set, the linear constraints of size 1 or 2 between the variables in these expressions will be used to derive cuts for this constraint. If it is not set, the solver will try to automatically derive it, from the linear constraints of size 1 or 2 in the model (this can fail in complex cases).
Definition at line 3835 of file CpModel.pb.cs.
1.14.0