5.106. cycle_resource
| DESCRIPTION | LINKS | GRAPH |
- Origin
CHIP
- Constraint
- Arguments
- Restrictions
- Purpose
Consider a digraph defined as follows:
To each item of the and collections corresponds one vertex of . A vertex that was generated from an item of the (respectively ) collection is called a resource vertex (respectively task vertex).
There is an arc from a resource vertex to a task vertex if .
There is an arc from a task vertex to a resource vertex if .
There is an arc from a task vertex to a task vertex if .
There is no arc between two resource vertices.
Enforce to cover in such a way that each vertex belongs to a single circuit. Each circuit is made up from a single resource vertex and zero, one or more task vertices. For each resource-vertex a domain variable indicates how many task-vertices belong to the corresponding circuit. For each task a domain variable provides the identifier of the resource that can effectively handle that task.
- Example
-
The constraint holds since the graph corresponding to the vertices described by its arguments consists of the following 3 disjoint circuits:
The first circuit involves the resource vertex 1 as well as the task vertices 5, 4 and 7.
The second circuit is limited to the resource vertex 2.
Finally the third circuit is made up from the remaining vertices, namely the resource vertex 3 and the task vertices 8 and 6.
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
All occurrences of two distinct values in or can be swapped.
- Usage
This constraint is useful for some vehicles routing problem where the number of locations to visit depends of the vehicle type that is actually used. The resource attribute allows expressing various constraints such as:
The compatibility or incompatibility between tasks and vehicles,
The fact that certain tasks should be performed by the same vehicle,
The pre-assignment of certain tasks to a given vehicle.
- Remark
This constraint could be expressed with the constraint of CHIP by using the following optional parameters:
The resource node parameterΒ [Bourreau99],
The circuit weight parameterΒ [Bourreau99],
The name parameterΒ [Bourreau99].
- See also
- Keywords
characteristic of a constraint: derived collection.
constraint type: graph constraint, resource constraint, graph partitioning constraint.
final graph structure: connected component, strongly connected component.
- Derived Collection
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph class
-
For all items of :
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph model
The graph model of the constraint illustrates the following points:
How to differentiate the constraint on the length of a circuit according to a resource that is assigned to a circuit? This is achieved by introducing a collection of resources and by asking a different graph property for each item of that collection.
How to introduce the concept of name that corresponds to the resource that handles a given task? This is done by adding to the arc constraint associated with the constraint the condition that the name variables of two consecutive vertices should be equal.
PartΒ (A) of FigureΒ 5.106.1 shows the initial graphs (of the second graph constraint) associated with resources 1, 2 and 3 of the Example slot. PartΒ (B) of FigureΒ 5.106.1 shows the corresponding final graphs (of the second graph constraint) associated with resources 1, 2 and 3. Since we use the graph property, the vertices of the final graphs are stressed in bold. To each resource corresponds a circuit of respectively 3, 0 and 2 task-vertices.
Figure 5.106.1. Initial and final graph of the constraint
(a) (b) - Signature
Since the initial graph of the first graph constraint contains vertices, the corresponding final graph cannot have more than vertices. Therefore we can rewrite the graph property to and simplify to .