Problem

The Problem entity represents a Vehicle Routing Problem. It consists of two main parts: plan and fleet.

Plan

A plan contains a list of jobs to be served, and optionally a list of relations between these jobs and vehicles as well as the optional clustering object with settings for grouping similar jobs.

Job

Essentially, this entity represents a job to be served by any vehicle taking into account specific properties:

  • location (required): location represented via latitude and longitude:

    "location": {"lat": 52.5622847, "lng": 13.4023099}

  • duration (required): duration in seconds (service time): a time spent at a given location:

    "duration": 120

  • demand (required): demand is represented via multidimensional units of measure, e.g. volume, mass, size, etc:

    "demand": [1]

  • times (optional): a list of time windows specifying when the vehicle is allowed to visit the given location. The date is represented in RFC3339 format:

    "times": [["2020-07-04T06:00:05.000Z","2020-07-04T12:05:05.000Z"]]

  • skills (optional): a list of skills which should be defined on the vehicle type serving the job.

    "skills": ["fridge"]

  • tag (optional): a user-defined tag associated with a given place. It is propagated back within the solution. Use it to distinguish between different job places.

    "tag": "pickup_1"

  • territoryIds (optional): represents the territory identifiers to which the job place belongs. This is used along with the territories property of the vehicle type to limit/incentivize vehicles to serve jobs with specific territories. This property is not allowed for complex jobs with more than one task.

    "territoryIds": ["territory1"]

  • priority (optional): priority of job with 1 for high priority jobs and 2 for normal jobs (default is 2):

    "priority": 1

  • customerId (optional): specifies a unique identifier for a customer. Jobs having the same customerId will be grouped in one or several clusters if possible, see clustering.

Note: Avoid referencing any confidential or personal information as part of the tag.

Depending on how the tasks property is specified, a job can be one of three types:

  • pickup: a job for picking something along the route and bringing it to the route's end location. It is used when only the pickups task with one job task is specified. An example of a pickup job:
{
        "id": "pickup1",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.5622847,
                    "lng": 13.4023099
                  },
                  "duration": 180,
                  "territoryIds": ["territory1"]
                }
              ],
              "demand": [1]
            }
          ]
        }
      }
  • delivery: a job for delivering something loaded at the beginning of the route. It is used when only the delivery's place with one job place is specified. An example of a delivery job:
{
        "id": "delivery1",
        "tasks": {
          "deliveries": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.5252832,
                    "lng": 13.41884
                  },
                  "duration": 180
                }
              ],
              "demand": [1]
            }
          ]
        }
      }
  • pickup and delivery job: a job for picking and delivering along the route. It is used when both pickup and delivery places are specified. The job can have multiple pickups and deliveries. All or none of them have to be served. Also, the sum of demands for pickup and delivery places should be equal. A basic scenario for it could be multiple pickups at different places followed by a single delivery. An example of a job with multiple job places:
{
        "id": "myMultiJob",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.5622847,
                    "lng": 13.4023099
                  },
                  "duration": 180,
                  "tag": "p1"
                }
              ],
              "demand": [1]
            },
            {
              "places": [
                {
                  "location": {
                    "lat": 52.5330881,
                    "lng": 13.3973059
                  },
                  "duration": 180,
                  "tag": "p2"
                }
              ],
              "demand": [1]
            }
          ],
          "deliveries": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.5252832,
                    "lng": 13.41884
                  },
                  "duration": 180,
                  "tag": "d1"
                }
              ],
              "demand": [2]
            }
          ]
        }
      }

An example job with priority (applicable to all job types):

{
        "id": "delivery1",
        "priority": 1,
        "tasks": {
          "deliveries": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.5252832,
                    "lng": 13.41884
                  },
                  "duration": 180
                }
              ],
              "demand": [1]
            }
          ]
        }
      }

Limit on the number of jobs

The total amount of jobs is calculated as the sum of all pickups and deliveries included in jobs.

Relation

Using the optional relations parameter, we can define various relations between jobs and vehicles.

There are three types of relations specified by type:

  • sequence: the order of the jobs which are specified in this relation may not be changed and must be served by this particular vehicle. No additional job may be inserted between those jobs that are specified in this relation
  • flexible: the jobs that are specified in this relation must be served by this particular vehicle. The order among the jobs defined in this relation may not be changed. Jobs that are not specified in this or another relation can be inserted anywhere in this vehicle's tour even between the jobs defined in this relation
  • tour: the jobs that are specified in this relation must be served by this particular vehicle. The order of the jobs specified in this relation may be changed.

With the jobs property, each relation specifies a list of activities performed by a specific vehicle. There are four possible job types:

  • jobId: regular job id. (Note: Avoid referencing any confidential or personal information as part of the jobId.)
  • departure: departure activity
  • arrival: arrival activity
  • break: vehicle break activity

The vehicleId property is used to stick jobs to the specific vehicle with the given id. Check the next section for details about the vehicle id.

By using relations for our vehicles and jobs, we can influence the behavior of the algorithm for the re-planning process, and its result.

{
  "relations": [
    {
      "type": "sequence",
      "jobs": ["departure", "job1", "job2"],
      "vehicleId": "myVehicleType_1"
    }
  ]
}

Please note that jobs added into a sequence or a flexible relation are not checked for any constraint violations, e.g. time windows, skill requirements, capacity violations, pickup/delivery assignment, routing availability, etc. This might lead to infeasible or undesired solutions. Similar to sequence and flexible relations, jobs added into a tour relation are generally not checked for constraint violations, however, there might be some cases where not all jobs in a tour relation get assigned. Also, a relation cannot be used with a job with multiple pickups or deliveries.

Clustering

Using the optional clustering property, we can enable the grouping of similar jobs into one or several job clusters, in order to ensure that they are assigned to the same stop if feasible and thus are served together.

Jobs are considered similar if they fulfil all the below conditions:

  • they have only a single job task with a single job place
  • they have the same type of task, either pickup OR delivery
  • they have identical locations
  • they have identical time windows
  • they have identical skills
  • they have the same amount of demand dimensions
  • they have the same territories

Jobs having the following properties are not considered for clustering:

  • jobs with more than a single task
  • jobs with more than one job place (alternative locations)
  • jobs, which have both pickup & delivery tasks
  • jobs with priority property
  • jobs, which are referenced in a relation

Or put in simpler terms, all jobs which contain more than 1 location, use priority or are used in relations, are not considered as candidates for clustering.

If a cluster violates some constraints, it is split into multiple smaller clusters. In that case, the customerId property of a job can be used to group jobs for the same customer into the same cluster(s) if possible.

The optional clustering object provides the following properties:

  • serviceTimeStrategy (required): Is used to control, how the duration or service time of the job clusters shall be determined.
    • maxDurationStrategy: The total duration of the job cluster shall be equal to the duration of the job with the longest duration, or more precisely the duration defined in the job task's place object.
    • fixedDurationStrategy: The total duration of the job cluster shall be equal to the duration value defined in the strategy object.
{
  "clustering": {
      "serviceTimeStrategy": {
        "type": "fixedDurationStrategy",
        "duration": 300
      }
  }
}

Fleet

A fleet specifies a list of vehicle types and their routing profiles besides traffic consideration options.

VehicleType

Each vehicle type is defined by the following properties:

  • id: a unique identifier of a vehicle type. In the solution, it is used to generate specific vehicle ids using the pattern ${vehicleTypeId}_${sequenceIndex}.

    "id": "myVehicleType"

    The sequenceIndex is the index of the vehicle. For example, for the given vehicleTypeId, if the amount is given as 2, the possible vehicle ids are ${vehicleTypeId}_1 and ${vehicleTypeId}_2.

Note: Avoid referencing any confidential or personal information as part of the vehicle's Id.

  • profile: specifies the name of the routing profile (see next section)

    "profile": "normal_car"

Note: Avoid assigning real-life identifiers, such as for instance a vehicle license plate id as the profileName of the routing profile.

  • costs: defines different vehicle costs:
    • fixed cost to start using the vehicle
    • distance cost per meter
    • time cost per second
  {
    "costs": {
      "distance": 0.0002,
      "time": 0.004806,
      "fixed": 22
    }
  }

distance, time and fixed are optional with a default value of zero. In case time and distance costs are not provided, then a small time cost of 0.00000000001 will be used instead. Setting the value of both time and distance costs as zero is not allowed.

  • shifts: specifies an array of depot places where vehicles of this particular type should start and end:

    {
  "shifts": [{
    "start": {
      "time": "2020-07-04T09:00:00Z",
      "location": {"lat": 52.46642, "lng": 13.28124}
    },
    "end": {
      "time": "2020-07-04T18:00:00Z",
      "location": [52.46642, 13.28124]
    },
    "breaks": [
      {
       "times": [["2020-07-04T12:00:05.000Z","2020-07-04T14:05:05.000Z"]],
       "location": {"lat": 52.46642, "lng": 13.28124},
       "duration": 3600
      }
    ]
  }]
}

    Each place is specified by time and location. Start time means the earliest departure time, end time latest arrival time. The optional parameter breaks specifies a list of vehicle breaks during the tour (at the moment, not more than one). A Break has an optional location property, if it is omitted then the vehicle takes it's break at the last served job's location.

    The end location is optional: if it is omitted then the vehicle's route ends at the last job location.

  • capacity: vehicle capacity represented via multidimensional units of measure, e.g. volume, mass, size, etc:

    "capacity": [10]

  • skills: a list of vehicle skills which can be used to serve jobs

    "skills": ["fridge"]

  • limits: specifies constraints applied to a vehicle type

    • maxDistance: specifies the maximum distance limitation for our vehicle in meters
    • shiftTime: defines the shift time for the vehicle in seconds
{
  "limits": {
    "maxDistance": 30000,
    "shiftTime": 28800
  }
}
  • territories: represents the vehicle type's territories with their priorities. If strict is set to false, then the vehicle type can serve jobs outside its assigned territories, but with lower priority, otherwise, it cannot. Each territory has a required id property and an optional priority property with the default value of 1. The allowed values for priority range from 1, as the highest priority, to 5 as the lowest priority. Jobs in a vehicle type's higher priority territories are preferably assigned to a vehicle with that type. Job territories are specified using the territoryIds property of the job place.
    {
"territories": {
  "strict": true,
  "items": [
    {
      "id": "territory1",
      "priority": 1
    }
  ]
}
}

Example scenarios demonstrating territories can be found in territory tutorials.

Routing Profile

Different routing profiles are specified as elements in the profiles collection. There are five possible profile types: car, truck, scooter, bicycle and pedestrian. They have the following common properties:

  • name: a unique name of the routing profile. It is used on the vehicle type definition "name": "normal_car"

  • type: specifies the routing profile type, possible values: car, truck, scooter, bicycle, pedestrian "type": "car"

  • departureTime: specifies a vehicle's departure time. If omitted, the earliest shift start time of all vehicle types sharing the same vehicle profile is used.

  • avoid: specifies a list of routing features that should be avoided. Note that this property can only be used, if the radius of the minimum bounding circle of all locations defined in the problem is less than or equal to 190 km.

  • exclude: specifies which countries have to be excluded from the tour planning. The country codes must be provided in ISO 3166-1 alpha-3 format. Note that to get meaningful results with such exclusions, one eventually has to increase the radius of the minimum bounding circle of all locations. The radius of the minimum bounding circle of all locations defined in the problem must not exceed 190 km when using this feature, otherwise, a validation error will be returned.

    {
"exclude": {
  "countries": [
    "AUT",
    "CHE"
  ]
}
}

Car Profile

At the moment, the car profile does not have any extra properties.

Truck Profile

Truck limitations are defined using the options field in the truck profile in the problem request.

The shippedHazardousGoods option sets a list of hazardous materials shipped by the trucks, such as explosives, gas and materials harmful to water. For the full list of options, see the API Reference.

Other options describe the physical attributes of the truck: weight limit, weight per axle, height, width and length. The tunnel category option restricts the routes to pass only through tunnels of a less strict category.

Scooter Profile

Scooter option allowHighway can be defined using the options field in the scooter profile in the problem request. allowHighway specifies whether routing calculation should take highways into account. When this parameter isn't provided, then by default highways would be avoided. If the avoid feature motorway is provided, then highways would be avoided, even if allowHighway is set to true.

The scooter profile is supported only if the radius of the minimum bounding circle of all locations defined in the problem is less than or equal to 190km.

Bicycle Profile

At the moment, the bicycle profile does not have any extra properties.

Pedestrian Profile

At the moment, the pedestrian profile does not have any extra properties.

Traffic

The traffic setting configures what kind of traffic information should be considered for routing:

  • liveOrHistorical: for departure times in the future, either live or historical traffic data are applied depending on how far in the future the departure time is. For departure times in the past, only historical traffic data are applied. The departure time of a vehicle type can be configured via the vehicle profile's optional departureTime property. In case this property is omitted when defining a vehicle profile, the earliest shift start time of all vehicle types sharing that same vehicle profile is used as that profile's departure time. Choose this setting if all locations are within a radius of 190 km and you want to use live traffic data whenever possible.
  • historicalOnly: only free-flow speeds based on historical traffic data are applied. Choose this setting if you want to avoid live traffic data usage.
  • automatic: the same as liveOrHistorical, if all coordinates are within a radius of 190 km, otherwise the same as historicalOnly. Choose this setting if you want the service to decide automatically what is the best option.

The default value is automatic.

Configuration

Configuration can be used to tweak the algorithm's default behaviour, see documentation here. In the following example, the solver will take a maximum of 2 seconds (maxTime) to solve the problem, and if within the 2 seconds there is a period of 1 second (stagnationTime) without a considerable solution improvement, then the algorithm will terminate.

Example

An example of a Problem:

{
  "plan": {
    "jobs": [
      {
        "id": "myJob",
        "tasks": {
          "deliveries": [
            {
              "places": [
                {
                  "location": {"lat": 52.46642, "lng": 13.28124},
                  "times": [["2020-07-04T10:00:00.000Z","2020-07-04T12:00:00.000Z"]],
                  "duration": 180
                }
              ],
              "demand": [1]
            }
          ]
        }
      }
    ]
  },
  "fleet": {
    "types": [
      {
        "id": "myVehicleType",
        "profile": "normal_car",
        "costs": {
          "distance": 0.0002,
          "time": 0.005,
          "fixed": 22
        },
        "shifts": [{
          "start": {
            "time": "2020-07-04T09:00:00Z",
            "location": {"lat": 52.52568, "lng": 13.45345}
          },
          "end": {
            "time": "2020-07-04T18:00:00Z",
            "location": {"lat": 52.52568, "lng": 13.45345}
          }
        }],
        "limits": {
          "maxDistance": 300000,
          "shiftTime": 28800
        },
        "capacity": [10],
        "amount": 1
      }
    ],
    "profiles": [{
      "name": "normal_car",
      "type": "car",
      "departureTime": "2020-07-04T09:15:00Z"
    }]
  },
  "configuration": {
    "termination": {
      "maxTime": 2,
      "stagnationTime": 1
    }
  }
}

results matching ""

    No results matching ""