2.17 Compatibility

Compatibility relationships are used to restrict what decisions the optimiser may make when generating a solution. The following kinds of compatibility relationships are supported:

• Order-vehicle compatibility: an order may only be assigned to a vehicle with which it is compatible.
• Order-compartment compatibility: an order may only be loaded in a compartment with which it is compatible.
• Order-order compatibility: orders may only be simultaneously loaded into a compartment if they are compatible.
• Load Order-order compatibility: orders may only be simultaneously loaded on to a vehicle if they are compatible.
• Location-vehicle compatibility: a vehicle must only pickup or deliver orders to locations with which it is compatible.

Compatibility relationships are specified using attributes. As an example, consider a fleet that consists of both refrigerated and non-refrigerated vehicles. To restrict an order that requires refrigeration to be assigned to only a refrigerated vehicle, we can label the order with the attribute REFRIGERATED and also label all of the refrigerated vehicles with the attribute REFRIGERATED. We can then specify an order-vehicle compatibility relationship such that orders with the attribute REFRIGERATED must only be assigned to vehicles with the attribute REFRIGERATED.

Table 1 is an example of an order-vehicle compatibility relationship, where true means that the attribute pair is compatible and an empty cell means that the attribute pair is not compatible.

Table 1 is interpreted as follows: for orders with the attribute REFRIGERATED, the compatible vehicles must have the attribute REFRIGERATED; for orders with the attribute TALL, the compatible vehicles must have either the attribute TALL or the attribute LONG; for the orders with the attribute ORDER7, the compatible vehicles must have the attribute VEHICLE1. For the last case, if ORDER7 is one of the order identifiers and VEHICLE1 is one of the vehicle identifiers then this will restrict ORDER7 to only be compatible with VEHICLE1. If ORDER7 has other attributes the VEHICLE1 is not compatible with then this will mean this order cannot be assigned to any vehicle. (See Conjunction Rule below).

There are three rules applied when interpreting attributes and their compatibility. Here we use order-vehicle compatibility to illustrate them.

1. Null Rule: An order attribute that is not part of a order-vehicle compatibility relationship imposes no restriction on which vehicle the order can be assigned to. We can ignore this attribute or, equivalently, consider it compatible with all vehicle attributes.
2. Disjunction Rule: If an order attribute has multiple compatible vehicle attributes, then any vehicle having one of the attributes is a candidate compatible vehicle.
3. Conjunction Rule: If an order has multiple attributes, a compatible vehicle for the order must have a compatible attribute for each of the order’s attributes.

These rules are applied in only one direction: attributes are interpreted as requirements for orders and features for vehicles. An order does not need to have a compatible attribute for each of a vehicle’s attributes to be compatible with that vehicle. For example, in Table 1, an order that has only one attribute, REFRIGERATED, is compatible with a vehicle that has attributes REFRIGERATED and LONG. These rules apply similarly to order-compartment and location-vehicle compatibility.

For order-order and load order-order compatibility, these rules must be applied in both directions, that is: for two compatible orders, each of them must have a compatible attribute for each attribute of the other order.