Optimization

Overview

Sygic’s Route Optimization is optimization that helps to find optimal waypoint sequence for route with up to 200 stops. This service can calculate optimal waypoint sequence for one or more vehicles without consideration of truck attributes.

Live Example

This simple example demonstrates the use of the Optimization service. Click on icons to see code on Github or play with it in JSFiddle:

Request

API Reference

https://optimization.api.sygic.com/v0/api/optimization?key=yourAPIkey

Request authentication is done via parameter key, which must be included in the request URL.

Methods

Parameters

Required Parameters

Optional Parameters

Locations

Locations are defined by the following parameters:

Example definitions

Base definition of location:

{
    "locations": [
        {
            "location_id": "depot",
            "coordinates": "48.212870,17.174013"
        },
        {
            "location_id": "customer01",
            "coordinates": "48.14713,17.0843"
        },
        {
            "location_id": "customer02",
            "coordinates": "48.15349,17.08556"
        },
        {
            "location_id": "customer03",
            "coordinates": "48.14932,17.21944"
        },
        {
            "location_id": "customer04",
            "coordinates": "48.16555,17.13828"
        },
        {
            "location_id": "customer05",
            "coordinates": "48.15032,17.15797"
        }
    ]
}

The location can be defined with time windows:

{
  "locations": [
    {
      "location_id": "depot",
      "coordinates": "48.212870,17.174013"
    },
    {
      "location_id": "customer01",
      "coordinates": "48.14713,17.0843",
      "availability": {
        "earliest_start": "2017-03-02T08:00:00Z",
        "latest_end": "2017-03-02T08:23:00Z"
      }
    },
    {
      "location_id": "customer02",
      "coordinates": "48.15349,17.08556",
      "availability": {
        "earliest_start": "2017-03-02T08:00:00Z",
        "latest_end": "2017-03-02T18:00:00Z"
      }
    },
    {
      "location_id": "customer03",
      "coordinates": "48.14932,17.21944",
      "availability": {
        "earliest_start": "2017-03-02T08:00:00Z",
        "latest_end": "2017-03-02T18:00:00Z"
      }
    },
    {
      "location_id": "customer04",
      "coordinates": "48.16555,17.13828",
      "availability": {
        "earliest_start": "2017-03-02T08:00:00Z",
        "latest_end": "2017-03-02T18:00:00Z"
      }
    },
    {
      "location_id": "customer05",
      "coordinates": "48.15032,17.15797",
      "availability": {
        "earliest_start": "2017-03-02T08:00:00Z",
        "latest_end": "2017-03-02T18:00:00Z"
      }
    }
  ]
}

Time window specification

Time windows specify hard limits for location, task activity or vehicle availability, task must be fully finished within given time frame (including service time), e.g. imagine following time window for task location having service_time 30 minutes:

{
  "earliest_start": "2018-01-01T13:00:00Z",
  "latest_end": "2018-01-01T17:00:00Z"
}

Vehicle can start fulfilling the task no earlier than 13:00. Before time window opens, vehicle can perform other tasks or simply wait (depending on problem structure). Having service_time 30 minutes means, that vehicle must arrive 16:30 at latest, to be able to complete the task until 17:00.

Time windows can also be half-open, i.e. arriving no earlier than 13:00 and not caring about departure:

{
  "earliest_start": "2018-01-01T13:00:00Z"
}

or not constraining arrival time but leaving no later than 17:00:

{
  "latest_end": "2018-01-01T17:00:00Z"
}

Availability specification

Availability is simply union of non-overlapping time windows, during which the location, task activity or vehicle is available for operation.

For example, location could be opened between 08:00 - 09:00 in the morning or 13:00 - 14:00 in the afternoon:

{
  "availability": [
    {
      "earliest_start": "2018-01-01T08:00:00Z",
      "latest_end": "2018-01-01T09:00:00Z"
    },
    {
      "earliest_start": "2018-01-01T13:00:00Z",
      "latest_end": "2018-01-01T14:00:00Z"
    }
  ]
}

For API backward compatibility, availability can be specified also as object intead of array with single item, i.e. following is valid input:

{
  "availability": {
      "earliest_start": "2018-01-01T08:00:00Z",
      "latest_end": "2018-01-01T17:00:00Z"
  }
}

with same meaning as:

{
  "availability": [
    {
      "earliest_start": "2018-01-01T08:00:00Z",
      "latest_end": "2018-01-01T17:00:00Z"
    }
  ]
}

Tasks

Tasks are defined by the following parameters:

Activities specification

Example definitions

Base definition of task:

{
    "tasks": [
        {
            "task_id": "task01",
            "activities": [
                {
                    "activity_type": "Visit",
                    "location_id": "customer01"
                }
            ]
        }
    ]
}

Complex task definition
High task priority, capacity 1 item and size 50 kg, compatible vehicles, pickup/delivery alternatives, service time and time windows:

{
  "tasks": [
    {
      "task_id": "Gift01",
      "priority": "High",
      "capacity": [
        1,
        50
      ],
      "compatible_vehicles": [
        "Rudolph",
        "Cupid"
      ],
      "activities": [
        {
          "activity_type": "Pickup",
          "location_id": [ "NorthPole", "DispatchHub" ]
        },
        {
          "activity_type": "Delivery",
          "location_id": [ "Child1@home", "Child1@grandparents" ],
          "service_time": "00:05:00",
          "availability": [
            {
              "earliest_start": "2017-12-24T16:00:00",
              "latest_end": "2017-12-24T22:00:00"
            },
            {
              "earliest_start": "2017-12-25T08:00:00",
              "latest_end": "2017-12-25T12:00:00"
            }
          ]
        }
      ]
    }
  ]
}

Combined availability
Location and activity availability can be specified independently, effective availability is calculated as intersection of time window intervals.
For example, let's have a location opened in the morning 08:00 - 12:00 and afternoon 13:00 - 16:00:

{
  "location_id": "customer",
  "coordinates": "48.14713,17.0843",
  "availability": [
    {
      "earliest_start": "2018-01-01T08:00:00",
      "latest_end": "2018-01-01T12:00:00"
    },
    {
      "earliest_start": "2018-01-01T13:00:00",
      "latest_end": "2018-01-01T16:00:00"
    }
  ]
}

and delivery task with time windows 11:00 - 14:00 and 15:00 - 18:00:

{
  "task_id": "delivery",
  "capacity": [
    1
  ],
  "activities": [
    {
      "activity_type": "pickup",
      "location_id": "depot"
    },
    {
      "activity_type": "delivery",
      "location_id": "customer",
      "availability": [
        {
          "earliest_start": "2018-01-01T11:00:00",
          "latest_end": "2018-01-01T14:00:00"
        },
        {
          "earliest_start": "2018-01-01T15:00:00",
          "latest_end": "2018-01-01T18:00:00"
        }
      ]
    }
  ]
}

Combining availability intervals for location and task leads to following delivery possibilities: 11:00 - 12:00, 13:00 - 14:00, 15:00 - 16:00.

Vehicles

Vehicles are defined by the following parameters:

Example definitions

Base definition of vehicle:

{
    "vehicles": [
        {
            "vehicle_id": "MyVehicle",
            "cost_per_km": 1,
            "cost_per_hour": 0,
            "fixed_cost": 10,
            "start_location_id": "depot",
            "end_location_id": "depot"
        }
    ]
}

Vehicle can be defined with time windows:

{
    "vehicles": [
        {
            "vehicle_id": "MyVehicle",
            "cost_per_km": 1,
            "cost_per_hour": 0,
            "fixed_cost": 10,
            "start_location_id": "depot",
            "end_location_id": "depot",
            "availability": [
                {
                    "earliest_start": "2018-01-01T08:00:00Z",
                    "latest_end": "2018-01-01T12:00:00Z"
                },
                {
                    "earliest_start": "2018-01-01T13:00:00Z",
                    "latest_end": "2018-01-01T18:00:00Z"
                }
            ]
        }
    ]
}

Vehicle with max. 100 items and 500 kg capacities:

{
    "vehicles": [
        {
            "vehicle_id": "MyVehicle",
            "cost_per_km": 1,
            "cost_per_hour": 0,
            "start_location_id": "depot",
            "end_location_id": "depot",
            "max_capacity": [100,500],
            "availability": {
                "earliest_start": "2017-03-02T08:00:00Z",
                "latest_end": "2017-03-02T18:00:00Z"
            }
        }
    ]
}

Settings

Submit optimization job

Optimization API is asynchronous, accepts POST request to initiate optimization computing and returns URL where result will be found when done.

Request

POST https://optimization.api.sygic.com/v0/api/optimization?key=yourAPIkey
Content-Type: application/json

{
    "locations": [..],
    "vehicles": [..],
    "tasks": [..],
    "settings": {..}
}

Request body

Described above

Response

Response header Location contains URI for polling the execution status and results retrieval.

Status: 202 Accepted
Location: https://optimization.api.sygic.com/v0/api/optimization/{id}?key=yourAPIkey

{
    "link": "https://optimization.api.sygic.com/v0/api/optimization/{id}?key=yourAPIkey",
    "status": "OK",
    "copyright": "© 2018 Sygic a.s."
}

Monitor optimization job

Optimization job can be monitored by performing GET operation on the returned URL location.

Request

GET https://optimization.api.sygic.com/v0/api/optimization/{id}?key=yourAPIkey

Response

Status: 200
Retry-After: 15

{
    "state": "Waiting|Running|Finished|Failed",
    "progress": 100,
    "status": "OK|NO_RESULT",
    "copyright": "© 2018 Sygic a.s."
}

Client is expected to perform regular polling on the result url until the job is finished. Client should wait between each try, as advised by Retry-After header value (in seconds).

More extensive examples of optimization API can be found here.