Interface de programmation (API) VRPTW
Vehicle Routing Problem With Time Windows (VRPTW)
Le problème de routage de véhicules avec fenêtre de temps est caractérisé par le nombre de combinaisons possibles. En effet, pour vérifier toutes les combinaisons de routes, la complexité algorithmique est O(n!). Dans le contexte routier, il est fréquent que le nombre d'endroits total à visiter dépasse 10, soit 10! (3628800) possibilités. Afin de mieux nous outiller envers ce problème, nous avons conçu le premier API de type VRPTW.
Exemple d'utilisation
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
}
Réponse
"[[4,1],[5,2],[3]]"
Configuration des paramètres
key
Cette valeur est requise seulement si vous dépassez 500 emplacements.
distanceMatrix
Cette matrice résume les distances de chacun des emplacements 'i' (rangée) vers chacun des emplacements 'j' (colonne). Il est important de retenir que l'index 0 (première rangée et première colonne) représente le dépôt. Selon l'exemple, soit 'D' la matrice carré des 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: dans le contexte de réseaux routiers, il existe des API qui calcul cette matrice pour vous. En autre, Bing Map Rest Service: Calculate a Distance Matrix est un moyen efficace d'obtenir cette matrice.
Interprétation de la réponse
Bien comprendre la réponse constitue la première étape de l'analyse paramétrique. En effet, la réponse de la requête dévoile beaucoup d'information sur les paramètres utilisés.
Aller-retour sans optimisation
Supposons que la capacité est moindre que celle requise pour visiter les emplacements, alors tous les emplacements seront visités par des aller-retour sans visiter d'autre point.
{
...
"capacity":2,
...
}
Réponse
"[[1],[2],[3],[4],[5]]"
Le nombre de routes dépasse le nombre de véhicules disponible dans la requête.
Priorisation (facultatif)
La configuration des premiers emplacements à visiter impacte la solution.
{
...
"firstToVisit":[3,4],
...
}
Réponse:
"[[4],[5,1],[3],[2]]"
{
...
"firstToVisit":[],
...
}
Réponse:
"[[2,5],[1,4],[3]]"
Version actuel: 1.1.1
28 mai 2018: version 1.1.1
Renvoi d'erreurs lorsqu'un paramètre est mal utilisé.
30 mars 2018: version 1.1.0
Publication de la preuve de concept, ajout des tests pour l'assurance qualité et correctifs mineurs.
4 décembre 2017: version 1.0.0
Mise en ligne de la version stable.
27 juillet 2017: version 0.1.1
Améliorations sur les trajets.
25 mai 2017: version 0.1.0
Développement et implémentation de la solution.
2 février 2017: version 0.0.1
Conception et design préliminaire.
Une suggestion?
Si vous détectez un problème concernant l'utilisation, vous pouvez nous en faire part en communiquant avec nous par courriel. Le cas échéant, un suivi vous sera envoyé pour vous aviser des démarches entreprises et de l'éventuelle correction du bogue en question.
Vos commentaires sont les bienvenus et nous les apprécions tous. En nous faisant part de vos commentaires, vous contribuez à une meilleure optimisation.
Nous ne vous pistons pas
Lorsque l’interface de programmation (API) est utilisée, nous ne pouvons pas déterminer les emplacements correspondants. En effet, les informations des adresses ne sont pas nécessaires, car les coûts des liens doivent être préalablement calculés. Ainsi vous conservez votre anonymat.
Envoyer un message