KangRouter Engine

KangRouter solves pickup and delivery vehicle routing problems. The core planning algorithm is available as a webservice on https://thesolvingmachine.com/kangrouter/srv. This section presents the programmatic interface (API) to the KangRouter planning engine.

Changelog

2015-11-26

This is significant revision to the “PTPlan” interface:

  • The product was rebranded as KangRouter, and the base URL is now https://thesolvingmachine.com/kangrouter/srv.
  • Authentication has changed. The webservice is now available only through HTTPS and therefore the previous HMAC protection is no longer necessary. Now simply pass the api_key in the Authorization header.
  • Return value from POST /solvers is now a string representing the solverId (was an object containing a string representing the solverId).
  • It is now allowed to queue multiple simultaneous solvers for a given licenseId, even if only a single solver may be running at any given moment. The pending solvers are executed with a FIFO policy.
  • Default vehicle overspeed is now 1 (was 1.25).
  • Default vehicle maximum work duration is now unbounded (was 24 hours).
  • Vehicle overspeed is now customizable for each vehicle (was a global parameter).
  • [Fix]: First and last tasks of each vehicle should have no waiting time.
  • Timespan of problem is no longer limited to 24:00. See Problem’s minTime and maxTime below.
  • New maxJobExtraDuration parameter, with default infinite value (was implicitly set to 60 minutes).
2015-05-13
  • Added new error GeocoderError to help diagnose input with invalid or too far off coordinates

Resources

The following data model mainly describes a problem to solve and its solution. It is common to all clients of KangRouter Engine.

Time

Time formatted as “hh:mm”.

Type:

string

Example:13:55

Duration

Time duration, in minutes.

Type:

integer

Example:10

Problem

A Problem object represents the problem we want to solve: the list of jobs to plan, the list of available vehicles, and a few global definitions.

Property Type Description Example
nbResources* integer Vehicles may have distinct resources (e.g. seat, wheelchair, bed) to satisfy specific job needs. This field sets the total number of distinct resources considered in this problem. 3
jobs* array[Job] List of jobs to plan.
vehicles* array[Vehicle] List of vehicles available to serve jobs.
minTime Time The earliest time to assume when no time is specified. Optional. Default is “00:00”. 00:00
maxTime Time The latest time to assume when no time is specified. Optional. Default is “24:00”. Note: This may be set to any string of the form “hh:mm”, possibly with hh>24. 32:00
maxJobExtraDuration Duration Constrains the maximum duration of any job in the problem. The duration of a job is guaranteed to be at most maxJobExtraDuration plus the minimum duration for that job, i.e. the duration of a direct route from the job’s origin to destination. Optional. Default is unbounded. Note: This constraint does not applies to jobs for which both the pickup and delivery time are already constrained.

Job

A Job object describes a request for the transportation of items/passengers from one location (origin) to another (destination). Besides setting the origin and destination, it also frames the pickup/delivery time, load/unload durations, and specifies the amount of resources that the transported cargo consumes.

Property Type Description Example
jobId* string Job identifier. Job01
origLat* string Latitude of origin (pickup location). 38.674921
origLon* string Longitude of origin (pickup location). -9.175401
destLat* string Latitude of destination (dropoff location). 38.716860
destLon* string Longitude of destination (dropoff location). -9.162417
minStartTime Time Lower bound on the job start time. Optional. Default is minTime. 13:00
maxStartTime Time Upper bound on the job start time. Optional. Default is maxTime. 13:15
minEndTime Time Lower bound on the job end time. Optional. Default is minTime.
maxEndTime Time Upper bound on the job end time. Optional. Default is maxTime.
pickupDuration Duration Time duration required for pickup at origin. Optional. Default is 0. 10
deliveryDuration Duration Time duration required for dropoff at destination. Optional. Default is 0. 10
cargoId string Cargo identifier. Optional. Used only for input validation (see Warning). Fernando Pessoa
consumptions array List of resource consumptions for this job. An element u at position r in this list specifies that the job requires u units of resource r. The size of the list must be equal to the value of the nbResources field. [0, 1, 0]

Vehicle

A Vehicle object describes a vehicle that is available for serving jobs during a contiguous time window, typically a work day. This object also allows to specify the vehicle’s (or driver’s) maximum work duration, a list of mandatory work breaks, and the vehicle’s capacity for each resource. Note: To model cases where a vehicle is available in multiple disjoint work windows, use different Vehicle objects.

Property Type Description Example
vehicleId* string Vehicle identifier. 12-AS-46
depotLat* string Latitude of vehicle depot. 38.806842
depotLon* string Longitude of vehicle depot. -9.382556
minStartTime Time Lower bound on the vehicle start time. Optional. Default is minTime. 07:00
maxEndTime Time Upper bound on the vehicle end time. Optional. Default is maxTime. 22:00
maxWorkDuration Duration Upper bound on the total work duration of vehicle (since it leaves the depot until it returns to the depot). Optional. Default is unbounded. 540
capacities* array List of resource capacities for this vehicle. An element u at position r in this list specifies that the vehicle can provide at most u units of resource r at any given time. The size of the list must be equal to the value of the nbResources field. [2, 3, 0]
breaks array[Break] List of mandatory breaks for this vehicle. Optional. Default is no breaks.
overspeed number Adjusts the travel duration (float). Travel time reported by the navigator is divided by this number. Optional. Default is 1. 1.25

Break

A work break object allows to program an interval of time during a given time window where the vehicle may interrupt work. A work break has no associated location - the planner simply allocates the required duration during the specified time window.

Property Type Description Example
breakId* string Break identifier.
minStartTime* string Lower bound on the break start time.
maxEndTime* string Upper bound on the break end time.
duration* Duration Break duration, in minutes.

Solution

Solution to the submitted problem.

Property Type Description Example
type string
  • unknown Solving has not completed yet.
  • none All jobs were discarded.
  • partial Some jobs were discarded.
  • total All jobs were scheduled.
total
jobsScheduled array[ScheduledJob] List of scheduled jobs.
vehiclesScheduled array[ScheduledVehicle] List of scheduled vehicles.
jobsDiscarded array[DiscardedJob] List of discarded jobs.
vehiclesDiscarded array[DiscardedVehicle] List of discarded vehicles.

ScheduledJob

A ScheduledJob object describes when a given Job was scheduled, and to which Vehicle it was assigned.

Property Type Description Example
jobId string Job identifier.
vehicleId string Vehicle identifier of the vehicle serving the scheduled job.
minStartTime Time Lower bound on the job start time.
maxStartTime Time Upper bound on the job start time.
minEndTime Time Lower bound on the job end time.
maxEndTime Time Upper bound on the job end time.

ScheduledVehicle

A ScheduledVehicle object describes the time window a given Vehicle is scheduled to work, and when each break is scheduled to occur (is appliable).

Property Type Description Example
vehicleId string Vehicle identifier. 12-AS-46
minStartTime Time Lower bound on the vehicle start time. 07:00
maxStartTime Time Upper bound on the vehicle start time. 11:51
minEndTime Time Lower bound on the vehicle end time. 14:15
maxEndTime Time Upper bound on the vehicle end time. 20:51
breaks array[ScheduledBreak] List of scheduled breaks for this vehicle.

ScheduledBreak

A ScheduledBreak object describes when a given Break was scheduled.

Property Type Description Example
breakId string Break identifier. Lunch
minStartTime Time Lower bound on the break start time. 12:00
maxStartTime Time Upper bound on the break start time. 12:15
minEndTime Time Lower bound on the break end time. 13:00
maxEndTime Time Upper bound on the break end time. 13:15

DiscardedJob

A DiscardedJob object describes a Job that could not be planned. A job may be discarded if there are not enough vehicles with capacity for the kind of resources used by that job working on a compatible time window.

Property Type Description Example
jobId string Job identifier.
reasonCode integer
  1. No available vehicle.
  2. Unsatisfiable time constraints. Occurs if minStartTime + pickupDuration >= maxEndTime - deliveryDuration.
reasonInfo string Additional information explaining the reason to discard the job.

DiscardedVehicle

A DiscardedVehicle object describes a Vehicle that could not be used. A vehicle may be discarded only if its availability window is ill defined.

Property Type Description Example
vehicleId string Vehicle identifier.
reasonCode integer
  1. Unsatisfiable time constraints. Occurs if minStartTime >= maxEndTime.
reasonInfo string Additional information explaining the reason to discard the vehicle.

Status

General information about the solving process.

Property Type Description Example
execStatus string
  • pending Solver is has not started yet.
  • solving Solver is executing.
  • completed Problem is solved.
  • invalid Problem is invalid (check errors).
completed
solverStartTime string Solver start time (in UTC). Thu Nov 12 19:24:56 2015 GMT
solverETA string Solver expected completion time (in UTC). This is an estimation. This field exists only when execStatus is solving. Thu Nov 12 19:25:03 2015 GMT
solverEndTime string Solver completion time (in UTC). This field exists only when execStatus is completed. Thu Nov 12 19:25:03 2015 GMT
totalDistance integer Total distance (in km) of the best solution found so far (for jobs that were scheduled). 75
nbJobsDiscarded integer Number of jobs discarded in the best solution found so far.
errors array[Error] List of critical errors that prevent solving the current problem. This list is non-empty if and only if execStatus is invalid.
warnings array[Warning] List of warnings. Warnings do not prevent solving but alert the user for unusual input.

Error

An API or solver exception.

Property Type Description Example
code* integer
  1. Invalid API usage. Triggered on invalid input, invalid request, or unauthorized request.
  2. Internal error. It should not happen unless there is a bug in the service/solver.
  3. Cancelled by user. Triggered when a “pending” solver is stopped.
  4. Geocoder error. Triggered when the geocoder is unable to compute the time and distance for a given pair of GPS coordinates.
info string Additional information about the error.

Warning

Warning regarding the problem instance.

Property Type Description Example
code integer
  1. Outlier location. Triggered when some GPS coordinate is unusually far from all the others.
  2. Unconstrained job time window. Triggered when a job has no constraints on the pickup or delivery.
  3. Underspeed. Triggered when overspeed factor is less than 1.
  4. Unused break. Triggered when a given break time window is outside of vehicle work time window.
  5. Unpaired job. Triggered when there is a single job for a cargo, or when there are two jobs for a cargo but the origin and destination coordinates are not symmetrically identical. This warning may be generated only if the optional jobs[].cargoId field is provided.
info string Additional information about the warning.

RESTful Interface

This section describes the KangRouter RESTful API. An interactive version of this documentation, useful for development/testing, is available at https://thesolvingmachine.com/swagger/kangrouter/srv/.

The following parameters authenticate the client and must be present in all method invocations. Please obtain them from https://thesolvingmachine.com/account.

Parameter Type Description Location
Authorization string Your KangRouter API key header
licenseId string License identifier query

All available methods operate on the /solvers endpoint. They are the following:

POST /solvers

Submit a new problem.

Creates a new solver for a given problem and puts the solver into the execution queue. The solver will begin executing as soon as all previously created solvers for this licenseId complete their tasks or are explicitely terminated.

Parameters

Name Type Description Location
problem* Problem Problem to solve. body
deleteExisting integer If deleteExisting=1 then the server deletes any existing solver for the given licenseId before attempting to create the new solver. Set this parameter to make sure the solving process starts immediately while avoiding having to explicitely the delete previous solvers. Optional. Default is 0. query

Responses

Code Type Description
200 string Identifier for the created solver. Note: This is a plain text response (not JSON).
other Error Unexpected error

DELETE /solvers/{solverId}

Deletes a solver for a previously submitted problem.

Removes a solver with the given solverId from the server, terminating it if necessary. Any posterior methods calls referring the given solverId are invalid.

Parameters

Name Type Description Location
solverId* string Solver identifier returned from POST /solvers. path

Responses

Code Type Description
200 Success.
other Error Unexpected error.

PUT /solvers/{solverId}/stop

Terminates a running solver.

Forces immediate termination of a solver with the specified solverId. This method terminates the solver, but unlike delete, it does not remove the solver from the server. This allows to access to the best solution found so far.

Parameters

Name Type Description Location
solverId* string Solver identifier returned from POST /solvers. path

Responses

Code Type Description
200 Success.
other Error Unexpected error.

GET /solvers/{solverId}/status

Returns the status of specified solver.

Parameters

Name Type Description Location
solverId* string Solver identifier returned from POST /solvers. path

Responses

Code Type Description
200 Status Success.
other Error Unexpected error.

GET /solvers/{solverId}/solution

Returns the best solution found for the submitted problem.

Parameters

Name Type Description Location
solverId* string Solver identifier returned from POST /solvers. path

Responses

Code Type Description
200 Solution Success.
other Error Unexpected error.

Python Client

A Python library for KangRouter Engine is available at https://github.com/TheSolvingMachine/kangrouter-py.

Javascript Client

A Javascript library for KangRouter Engine is available at https://github.com/TheSolvingMachine/kangrouter-js.