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.

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 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. Date is represented in RFC3339 format:

    "times": [["2019-07-04T06:00:05.000Z","2019-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 (required): a user defined tag associated within a given place. It is propagated back within the solution.

    "tag": "pickup_1"

A job can be one of two types: simple job or multi job.

Simple job

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

  • pickup: a job for picking something along the route and bringing it to route's end location. It is used when only the pickup place is specified.
  • delivery: a job for delivering something loaded at the beginning of the route. It is used when only the delivery place is specified.
  • pickup and delivery job: a job for picking and delivering along the route. It is used when both pickup and delivery places are specified.

A basic example of a pickup and delivery job:

{
        "id": "myPickupAndDeliveryJob",
        "places": {
          "pickup": {
            "location": {"lat": 52.5622847, "lng": 13.4023099},
            "duration": 120
          },
          "delivery": {
            "location": {"lat": 52.5622847, "lng": 13.4023099},
            "duration": 180
          }
        },
        "demand": [1]
      }

Multi job

A multi job consists of 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.

A basic example of a multi job:

{
        "id": "myMultiJob",
        "places": {
          "pickups": [
            {
              "location": {"lat": 52.5622847, "lng": 13.4023099},
              "duration": 180,
              "demand": [1],
              "tag": "p1"
            },
            {
              "location": {"lat": 52.5330881, "lng": 13.3973059},
              "duration": 180,
              "demand": [1],
              "tag": "p2"
            }
          ],
          "deliveries": [
            {
              "location": {"lat": 52.5252832, "lng": 13.41884},
              "duration": 180,
              "demand": [2],
              "tag": "d1"
            }
          ]
        }
      }

Max jobs size

The total amount of jobs is calculated as the sum of all simple jobs plus the sum of all pickups and deliveries defined in all multi 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 job can’t be touched and a new job cannot be inserted between existing jobs
  • Flexible: the new job can be inserted anywhere in the existing plan but the already existing jobs will not be reshuffled
  • Tour: the new job can be inserted anywhere in the existing plan and the already existing jobs can be reshuffled

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.
  • 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 it's result.

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

Please note that jobs added into a sequence or a fexible 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.

Fleet

A fleet specifies a list of vehicle types and their routing profiles.

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 ${vehicleType}_${sequence_index}.

    "id": "vehicle"

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

    "profile": "normal_car"

  • 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
      }
    }
    
  • shifts: specifies an array of depot places where vehicles of this particular type should start and end:

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

    Each place is specified by time and location. Start time means 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 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
      }
    }
    

Routing Profile

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

  • name: 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

    "profile": "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.

  • avoidRoutes: specifies a list of routing features that should be avoided

Car Profile

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

Truck Profile

Truck limitations are defined using the truckOptions field 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.

Example

An example of a Problem:

{
  "id": "myProblem",
  "plan": {
    "jobs": [
      {
        "id": "myJob",
        "places": {
          "delivery": {
            "location": {"lat": 52.46642, "lng": 13.28124},
            "times": [["2019-07-04T10:00:00.000Z","2019-07-04T12:00:00.000Z"]],
            "duration": 180
          }
        },
        "demand": [1]
      }
    ]
  },
  "fleet": {
    "types": [
      {
        "id": "myVehicle",
        "profile": "normal_car",
        "costs": {
          "distance": 0.0002,
          "time": 0.004806,
          "fixed": 22
        },
        "shifts": [{
          "start": {
            "time": "2019-07-04T09:00:00Z",
            "location": {"lat": 52.52568, "lng": 13.45345}
          },
          "end": {
            "time": "2019-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": "2019-07-04T09:15:00Z"
     }]
  }
}

results matching ""

    No results matching ""