# How to use VRPTW API?

## Application Programming interface (API) VRPTW

### Vehicle Routing Problem With Time Windows (VRPTW)

The problem of routing vehicles with a time window is characterized by the number of possible combinations. Indeed, to verify all the combinations of routes, the algorithmic complexity is O (n!). In the road context, it is common for the total number of places to visit to exceed 10, or 10! (3628800) possibilities. In order to better solve this problem, we designed the first VRPTW type API.

## Example of use

### URL

POST https://www.algorithmesolutions.com/routing

### Requête: raw

 { "key":"98C10D89-9FE2-4AE9-A9BE-F149ECE8AD97", "distanceMatrix":[ [0, 531, 495, 3081,2974,961], [531, 0, 1104,3521,3408,1222], [495, 1104,0, 3040,2856,876], [3081,3521,3040,0, 2847,3147], [2974,3408,2856,2847,0, 3059], [961, 1222,876, 3147,3059,0] ], "weight":[0,7200,10800,28800,12600,10800], "firstToVisit":[3,4], "capacity":37800, "available":4 } 

 "[[4,1],[5,2],[3]]" 

## Parameter configuration

### key

This value is required only if you exceed 500 locations.

### distanceMatrix

This matrix summarizes the distances from each of the 'i' locations (row) to each of the 'j' locations (column). It is important to remember that index 0 (first row and first column) represents the deposit. According to the example, let 'D' be the square matrix of distances:

 0 531 495 3081 2974 961 531 0 1104 3521 3408 1222 495 1104 0 3040 2856 876 3081 3521 3040 0 2847 3147 2974 3408 2856 2847 0 3059 961 1222 876 3147 3059 0

Note: in the context of road networks, there are APIs that calculate this matrix for you. Among others, Bing Map Rest Service: Calculate a Distance Matrix is an efficient way to get this matrix.

$$D_{ij} = \begin{bmatrix} 0 & D_{1,2} & D_{1,3} & ... & D_{1,n-1} & D_{1,n} \\ 0 & 0 & D_{2,3} & ... & D_{2,n-1} & D_{2,n} \\ 0 & 0 & 0 & ... & D_{3,n-1} & D_{3,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & ... & 0 & D_{n-1,n} \\ 0 & 0 & 0 & ... & 0 & 0 \\ \end{bmatrix} D_{ij} = \left\{ \begin{array}{ll} 0\ \ si\ \ i=j \\ D_{ij} = D_{ji}\\ (i = 0) = {à\ partir\ du\ dépôt} \\ (j = 0) = vers\ le\ dépôt \\ (i \neq0) = à\ partir\ de\ l'emplacement \\ (j \neq0) = vers\ l'emplacement \\ \end{array} \right.\\$$

Considering that the distance traveled between 'i' and 'j' is approximately the same as between 'j' and 'i' (outward = return), we can therefore use matrix reflection:

$$D'_{ij} = \begin{bmatrix} 0 & D_{1,2} & D_{1,3} & ... & D_{1,n-1} & D_{1,n} \\ D_{1,2} & 0 & D_{2,3} & ... & D_{2,n-1} & D_{2,n} \\ D_{1,3} & D_{2,3} & 0 & ... & D_{3,n-1} & D_{3,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ D_{1,n-1} & D_{2,n-1} & D_{3,n-1} & ... & 0 & D_{n-1,n} \\ D_{1,n} & D_{2,n} & D_{3,n} & ... & D_{n-1,n} & 0 \\ \end{bmatrix}$$

### weight

Table of costs for each location.

$$E_j = \begin{bmatrix} E_{Depot} & E_{Cons._1} & E_{Cons._2} & ... & E_{Cons.n-1} & E_{Cons.n} \end{bmatrix}$$

### firstToVisit (facultatif)

Array of integers greater than 1 corresponding to the locations that must be visited first. For example: for location 3 (index 3) and location 4 (index 4) we get:

$$C_{f} = \begin{bmatrix} 3, 4 \end{bmatrix}$$

### capacity

Positive integer value of the number of vehicles available.

## Interpretation of the response

Understanding the answer is the first step in parametric analysis. Indeed, the response of the request reveals a lot of information on the parameters used.

### Round trip without optimization

Suppose the capacity is less than that required to visit the locations, then all locations will be visited by round trips without visiting any other point.

 { ... "capacity":2, ... } 

 "[[1],[2],[3],[4],[5]]" The number of roads exceeds the number of vehicles available in the request. 

### Prioritization (optional)

The configuration of the first locations to visit impacts the solution.

 { ... "firstToVisit":[3,4], ... } 
Answer:  "[[4],[5,1],[3],[2]]" 
 { ... "firstToVisit":[], ... } 
Answer:  "[[2,5],[1,4],[3]]" 

## Version actuel: 1.1.1

### May 28 2018: version 1.1.1

Return errors when a parameter is incorrectly used.

### March 30 2018: version 1.1.0

Publish proof of concept, add tests for quality assurance and minor fixes.

### July 27 2017: version 0.1.1

Improvements on paths.

### May 25 2017: version 0.1.0

Development and implementation of the solution.

### February 2 2017: version 0.0.1

Concept and preliminary design.

## Source code

An example code for using the API is available:

## Having a suggestion?

If you detect a problem with the use, you can let us know by contacting us by email. If necessary, a follow-up will be sent to you to inform you of the steps taken and of the possible correction of the bug in question.