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
Header: Content-Type application/json
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
}
Answer
"[[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.
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,
...
}
Answer
"[[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.
December 4 2017: version 1.0.0
Upload of the stable version.
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.
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.
Your comments are welcome and we all appreciate them. By giving us your comments, you contribute to better optimization.
We don't track you
When the application programming interface (API) is used, we cannot determine the corresponding locations. Indeed, the address information is not necessary, because the costs of the links must be calculated beforehand. So you keep your anonymity.
Send a message