IVR JobJob

Overview

Jobs are used to link together tasks in a schedule. There are two typical use cases for jobs. The first is a situation where vehicles are being physically loaded with goods and the vehicle capacity is a constraint being considered, one would model both the pickup and dropoff tasks of a vehicle. In this situation, we would also implicitly be modelling the reloading of vehicles (in a typical VRP context). If reloading of vehicles is not permitted, there are several ways to add constraints which limit the reloading of vehicles throughout the day (depending on how the model has been configured). It may also be the case (in the general pickup and dropoff problem) where pickups and dropoffs are all at different locations (similar to the dial-a-ride problem). We don’t support swapping order origin/destinations (i.e. exchanging 1 unit from job A with 1 unit from job B) as often orders have been pre-labelled for certain customers and it is not possible to exchange orders in this manner. As such, there are certain implicit constraints to watch out for on the job (which are desirable in real-world modelling).

The second use case for the job is where we are interested in performing visits. This would be typical with the planning of sales reps. In this situation, the capacity of the vehicle (or rep) is not relevant, but the visit windows and all the other attributes used for planning remain. In this model, we can choose to model either the pickup or dropoff (i.e. omit one) which will create a Job with a single Task which should be performed. One can consider the typical CVRP an instance where we have single task for each job - modelling the problem in this manner prevents reloading as vehicles all start at the depot and never technically “pickup” orders at the depot, they simply visit the customers, but the cumulative quantity they may accrue during the visits is limited to the vehicle capacity.

The first use case (defining both the pickup and dropoff tasks) remains the most typical case to model.

Applicable models

• IVR7 ivr7-kt461v8eoaif
• IVR8 ivr8-yni1c9k2swof

Job

The Job defines a collection of work to be performed. If the collection is not performed in the schedule, a penalty is incurred. It is required that if a pickup and dropoff task is specified, that both be performed in order to avoid the penalty cost.

Schema Definition

message Job {
  required string id = 1;
  optional Task pickupTask = 2;
  optional Task dropoffTask = 3;
  required float penalty = 4;                            // the cost of not performing both tasks (if specified)
  optional VehicleRelation vehicleRelations = 5;         // for specifying inclusions/exclusions
  optional CompartmentRelation compartmentRelations = 6; // IVR8 only.
}

Fields

id

The unique identifier for this job. Should be unique across all jobs provided in the model

pickupTask

The pickup task for this particular job. If the dropoffTask is defined, we have an implicit constraint which requires that the pickupTask occurs before the dropoffTask as well as the two tasks are required to be performed by the same vehicle. It is required that either the pickup, dropoff or both tasks are provided for a job to be valid.

dropoffTask

The dropoff task for this particular job. If the pickupTask is defined, we have an implicit constraint which requires that the pickupTask occurs before the dropoffTask as well as the two tasks are required to be performed by the same vehicle. It is required that either the pickup, dropoff or both tasks are provided for a job to be valid.

penalty

The penalty cost incurred if both the pickupTask and dropoffTask are unperformed in the solution. The pickupTask and dropoffTask are either both performed, or both unperformed in a valid solution, i.e. a scheduled pickupTask without a dropoffTask is considered an infeasible solution. A high penalty cost encourages the order to be planned. A lower penalty cost suggests that an order may be optional, or only cost effective if other orders (nearby) are also performed. A typical model may have a large penalty cost for each job.

vehicleRelations

Defines a relation between the job and either allowable or excluded vehicles. This is typical in situations where incompatibilites exist between the product related to the task and particular vehicles defined in the model.

compartmentRelations

Defines a relation between the task and the compartments to which the job components (i.e. pickupTask and dropoffTask) may be assigned. Since the model assumes that the product on the pickupTask is the product on the dropoffTask a single compartment is assigned for both tasks.

Examples

This example shows the use of both the pickup task and dropoff task to create a standard pickup at the depot (the Guiness Storehouse) and dropoff at the Oval Bar. The task attributes define the size of the pickup and dropoff (on the capacity dimension) as well as the time taken to perform both tasks. The penalty of 10000 units ensures that the tasks are performed in the schedule. The objective of the schedule is to minimise cost (within the constraints) and if the tasks are unperformed this would result in a schedule with a higher cost (which will occur if the tasks are infeasible).

id: "job_1"
pickupTask {
  taskId: "pickup_1"
  locationId: "Guinness Storehouse"
  attributes {
    dimensionId: "time"
    quantity: 5
  }
  attributes {
    dimensionId: "capacity"
    quantity: 100
  }
}
dropoffTask {
  taskId: "dropoff_1"
  locationId: "The Oval Bar Dublin"
  attributes {
    dimensionId: "time"
    quantity: 20
  }
  attributes {
    dimensionId: "capacity"
    quantity: -100
  }
}
penalty: 10000

This next example illustrates a simple visit style job where two hours are spent at The Confession Box, but this job can only be serviced by vehicles v-1 and v-3. It would have also been valid to simply exclude v-2 (assuming there were three vehicles available in the model named v-1, v-2 and v-3).

id: "job_2"
pickupTask {
  taskId: "dropoff_2"
  locationId: "The Confession Box"
  attributes {
    dimensionId: "time"
    quantity: 120
  }
}
penalty: 10000
vehicleRelations {
  type: INCLUSIVE
  vehicleIds: "v-1"
  vehicleIds: "v-3"
}
}

Notes

• A valid job definition requires at least the pickupTask or dropoffTask to be defined.
• It is typical to define both the pickupTask and dropoffTask for a set of jobs.
• It is implicitly assumed that both tasks defined by a job should be performed by the same vehicle
• It is implicitly assumed that the pickupTask should be performed before the dropoffTask.

Job Vehicle Relation

Schema definition

message VehicleRelation {
  enum Type {
    INCLUSIVE = 0;
    EXCLUSIVE = 1;
  }
  required Type type = 1;
  repeated string vehicleIds = 2;
}

Fields

type

Either inclusive or exclusive. Inclusive refers to all vehicles which may perform the specified job. Exclusive refers to all vehicles which are not permitted to perform the job.

vehicleIds

A list of vehicle id’s applicable to the type specified (inclusive or exclusive). This list may not be empty as this would immediately result in the job incurring a penalty cost - which is typical of an input-data issue. Vehicle id’s provided must be defined within the set of vehicles provided in the model.

Examples

This example defines an exclusion between a Job and the vehicle with id v-2.

vehicleRelations {
  type: EXCLUSIVE
  vehicleIds: "v-2"
}

Notes

• It is assumed that if no vehicle relations are provided that a Job is compatible with all vehicles.
• If a vehicle relation is specified, the list of vehicleIds in the relation may not be empty.

Job Compartment Relation

Schema definition

message CompartmentRelation {
  enum Type {
    INCLUSIVE = 0;
    EXCLUSIVE = 1;
  }
  required Type type = 1;
  repeated string compartmentIds = 2;
}

Fields

type

Either inclusive or exclusive. Inclusive refers to all compartments to which the specified job may be assigned. Exclusive refers to all compartments which are not permitted in the job assignment.

compartmentIds

A list of compartment id’s applicable to the type specified (inclusive or exclusive). This list may not be empty as this would immediately result in the job being unassignable (incurring a penalty cost). This is typical of an input-data issue. Compartment id’s provided must be defined within the set of compartments provided in the model.

Examples

This example defines an exclusion between a Job and the compartment with id c-2.

compartmentRelations {
  type: EXCLUSIVE
  compartmentIds: "c-2"
}

Notes

• It is assumed that if no compartment relations are provided that a Job is compatible with all compartments.
• If a compartment relation is specified, the list of compartmentIds in the relation may not be empty.